EFFICIENT CONSTRUCTION OF SYNTHETIC BACKUPS WITHIN DEDUPLICATION STORAGE SYSTEM

• US 20120143835A1
• Filed: 12/01/2010
• Published: 06/07/2012
• Est. Priority Date: 12/01/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ARONOVICH, Lior, HIRSCH, Michael, TOAFF, Yair
• Granted Patent: US 8,682,873 B2
• Time in Patent Office: Days
• US Class Current: 707/696
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• 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/2255 Hash tables
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

Various embodiments are provided for facilitating construction of a synthetic backup in a deduplication storage system. In one embodiment, a deduplication storage system enables new input data to be deduplicated with data of synthetic backups already constructed, and for this purpose efficiently calculates deduplication digests for synthetic backups being constructed, based on already existing digests of data referenced by the synthetic backups. For each input data segment of the plurality of input data segments of a synthetic backup being constructed, a plurality of deduplication digests of stored data segments, referenced by the input data segment, is retrieved from an index. Each input data segment is partitioned into each of a plurality of fixed-sized data sub-segments. A calculation is performed producing a deduplication digest for a data sub-segment, where the calculation is based on the retrieved deduplication digests of the plurality of stored data sub-segments referenced by the input data sub-segment.

Claims

1. For a plurality of input data segments in a deduplication storage system, a method of facilitating construction of a synthetic backup by a processor device, comprising:

for each input data segment of the plurality of input data segments, retrieving a plurality of stored deduplication digests of stored data segments, referenced by the input data segments;

partitioning each input data segment into each of a plurality of fixed-sized data sub-segments;

for each of the plurality of data sub-segments, calculating each of a plurality of input deduplication digests based on the retrieved plurality of stored deduplication digests; and

aggregating each of the plurality of sub-segment deduplication digests to generate a deduplication digest of each input data segment, wherein the deduplication digests of each input data segment form a deduplication digest of the synthetic backup.

2. The method of claim 1, further including deduplicating each input data segment by matching the plurality of the stored deduplication digests of the stored data segments against the plurality of input deduplication digests.

3. The method of claim 2, further including subsequent to the matching, storing the plurality of input deduplication digests in the index, wherein at least one stored deduplication digest of the plurality of stored deduplication digests matched with at least one input deduplication digest of the plurality of input deduplication digests may be displaced by the at least one input deduplication digest.

4. The method of claim 1, further including constructing the synthetic backup.

5. The method of claim 4, wherein constructing the synthetic backup further includes performing at least one of:

creating a metadata file in the deduplicated storage system, and

optimizing successive storage instructions.

6. The method of claim 5, further including, for each optimized storage instruction, performing at least one of:

retrieving a metadata segment associated with an input data segment indicated by the optimized storage instruction,

adjusting the metadata segment to reference solely the input data segment,

copying the adjusted metadata segment to the metadata file of the synthetic backup, and

for each storage block referenced by the metadata segment, incrementing a reference count value.

7. The method of claim 1, wherein calculating each of a plurality of sub-segment deduplication digests includes performing at least one of:

calculating a hash value for each block in the plurality of input data segments in byte offsets,

arranging a selected plurality of maximal hash values in descending order according to an order of significance,

identifying blocks in determined positions relative to the blocks associated with the maximal hash values as shifted blocks, and

selecting a subset of the hash values of the shifted blocks for at least one first distinguishing characteristic of the plurality of input data sub-segments, and

selecting an additional subset of the hash values of the shifted blocks, for at least one second distinguishing characteristic of the plurality of input data segments.

8. The method of claim 7, further including configuring a distinguishing characteristics (DC) index for the plurality of input data segments for storing the at least one second distinguishing characteristic, and configuring a storage identifiers (SI) index for the plurality of input data sub-segments for storing the at least one first distinguishing characteristic.

9. The method of claim 8, further including calculating the at least one first and second distinguishing characteristics.

10. A system, for a plurality of input data segments in a deduplication storage system, for facilitating construction of a synthetic backup, comprising:

at least one processor device, operable in the deduplication computing storage environment, wherein the at least one processor device is adapted for;

for each input data segment of the plurality of input data segments, retrieving a plurality of stored deduplication digests of stored data segments, referenced by the input data segments,

partitioning each input data segment into each of a plurality of fixed-sized data sub-segments,

for each of the plurality of data sub-segments, calculating each of a plurality of input deduplication digests based on the retrieved plurality of stored deduplication digests, and

aggregating each of the plurality of sub-segment deduplication digests to generate a deduplication digest of each input data segment, wherein the deduplication digests of each input data segment form a deduplication digest of the synthetic backup.

11. The system of claim 10, wherein the at least one processor device is further adapted for deduplicating each input data segment by matching the plurality of the stored deduplication digests of the stored data segments against the plurality of input deduplication digests.

12. The system of claim 11, wherein the at least one processor device is further adapted for, subsequent to the matching, storing the plurality of input deduplication digests in the index, wherein at least one stored deduplication digest of the plurality of stored deduplication digests matched with at least one input deduplication digest of the plurality of input deduplication digests may be displaced by the at least one input deduplication digest.

13. The system of claim 10, wherein the at least one processor device is further adapted for constructing the synthetic backup.

14. The system of claim 13, wherein the at least one processor device is further adapted for, pursuant to constructing the synthetic backup, performing at least one of:

creating a metadata file in the deduplicated storage system, and

optimizing successive storage instructions.

15. The system of claim 14, wherein the at least one processor device is further adapted for, for each optimized storage instruction, performing at least one of:

retrieving a metadata segment associated with an input data segment indicated by the optimized storage instruction,

adjusting the metadata segment to reference solely the input data segment,

copying the adjusted metadata segment to the metadata file of the synthetic backup, and

for each storage block referenced by the metadata segment, incrementing a reference count value.

16. The system of claim 10, wherein the at least one processor device is further adapted for, pursuant to calculating each of a plurality of sub-segment deduplication digests, performing at least one of:

calculating a hash value for each block in the plurality of input data segments in byte offsets,

arranging a selected plurality of maximal hash values in descending order according to an order of significance,

identifying blocks in determined positions relative to the blocks associated with the maximal hash values as shifted blocks, and

selecting a subset of the hash values of the shifted blocks for at least one first distinguishing characteristic of the plurality of input data sub-segments, and

selecting an additional subset of the hash values of the shifted blocks, for at least one second distinguishing characteristic of the plurality of input data segments.

17. The system of claim 16, wherein the at least one processor device is further adapted for configuring a distinguishing characteristics (DC) index for the plurality of input data segments for storing the at least one second distinguishing characteristic, and configuring a storage identifiers (SI) index for the plurality of input data sub-segments for storing the at least one first distinguishing characteristic.

18. The system of claim 17, wherein the at least one processor device is further adapted for calculating the at least one first and second distinguishing characteristics.

19. A computer program product, for a plurality of input data segments in a deduplication storage system, for facilitating construction of a synthetic backup by at least one processor device, the computer program product comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion for, for each input data segment of the plurality of input data segments, retrieving a plurality of stored deduplication digests of stored data segments, referenced by the input data segments;

a second executable portion for partitioning each input data segment into each of a plurality of fixed-sized data sub-segments;

a third executable portion for, for each of the plurality of data sub-segments, calculating each of a plurality of input deduplication digests based on the retrieved plurality of stored deduplication digests; and

a fourth executable portion for aggregating each of the plurality of sub-segment deduplication digests to generate a deduplication digest of each input data segment, wherein the deduplication digests of each input data segment form a deduplication digest of the synthetic backup.

20. The computer program product of claim 19, further including a fifth executable portion for deduplicating each input data segment by matching the plurality of the stored deduplication digests of the stored data segments against the plurality of input deduplication digests.

21. The computer program product of claim 20, further including a sixth executable portion for, subsequent to the matching, storing the plurality of input deduplication digests in the index, wherein at least one stored deduplication digest of the plurality of stored deduplication digests matched with at least one input deduplication digest of the plurality of input deduplication digests may be displaced by the at least one input deduplication digest.

22. The computer program product of claim 19, further including a fifth executable portion for constructing the synthetic backup.

23. The computer program product of claim 22, further including a sixth executable portion for, pursuant to constructing the synthetic backup, performing at least one of:

creating a metadata file in the deduplicated storage system, and

optimizing successive storage instructions.

24. The computer program product of claim 23, further including a seventh executable portion for, for each optimized storage instruction, performing at least one of:

retrieving a metadata segment associated with an input data segment indicated by the optimized storage instruction,

adjusting the metadata segment to reference solely the input data segment,

copying the adjusted metadata segment to the metadata file of the synthetic backup, and

for each storage block referenced by the metadata segment, incrementing a reference count value.

25. The computer program product of claim 19, further including a fifth executable portion for, pursuant to calculating each of a plurality of sub-segment deduplication digests, performing at least one of:

calculating a hash value for each block in the plurality of input data segments in byte offsets,

arranging a selected plurality of maximal hash values in descending order according to an order of significance,

identifying blocks in determined positions relative to the blocks associated with the maximal hash values as shifted blocks, and

selecting a subset of the hash values of the shifted blocks for at least one first distinguishing characteristic of the plurality of input data sub-segments, and

selecting an additional subset of the hash values of the shifted blocks, for at least one second distinguishing characteristic of the plurality of input data segments.

26. The computer program product of claim 25, further including a sixth executable portion for configuring a distinguishing characteristics (DC) index for the plurality of input data segments for storing the at least one second distinguishing characteristic, and configuring a storage identifiers (SI) index for the plurality of input data sub-segments for storing the at least one first distinguishing characteristic.

27. The computer program product of claim 26, further including a seventh executable portion for calculating the at least one first and second distinguishing characteristics.