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

• US 9,639,278 B2
• Filed: 10/29/2015
• Issued: 05/02/2017
• Est. Priority Date: 01/17/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Kimmel, Jeffrey S., Rakitzis, T. Byron
• Primary Examiner(s): Sadler, Nathan
• Application Number:
  US14/927,230
• Publication Number:
  US 20160048332A1
• Time in Patent Office: 551 Days
• 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

The embodiments described herein are directed to the use of hashing in a file system metadata arrangement that reduces an amount of metadata stored in a memory of a node in a cluster and that reduces the amount of metadata needed to process an input/output (I/O) request at the node. Illustratively, the embodiments are directed to cuckoo hashing and, in particular, to a manner in which cuckoo hashing may be modified and applied to construct the file system metadata arrangement. In an embodiment, the file system metadata arrangement may be illustratively include a hash collision technique that employs a hash collision computation to determine a unique candidate extent key (having a candidate hash table index) in the event of a collision, i.e., a hash table index collides with a slot of a hash table matching a key found in the slot.

Claims

1. A method comprising:

receiving write requests having a plurality of extents at a cluster of nodes, each write request processed at a node having a processor and a memory, the memory configured to store a storage input/output (I/O) stack having a plurality of layers implemented as one or more instances executable by the processor, the node coupled to one or more solid state drives (SSDs);

applying a hash function to an extent of the plurality of extents to generate a hash value, the hash value including a hash table selector, a first hash table index, and a second hash table index;

mapping the hash value to an extent store instance of the storage I/O stack that is responsible for storing the extent on a SSD of the one or more SSDs;

selecting a hash table from a set of hash tables served by the extent store instance using the hash table selector, each hash table divided into one or more index address spaces;

selecting a first entry in an index address space of the hash table using the first hash table index, the first entry including a first set of slots having first keys;

matching one of the first keys of the first set of slots to the second hash table index; and

in response to matching one of the first keys, generating a candidate extent key including a candidate hash table index used to select a second entry of the set of hash tables for storing an identification of a storage location on SSD for the extent, the candidate hash table index resolving to the extent store instance serving the set of hash tables.

2. The method of claim 1 wherein generating the candidate extent key comprises:

computing the candidate extent key from the hash value using a hash collision computation that adds a prime to the hash value.

3. The method of claim 2 wherein the prime is 65521.

4. The method of claim 2 wherein computing the candidate extent key comprises:

computing the candidate extent key from a substring of the hash value, wherein the substring is formed from low-order bits of the hash value.

5. The method of claim 1 wherein mapping the hash value comprises:

dividing a hash space of the hash value into a plurality of buckets representative of the plurality of extents; and

associating one or more of the buckets to the extent store instance based on results of a remainder computation that maps a bucket number to the extent store instance.

6. The method of claim 5 wherein generating the candidate extent key comprises:

computing the candidate extent key from the hash value using a hash collision computation that adds a prime to the hash value such that the candidate extent key resolves to the bucket number mapped to the extent store instance.

7. The method of claim 6 wherein computing the candidate extent key comprises:

computing the candidate extent key from the hash value using the hash collision computation such that the candidate extent key and hash value resolve to the bucket number as well as to different entries in the set of hash tables.

8. A system comprising:

a storage system of a cluster configured to receive write requests having a plurality of extents, the storage system having a memory connected to a processor via a bus, the storage system coupled to a storage array having one or more solid state drives (SSDs), the memory configured to store a storage input/output (I/O) stack having a plurality of layers implemented as one or more instances executable by the processor, the storage I/O stack configured to;

apply a hash function to an extent of the plurality of extents to generate a hash value, the hash value including a hash table selector, a first hash table index, and a second hash table index;

map the hash value to an extent store instance of the storage I/O stack that is responsible for storing the extent on a SSD of the one or more SSDs;

select a hash table from a set of hash tables served by the extent store instance using the hash table selector, each hash table divided into one or more index address spaces;

select a first entry in an index address space of the hash table using the first hash table index, the first entry including a first set of slots having first keys;

match one of the first keys of the first set of slots to the second hash table index; and

in response to matching one of the first keys, generate a candidate extent key including a candidate hash table index used to select a second entry of the set of hash tables for storing an identification of a storage location on SSD for the extent, the candidate hash table index resolving to the extent store instance serving the set of hash tables.

9. The system of claim 8 wherein the storage I/O stack configured to generate the candidate extent key is further configured to:

compute the candidate extent key from the hash value using a hash collision computation that adds a prime to the hash value.

10. The system of claim 9 wherein the prime is 65521.

11. The system of claim 9 wherein the storage I/O stack configured to compute the candidate extent key is further configured to:

compute the candidate extent key from a substring of the hash value, wherein the substring is formed from low-order bits of the hash value.

12. The system of claim 8 wherein the storage I/O stack configured to map the hash value is further configured to:

divide a hash space of the hash value into a plurality of buckets representative of the plurality of extents; and

associate one or more of the buckets to the extent store instance based on results of a remainder computation that maps a bucket number to the extent store instance.

13. The system of claim 12 wherein the storage I/O stack configured to generate the candidate extent key is further configured to:

compute the candidate extent key from the hash value using a hash collision computation that adds a prime to the hash value such that the candidate extent key resolves to the bucket number mapped to the extent store instance.

14. The system of claim 13 wherein the storage I/O stack configured to compute the candidate extent key is further configured to:

compute the candidate extent key from the hash value using the hash collision computation such that the candidate extent key and hash value resolve to the bucket number as well as to different entries in the set of hash tables.

15. A non-transitory computer readable medium including program instructions for execution on one or more processors of a cluster configured to process write requests having a plurality of extents, the cluster including a storage system coupled to one or more solid state drives (SSDs), the storage system having a memory configured to store a storage input/output (I/O) stack having a plurality of layers implemented as one or more instances executable by the processor, the program instructions configured to:

apply a hash function to an extent of the plurality of extents to generate a hash value, the hash value including a hash table selector, a first hash table index, and a second hash table index;

map the hash value to an extent store instance of the storage I/O stack that is responsible for storing the extent on a SSD of the one or more SSDs;

select a hash table from a set of hash tables served by the extent store instance using the hash table selector, each hash table divided into a plurality of index address spaces;

select a first entry in an index address space of the hash table using the first hash table index, the first entry including a first set of slots having first keys;

match one of the first keys of the first set of slots to the second hash table index; and

in response to matching one of the first keys, generate a candidate extent key including a candidate hash table index used to select a second entry of the set of hash tables for storing an identification of a storage location on SSD for the extent, the candidate hash table index resolving to the extent store instance serving the set of hash tables.

16. The non-transitory computer readable medium of claim 15 wherein the program instructions configured to generate the candidate extent key are further configured to:

compute the candidate extent key from the hash value using a hash collision computation that adds a prime to the hash value.

17. The non-transitory computer readable medium of claim 16 wherein the program instructions configured to compute the candidate extent key are further configured to:

compute the candidate extent key from a substring of the hash value, wherein the substring is formed from low-order bits of the hash value.

18. The non-transitory computer readable medium of claim 15 wherein the program instructions configured to map the hash value are further configured to:

divide a hash space of the hash value into a plurality of buckets representative of the plurality of extents; and

associate one or more of the buckets to the extent store instance based on results of a remainder computation that maps a bucket number to the extent store instance.

19. The non-transitory computer readable medium of claim 18 wherein the program instructions configured to generate the candidate extent key are further configured to:

compute the candidate extent key from the hash value using a hash collision computation that adds a prime to the hash value such that the candidate extent key resolves to the bucket number mapped to the extent store instance.

20. The non-transitory computer readable medium of claim 19 wherein the program instructions configured to compute the candidate extent key are further configured to:

compute the candidate extent key from the hash value using the hash collision computation such that the candidate extent key and hash value resolve to the bucket number as well as to different entries in the set of hash tables.