Efficient construction of synthetic backups within deduplication storage system

• US 8,682,873 B2
• Filed: 12/01/2010
• Issued: 03/25/2014
• 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
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): BUCKINGHAM, KELLYE DEE
• Application Number:
  US12/958,205
• Publication Number:
  US 20120143835A1
• Time in Patent Office: 1,210 Days
• Field of Search: None
• 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

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. A system, for a plurality of new input data segments in a deduplication storage system, for facilitating construction of a synthetic backup, the synthetic backup being independent of and constructed from an originating backup being a full, existing backup, the system comprising:

a memory; and

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

for each new input data segment of the plurality of new input data segments, retrieving a plurality of stored deduplication digests of stored data segments, referenced by the new input data segments, the stored data segments being data taken from the originating backup, and the plurality of stored deduplication digests being deduplication digests calculated from the stored data segments,

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

for each of the plurality of data sub-segments, during the construction of the synthetic backup, calculating each of a plurality of input deduplication digests based on the retrieved plurality of stored deduplication digests,

aggregating each of the plurality of sub-segment deduplication digests to generate a deduplication digest of each new input data segment,

searching the plurality of stored deduplication digests of the stored data segments for matches with the deduplication digest of each new input data segment to thereby deduplicate each new input data segment, and

forming a deduplication digest of the synthetic backup from the deduplication digests of each new input data segment.

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

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

creating a metadata file in the deduplicated storage system, and

optimizing successive storage instructions.

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

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

adjusting the metadata segment to reference solely the new 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.

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

calculating a hash value for each block in the plurality of new 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,

selecting a subset of the hash values of the shifted blocks for a 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 a second distinguishing characteristic of the plurality of new input data segments.

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

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

8. A computer program product, for a plurality of new input data segments in a deduplication storage system, for facilitating construction of a synthetic backup by at least one processor device, the synthetic backup being independent of and constructed from an originating backup being a full, existing backup, the computer program product comprising a non-transitory 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 new input data segment of the plurality of new input data segments, retrieving a plurality of stored deduplication digests of stored data segments, referenced by the new input data segments, the stored data segments being data taken from the originating backup, and the plurality of stored deduplication digests being deduplication digests calculated from the stored data segments;

a second executable portion for partitioning each new 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, during the construction of the synthetic backup, calculating each of a plurality of input deduplication digests based on the retrieved plurality of stored deduplication digests;

a fourth executable portion for aggregating each of the plurality of sub-segment deduplication digests to generate a deduplication digest of each new input data segment;

a fifth executable portion for searching the plurality of stored deduplication digests of the stored data segments for matches with the deduplication digest of each new input data segment to thereby deduplicate each new input data segment; and

a sixth executable portion for forming a deduplication digest of the synthetic backup from the deduplication digests of each new input data segment.

9. The computer program product of claim 8, further including a seventh executable portion for, subsequent to the searching, storing the plurality of input deduplication digests in the index, wherein a stored deduplication digest of the plurality of stored deduplication digests matched with an input deduplication digest of the plurality of input deduplication digests may be displaced by the input deduplication digest.

10. The computer program product of claim 8, further including a seventh executable portion for, pursuant to constructing the synthetic backup:

creating a metadata file in the deduplicated storage system, and

optimizing successive storage instructions.

11. The computer program product of claim 10, further including an eighth executable portion for, for each optimized storage instruction:

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

adjusting the metadata segment to reference solely the new 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.

12. The computer program product of claim 8, further including a seventh executable portion for, pursuant to calculating each of a plurality of sub-segment deduplication digests:

calculating a hash value for each block in the plurality of new 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,

selecting a subset of the hash values of the shifted blocks for a 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 a second distinguishing characteristic of the plurality of new input data segments.

13. The computer program product of claim 12, further including an eighth executable portion for configuring a distinguishing characteristics (DC) index for the plurality of new input data segments for storing the second distinguishing characteristic, and configuring a storage identifiers (SI) index for the plurality of input data sub-segments for storing the first distinguishing characteristic.

14. The computer program product of claim 13, further including a ninth executable portion for calculating the first and second distinguishing characteristics.