EXTENT HASHING TECHNIQUE FOR DISTRIBUTED STORAGE ARCHITECTURE

• US 20150095346A1
• Filed: 10/02/2013
• Published: 04/02/2015
• Est. Priority Date: 10/02/2013
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Kimmel, Jeffrey S., Lewis, Blake H.
• Granted Patent: US 9,405,783 B2
• Time in Patent Office: Days
• US Class Current: 707/747
• 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-20. -20. (canceled)

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

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

23. The system of claim 21 wherein the hash function includes a property of block data randomization.

24. The system of claim 21 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.

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

26. The system of claim 21 wherein the remainder computation is based on modulus arithmetic.

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

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

29. The method of claim 28 wherein overloading the hash value further comprises:

applying prime divisors to the hash value.

30. The method of claim 28 wherein the hash function includes a property of data randomization.

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

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

33. The method of claim 28 wherein the remainder computation is based on modulus arithmetic.

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

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

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

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

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

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

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