SET-ASSOCIATIVE HASH TABLE ORGANIZATION FOR EFFICIENT STORAGE AND RETRIEVAL OF DATA IN A STORAGE SYSTEM

• US 20150205727A1
• Filed: 01/17/2014
• Published: 07/23/2015
• Est. Priority Date: 01/17/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Kimmel, Jeffrey S., Rakitzis, T. Byron
• Granted Patent: US 9,256,549 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

In one embodiment, an extent key reconstruction technique is provided for use with a set of hash tables embodying metadata. The metadata includes 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 has a plurality of entries, and each entry includes a plurality of slots. A first field of the extent key is recreated implicitly from an entry in a first address space portion of a hash table. A second field of the extent key is stored in the slot. A third field of the extent key is stored in the slot. A fourth field of the extent key is recreated implicitly from the hash table of the set of hash tables.

Claims

1-20. -20. (canceled)

21. 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.

22. The system of claim 21 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 the hash value required to identify the slot and reconstruct the extent key.

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

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

25. The system of claim 21 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 the amount of the metadata stored in the slot.

26. The system of claim 25 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.

27. The system of claim 25 wherein the determination of the slot includes indexing into the hash table.

28. 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.

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

30. The method of claim 28 further comprising:

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

31. The method of claim 30 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.

32. The method of claim 28 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 the amount of the metadata stored in the slot.

33. The method of claim 32 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.

34. The method of claim 32 wherein determination of the slot includes indexing into the hash table.

35. 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.

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

37. The non-transitory computer readable medium of claim 35 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.

38. The non-transitory computer readable medium of claim 35 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 the amount of the metadata stored in the slot.

39. The non-transitory computer readable medium of claim 38 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.

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