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

A system for performing data deduplication during a backup procedure, the system comprising:

• a storage device having a segment store that includes a plurality of existing data blocks from prior backups;
• a memory storing a first log-structured merge (LSM) tree;
• at least one hardware processor configured to:
• calculate, for a first data block, a first hash value associated with the first data block;
• determine a reduced hash value based on the first hash value, wherein the reduced hash value is smaller in size than the first hash value;
• determine whether the first data block contains data duplicative of an existing data block based on whether the reduced hash value occurs in the first LSM tree;
• and
• responsive to determining that the reduced hash value occurs in the first LSM tree:
• compare the first hash value to one or more hash values in a second LSM tree to identify a matching hash value;
• and
• write a first segment identifier (ID) corresponding to the matching hash value in an archive, the first segment ID referencing the existing data block in the segment store.

A non-transitory computer readable medium comprising computer executable instructions for performing data deduplication during a backup procedure, including instructions for:

• calculating, for a first data block, a first hash value associated with the first data block;
• determining a reduced hash value based on the first hash value, wherein the reduced hash value is smaller in size than the first hash value;
• 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, the first LSM tree stored in volatile memory;
• and
• responsive to determining that the reduced hash value occurs in the first LSM tree:
• 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.