Acronis International Gmbh

Vitaly Pogosyan

Serguei M Beloussov

Stanislav Protasov

Mark Shmulevich

Kirill Korotaev

Andrey Panin

Disclosed are methods and systems for performing data backup which implement data binning using log-structured merge (LSM) trees during deduplication. An exemplary method includes: calculating a reduced hash value (RHV) associated with each of a plurality of data blocks; partitioning the plurality of reduced hash values into groups; selecting a representative hash value for each group; determining whether the representative hash value occurs in a first LSM tree, the first LSM tree stored in a volatile memory; and when the representative hash value occurs in the first LSM tree: loading the RHVs in the representative hash value's group into volatile memory; comparing each of the RHVs to one or more hash values in a second LSM tree to identify a matching hash value; and writing a segment identifier (ID) corresponding to the matching hash value in an archive, which references a data block in a segment store.

Systems and methods for data backup using data binning and deduplication

Disclosed are systems, methods and computer program products for data deduplication during a backup using at least two LSM trees. An example method includes calculating, for a first data block, a first hash value associated with the first data block and determining a reduced hash value based on the first hash value. The method includes determining whether the first data block contains data duplicative of an existing data block in a prior backup based on whether the reduced hash value occurs in a first log-structured merge (LSM) tree. If so, the method includes comparing the first hash value to one or more hash values in a second LSM tree to identify a matching hash value, and writing a first segment identifier (ID) corresponding to the matching hash value in an archive, the first segment ID referencing the existing data block in a segment store.

System and method for data deduplication using log-structured merge trees

A method, computer program product, computing system, and system for preventive hash loading are described. The method may include receiving an indication at a storage server that a machine will be backed up. The method may further include loading fingerprints of blocks related to a previous backup of the machine to RAM of the storage server. The method may also include searching the storage server for fingerprints in the RAM that match fingerprints of incoming blocks from the machine being backed up. The method may additionally include, in response to determining that the fingerprints of the incoming blocks do not match fingerprints in the RAM, searching for the fingerprints in a database. Moreover, the method may include transferring only blocks from the machine being backed up that are not in the RAM or the database of the storage server to the storage server.

Preventive hash loading

A system and method is provided for data storage using log-structured merge (LSM) trees. An example method includes storing data blocks for a number of files backup data files in a data archive, storing data values and corresponding segment identifiers for each data block in a first LSM tree, and storing the segment identifiers and associated physical addresses for each data block in a second LSM tree. The method further includes determining that one or more data blocks is no longer referenced by the backup data file and storing, in a third LSM tree, the physical address of the unused space in the data archive. Finally, the method includes copying data blocks from the end of the data archive to unused memory space at the physical address in the data archive and then deleting these data block at the end position of the archive to truncate the archive.

Growing community of inventors

Moscow, Russia

Vitaly Pogosyan