METHOD AND SYSTEM FOR DATA BACKUP

• US 20140032499A1
• Filed: 06/04/2013
• Published: 01/30/2014
• Est. Priority Date: 07/30/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sisco, Michael G., Li, Ya J., Li, Yu M., Xiong, Yin X.
• Granted Patent: US 9,465,699 B2
• Time in Patent Office: Days
• US Class Current: 707/646
• 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 method for data backup, wherein, there is original backup data and current data to be backed up, the method comprising:

performing first chunking on the current data by using the same chunking method as that used by the 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.

2. The method according to claim 1, further comprising:

determining whether the number of continuous matched chunks exceeds a threshold, and 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 hash value of the new current chunk.

3. The method according to claim 2, further comprising:

acquiring 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 number of continuous matched chunks by one;

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

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

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

determining whether the number of continuous matched chunks exceeds a threshold, and in response to exceeding the threshold; and

acquiring 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 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 hash value of the new current chunk;

acquiring hash value of the next chunk of the matched chunk from a 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;

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 system for data backup, wherein, there is original backup data and current data to be backed up, the system comprising:

a chunking unit configured to perform first chunking on the current data by using the same chunking method as that used by the original backup data to obtain a current chunk;

a calculating unit configured to calculate hash value of the current chunk; and

an acquiring unit configured to acquire, 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 to increment number of continuous matched chunks by one.

7. The system according to claim 6, further comprising:

a determining unit configured to determine whether the number of continuous matched chunks exceeds a threshold, and in response to not exceeding the threshold;

the chunking unit is further configured to continue 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

the calculating unit is further configured to calculate hash value of the new current chunk.

8. The system according to claim 7, further comprising:

the acquiring unit is further configured to acquire hash value of a next chunk of the matched chunk from the hash value table of the original backup data;

a comparing unit configured to compare 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, the system is further configured to;

increment number of continuous matched chunks by one;

take the next chunk of the matched chunk as a new matched chunk;

return to determine 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, the system is further configured to;

clear the number of continuous matched chunks; and

return to acquire, 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.

9. The system according to claim 6, further comprising:

a determining unit configured to determine whether the number of continuous matched chunks exceeds a threshold, and in response to exceeding the threshold; and

the acquiring unit is further configured to acquire length of a data block corresponding to an identifier of a next chunk of the matched chunk.

10. The system according to claim 9, further comprising:

the chunking unit is further configured to continue to perform 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;

the calculating unit is further configured to calculate hash value of the new current chunk;

the acquiring unit is further configured to acquire hash value of the next chunk of the matched chunk from a hash value table of the original backup data;

the comparing unit is further configured to compare 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, the system is further configured to;

take the next chunk of the matched chunk as a new matched chunk;

return to acquire 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, the system is further configured to;

clear the number of continuous matched chunks; and

return to acquire, 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.

11. A computer program product for data backup, wherein, there is original backup data and current data to be backed up, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

perform first chunking on the current data by using the same chunking method as that used by the original backup data to obtain a current chunk;

calculate hash value of the current chunk; and

acquire, 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 increment number of continuous matched chunks by one.

12. The computer program product according to claim 11, further comprising program code executable by a processor to:

determine whether the number of continuous matched chunks exceeds a threshold, and in response to not exceeding the threshold;

continue 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

calculate hash value of the new current chunk.

13. The computer program product according to claim 12, further comprising program code executable by a processor to:

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

compare 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;

increment number of continuous matched chunks by one;

take the next chunk of the matched chunk as a new matched chunk;

return 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;

clear the number of continuous matched chunks; and

return 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.

14. The computer program product according to claim 11, further comprising program code executable by a processor to:

determine whether the number of continuous matched chunks exceeds a threshold, and in response to exceeding the threshold; and

acquire length of a data block corresponding to an identifier of a next chunk of the matched chunk.

15. The computer program product according to claim 14, further comprising program code executable by a processor to:

continue to perform 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;

calculate hash value of the new current chunk;

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

compare 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;

take the next chunk of the matched chunk as a new matched chunk;

return 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;

clear the number of continuous matched chunks; and

return 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.