System and method for efficient backup using hashes
View Patent ↗A method for data backup including (a) forming an image of the storage device; (b) for each block to be backed up to the image, generating a hash; (c) for each block stored in the image, storing a hash in a hash table; (c) for each additional block of the storage device to be backed up, generating a hash; (d) sorting all the generated hashes and deleting duplicate hashes; (e) comparing the hashes to identify candidate blocks that might have identical contents with contents of blocks stored in the image; (f) if the hashes are not coincident, then backing up, to the image, contents of unidentified blocks and blocks that do not have identical hashes, and (g) otherwise, storing links in the image instead of the contents of the blocks, (h) after checking all the hashes for those blocks that need to be backed up, writing only unique hashes to the hash table; (h) links for multiple blocks with identical contents point to a single block in the image, (i) the image contains a bitmap of the backup; (j) the bitmap contains indicators for the links that define if a block contains the content or if the block points to another block, (k) also indicators that reflect used and unused blocks such that an indicator whether contents are shared with another block vs. contents are unique to every other block in the image.
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 of the storage device to be backed up to the image, generating a hash function value corresponding to contents of that block;
(c) 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) sorting all the generated hash function values and deleting duplicate hash values;
(e) 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;
(f) 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
(g) 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;
(h) after checking all the hash function values for those blocks that need to be backed up, writing only unique hash function values to the hash table;
(h) wherein links for multiple blocks of the storage device with identical contents point to a single block in the image,
(i) wherein the image contains a bitmap of the storage device backup;
(j) 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,
(k) wherein 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 image; and
(l) 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, a memory, and code loaded into the memory for performing the method of claim 1 .