# US 2012/0239625 A1 · Efficient construction of synthetic backups within deduplication storage system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0239625 A1
- Document ID: US20120239625A1
- Status: Published application
- Kind: A1
- Application number: 13/488,180
- Filed: 2012-06-04
- Published: 2012-09-20
- Earliest claimed: 2010-12-01
- Assignees: International Business Machines Corporation
- Inventors: Lior ARONOVICH; Michael HIRSCH; Yair TOAFF
- Web page: https://patentgrep.com/patent/US20120239625A1

## CPC

- 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)}
- G06F 11/1453: {using de-duplication of the data}
- G06F 16/2255: {Hash tables}
- G06F 16/24556: {Aggregation; Duplicate elimination}
- G06F 16/907: Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 8)

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