Patent ID: 8484427

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