# US 9,436,558 B1 · System and method for fast backup and restoring using sorted hashes

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,436,558 B1
- Document ID: US9436558B1
- Status: Granted
- Kind: B1
- Application number: 12/974,753
- Filed: 2010-12-21
- Granted: 2016-09-06
- Earliest claimed: 2010-12-21
- Assignees: Acronis International GmbH
- Applicants: Yuri S. Per; Maxim V. Lyadvinsky; Serguei M. Beloussov
- Inventors: Yuri S. Per; Maxim V. Lyadvinsky; Serguei M. Beloussov
- Web page: https://patentgrep.com/patent/US9436558B1

## CPC

- G06F 11/1451: {by selection of backup contents}
- G06F 11/1453: {using de-duplication of the data}
- G06F 16/113: {Details of archiving (lifecycle management in storage systems G06F3/0649; point-in-time backing up or restoration of persistent data G06F11/1446)}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 16/2255: {Hash tables}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

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

### Claim 2 (depends on 1)

The method of claim 1, further comprising deleting redundant data blocks using the location pointers.

### Claim 3 (depends on 1)

The method of claim 1, wherein the data blocks are backed up to different data storages.

### Claim 4 (depends on 1)

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).

### Claim 5 (depends on 1)

The method of claim 1, wherein the location pointers are stored in the hash table.

### Claim 6 (depends on 1)

The method of claim 1, wherein the hash values are sorted after being compared to the stored hash values from the hash table.

### Claim 7 (depends on 1)

The method of claim 1, further comprising sorting the location pointers.

### Claim 8 (depends on 1)

The method of claim 1, wherein the hash values are sorted according to their addresses.

### Claim 9 (depends on 1)

The method of claim 1, wherein the hash values are sorted sequentially.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

The method of claim 1, wherein the hash values are sorted in parallel with the
backup of the data blocks onto the backup storage.

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

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 1)

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.