Hash tables in flash memory
Systems and methods for managing content in a flash memory. Systems and methods for implementing hash tables in a flash memory are disclosed. A hash table may include a flat array or an array of buckets that are each associated with a linked list. Adding or removing entries from the hash table or from the linked list are achieved by performing an overwrite operation where possible to pointers affected by the table operation.
1. A method for implementing a data structure in a flash memory, the method comprising:
creating a hash table, wherein at least a portion of the hash table is implemented in the flash memory;
receiving a call to enter a value from a client;
when the value is entered into the hash table, adding the value to an entry in the hash table, wherein the value is associated with a key and wherein the value is added at a location indicated by a hash of the key, wherein the value is only added at the location when an existing value can be overwritten with the value by only setting bits, wherein a client providing the value specifies a method for overwriting the existing value in the call;
when the entry in the hash table corresponds to a bucket, adding the entry to a linked list associated with the bucket, wherein the linked list is implemented in the flash memory;
adjusting pointers associated with the linked list that are affected by the entry to the linked list by storing the pointers in a different location when unsetting bits is required to adjust the pointers associated with the linked list; and
setting the pointers in an original location as an invalid value indicating the pointers are invalid when an overwrite operation cannot be performed, wherein the overwrite operation includes setting bits in the pointers.
2. The method of claim 1 , wherein the pointers are located within nodes of the linked list wherein the nodes includes a data portion and a pointer portion.
3. The method of claim 2 , wherein each node of the linked list is provisioned with one or more pointer fields.
4. The method of claim 3 , wherein the one or more pointer fields are initialized to all zeros.
5. The method of claim 2 , further comprising, after setting a first pointer in a first pointer field as the invalid value, adding a new pointer to a second pointer field such that the pointer portion can be evaluated in sequence until a valid pointer is found.
6. The method of claim 2 , wherein the pointer portion of each node is associated with an in-memory table, wherein the table can be used to store next pointers of various nodes when the pointer portions of the nodes cannot be overwritten and invalidated.
7. The method of claim 6 , wherein the in-memory table is initialized with all zeros.
8. The method of claim 6 , wherein the in-memory table may be implemented as a hash table, tree, or array.
9. The method of claim 7 , wherein the key to the in-memory table is an address of a node within the linked list or an identifier associated with data stored in the data portion of the node.
10. The method of claim 1 , wherein setting the pointer as an invalid value comprises setting all bits of the pointers to 1.
11. The method of claim 1 , wherein changing a value in a hash table is an atomic compare and swap operation such that the operation is isolated from other operations.
12. The method of claim 1 , wherein the hash table is implemented in both memory and flash memory.
13. A non-transitory computer readable medium comprising computer executable instructions for performing a method, the method including implementing a data structure in a flash memory, the method comprising:
creating a hash table, wherein at least a portion of the hash table is implemented in the flash memory;
receiving a call to enter a value from a client;
when the value is entered into the hash table, adding the value to an entry in the hash table, wherein the value is associated with a key and wherein the value is added at a location indicated by a hash of the key, wherein the value is only added at the location when an existing value can be overwritten with the value by only setting bits, wherein a client providing the value specifies a method for overwriting the existing value in the call;
when the entry in the hash table corresponds to a bucket, adding the entry to a linked list associated with the bucket, wherein the linked list is implemented in the flash memory;
adjusting pointers associated with the linked list that are affected by the entry to the linked list by storing the pointers in a different location when unsetting bits is required to adjust the pointers associated with the linked list; and
setting the pointers in an original location as an invalid value indicating the pointers are invalid when an overwrite operation cannot be performed, wherein the overwrite operation includes setting bits in the pointers.
14. The non-transitory computer readable medium of claim 13 , wherein the pointers are located within nodes of the linked list wherein the nodes includes a data portion and a pointer portion.
15. The non-transitory computer readable medium of claim 14 , wherein each node of the linked list is provisioned with one or more pointer fields.
16. The non-transitory computer readable medium of claim 15 , wherein the one or more pointer fields are initialized to all zeros.
17. The non-transitory computer readable medium of claim 14 , the method further comprising, after setting a first pointer in a first pointer field as the invalid value, adding a new pointer to a second pointer field such that the pointer portion can be evaluated in sequence until a valid pointer is found.
18. The non-transitory computer readable medium of claim 13 , wherein setting the pointer as an invalid value comprises setting all bits of the pointers to 1.
19. The non-transitory computer readable medium of claim 13 , wherein changing a value in a hash table is an atomic compare and swap operation such that the operation is isolated from other operations.
20. The non-transitory computer readable medium of claim 13 , wherein the hash table is implemented in both memory and flash memory.