Content aligned block-based deduplication

• US 8,577,851 B2
• Filed: 12/30/2010
• Issued: 11/05/2013
• 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): Chbouki, Tarek
• Application Number:
  US12/982,086
• Publication Number:
  US 20120084269A1
• Time in Patent Office: 1,041 Days
• Field of Search: None
• 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 defining deduplication block alignments within a data segment, the method comprising:

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

in response to determining that the output of the block alignment function performed on a current window of data satisfies a predetermined criteria;

establishing with one or more computer processors a deduplication data block having a predetermined block size; and

moving the sliding window relative to the data segment by an amount based on the predetermined block size before a next iterative performance of the block alignment function; and

in response to determining that the output of the block alignment function performed on the current window of data does not satisfy the predetermined criteria;

moving the sliding window relative to the data segment by a predetermined incremental amount that is different from the predetermined block size before the next iterative performance of the block alignment function and without establishing a deduplication data block,

wherein gaps of data not belonging to any deduplication data block exist between at least some established deduplication data blocks following performance of the block alignment function across the data segment, and

wherein the size of the gaps of data is based at least on a number of successive outputs of the block alignment function that do not satisfy the predetermined criteria.

2. The method of claim 1, wherein each of the established deduplication data blocks have the same predetermined block size.

3. The method of claim 1, wherein the gaps of data comprise variable gap sizes.

4. The method of claim 1, further comprising changing the predetermined criteria 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 satisfy the predetermined criteria.

5. The method of claim 4, wherein the predetermined criteria is whether the output of the block alignment function falls within a predetermined range, and changing the predetermined criteria comprises altering the predetermined range.

6. The method of claim 4, wherein the changing the predetermined criteria comprises altering the block alignment function.

7. The method of claim 6, wherein the block alignment function is a hash function and altering the block alignment function comprises using a different hash function.

8. The method of claim 4, further comprising iteratively performing the block alignment function across at least a portion of the data segment again in response to changing the predetermined criteria.

9. The method of claim 1, further comprising:

in response to determining for a threshold number of consecutive iterations that the output of the block alignment function performed on the current window of data does not satisfy the predetermined criteria;

establishing a deduplication data block; and

moving the sliding window relative to the data segment by an incremental amount.

10. The method of claim 1, wherein a size of the gaps of data correspond to a size of one or more incremental amounts.

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

a deduplication block alignment module executing in one or more processors and configured to iteratively perform a deduplication block alignment function on data within a sliding window in a data segment and which, for each iterative performance of the block alignment function, is configured to;

establish a deduplication block having 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 satisfies a predetermined criteria; and

define at least a portion of data having a predetermined incremental size that is different from the predetermined block size as not belonging to a deduplication block in response to determining that the output of the block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria,

wherein the predetermined incremental size is determined prior to determining that the output of the block alignment function performed on the data within the sliding window does not satisy the predetermined criteria.

12. The system of claim 11, wherein the block alignment module is further configured to:

move the sliding window relative to the data segment by an amount based on the predetermined block size in response to determining that the output of the block alignment function performed on the data within the sliding window satisfies the predetermined criteria; and

move the sliding window relative to the data segment by an incremental amount in response to determining that the output of the block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria.

13. The system of claim 12, wherein the block alignment module is further configured to change the predetermined criteria in response to determining, for a threshold number of consecutive iterations, that the output of the block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria.

14. The system of claim 13, wherein the block alignment module is further configured to perform the block alignment function across at least a portion of the data segment again in response to the criteria adjustment module changing the predetermined criteria.

15. The method of claim 13, wherein the changing the predetermined criteria comprises altering the block alignment function.

16. The system of claim 11, wherein the block alignment module is further configured to:

establish a deduplication data block in response to the block alignment module determining for a threshold number of consecutive iterations that the output of the block alignment function performed on the current window of data does not satisfy the predetermined criteria; and

move the sliding window relative to the data segment by an incremental amount in response to the block alignment module determining for a threshold number of consecutive iterations that the output of the block alignment function performed on the current window of data does not satisfy the predetermined criteria.

17. A method for defining deduplication block alignments within a data segment, the method comprising:

iteratively performing a 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;

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 deduplication block alignment function performed on the data within the sliding window satisfies a predetermined criteria; and

defining at least a portion of a gap of data having a predetermined incremental size that is different from the predetermined block size as not belonging to a deduplication data block in response to determining that the output of the deduplication block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria, wherein the predetermined incremental size is determined prior to determining that the output of the block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria.

18. The method of claim 17, further comprising:

moving the sliding window relative to the data segment by an amount that is based on the predetermined block size before performing the next iteration in response to determining that the output of the block alignment function performed on the data within the sliding window satisfies the predetermined criteria; and

moving the sliding window relative to the data segment by an incremental amount in response to determining that the output of the block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria.

19. The method of claim 18, further comprising iteratively performing the block alignment function across at least a portion of the data segment again in response to changing the predetermined criteria.

20. The method of claim 17, further comprising changing the predetermined criteria in response to determining, for a threshold number of consecutive iterations, that the output of the block alignment function performed on the data within the sliding window does not satisfy the predetermined criteria.

21. The method of claim 17, further comprising:

in response to determining for a threshold number of consecutive iterations that the output of the block alignment function performed on the current window of data does not satisfy the predetermined criteria;

establishing a deduplication data block; and

moving the sliding window relative to the data segment by an incremental amount.

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

a deduplication block alignment module executing in one or more processors and configured to iteratively perform a deduplication block alignment function on data within a sliding window in a data segment and which, for each iterative performance of the block alignment function, is configured to;

in response to a determination that the output of the block alignment function performed on a current window of data satisfies a predetermined criteria;

establish a deduplication block having a predetermined block size, and

move the sliding window relative to the data segment by an amount based on the predetermined block size before a next iterative performance of the block alignment function; and

in response to a determination that the output of the block alignment function performed on the current window of data does not satisfy the predetermined criteria;

move the sliding window relative to the data segment by a predetermined incremental amount that is different from the predetermined block size before the next iterative performance of the block alignment function and without establishing a deduplication data block,

wherein gaps of data not belonging to any deduplication data block exist between at least some established deduplication data blocks following performance of the block alignment function across the data segment, and

wherein the size of the gaps of data is based at least on a number of successive outputs of the block alignment function that do not satisfy the predetermined criteria.