CONTENT ALIGNED BLOCK-BASED DEDUPLICATION

• US 20120084268A1
• Filed: 12/30/2010
• Published: 04/05/2012
• 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
• Granted Patent: US 8,364,652 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• 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 method for refining criteria for determining deduplication block alignments within a data segment, the method comprising:

selecting a first range of output values for a deduplication block alignment function which indicate that a block alignment has been found; and

iteratively performing a block alignment function on data within a sliding window in a data segment and, for each iterative performance of the block alignment function;

in response to determining with one or more computer processors whether the output of the block alignment function performed on a current window of data falls within the first range;

establishing a deduplication data block having a predetermined block size;

moving the sliding window in a first direction relative to the data segment by an amount based on the predetermined block size before performing the next iteration; and

in response to determining that the output of the block alignment function performed on the current window of data does not fall within the first range for a threshold number of iterations;

selecting a second range of output values for the block alignment function which indicate that a block alignment has been found; and

moving the sliding window over data relative to the data segment in a second direction opposite the first direction before performing the next iteration using the second range, wherein the next iteration is performed on data on which the block alignment function was previously performed using the first range.

2. The method of claim 1, wherein the threshold number of iterations is a threshold number of consecutive iterations.

3. The method of claim 1, further comprising, following the selecting the second range of output values, establishing with one or more computer processors one or more deduplication data blocks each having the predetermined block size in response to determining that the output of the block alignment function performed on data previously within the sliding window falls within the second range.

4. The method of claim 3, wherein the data previously within the sliding window comprises data that did not fall within the first range.

5. The method of claim 1, further comprising moving the sliding window relative to the data segment to a previous location within the data segment in response to determining, for a threshold number of consecutive iterations, that the output of the block alignment performed on the data within the sliding window does not fall within the first range.

6. The method of claim 5, wherein the previous location is the beginning of the data segment.

7. The method of claim 1, further comprising iteratively performing the alignment function across at least a portion of the data segment again after selecting the second range.

8. The method of claim 1, wherein the first range overlaps with the second range.

9. The method of claim 8, wherein the first range is a subset of the second range.

10. The method of claim 1, wherein the first range and the second range do not overlap.

11. The method of claim 1, wherein the block alignment function is a hash function and the method further comprises performing an intermediate modulo operation on the output of the block alignment function, and wherein the determining comprises determining whether the output of the intermediate modulo operation falls within the first range.

12. The method of claim 1, further comprising defining at least a portion of a gap of data not belonging to a deduplication data block in response to determining that the output of the block alignment function performed on the data within the sliding window does not fall within the first range.

13. The method of claim 1, further comprising establishing a deduplication data block in response to determining for a second threshold number of consecutive iterations that the output of the block alignment function performed on the current window of data does not fall within the first range.

14. A deduplication system configured determining deduplication block alignments within a data segment, the system comprising:

a block alignment module executing in one or more processors and configured to;

select a first range of output values for a deduplication block alignment function which indicate that a block alignment has been found; and

iteratively perform the deduplication block alignment function on data within a sliding window in a data segment and, for each iterative performance of the deduplication block alignment function, the block alignment module configured to;

determine whether the output of the deduplication block alignment function performed on data within the sliding window falls within the first range; and

establish a deduplication data block with a predetermined block size in response to determining that the output of the deduplication block alignment function performed on the data within the sliding window falls within the first range; and

a criteria adjustment module configured to select a second range of output values for the block alignment function which indicate that a block alignment has been found, the selection of the second range in response to the block alignment module determining, for a threshold number of iterations, that the output of the block alignment performed on the data within the sliding window does fall within the first range, wherein the second range is used instead of the first range for subsequent iterations of the block alignment function.

15. The deduplication system of claim 14, wherein the block alignment module is further configured to iteratively perform the alignment function across at least a portion of the data segment again after selecting the second range.

16. The method of claim 14, wherein the first range overlaps with the second range.

17. The method of claim 16, wherein the first range is a subset of the second range.

18. The method of claim 14, wherein the first range and the second range do not overlap.

19. The system of claim 14, wherein the block alignment module is further configured to establish a deduplication data block in response to determining for a second threshold number of iterations that the output of the block alignment function performed on the current window of data does not fall within the first range.

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

selecting a first range of possible output values of a deduplication block alignment function which indicate that a block alignment has been found; and

iteratively performing the deduplication block alignment function on data within a sliding window in a data segment and, for each iterative performance of the deduplication block alignment function;

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

establishing with one or more computer processors a deduplication data block having a predetermined block size in response to determining that the output of the block alignment function falls within the first range; and

selecting a second range of output values for the block alignment function which indicate that a block alignment has been found, the selection of the second range performed in response to determining, for a threshold number of iterations, that the output of the block alignment does not fall within the first range, wherein the second range is used instead of the first range for subsequent iterations of the block alignment function.