System and method for efficient backup using hashes
View Patent ↗Methods, systems, and apparatus, including computer programs encoded on computer storage media, for efficient backup using hashes One of the methods includes forming an image of a storage device, wherein contents of blocks of the storage device are restorable from the contents of blocks of the image. The method includes generating a first plurality of hash values, each hash value generated from contents of a block of the image. The method includes selecting a block of the storage device. The method includes generating a hash value from the contents of the selected block. The method includes determining whether the hash value occurs in the plurality of hash values. The method also includes generating an entry in the image in response to the determination.
1. A computer implemented method for data backup, the method for data backup executed on a processor, the method comprising:
forming an image of a storage device, wherein contents of blocks of the storage device are restorable from the contents of blocks of the image;
generating a first plurality of hash values, each hash value generated from contents of a block of the image;
selecting a block of the storage device;
generating a hash value from the contents of the selected block;
determining whether the hash value occurs in the plurality of hash values; and
generating an entry in the image in response to the determination;
wherein:
selecting the block of the storage device further comprises selecting a plurality of blocks to be backed up;
generating the hash value from the contents of the selected block further comprises for each of the selected plurality of blocks to be backed up to the image, generating a hash function value corresponding to contents of that block; and
determining whether the hash value occurs in the plurality of hash values further comprises sorting all the generated hash function values and deleting duplicate hash values and 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.
2. The method of claim 1 , wherein generating the entry in the image comprises copying the contents of the selected block if the hash value does not occur in the plurality of values and storing a link in the image if the hash value does occur in the plurality of values.
3. The method of claim 1 , wherein generating the entry in the image comprises copying the contents of the selected block to the image in response to determining that the hash value does not occur in the plurality of values.
4. The method of claim 1 , wherein generating the entry in the image comprises storing a link in the image instead of the contents of the block in response to determining that the hash value does occur in the plurality of values.
5. The method of claim 4 , further comprising restoring the storage device from the image, wherein contents of blocks pointed by link is restored to corresponding blocks of the storage device.
6. The method of claim 4 , wherein links for multiple blocks of the storage device with identical contents point to a single block in the image.
7. The method of claim 4 , wherein the link for the block is stored in the image instead of contents of the corresponding block.
8. The method of claim 1 , further comprising adding the hash value for the selected block to the hash table in response to determining that the hash value does not occur in the plurality of values.
9. The method of claim 1 , further comprising storing first plurality of hash values in a hash table.
10. The method of claim 1 , wherein the image contains a bitmap of the storage device backup.
11. The method of claim 1 , wherein the image includes data of different backups.
12. The method of claim 1 , wherein hash function comprises a hash function selected from the group consisting of MD4, MD5, CRC, CRC32, SHA1, SHA2, SHA512, SHA256, GOST, hash function based on block ciphers and Message Authentication Code (MAC).
13. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
forming an image of a storage device, wherein contents of blocks of the storage device are restorable from the contents of blocks of the image;
generating a first plurality of hash values, each hash value generated from contents of a block of the image;
selecting a block of the storage device;
generating a hash value from the contents of the selected block;
determining whether the hash value occurs in the plurality of hash values; and
generating an entry in the image in response to the determination;
wherein:
selecting the block of the storage device further comprises selecting a plurality of blocks to be backed up;
generating the hash value from the contents of the selected block further comprises for each of the selected plurality of blocks to be backed up to the image, generating a hash function value corresponding to contents of that block; and
determining whether the hash value occurs in the plurality of hash values further comprises sorting all the generated hash function values and deleting duplicate hash values and 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.
14. A computer storage medium encoded with computer program instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
forming an image of a storage device, wherein contents of blocks of the storage device are restorable from the contents of blocks of the image;
generating a first plurality of hash values, each hash value generated from contents of a block of the image;
selecting a block of the storage device;
generating a hash value from the contents of the selected block;
determining whether the hash value occurs in the plurality of hash values; and
generating an entry in the image in response to the determination;
wherein:
selecting the block of the storage device further comprises selecting a plurality of blocks to be backed up;
generating the hash value from the contents of the selected block further comprises for each of the selected plurality of blocks to be backed up to the image, generating a hash function value corresponding to contents of that block; and
determining whether the hash value occurs in the plurality of hash values further comprises sorting all the generated hash function values and deleting duplicate hash values and 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.