Extent hashing technique for distributed storage architecture

• US 9,405,783 B2
• Filed: 10/02/2013
• Issued: 08/02/2016
• Est. Priority Date: 10/02/2013
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Kimmel, Jeffrey S., Lewis, Blake H.
• Primary Examiner(s): Hershley, Mark E
• Application Number:
  US14/044,624
• Publication Number:
  US 20150095346A1
• Time in Patent Office: 1,035 Days
• Field of Search: 707/747
• US Class Current: 1/1
• 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 16/9014 hash tables
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

In one embodiment, a technique is provided for distributing data and associated metadata within a distributed storage architecture. A set of hash tables that embody mappings of cluster-wide identifiers associated with storage locations are stored for write data of write requests organized into extents. A hash value is generated from a hash function applied to each extent. The hash value is overloaded and used for multiple purposes within the distributed storage architecture, including (i) a remainder computation on the hash value to select a bucket of a plurality of buckets representative of the extents, (ii) a hash table selector of the hash value to select a hash table from the set of hash tables, and (iii) a hash table index computed from the hash value to select an entry from a plurality of entries of the selected hash table having a cluster-wide identifier identifying a storage location for the extent.

Claims

1. A system comprising:

a central processing unit (CPU) of a node of a cluster having additional nodes, each node coupled to one or more solid state drives (SSDs); and

a memory coupled to the CPU and configured to store a set of hash tables embodying mappings of cluster-wide identifiers associated with storage locations on the SSDs for write data of write requests organized into extents, the memory further configured to store a storage input/output (I/O) stack having a plurality of layers that cooperate with components of the additional nodes to provide a distributed storage architecture of the cluster, the layers of the storage I/O stack implemented as one or more processes executable by the CPU to;

generate a hash value from a hash function applied to each extent; and

overload the hash value for multiple purposes within the distributed storage architecture, including (i) a remainder computation on the hash value to select a bucket of a plurality of buckets representative of the extents, (ii) a hash table selector of the hash value to select a hash table from the set of hash tables, and (iii) a hash table index computed from the hash value to select an entry from a plurality of entries of the selected hash table having a cluster-wide identifier identifying a SSD storage location for an extent.

2. The system of claim 1 wherein overload of the hash value is achieved by applying prime divisors to the hash value.

3. The system of claim 1 wherein the hash function includes a property of block data randomization.

4. The system of claim 1 wherein the hash function includes a property that changing of bits of the extent results in each bit independently having a same chance of changing in the hash value.

5. The system of claim 1 wherein the hash function includes a distribution property that ensures the entries of the selected hash table are substantially balanced and substantially evenly accessed.

6. The system of claim 1 wherein the remainder computation is based on modulus arithmetic.

7. The system of claim 6 wherein the modulus arithmetic comprises a remainder of the hash value modulo a number of buckets.

8. A method comprising:

storing a set of hash tables that embody mappings of cluster-wide identifiers associated with storage locations on one or more solid state drives (SSDs) of a distributed storage architecture for write data of write requests organized into extents;

generating a hash value from a hash function applied to each extent; and

overloading the hash value for multiple purposes within the distributed storage architecture, including (i) a remainder computation on the hash value to select a bucket of a plurality of buckets representative of the extents, (ii) a hash table selector of the hash value to select a hash table from the set of hash tables, and (iii) a hash table index computed from the hash value to select an entry from a plurality of entries of the selected hash table having a cluster-wide identifier identifying a SSD storage location for an extent.

9. The method of claim 8 wherein overloading the hash value further comprises:

applying prime divisors to the hash value.

10. The method of claim 8 wherein the hash function includes a property of data randomization.

11. The method of claim 8 wherein the hash function includes a property that changing of bits of the extent results in each bit independently having a same chance of changing in the hash value.

12. The method of claim 8 wherein the hash function includes a distribution property that ensures the entries of the selected hash table are substantially balanced and substantially evenly accessed.

13. The method of claim 8 wherein the remainder computation is based on modulus arithmetic.

14. The method of claim 13 wherein the modulus arithmetic comprises a remainder of the hash value modulo a number of buckets.

15. A non-transitory computer readable medium including program instructions for execution on one or more processors, the program instructions when executed operable to:

store a set of hash tables that embody mappings of cluster-wide identifiers associated with storage locations on one or more solid state drives (SSDs) of a distributed storage architecture for write data of write requests organized into extents;

generate a hash value from a hash function applied to each extent; and

overload the hash value for multiple purposes within the distributed storage architecture, including (i) a remainder computation on the hash value to select a bucket of a plurality of buckets representative of the extents, (ii) a hash table selector of the hash value to select a hash table from the set of hash tables, and (iii) a hash table index computed from the hash value to select an entry from a plurality of entries of the selected hash table having a cluster-wide identifier identifying a SSD storage location for an extent.

16. The non-transitory computer readable medium of claim 15 wherein overload of the hash value is achieved by applying prime divisors to the hash value.

17. The non-transitory computer readable medium of claim 15 wherein the hash function includes a property of block data randomization.

18. The non-transitory computer readable medium of claim 15 wherein the hash function includes a property that changing of bits of the extent results in each bit independently having a same chance of changing in the hash value.

19. The non-transitory computer readable medium of claim 15 wherein the hash function includes a distribution property that ensures the entries of the selected hash table are substantially balanced and substantially evenly accessed.

20. The non-transitory computer readable medium of claim 15 wherein the remainder computation is based on modulus arithmetic.