System and method for efficient backup using hashes
First Claim
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.
8 Assignments
0 Petitions
Accused Products
Abstract
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.
42 Citations
14 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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.
-
Specification