Content aligned block-based deduplication

• US 9,898,225 B2
• Filed: 03/03/2017
• Issued: 02/20/2018
• 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:
  US15/449,246
• Publication Number:
  US 20170177271A1
• Time in Patent Office: 354 Days
• Field of Search: None
• 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 system configured to perform block-aligned deduplication, the system comprising:

a storage manager implemented in computer hardware and comprising one or more hardware processors, the storage manager configured to;

position a window with respect to a data segment, the data segment comprising a set of blocks, the window comprising a first plurality of blocks from the set of blocks, the first plurality of blocks less than the set of blocks, the window corresponding in size to a deduplication block size;

perform a block alignment function on the first plurality of blocks;

in response to determining that a result of the block alignment function satisfies a set of criteria;

designate the first plurality of blocks as a deduplication block; and

move the window of the data segment with respect to the data segment by an amount equal to the deduplication block size, wherein the moved window comprises a second plurality of blocks, the second plurality of blocks differing in its entirety from the first plurality of blocks; and

in response to determining that the result of the block alignment function does not satisfy the set of criteria;

move the window of the data segment with respect to the data segment by an amount less than the deduplication block size, wherein the moved window comprises a third plurality of blocks, the third plurality of blocks partially overlapping with the first plurality of blocks; and

perform the block alignment function on the third plurality of blocks.

2. The system of claim 1, wherein at least one block from the set of blocks exists between a first deduplication block and a second deduplication block, the at least one block not part of a deduplication block.

3. The system of claim 1, wherein a third deduplication block and a fourth deduplication block are adjacent without a block from the set of blocks existing between the third deduplication block and the fourth deduplication block.

4. The system of claim 1, wherein the block alignment function comprises a hash function.

5. The system of claim 4, wherein the set of criteria comprises a set of hash values.

6. The system of claim 1, wherein, in response to determining that the result of the block alignment function does not satisfy the set of criteria, the storage manager is further configured to:

determine a count of results of the block alignment function that do not satisfy the set of criteria;

determine whether the count satisfies a threshold; and

in response to the count satisfying the threshold, modify the set of criteria.

7. The system of claim 6, wherein the count is a count of consecutive iterations of performance of the block alignment function that do not satisfy the set of criteria.

8. The system of claim 6, wherein, upon modifying the set of criteria, the storage manager is further configured to:

reset a position of the window to a start of the data segment; and

repeat performance of the block alignment function on the first plurality of blocks using the modified set of criteria.

9. The system of claim 6, wherein, upon modifying the set of criteria, the storage manager is further configured to perform the block alignment function on blocks of the data segment without repeating performance of the block alignment function on the first plurality of blocks.

10. The system of claim 6, wherein modifying the set of criteria comprises modifying the block alignment function.

11. The system of claim 1, wherein, when moving the window of the data segment with respect to the data segment by the amount less than the deduplication block size, a non-overlapping portion of the first plurality of blocks is not associated with the deduplication block.

12. A computer-implemented method of performing block-aligned deduplication comprising:

as implemented by a storage manager comprising one or more hardware processor and configured with specific computer-executable instructions,

positioning a window with respect to a data segment, the data segment comprising a set of blocks, the window comprising a first plurality of blocks from the set of blocks, the first plurality of blocks less than the set of blocks, the window corresponding in size to a deduplication block size;

performing a block alignment function on the first plurality of blocks;

in response to determining that a result of the block alignment function satisfies a set of criteria;

designating the first plurality of blocks as a deduplication block; and

moving the window of the data segment with respect to the data segment by an amount equal to the deduplication block size, wherein the moved window comprises a second plurality of blocks, the second plurality of blocks differing in its entirety from the first plurality of blocks; and

in response to determining that the result of the block alignment function does not satisfy the set of criteria;

moving the window of the data segment with respect to the data segment by an amount less than the deduplication block size, wherein the moved window comprises a third plurality of blocks, the third plurality of blocks partially overlapping with the first plurality of blocks; and

performing the block alignment function on the third plurality of blocks.

13. The computer-implemented method of claim 12, wherein at least some deduplication blocks identified in the data segment are separated by one or more blocks from the set of blocks.

14. The computer-implemented method of claim 12, wherein the block alignment function comprises a hash function.

15. The computer-implemented method of claim 14, wherein the set of criteria comprises a set of hash values.

16. The computer-implemented method of claim 12, wherein, in response to determining that the result of the block alignment function does not satisfy the set of criteria, the method further comprises:

determining a count of results of the block alignment function that do not satisfy the set of criteria;

determining whether the count satisfies a threshold; and

in response to the count satisfying the threshold, modifying the set of criteria.

17. The computer-implemented method of claim 16, wherein the count is a count of consecutive iterations of performance of the block alignment function that do not satisfy the set of criteria.

18. The computer-implemented method of claim 16, wherein, upon modifying the set of criteria, the method further comprises:

resetting a position of the window to a start of the data segment; and

repeating performance of the block alignment function on the first plurality of blocks using the modified set of criteria.

19. The computer-implemented method of claim 16, wherein, upon modifying the set of criteria, the method further comprises performing the block alignment function on blocks of the data segment without repeating performance of the block alignment function on the first plurality of blocks.

20. The computer-implemented method of claim 16, wherein modifying the set of criteria comprises modifying the block alignment function.