Selecting a store for deduplicated data

• US 10,592,347 B2
• Filed: 05/16/2013
• Issued: 03/17/2020
• Est. Priority Date: 05/16/2013
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Todd, Andrew, Camble, Peter Thomas, Jeong, Wayland Kenneth, Chandrasekharan, Kaushik, Suehr, Dennis
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Caiado, Antonio J
• Application Number:
  US14/787,086
• Publication Number:
  US 20160077924A1
• Time in Patent Office: 2,497 Days
• Field of Search: 707652, 707679, 707189, 707747, 707812
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A technique includes communicating a plurality of hashes associated with chunks of an object to at least some stores of a plurality of stores on which the object is distributed; and in response to the communication, receiving responses indicating a distribution of the associated chunks. The technique includes selecting one of the stores based at least in part on the responses and communicating deduplicated data associated with the object to the selected store.

Claims

1. A method comprising:

communicating, by a processor, a subset of a plurality of hashes associated with chunks of an object to each of a plurality of stores, wherein each of the stores is to match the subset of hashes to a list of hashes of data stored in the store and generate a count value of matched hashes;

in response to the communication, receiving, by the processor, the count value of matched hashes from each of the stores;

selecting, by the processor, one of the stores to store deduplicated data associated with the object based on a comparison of the count values of matched hashes received from the stores to a threshold; and

performing, by the processor, a deduplication process with the selected store using remaining hashes of the plurality of hashes to identify the deduplicated data associated with the object; and

communicating, by the processor, the deduplicated data associated with the object to the selected store for storage.

2. The method of claim 1, wherein performing the deduplication process with the selected store includes:

sending the remaining hashes of the plurality of hashes to the selected store, wherein the selected store is to match the remaining hashes to the list of hashes of data stored in the selected store and generate hashes that match the hashes stored in the selected store;

receiving the matched hashes from the selected store;

based on the matched hashes, identifying chunks of the object that are not stored in the selected store as the deduplicated data.

3. The method of claim 1, wherein selecting one of the stores includes:

in response to a determination that a plurality of the count values of matched hashes exceeds the threshold, determining whether one of the stores whose count values of matched hashes exceed the threshold is a same as an immediate previous selected store; and

in response to a determination that one of the stores is the same as the immediate previous selected store, selecting the immediate previous selected store as a current selected store to store the deduplicated data.

4. The method of claim 1, wherein selecting one of the stores comprises, responsive to a determination that none of the count values of matched hashes received from the stores is above the threshold, selecting a current seeding store of the plurality of stores.

5. The method of claim 1, further comprising:

communicating to each of the non-selected stores an indication that the non-selected store will not be receiving the deduplicated data.

6. A system comprising:

a plurality of team members to store a distributed teamed object; and

a client server comprising at least one central processing unit and a memory comprising instructions that, when executed by the at least one central processing unit, are to cause the client server to;

communicate a subset of hashes associated with chunks of the object to each of the plurality of team members, wherein each of the plurality of team members is to match the subset of hashes to a list of hashes of data stored in the team member and generate a count value of matched hashes;

in response to the communication, receive the count value of matched hashes from each team member of the plurality of team members;

select a team member of the plurality of team members to store deduplicated data associated with the object based on a comparison of the count values of matched hashes to a threshold;

perform a deduplication process with the selected team member using remaining hashes of the plurality of hashes to identify the deduplicated data associated with the object; and

communicate the deduplicated data associated with the object to the selected team member for storage.

7. The system of claim 6, wherein the subset of hashes is indicative of the chunks of the object.

8. The system of claim 6, wherein to perform the deduplication process with the selected store, the client server is to:

send the remaining hashes of the plurality of hashes to the selected store, wherein the selected store is to match the remaining hashes to the list of hashes of data stored in the selected store and generate hashes that match the hashes stored in the selected store;

receive the matched hashes from the selected store; and

based on the matched hashes, identify chunks of the object that are not stored in the selected store as the deduplicated data.

9. The system of claim 6, wherein at least one of the team members is to, in response to not being selected, receive an indication that the team member will not receive the deduplicated data.

10. A non-transitory computer readable storage medium storing instructions that when executed by a computer cause the computer to:

communicate a subset of hashes associated with chunks of an object to each of a plurality of stores, wherein each of the plurality of stores is to match the subset of hashes to a list of hashes of data stored in the store and generate a count value of matched hashes;

in response to the communication, receive the count value of matched hashes from each of the plurality of stores;

select one of the stores to store deduplicated data associated with the object based at least in part on a comparison of the count values of matched hashes to a threshold;

perform a deduplication process with the selected store using remaining hashes of the plurality of hashes to identify the deduplicated data associated with the object; and

communicate the deduplicated data associated with the object to the selected store for storage.

11. The non-transitory computer readable medium of claim 10, wherein, to select one of the stores, the instructions are executable to cause the computer to:

in response to a determination that a plurality of the count values of matched hashes exceeds the threshold, determine whether one of the stores whose count values of matched hashes exceed the threshold is a same as an immediate previous selected store; and

in response to a determination that one of the stores is the same as the immediate previous selected store, select the immediate previous selected store as a current selected store to store the deduplicated data.

12. The non-transitory computer readable medium of claim 11, wherein, to perform the deduplication process with the selected store, the instructions are executable to cause the computer to:

send the remaining hashes of the plurality of hashes to the selected store, wherein the selected store is to match the remaining hashes to the list of hashes of data stored in the selected store and generate hashes that match the hashes stored in the selected store;

receive the matched hashes from the selected store; and

based on the matched hashes, identify chunks of the object that are not stored in the selected store as the deduplicated data.

13. The non-transitory computer readable medium of claim 10, wherein the instructions are executable to cause the computer to, in response to a determination that none of the count values of matched hashes received from the stores is above the threshold, select a current seeding store of the plurality of stores.

14. The non-transitory computer readable medium of claim 10, wherein the instructions are executable to cause the computer to communicate to each of the non-selected stores an indication that the non-selected store will not be receiving the deduplicated data.