Extent hashing technique for distributed storage architecture

• US 8,996,535 B1
• Filed: 01/21/2014
• Issued: 03/31/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.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Oberly, Van
• Application Number:
  US14/160,048
• Publication Number:
  US 20150095347A1
• Time in Patent Office: 434 Days
• Field of Search: 707/747
• 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, an extent hashing technique is used to efficiently distribute data and associated metadata substantially evenly among nodes of a cluster. The data may be write data associated with a write request issued by a host and received at a node of the cluster. The write data may be organized into one or more extents. A hash function may be applied to the extent to generate a result which may be truncated or trimmed to generate a hash value. A hash space of the hash value may be divided into a plurality of buckets representative of the write data, i.e., the extents, and the associated metadata, i.e., extent metadata. A number of buckets may be assigned to each extent store instance of the nodes to distribute ownership of the buckets, along with their extents and extent metadata, across all of the extent store instances of the nodes.

Claims

1. A method comprising:

organizing write data of write requests into one or more extents, wherein each extent is a block of data that provides a unit of storage on one or more storage devices of a cluster, the write requests processed at a node of the cluster, the cluster having a plurality of nodes;

applying a hash function to each extent to generate a hash value;

dividing a hash space of the hash value into a plurality of buckets representative of the one or more extents and associated extent metadata, a number of the buckets being less than a number of values in the hash space; and

assigning the buckets to extent store instances of the nodes in the cluster based on results of a remainder computation, wherein the remainder computation divides a remainder of the hash value of each extent by the number of buckets using modulo arithmetic, and the results of the remainder calculation are bucket numbers that operate as indexes in a bucket mapping data structure having bucket number entries, wherein each bucket number entry maps to an extent store instance.

2. The method of claim 1 wherein the number of buckets is relatively prime to a number used in a metadata selection computation by each extent store instance, wherein relatively prime denotes a lack of a common divisor.

3. The method of claim 1 wherein the number of buckets is a prime number.

4. The method of claim 1 wherein applying the hash function comprises inserting a secret value into the hash function.

5. The method of claim 1 wherein dividing the hash space of the hash value comprises dividing the hash value by the number of buckets, wherein the number of buckets is a prime number.

6. The method of claim 1 further comprising:

overloading the hash value for multiple different purposes within a context of a distributed storage architecture.

7. A method comprising:

forming an extent at a node of a cluster having a plurality of nodes, wherein the extent is a block of data that provides a unit of storage on one or more storage devices of the cluster;

applying a hash function to the extent to generate a hash value;

processing the hash value using a remainder computation to generate a bucket number of a bucket that includes a portion of a hash space of the hash function, wherein the remainder computation divides a remainder of the hash value by a number of buckets using modulo arithmetic; and

indexing into a selected entry of a bucket mapping data structure having bucket number entries using the bucket number, each bucket number entry mapping to an extent store instance, the indexing to identify an extent store instance of the node that serves the extent.

8. The method of claim 7 further comprising:

passing the hash value to the identified extent store instance to enable selection of extent metadata used to identify a location of the extent on a storage device of the one or more storage devices of the cluster.

9. The method of claim 8 further comprising:

using a first field of the hash value to select a hash table storing an extent key that is used to map to the location on the storage device.

10. The method of claim 9 wherein using the first field comprises using a hash table index field of the hash value.

11. The method of claim 9 further comprising:

using a second field of the hash value to index into the selected hash table to select an entry configured to store an identification of the location on the storage device.

12. The method of claim 11 wherein the entry is not found, using a third field of the hash value to index into the selected hash table.

13. The method of claim 7 wherein the number of buckets is a prime number.

14. A system comprising:

a central processing unit (CPU) of a node of a cluster having a plurality of nodes; and

a memory coupled to the CPU and configured to store one or more processes executable by the CPU, the one or more processes when executed operable to;

organize write data of write requests into one or more extents, an extent being a block of data that provides a unit of storage on one or more storage devices of the cluster;

apply a hash function to each extent to generate a hash value;

divide a hash space of the hash value into a plurality of buckets representative of the one or more extents and associated extent metadata, a number of the buckets being less than a number of values in the hash space; and

assign the buckets to extent store instances of the nodes in the cluster to thereby distribute ownership of the buckets across the extent store instances of the nodes, the assignment of buckets based on a remainder computation that divides a remainder of the hash value of each extent by the number of buckets using modulo arithmetic to generate bucket numbers, the bucket numbers used as indexes in a bucket mapping data structure having bucket number entries, wherein each bucket number entry maps to an extent store instance.

15. The system of claim 14 wherein the one or more storage devices are solid state drives (SSDs).

16. The system of claim 15 wherein the SSDs are flash storage devices.

17. A method comprising:

organizing write data of write requests into one or more extents, wherein each extent is a block of data that provides a unit of storage on one or more storage devices of a cluster, the write requests processed at a node of the cluster, the cluster having a plurality of nodes;

applying a hash function to each extent to generate a hash value;

dividing a hash space of the hash value into a plurality of buckets, a number of the buckets being less than a number of values in the hash space;

assigning the buckets to extent store instances of the nodes in the cluster by

performing a remainder computation, wherein the remainder computation divides a remainder of the hash value of each extent by the number of buckets using modulo arithmetic to generate bucket numbers, and

using the bucket numbers as indexes in a bucket mapping data structure having bucket number entries, wherein each bucket number entry maps to an extent store instance.

18. The method of claim 17, wherein the number of buckets is relatively prime to a number used in a metadata selection computation by each extent store instance, wherein relatively prime denotes a lack of a common divisor.

19. The method of claim 17, wherein applying the hash function comprises inserting a secret value into the hash function, wherein the secret value is a random value that is unique to the cluster.