System and method for fast backup and restoring using sorted hashes
View Patent ↗A method, system and computer program product for backup and restoration of data. Hash values for data blocks subject to backup are generated. After a number of hashes are accumulated, e.g., on a backup server, these hashes are sorted. Then, the hashes are compared against the hash values in the hash table corresponding to data blocks that have already been backed up. If a hash matches the hash from the hash table, a pointer to the block in the archive is written to the table of pointers to the redundant blocks. Then, this hash value is deleted from a set of the hash values. A check is made if a hash is the last in the group. If the hash is the last in the group, the remaining unique hash values are written into the hash table. Otherwise, the next hash is selected from the group. The redundant data blocks are discarded and only unique data is backed up.
1. A method for data backup, the method comprising:
determining a set of data blocks subject to a backup;
for each data block generating a hash value and a location pointer;
accumulating the hash values into a set;
sorting the hash values within the set;
comparing the hash values against hash values stored in a hash table, wherein the hash values stored in the hash table correspond to previously backed up unique data blocks;
storing location pointers of the data blocks, if the corresponding hash values match the hash values from the hash table;
deleting the matching hash value from the set;
writing remaining unique hash values into the hash table; and
identifying redundant data block locations of data blocks in the backup data storage that are absent from the hash table;
dividing the backup data storage into containers;
determining a number of redundant data blocks in each container; and
determining whether to delete a redundant data block based on a ratio of the number of redundant data blocks in a corresponding container to the number of used data blocks in the corresponding container.
2. The method of claim 1 , further comprising deleting redundant data blocks using the location pointers.
3. The method of claim 1 , wherein the data blocks are backed up to different data storages.
4. The method of claim 1 , wherein the hash values are generated using any of hash function MD4, MD5, CRC, CRC32, SHA1, SHA2, SHA512, SHA256, GOST, hash function based on block ciphers and Message Authentication Code (MAC).
5. The method of claim 1 , wherein the location pointers are stored in the hash table.
6. The method of claim 1 , wherein the hash values are sorted after being compared to the stored hash values from the hash table.
7. The method of claim 1 , further comprising sorting the location pointers.
8. The method of claim 1 , wherein the hash values are sorted according to their addresses.
9. The method of claim 1 , wherein the hash values are sorted sequentially.
10. The method of claim 1 , wherein the hash values are sorted based on a set number of last bits of each of the hash values.
11. The method of claim 1 , wherein the hash values are sorted in parallel with the
backup of the data blocks onto the backup storage.
12. A system for data backup, the system comprising:
a set of data blocks located on a storage media subject to a backup;
a backup storage for backup of the data blocks;
a module for generating hash values of the data blocks;
location pointers corresponding to the data blocks;
a hash table for storing the location pointers and hash values corresponding to the data blocks, wherein:
the hash values are sorted and compared against the hash values from the hash table corresponding to previously backed up data blocks;
the location pointers of the data blocks are stored, if the hash values match the hash values corresponding to the previously backed up data blocks;
the matching hash values are deleted and remaining unique hash values are stored into the hash table;
the data blocks corresponding to the unique hash values are backed up to the backup storage;
redundant data block locations of data blocks in the backup data storage that are absent from the hash table are identified;
the backup data storage is divided into containers;
a number of redundant data blocks in each container is determined; and
whether to delete a redundant data block is determined based on a ratio of the number of redundant data blocks in a corresponding container to the number of used data blocks in the corresponding container.
13. The system of claim 12 , wherein the hash values are sorted according to any of:
sequential order;
hash value addresses; and
a set number of last bits.
14. A system for data backup comprising:
a processor;
a memory couple to the processor;
a computer program logic stored on the memory and executed on the processor, the computer program logic for implementing the steps of claim 1 .