Content aligned block-based deduplication

• US 9,110,602 B2
• Filed: 01/25/2013
• Issued: 08/18/2015
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Vijayan, Manoj Kumar, Attarde, Deepak Raghunath, Viswanathan, Srikant
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US13/750,105
• Publication Number:
  US 20130232309A1
• Time in Patent Office: 935 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• 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/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A content alignment system according to certain embodiments aligns a sliding window at the beginning of a data segment. The content alignment system performs a block alignment function on the data within the sliding window. A deduplication block is established if the output of the block alignment function meets a predetermined criteria. At least part of a gap is established if the output of the block alignment function does not meet the predetermined criteria. The predetermined criteria is changed if a threshold number of outputs fail to meet the predetermined criteria.

Claims

1. A deduplication system configured to determine deduplication block alignments within a data segment, the system comprising:

one or more computer processors comprising computer hardware;

a duplication module being executed by the one or more computer processors and configured to;

select one or more first block alignment indicator values for a deduplication block alignment function;

iteratively perform the deduplication block alignment function on data within a sliding window of the data segment, wherein the sliding window comprises a sliding boundary;

establish a deduplication data block based at least in part on a determination that an output of the deduplication block alignment function performed on the data matches one of the one or more first block alignment indicator values, indicating that a deduplication block alignment has been found; and

deduplicate the deduplication data block; and

a criteria adjustment module configured to select one or more second block alignment indicator values to replace the one or more first block alignment indicator values based at least in part on a determination that, for a threshold number of the iterative performances of the deduplication block alignment function, the output of the deduplication block alignment function performed on the data within the sliding window does not match any of the one or more first block alignment indicator values, wherein the one or more second block alignment indicator values are used instead of the one or more first block alignment indicator values for subsequent iterations of the deduplication block alignment function.

2. The deduplication system of claim 1, wherein the deduplication module is further configured to iteratively perform the deduplication block alignment function across at least a portion of the data segment again after selecting the one or more second block alignment indicator values.

3. The deduplication system of claim 1, wherein the one or more first block alignment indicator values overlap with the one or more second block alignment indicator values.

4. The deduplication system of claim 3, wherein the one or more first block alignment indicator values is a subset of the one or more second block alignment indicator values.

5. The deduplication system of claim 1, wherein the one or more first block alignment indicator values and the one or more second block alignment indicator values do not overlap.

6. The deduplication system of claim 1, wherein the deduplication data block is a first deduplication block and the deduplication module is further configured to establish a second deduplication data block based at least in part on determining for a second threshold number of iterations that the output of the deduplication block alignment function performed on current window of data does not fall within the one or more first block alignment indicator values.

15. The deduplication system of claim 1, wherein the deduplication data block is a predetermined size.

16. The deduplication system of claim 1, wherein the deduplicated data block is stored in one or more memory devices of a backup storage subsystem residing on a storage area network.

7. A method of determining deduplication block alignments within a data segment, the method comprising:

selecting one or more first block alignment indicator values of a deduplication block alignment function;

iteratively performing the deduplication block alignment function on data within a sliding window in the data segment, wherein the sliding window comprises a sliding boundary;

determining with one or more computer processors whether an output of the deduplication block alignment function performed on the data within the sliding window falls within the one or more first block alignment indicator values;

establishing with one or more computer processors a deduplication data block based at least in part on determining that the output of the deduplication block alignment function matches one of the one or more first block alignment indicator values, indicating that a deduplication block alignment has been found; and

selecting one or more second block alignment indicator values to replace the one or more first block alignment indicator values based at least in part on determining, for a threshold number of the iterative performances of the deduplication block alignment function, the output of the deduplication block alignment function does not match any of the one or more first block alignment indicator values, wherein the one or more second block alignment indicator values are used instead of the one or more first block alignment indicator values for subsequent iterations of the deduplication block alignment function; and

deduplicating the deduplication data block.

8. The method of claim 7, further comprising iteratively performing the deduplication block alignment function across at least a portion of the data segment again after adjusting the one or more first block alignment indicator values to the one or more second block alignment indicator values.

9. The method of claim 7, wherein the one or more first block alignment indicator values overlap with the one or more second block alignment indicator values.

10. The method of claim 9, wherein the one or more first block alignment indicator values being a subset of the one or more second block alignment indicator values.

11. The method of claim 7, wherein the one or more first block alignment indicator values and the one or more second block alignment indicator values do not overlap.

12. The method of claim 7, wherein the deduplication data block is a first deduplication block, the method further comprising establishing a second deduplication data block based at least in part on determining for a second threshold number of the iterative performances of the deduplication block alignment function that the output of the deduplication block alignment function performed on current window of data does not fall within the one or more first block alignment indicator values.

13. The method of claim 7, wherein the deduplication data block is a predetermined size.

14. The method of claim 7, wherein the deduplicated data block is stored in one or more memory devices of a backup storage subsystem residing on a storage area network.

17. A method of generating a deduplication data block within a data segment, the method comprising:

selecting one or more first block alignment indicator values of a deduplication block alignment function; and

iteratively performing the deduplication block alignment function on data within a sliding window in the data segment, the sliding window comprising a sliding boundary;

determining with one or more computer processors whether an output of the deduplication block alignment function performed on the data within the sliding window matches at least one of the one or more first block alignment indicator values, indicating that a deduplication block alignment has been found;

establishing with one or more computer processors a first deduplication data block based at least in part on determining that the output of the deduplication block alignment function matches the at least one of the one or more first block alignment indicator values;

establishing with one or more computer processors a second deduplication data block based at least in part on determining, for a threshold number of the iterative performances of the deduplication block alignment function, that the output of the deduplication block alignment function does not match the at least one of the one or more first block alignment indicator values; and

deduplicating at least one of the first deduplication data block or the second deduplication data block.