Deduplicating input backup data with data of a synthetic backup previously constructed by a deduplication storage system

• US 9,858,286 B2
• Filed: 03/13/2013
• Issued: 01/02/2018
• 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): Singh, Amresh
• Application Number:
  US13/801,774
• Publication Number:
  US 20130232120A1
• Time in Patent Office: 1,756 Days
• Field of Search: None
• 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

Input backup data is deduplicated with data of a synthetic backup previously constructed by a deduplication storage system. A synthetic backup is constructed by processing metadata instructions provided by a backup application. Deduplication digests are calculated based on the data of the synthetic backup and the deduplication digests are stored in a digests index. When new backup data is processed, deduplication digests of the new data are calculated and searched in the digests index. Matching digests of previously constructed synthetic backups are located in the digests index. Each of the located matching digest references stored data are included in the synthetic backup, and the stored data is similar to the input backup data. Data matches are found in the input backup data and data in the synthetic backup.

Claims

1. A method for deduplicating input backup data with data of a synthetic backup previously constructed by a deduplication storage system using a processor device, comprising:

constructing the synthetic backup by processing a plurality of metadata instructions provided by a backup application, the synthetic backup to be independent of referenced stored backups;

processing each of the plurality of metadata instructions by each of;

partitioning each data segment input into each of a plurality of fixed-sized data sub-segments, each sub-segment referencing a plurality of stored 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 a retrieved plurality of stored deduplication digests by aggregating calculated deduplication digests of the plurality of data sub-segments to produce a respective one of the plurality of input deduplication digests for each data segment input,

locating those of the plurality of data sub-segments in the deduplication storage system specified by the data segment in each of the plurality of metadata instructions, and

creating metadata references to each of the plurality of data sub-segments and adding the metadata references to metadata of the synthetic backup being created;

wherein the metadata references include physical and logical data patterns;

transforming a set of the plurality of metadata instructions into a transformed set of the plurality of metadata instructions;

creating the synthetic backup by the deduplication system and the backup application by consolidating the plurality of metadata instructions that reference adjacent backup data segments into a single metadata instruction;

wherein the synthetic backup includes data from an existing full backup and subsequent incremental backups of the existing full backup dating until a specific point in time;

calculating deduplication digests based on the data of the synthetic backup;

storing the deduplication digests in a digests index;

calculating and searching, in the digests index, the deduplication digests of new data when new backup data is processed;

locating matching digests of previously constructed synthetic backups in the digests index, wherein each of the located matching digest references stored data included in the synthetic backup, and the stored data is similar to the input backup data; and

finding data matches in the input backup data and data in the synthetic backup.

2. The method of claim 1, further including specifying, by each one of the plurality of metadata instructions provided by the backup application, a data segment of an originating backup and a designated location of the data segment in the synthetic backup being created.

3. The method of claim 1, further including processing each of the plurality of metadata instructions by each of:

locating the stored data in the deduplication storage system specified by a data segment in the plurality of metadata instructions, and

adding references to the stored data to metadata of the synthetic backup being created.

4. The method of claim 1, further including selecting maximal hash values out of a set of rolling hash values calculated on the data of the synthetic backup for calculating the deduplication digests.

5. The method of claim 1, further including providing matching digests stored in the digests index, wherein the digests index enables searching for a digest value.

6. The method of claim 1, further including finding the data matches in the input backup data and the data in the synthetic backup using a binary differencing procedure.

7. The method of claim 1, further including allowing the synthetic backup to be available upon a deletion of stored backups whose data was referenced for creating the synthetic backup.

8. A system for deduplicating input backup data with data of a synthetic backup previously constructed by a deduplication storage system, comprising:

the deduplication storage system;

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

constructs the synthetic backup by processing a plurality of metadata instructions provided by a backup application, the synthetic backup to be independent of referenced stored backups,

processes each of the plurality of metadata instructions by each of;

partitioning each data segment input into each of a plurality of fixed-sized data sub-segments, each sub-segment referencing a plurality of stored 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 a retrieved plurality of stored deduplication digests by aggregating calculated deduplication digests of the plurality of data sub-segments to produce a respective one of the plurality of input deduplication digests for each data segment input,

locating those of the plurality of data sub-segments in the deduplication storage system specified by the data segment in each of the plurality of metadata instructions, and

creating metadata references to each of the plurality of data sub-segments and adding the metadata references to metadata of the synthetic backup being created;

wherein the metadata references include physical and logical data patterns,

transforms a set of the plurality of metadata instructions into a transformed set of the plurality of metadata instructions,

creates the synthetic backup by the deduplication system and the backup application by consolidating the plurality of metadata instructions that reference adjacent backup data segments into a single metadata instruction;

wherein the synthetic backup includes data from an existing full backup and subsequent incremental backups of the existing full backup dating until a specific point in time,

calculates deduplication digests based on the data of the synthetic backup,

storing the deduplication digests in a digests index,

calculates and searches, in the digests index, the deduplication digests of new data when new backup data is processed,

locates matching digests of previously constructed synthetic backups in the digests index, wherein each of the located matching digest references stored data included in the synthetic backup, and the stored data is similar to the input backup data, and

finds data matches in the input backup data and data in the synthetic backup.

9. The system of claim 8, wherein the at least one processor device specifies, by each one of the plurality of metadata instructions provided by the backup application, a data segment of an originating backup and a designated location of the data segment in the synthetic backup being created.

10. The system of claim 8, wherein the at least one processor device processes each of the plurality of metadata instructions by each of:

locating the stored data in the deduplication storage system specified by a data segment in the plurality of metadata instructions, and

adding references to the stored data to metadata of the synthetic backup being created.

11. The system of claim 8, wherein the at least one processor device selects maximal hash values out of a set of rolling hash values calculated on the data of the synthetic backup for calculating the deduplication digests.

12. The system of claim 8, wherein the at least one processor device provides matching digests stored in the digests index, wherein the digests index enables searching for a digest value.

13. The system of claim 8, wherein the at least one processor device finds the data matches in the input backup data and the data in the synthetic backup using a binary differencing procedure.

14. The system of claim 8, wherein the at least one processor device allows the synthetic backup to be available upon a deletion of stored backups whose data was referenced for creating the synthetic backup.

15. A computer program product for deduplicating input backup data with data of a synthetic backup previously constructed by a deduplication storage system using at least one processor device, 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:

an executable portion that constructs the synthetic backup by processing a plurality of metadata instructions provided by a backup application, the synthetic backup to be independent of referenced stored backups;

an executable portion that processes each of the plurality of metadata instructions by each of;

partitioning each data segment input into each of a plurality of fixed-sized data sub-segments, each sub-segment referencing a plurality of stored 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 a retrieved plurality of stored deduplication digests by aggregating calculated deduplication digests of the plurality of data sub-segments to produce a respective one of the plurality of input deduplication digests for each data segment input,

locating those of the plurality of data sub-segments in the deduplication storage system specified by the data segment in each of the plurality of metadata instructions, and

creating metadata references to each of the plurality of data sub-segments and adding the metadata references to metadata of the synthetic backup being created;

wherein the metadata references include physical and logical data patterns;

an executable portion that transforms a set of the plurality of metadata instructions into a transformed set of the plurality of metadata instructions;

an executable portion that creates the synthetic backup by the deduplication system and the backup application by consolidating the plurality of metadata instructions that reference adjacent backup data segments into a single metadata instruction;

wherein the synthetic backup includes data from an existing full backup and subsequent incremental backups of the existing full backup dating until a specific point in time;

an executable portion that calculates deduplication digests based on the data of the synthetic backup;

an executable portion that stores the deduplication digests in a digests index;

an executable portion that calculates and searches, in the digests index, the deduplication digests of new data when new backup data is processed;

an executable portion that locates matching digests of previously constructed synthetic backups in the digests index, wherein each of the located matching digest references stored data included in the synthetic backup, and the stored data is similar to the input backup data; and

an executable portion that finds data matches in the input backup data and data in the synthetic backup.

16. The computer program product of claim 15, further including an executable portion that specifies, by each one of the plurality of metadata instructions provided by the backup application, a data segment of an originating backup and a designated location of the data segment in the synthetic backup being created.

17. The computer program product of claim 15, further including an executable portion that processes each of the plurality of metadata instructions by each of:

locating the stored data in the deduplication storage system specified by a data segment in the plurality of metadata instructions, and

adding references to the stored data to metadata of the synthetic backup being created.

18. The computer program product of claim 15, further including an executable portion that selects maximal hash values out of a set of rolling hash values calculated on the data of the synthetic backup for calculating the deduplication digests.

19. The computer program product of claim 15, further including an executable portion that provides matching digests stored in the digests index, wherein the digests index enables searching for a digest value.

20. The computer program product of claim 15, further including an executable portion that finds the data matches in the input backup data and the data in the synthetic backup using a binary differencing procedure.

21. The computer program product of claim 15, further including an executable portion that allows the synthetic backup to be available upon a deletion of stored backups whose data was referenced for creating the synthetic backup.