Method and system for hash fragment representation
A method for writing data to persistent storage. The method include receiving a first write request including a key and a value, hashing the key to obtain a hashed key, obtaining a hash table depth (d), obtaining d bits from the hashed key, and making a first determination that a hash frag associated with the d bits from the hashed key exists. In response to the first determination, obtaining the hash frag, making a second determination that there is available space to store a hash frag entry in the hash frag, storing the hash frag entry in the hash frag to obtain an updated hash frag, where the hash frag entry includes the hashed key and value information for the value, and storing the updated hash frag in the persistent storage.
1. 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.
2. The non-transitory computer readable medium of claim 1 , wherein a hash object comprises the updated first hash frag, the third hash frag, and the fourth hash frag.
3. The non-transitory computer readable medium of claim 2 , wherein the first hash frag, the third hash frag, and the fourth hash frag are in non-contiguous locations in the persistent storage.
4. The non-transitory computer readable medium of claim 1 , wherein making the first determination comprises:
generating a fragment ID using the d bits from the first hashed object; and
searching a data structure using a hash object ID and the fragment ID.
5. The non-transitory computer readable medium of claim 4 , wherein the data structure is an in-memory data structure.
6. The non-transitory computer readable medium of claim 1 , wherein the value information comprises an object ID for the first value and an offset for the first value, wherein the first value is stored in the persistent storage using the object ID and the offset.
7. The non-transitory computer readable medium of claim 1 , wherein the value information comprises a logical address for the first value, wherein the first value is stored in the persistent storage using the logical address.
8. The non-transitory computer readable medium of claim 1 , wherein the first hash frag is obtained from the persistent storage.
9. The non-transitory computer readable medium of claim 1 , wherein the first hashed key is a 256-bit value.
10. The non-transitory computer readable medium of claim 1 , wherein hashing the first key comprises applying SHA 2 to the first key.
11. The non-transitory computer readable medium of claim 1 , wherein obtaining the d bits from the first hashed key comprises applying a bit-mask to the first hashed key, wherein the bit mask is generated using d.
12. The non-transitory computer readable medium of claim 1 , wherein obtaining the hash table depth d comprises using a current size for a hash object.
13. The non-transitory computer readable medium of claim 1 , wherein the persistent storage is NAND flash.
14. The non-transitory computer readable medium of claim 1 , wherein the first hash key entry further comprises key information for the first hashed key.
15. 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 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.