Using index partitioning and reconciliation for data deduplication

• US 9,785,666 B2
• Filed: 07/13/2015
• Issued: 10/10/2017
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Li, Jin, Sengupta, Sudipta, Kalach, Ran, Desai, Ronakkumar N., Oltean, Paul Adrian, Benton, James Robert
• Primary Examiner(s): Pham, Khanh
• Application Number:
  US14/797,890
• Publication Number:
  US 20160012098A1
• Time in Patent Office: 820 Days
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

The subject disclosure is directed towards a data deduplication technology in which a hash index service'"'"'s index is partitioned into subspace indexes, with less than the entire hash index service'"'"'s index cached to save memory. The subspace index is accessed to determine whether a data chunk already exists or needs to be indexed and stored. The index may be divided into subspaces based on criteria associated with the data to index, such as file type, data type, time of last usage, and so on. Also described is subspace reconciliation, in which duplicate entries in subspaces are detected so as to remove entries and chunks from the deduplication system. Subspace reconciliation may be performed at off-peak time, when more system resources are available, and may be interrupted if resources are needed. Subspaces to reconcile may be based on similarity, including via similarity of signatures that each compactly represents the subspace'"'"'s hashes.

Claims

1. An apparatus, comprising:

a processor; and

a memory containing logic operative on the processor to cause the processor to perform a process comprising;

loading a subspace index comprising less than all index entries of a signature index service from a secondary media into a primary memory, wherein the loaded subspace index corresponds to a set of subspaces individually containing a set of signatures each corresponding to a data chunk stored in a data store, two of the subspaces having at least one signature representative of one subspace generally matching at least one signature representative of the other subspace; and

reconciling the two subspaces associated with the loaded subspace index to remove at least one duplicate chunk by;

using a resemblance metric to compare a signature of a data chunk in one of the two subspaces to multiple signatures of data chunks in the other of the two subspaces; and

in response to determining that the signature of the data chunk in one of the two subspaces matches another signature in the other of the two subspaces, marking a data chunk corresponding to the signature or the another signature for deletion from a corresponding data store.

2. The apparatus of claim 1, wherein the process performed by the processor further includes determining a similarity between a type of the one of the subspaces and a type of the other subspaces.

3. The apparatus of claim 1, wherein the process performed by the processor further includes use the subspace index to deduplicate a dataset.

4. The apparatus of claim 1, wherein the process performed by the processor further includes chunking the dataset into one or more data chunks, and for each data chunk, determining whether a signature value computed for that data chunk matches a signature value of an entry in the primary memory, and in response to determining that the computed signature value for that data chunk does not match a signature value of an entry in the primary memory, storing the data chunk in data store and adding an entry for that signature value into the subspace index in association with a reference to that data chunk, and in response to determining that the computed signature value for that data chunk matches a signature value of an entry in the primary memory, return information by which the existing data chunk is locatable.

5. The apparatus of claim 1, wherein the process performed by the processor further includes limiting a duplication chain to a number of I/O accesses and generating a reconciliation tree to have a number of branches no more than the number of I/O accesses.

6. The apparatus of claim 5, wherein the process performed by the processor further includes restoring a most recent backup in the deduplication chain without incurring more than the number of I/O accesses.

7. The apparatus of claim 1, wherein the process performed by the processor further includes reconciling the subspace index with a subspace.

8. The apparatus of claim 7, wherein the process performed by the processor further includes using the resemblance metric to determine a similarity between at least one signature representative of the subspace index and at least one signature representative of the subspace.

9. The apparatus of claim 1, wherein the process performed by the processor further includes creating a modified subspace, and copying an entry in the subspace index into the modified subspace when that entry does not correspond to a data chunk in the one of the subspaces.

10. The apparatus of claim 9, wherein the process performed by the processor further includes updating a reference to the data chunk in one of the subspaces to a reference to the chunk in the other of the subspaces when the data chunk in the one of the subspaces is removed.

11. A method performed by a computing device in a network storage system, the method comprising:

selecting first and second subspaces of a global index for reconciliation, the first and second subspaces individually containing multiple (i) signatures of data chunks each stored in a data store in the network storage system and (ii) references to the data chunks stored in the corresponding data stores, wherein selecting the first and second subspaces including;

using a resemblance metric to determine a subspace similarity between the first and second subspaces; and

choosing the first and second subspaces for reconciliation based on the determined subspace similarity; and

reconciling the first and second subspaces to remove at least one duplicate chunk from the first and second subspaces, comprising;

determining whether a first signature in the first subspace matches a second signature in the second subspace; and

in response to determining that the first signature in the first subspace matches the second signature in the second subspace, marking a data chunk referenced to either the first signature or the second signature for deletion from a corresponding data store.

12. The method of claim 11, further comprising comparing the first subspace to the second subspace by determining a similarity between signatures representative of the first and second subspaces, respectively.

13. The method of claim 11, further comprising determining whether one of the first or second subspace is similar to a subspace index loaded into a primary memory based upon a similarity between a signature representative of the first or second subspace and a signature representative of the subspace index.

14. The method of claim 13, further comprising using the subspace index to deduplicate a dataset having multiple data chunks, including:

for each chunk of the dataset, determining whether a signature of the data chunk corresponds to an entry in the primary memory; and

in response to determining that the signature of the data chunk does not correspond to any entry in the primary memory , adding an entry for the data chunk into the subspace index in association with a reference to the data chunk stored in a corresponding data store.

15. The method of claim 11, further comprising copying an entry in one of the first or second subspace into a new subspace when that entry does not correspond to a data chunk in another one of the first or second subspace.

16. The method of claim 11, further comprising eliminating an entry in one of the first or second subspace when that entry corresponds to a data chunk that is similar to another data chunk of another one of the first or second subspace and updating each reference to the data chunk to a reference to the another chunk in the another one of the first or second subspace.

17. In a computing environment, a method performed on one or more processors, the method comprising:

loading a subspace index comprising less than all index entries of a hash index service from a secondary media into a primary memory, wherein the subspace index corresponds to a partitioning of a global index into separate subspaces;

reconciling at least two of the subspaces to remove at least one duplicate chunk, including using a resemblance metric to compare a subspace and another subspace by determining a similarity between at least one signature representative of the subspace and at least one signature representative of the other subspace; and

using the subspace index to deduplicate a dataset, including;

chunking the dataset into one or more chunks;

for each chunk, determining whether a hash value computed for that chunk matches a hash value of an entry in the primary memory;

in response to determining that the hash value computed for the chunk does not match any hash value of an entry in the primary memory, storing the chunk and adding an entry for the computed hash value associated with the chunk into the subspace index in association with a reference to the chunk; and

in response to determining that the hash value computed for the chunk matches a hash value of an entry in the primary memory, returning data representing information by which an existing chunk corresponding to the hash value of the entry in the primary memory is locatable.

18. The method of claim 17 wherein partitioning the global index comprises partitioning based upon machine location, storage volume location, data location, learned criteria or adaptive criteria, or any combination of machine location, storage volume location, data location, learned criteria or adaptive criteria.

19. The method of claim 17 wherein returning the data representing information by which the existing chunk is locatable comprises returning a chunk identifier comprising a reference to the chunk that is associated with the entry, or returning a hash value and an identifier of the subspace to which the hash value of the chunk belongs.

20. The method of claim 17, further comprising computing the signature for the subspace based upon a min hash computation, a variant of min-hash, or a combination thereof.