Deduplication aware scalable content placement

• US 10,359,942 B2
• Filed: 10/31/2016
• Issued: 07/23/2019
• Est. Priority Date: 10/31/2016
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Lee, Robert, Lumb, Christopher, Miller, Ethan L., Ostrovsky, Igor
• Primary Examiner(s): Blust, Jason W
• Application Number:
  US15/339,302
• Publication Number:
  US 20180121089A1
• Time in Patent Office: 995 Days
• Field of Search: None
• 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/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Systems and methods of deduplication aware scalable content placement are described. A method may include receiving data to be stored on one or more nodes of a storage array and calculating a plurality of hashes corresponding to the data. The method further includes determining a first subset of the plurality of hashes, determining a second subset of the plurality of hashes of the first subset, and generating a node candidate placement list. The method may further include sending the first subset to one or more nodes represented on the node candidate placement list and receiving, from the nodes represented on the node candidate placement list, characteristics corresponding to the nodes represented on the candidate placement list. The method may further include identifying one of the one or more nodes represented on the candidate placement list in view of the characteristic and sending the data to the identified node.

Claims

1. A system comprising:

a storage array comprising a plurality of solid state drives; and

a storage controller coupled to one of the plurality of solid state drives, the storage controller comprising a processing device, the processing device to;

receive data to be stored in the storage array;

calculate a plurality of hashes corresponding to the data to be stored by utilizing a rolling hash algorithm on the data to be stored;

determine a first subset of the plurality of hashes corresponding to the data to be stored;

determine a second subset of the plurality of hashes of the first subset;

generate, in view of the second subset, a candidate placement list, wherein the candidate placement list comprises less than all of the plurality of solid state drives;

send the first subset of the plurality of hashes to one or more solid state drives, of the plurality of solid state drives, represented on the candidate placement list;

receive, from the one or more solid state drives represented on the candidate placement list, in response to sending the first subset of the plurality of hashes to the one or more solid state drives, characteristics corresponding to the one or more solid state drives represented on the candidate placement list; and

in view of the characteristics, identify one of the one or more solid state drives represented on the candidate placement list and send the data to the identified solid state drive.

2. The system of claim 1, wherein the processing device is further to:

receive the characteristics from a first solid state drive, of the plurality of solid state drives, represented on the candidate placement list, wherein the characteristics correspond to the first solid state drive; and

send the data to the first solid state drive.

3. The system of claim 1, wherein the processing device is further to:

receive the characteristics from a first solid state drive, of the plurality of solid state drives, represented on the candidate placement list, wherein the characteristics correspond to a second solid state drive of the plurality of solid state drives; and

send the data to the second solid state drive.

4. The system of claim 1, wherein the characteristics comprise a matching score corresponding to:

the first subset of the plurality of hashes corresponding to the data to be stored; and

data stored on one of the one or more solid state drives represented on the candidate placement list.

5. The system of claim 4, wherein the characteristics further comprise at least one of a capacity score or a load score, associated with a corresponding one of the one or more solid state drives represented on the candidate placement list.

6. The system of claim 1, wherein the processing device is to determine the first subset and the second subset in view of a predetermined number of low order bits corresponding to the plurality of hashes.

7. A method comprising:

receiving data to be stored on a plurality of nodes of a storage array;

calculating, by a processing device, a plurality of hashes corresponding to the data;

determining a first subset of the plurality of hashes corresponding to the data by utilizing a rolling hash algorithm on the data to be stored;

determining a second subset of the plurality of hashes of the first subset;

generating, by the processing device, in view of the second subset, a candidate placement list, wherein the candidate placement list comprises less than all of the plurality of nodes;

sending, by the processing device, the first subset of the plurality of hashes to one or more nodes represented on the candidate placement list;

receiving, from the one or more nodes represented on the candidate placement list, in response to sending the first subset of the plurality of hashes to the one or more nodes, characteristics corresponding to the one or more nodes represented on the candidate placement list; and

in view of the characteristics, identifying one of the one or more nodes represented on the candidate placement list and sending the data to the identified node.

8. The method of claim 7, wherein the plurality of nodes of the storage array is a plurality of solid state drives.

9. The method of claim 7, the method further comprising:

receiving the characteristics from a first node, of the plurality of nodes, represented on the candidate placement list, wherein the characteristics correspond to the first node; and

sending the data to the first node.

10. The method of claim 7, the method further comprising:

receiving the characteristics from a first solid state drive, of the plurality of nodes, represented on the candidate placement list, wherein the characteristics correspond to a second node of the plurality of nodes; and

sending the data to the second node.

11. The method of claim 7, wherein the characteristics comprise a matching score corresponding to:

the first subset of the plurality of hashes corresponding to the data to be stored; and

data stored on one of the one or more nodes represented on the candidate placement list.

12. The method of claim 11, wherein the characteristics further comprise at least one of a capacity score or a load score, associated with a corresponding one of the one or more nodes represented on the candidate placement list.

13. The method of claim 7, the method further comprising:

determining the first subset and the second subset in view of a predetermined number of low order bits corresponding to the plurality of hashes.

14. A non-transitory computer readable storage medium storing instructions, which when executed, cause a processing device to:

receive data to be stored on a plurality of nodes of a storage array;

calculate a plurality of hashes corresponding to the data by utilizing a rolling hash algorithm on the data to be stored;

determine a first subset of the plurality of hashes corresponding to the data;

generate, in view of the first subset, a candidate placement list, wherein the candidate placement list comprises less than all of the plurality of nodes; and

send the first subset of the plurality of hashes to one or more nodes represented on the candidate placement list;

receive, from the one or more nodes, of the plurality of nodes represented on the candidate placement list, in response to sending the first subset of the plurality of hashes to the one or more nodes, characteristics corresponding to the one or more nodes represented on the candidate placement list;

in view of the characteristics, identify the identified node of the one or more nodes represented on the candidate placement list and send the data to an identified node of the candidate placement list.

15. The non-transitory computer readable storage medium of claim 14, wherein the processing device is further to:

receive the characteristics from a first node, of the plurality of nodes, represented on the candidate placement list, wherein the characteristics correspond to the first node; and

send the data to the first node.

16. The non-transitory computer readable storage medium of claim 14, wherein the processing device is further to:

receive the characteristics from a first node, of the plurality of nodes, represented on the candidate placement list, wherein the characteristics correspond to a second node of the plurality of nodes; and

send the data to the second node.

17. The non-transitory computer readable storage medium of claim 14, wherein the characteristics comprise a matching score corresponding to:

the first subset of the plurality of bashes corresponding to the data to be stored; and

data stored on one of the one or more nodes represented on the candidate placement list.