System and method for efficient backup using hashes

• US 7,886,120 B1
• Filed: 12/21/2009
• Issued: 02/08/2011
• Est. Priority Date: 06/28/2006
• Status: Active Grant

• Current Assignee: MidCap Financial Trust
• Original Assignee: Acronis, Inc. (Acronis AG)
• Inventors: Tormasov, Alexander G.
• Primary Examiner(s): Bragdon; Reginald G
• Assistant Examiner(s): Talukdar; Arvind
• Application Number:
  US12/643,076
• Time in Patent Office: 414 Days
• Field of Search: None
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

A method, system and computer program product for data backup such that: for each block of a storage device to be backed up to an image, generating a hash function value corresponding to contents of that block; generating a map of links between blocks in the image and corresponding blocks the storage device; using the hash function values to identify blocks of the storage device with identical contents, such that links for the blocks in the storage device with identical contents point to a single block in the image; and modifying the link in the map when a block in the storage is moved (for example, due to defragmentation) but its contents is not altered, so that the link points to the same backed up block.

Claims

1. A computer implemented method for data backup, the method for data backup executed on a processor, the method comprising:

(a) forming an image of a storage device, wherein contents of blocks of the storage device are restorable from the image;

(b) for each block stored in the image, storing a hash function value in a hash table representing contents of each block;

(c) for each additional block of the storage device to be backed up to the image, generating a hash function value corresponding to contents of that block;

(d) comparing the hash function values to identify, out of blocks of the storage device, candidate blocks that might have identical contents with contents of blocks stored in the image;

(e) if the hash function values are not coincident, then backing up, to the image, contents of unidentified blocks and blocks that do not have identical hash function values, and

(f) if the hash function values are coincident, then for blocks of the storage device with identical hash function values, storing links in the image instead of the contents of the blocks,

(g) wherein links for multiple blocks of the storage device with identical contents point to a single block in the image,

(h) wherein the image of the storage device contains a bitmap of the storage device backup;

(i) the bitmap contains indicators for use of the links, such that an indicator defines if a block contains the content or if the block points to another block,

(j) the bitmap contains indicators that reflect used and unused blocks such that an indicator of one setting represents a used block whose contents are shared with another block in the image, and a bit of an alternate setting corresponds to an unused block whose contents are unique to every other block in the storage image; and

(k) wherein the unused blocks do not require backing up of their contents.

2. The method of claim 1, wherein if the hash function values are coincident, then further comprising comparing contents of candidate blocks with contents of corresponding blocks stored in the image, and backing up, to the image, contents of unidentified blocks and blocks that do not have identical contents.

3. The method of claim 1, wherein the image includes data of different backups.

4. The method of claim 1, wherein the image contains backups of different storage devices.

5. The method of claim 1, wherein hash function is any of MD4, MD5, CRC, CRC32, SHA1, SHA2, SHA512, SHA256, GOST, hash function based on block ciphers and Message Authentication Code (MAC).

6. The method of claim 1, further comprising restoration of the storage device from the image, wherein contents of blocks pointed by link is restored to corresponding blocks of the storage device.

7. The method of claim 1, wherein the link for the block is stored in the image instead of contents of the corresponding block.

8. The method of claim 1, wherein the image includes an indicator reflecting use of the link for the block contents.

9. The method of claim 8, wherein a bitmap is created for the storage device backup;

and

wherein the bitmap includes indicators for use of the links.

10. The method of claim 9, wherein the bitmap further reflects unused blocks of the storage device;

and

wherein the unused blocks do not require backing up of their contents.

11. A non-transitory computer useable recording medium having computer program logic stored thereon for executing on a processor for data backup, the computer program logic performing the method of claim 1.

12. A system comprising a processor and a memory and code loaded into the memory for performing the method of claim 1.