Set-associative hash table organization for efficient storage and retrieval of data in a storage system

1. A method comprising:

storing a set of hash tables embodying metadata including an extent key associated with a storage location on storage devices of a cluster for write data of one or more write requests organized into an extent, each hash table having a plurality of entries, wherein each entry includes a plurality of slots;

recreating, by a node of the cluster, a first field of the extent key implicitly from an entry in a first address space portion of a hash table, the first field having first bits used as a first hash table index to address the first address space portion of the hash table to select the entry and to determine a slot;

storing a second field of the extent key in the slot, the second field having second bits used as a second hash table index to address a second address space portion of the hash table;

storing a third field of the extent key in the slot, the third field having third bits used to realize uniqueness in an event of a collision in the hash table; and

recreating, by the node of the cluster, a fourth field of the extent key implicitly from the hash table of the set of hash tables, the fourth field having fourth bits used as a hash table selector to select the hash table from the set of hash tables, wherein the first through fourth fields of the extent key are separate fields.

2. The method of claim 1 wherein only bits of a hash value required to identify the slot and reconstruct the extent key are stored in the slot.

3. The method of claim 1 further comprising:

executing, by the node of the cluster, one or more extent store instances.

4. The method of claim 3 wherein the recreating the first field, storing the second field, storing the third field and recreating the fourth field are performed in migration of buckets between the extent store instances.

5. The method of claim 1 wherein the first bits of the first field and the fourth bits of the fourth field are recreated without storage in the slot to reduce an amount of the metadata stored in the slot.

6. The method of claim 5 wherein use of the first bits in the first field of the extent key for hash table indexing enables inferential determination of the first bits.

7. The method of claim 5 wherein determination of the slot includes indexing into the hash table.

8. A non-transitory computer readable medium including program instructions for execution on one or more processors of a distributed storage architecture, the program instructions when executed operable to:

store a set of hash tables embodying metadata including an extent key associated with a storage location on storage devices for write data of one or more write requests organized into an extent, each hash table having a plurality of entries, wherein each entry includes a plurality of slots;

recreate a first field of the extent key implicitly from an entry in a first address space portion of a hash table, the first field having first bits used as a first hash table index to address the first address space portion of the hash table to select the entry and to determine a slot;

store a second field of the extent key in the slot, the second field having second bits used as a second hash table index to address a second address space portion of the hash table;

store a third field of the extent key in the slot, the third field having third bits used to realize uniqueness in an event of a collision in the hash table; and

recreate a fourth field of the extent key implicitly from the hash table of the set of hash tables, the fourth field having fourth bits used as a hash table selector to select the hash table from the set of hash tables, wherein the first through fourth fields of the extent key are separate fields.

9. The non-transitory computer readable medium of claim 8 wherein only bits of a hash value required to identify the slot and reconstruct the extent key are stored in the slot.

10. The non-transitory computer readable medium of claim 8 wherein the program instructions include program instructions for one or more extent store instances, and the program instruction operable to recreate the first field, store the second field, store the third field and recreate the fourth field are executed in migration of buckets between the extent store instances.

11. The non-transitory computer readable medium of claim 8 wherein the first bits of the first field and the fourth bits of the fourth field are recreated without storage in the slot to reduce an amount of the metadata stored in the slot.

12. The non-transitory computer readable medium of claim 11 wherein use of the first bits in the first field of the extent key for hash table indexing enables inferential determination of the first bits.

13. The non-transitory computer readable medium of claim 11 wherein determination of the slot includes indexing into the hash table.

14. A system comprising:

a central processing unit (CPU) of a node of a cluster having a plurality of nodes, each node coupled to a plurality of storage devices; and

a memory coupled to the CPU and configured to store a set of hash tables embodying metadata including an extent key associated with a storage location on the storage devices for write data of one or more write requests organized into an extent, each hash table having a plurality of entries, wherein each entry includes a plurality of slots, the memory further configured to store a storage input/output (I/O) stack having a plurality of layers implemented as one or more instances executable by the CPU, the one or more instances when executed operable to implement an extent key reconstruction technique to:

recreate a first field of the extent key implicitly from an entry in a first address space portion of a hash table, the first field having first bits used as a first hash table index to address the first address space portion of the hash table to select the entry and to determine a slot;

store a second field of the extent key in the slot, the second field having second bits used as a second hash table index to address a second address space portion of the hash table;

store a third field of the extent key in the slot, the third field having third bits used to realize uniqueness in an event of a collision in the hash table; and

recreate a fourth field of the extent key implicitly from the hash table of the set of hash tables, the fourth field having fourth bits used as a hash table selector to select the hash table from the set of hash tables, wherein the first through fourth fields of the extent key are separate fields.

15. The system of claim 14 wherein the extent key reconstruction technique enables reconstruction of the extent key based on contents of the slot to permit storage in the slot of only bits of a hash value required to identify the slot and reconstruct the extent key.

16. The system of claim 14 wherein the one or more instances executable by the CPU includes one or more extent store instances.

17. The system of claim 16 wherein the extent key reconstruction technique is performed in migration of buckets between the extent store instances within the cluster.

18. The system of claim 14 wherein the first bits of the first field and the fourth bits of the fourth field are recreated without storage in the slot to reduce an amount of the metadata stored in the slot.

19. The system of claim 18 wherein use of the first bits in the first field of the extent key for hash table indexing enables inferential determination of the first bits.

20. The system of claim 18 wherein the determination of the slot includes indexing into the hash table.