Patent ID: 8392428

Claim:
A non-transitory computer readable medium comprising instructions to perform a method, the method for writing data to persistent storage, comprising: receiving a first write request comprising a first key and a first value; hashing the first key to obtain a first hashed key; obtaining a hash table depth (d); obtaining d bits from the first hashed key, wherein the d bits from the first hashed key are d least significant bits in the first hashed key; making a first determination that a first hash frag associated with the d bits from the first hashed key exists; in response to the first determination: obtaining the first hash frag; making a second determination that there is available space to store a first hash frag entry in the first hash frag; storing the first hash frag entry in the first hash frag to obtain an updated first hash frag, wherein the first hash frag entry comprises the first hashed key and value information for the first value; storing the updated first hash frag in the persistent storage; receiving a second write request comprising a second key and a second value; hashing the second key to obtain a second hashed key; obtaining d bits from the second hashed key, wherein the d bits from the second hashed key are d least significant bits in the second hashed key; making a third determination that a second hash frag associated with the d bits from the second hashed key exists; in response to the third determination: obtaining the second hash frag, wherein the second hash frag comprises a plurality of existing hash frag entries; making a fourth determination that there is no available space to store a second hash frag entry in the second hash frag; creating, in response to the fourth determination, a third hash frag and a fourth hash frag; using d+1 least significant bits of each of the plurality of existing hash frags to place each of the existing hash frag entries in one selected from a group consisting of the third hash frag and the fourth hash frag; storing the second hash frag entry, comprising the second hashed key, in one selected from a group consisting of the third hash frag and the fourth hash frag using d+1 least significant bits in the second key hash; storing the third hash frag and the fourth hash frag in the persistent storage; and invalidating the second hash frag.