Method and system for data backup

• US 10,055,310 B2
• Filed: 08/28/2014
• Issued: 08/21/2018
• Est. Priority Date: 07/30/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Li, Ya J., Li, Yu M., Sisco, Michael G., Xiong, Yin X.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US14/471,183
• Publication Number:
  US 20140372379A1
• Time in Patent Office: 1,454 Days
• Field of Search: 707646
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

The present invention relates to a method, system, and computer program product for data backup, the method comprising: performing first chunking on current data by using the same chunking method as that used by original backup data to obtain a current chunk; calculating hash value of the current chunk; and acquiring, from a hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk, and incrementing number of continuous matched chunks by one. Since the pertinence between original backup data and current data is maximally utilized, performance of de-duplication method can be efficiently improved.

Claims

1. A computer system for data backup, the system comprising:

one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage devices, and program instructions stored on at least one of the one or more storage devices for execution by at least one of the one or more processors via at least one of the one or more memories, the program instructions, when executed by the at least one of the one or more of the processors, cause the at least one of the one or more of the processors to perform a method comprising;

receiving, from one of the one or more computer-readable tangible storage devices, original backup data;

receiving, from one of the one or more computer-readable tangible storage devices, current backup data;

performing first chunking on the current data by using the same chunking method as that used on the original backup data to obtain a current chunk, wherein the original backup data is a chunking data that is defined by content;

calculating a hash value of the current chunk, wherein a determination of whether a number of continuous matched chunks exceeds a threshold is determined, based on the calculated hash value, and wherein the threshold is a preset value, if a number of continuous matched chunks exceeds the preset threshold, a time for chunking the data is saved, and, wherein, then data blocks of the current chunk of data is equal to a matched block of the original backup data;

in response to a number of continuous matched chunks exceeding the threshold, the length of a data block that corresponds to an identifier of a next chunk of the matched chunk is acquired;

acquiring from a hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk, and incrementing a number of continuous matched chunks, based on the exceeded threshold; and

clearing the number of continuous matched chunks, whereby, the hash value table of the original backup data, and the identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk are returned in response to the number of continuous matched chunks exceeding the threshold; and

backing up remaining data after clearing the continuous matched chunks to one of the one or more computer-readable tangible storage devices.

2. The computer system according to claim 1, further comprising:

in response to not exceeding the threshold, continuing to perform second chunking on the current data by using the same chunking method as that used by the original backup data to obtain a new current chunk data; and

calculating a hash value of the new current chunk.

3. The computer system according to claim 2, further comprising:

acquiring a hash value of a next chunk of the matched chunk from the hash value table of the original backup data;

comparing the hash value of the new current chunk with the hash value of the next chunk of the matched chunk;

in response to the hash value of the new current chunk being the same as the hash value of the next chunk of the matched chunk;

incrementing a number of continuous matched chunks;

taking the next chunk of the matched chunk as a new matched chunk; and

returning to the step of determining whether the number of continuous matched chunks exceeds a threshold;

in response to the hash value of the new current chunk being different from the hash value of the next chunk of the matched chunk;

clearing the number of continuous matched chunks; and

returning to the step of acquiring, from the hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk.

4. The computer system according to claim 1, further comprising:

determining whether the number of continuous matched chunks exceeds a threshold, and in response to exceeding the threshold, acquiring a length of a data block corresponding to an identifier of a next chunk of the matched chunk.

5. The method according to claim 4, further comprising:

continuing to perform a third chunking on the current data by using the acquired length of a data block corresponding to an identifier of a next chunk of the matched chunk to obtain a new current chunk;

calculating a hash value of the new current chunk;

acquiring a hash value of the next chunk of the matched chunk from the hash value table of the original backup data;

comparing the hash value of the new current chunk with the hash value of the next chunk of the matched chunk;

in response to the hash value of the new current chunk being the same as the hash value of the next chunk of the matched chunk;

taking the next chunk of the matched chunk as a new matched chunk; and

returning to the step of acquiring an identifier of the next chunk of the matched chunk from a hash value table of the original backup data;

in response to the hash value of the new current chunk being different from the hash value of the next chunk of the matched chunk;

clearing the number of continuous matched chunks; and

returning to the step of acquiring, from a hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk.

6. A computer program product for data backup, computer program product comprising:

one or more non-transitory computer-readable tangible storage devices and program instructions stored on at least one of the one or more non-transitory computer-readable tangible storage devices, the program instructions executable to perform a method comprising;

receiving, from one of the one or more computer-readable tangible storage devices, original backup data;

receiving, from one of the one or more computer-readable tangible storage devices, current backup data;

performing first chunking on the current data by using the same chunking method as that used on the original backup data to obtain a current chunk, wherein the original backup data is a chunking data that is defined by content;

calculating a hash value of the current chunk, wherein a determination of whether a number of continuous matched chunks exceeds a threshold is determined, based on the calculated the hash value, and wherein the threshold is a preset value, if a number of continuous matched chunks exceeds the preset threshold, a time for chunking the data is saved, and, wherein, then data blocks of the current chunk of data is equal to a matched block of the original backup data;

in response to a number of continuous matched chunks exceeding the threshold, the length of a data block that corresponds to an identifier of a next chunk of the matched chunk is acquired;

acquiring from a hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk, and incrementing a number of continuous matched chunks based on the exceeded threshold; and

clearing the number of continuous matched chunks, whereby, the hash value table of the original backup data, and the identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk are returned in response to the number of continuous matched chunks exceeding the threshold; and

backing up remaining data after clearing the continuous matched chunks to one of the one or more computer-readable tangible storage devices.

7. The computer program product according to claim 6, wherein the method further comprises:

in response to not exceeding the threshold, continuing to perform second chunking on the current data by using the same chunking method as that used by the original backup data to obtain a new current chunk; and

calculating a hash value of the new current chunk.

8. The computer program product according to claim 7, wherein the method further comprises:

acquiring a hash value of a next chunk of the matched chunk from the hash value table of the original backup data;

comparing the hash value of the new current chunk with the hash value of the next chunk of the matched chunk;

in response to the hash value of the new current chunk being the same as the hash value of the next chunk of the matched chunk;

incrementing a number of continuous matched chunks;

taking the next chunk of the matched chunk as a new matched chunk; and

returning to the step of determining whether the number of continuous matched chunks exceeds a threshold;

in response to the hash value of the new current chunk being different from the hash value of the next chunk of the matched chunk;

clearing the number of continuous matched chunks; and

returning to the step of acquiring, from the hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk.

9. The computer program product according to claim 6, wherein the method further comprises:

determining whether the number of continuous matched chunks exceeds a threshold, and in response to exceeding the threshold, acquiring a length of a data block corresponding to an identifier of a next chunk of the matched chunk.

10. The computer program product according to claim 9, wherein the method further comprises:

continuing to perform a third chunking on the current data by using the acquired length of a data block corresponding to an identifier of a next chunk of the matched chunk to obtain a new current chunk;

calculating a hash value of the new current chunk;

acquiring a hash value of the next chunk of the matched chunk from the hash value table of the original backup data;

comparing the hash value of the new current chunk with the hash value of the next chunk of the matched chunk;

in response to the hash value of the new current chunk being the same as the hash value of the next chunk of the matched chunk;

taking the next chunk of the matched chunk as a new matched chunk; and

returning to the step of acquiring an identifier of the next chunk of the matched chunk from a hash value table of the original backup data;

in response to the hash value of the new current chunk being different from the hash value of the next chunk of the matched chunk;

clearing the number of continuous matched chunks; and

returning to the step of acquiring, from a hash value table of the original backup data, an identifier of a matched chunk whose hash value is the same as the calculated hash value of the current chunk.