Deduplicating full and partial block matches
AssigneeEMC IP Holding Company LLC
InventorsUri Shabi, Ronen Gazit, Alon Titelman, Alex Soukhman
Life of this patent
Estimating the term…
Abstract
A technique for performing deduplication traverses a deduplication database and assigns digest values in the database to buckets, where each bucket covers a respective range of digest values. To deduplicate a particular candidate block, the technique generates a digest from the candidate block and searches for the computed digest in a subset of the buckets, where the subset is selected based on the computed digest. If a target block providing an exact match or a suitably close partial match is found in the subset of buckets, the technique effects storage of the candidate block at least in part by providing a reference to the target block.
Claims19
A method of performing data deduplication, the method comprising:
- assigning multiple digests in a deduplication database to multiple buckets, each bucket dedicated to a respective range of digest values;
- upon obtaining a candidate block of data to be deduplicated, generating a candidate digest of the candidate block and searching a subset of the buckets for the candidate digest, the subset of the buckets selected for searching based on the candidate digest;
- and
- in response to the searching identifying a target digest that represents a target block that at least partially matches the candidate block, effectuating storage of the candidate block at least in part by providing a reference to the target block,
- wherein each of the multiple digests in the deduplication database represents a respective data block and includes a similarity hash (sim hash), each sim hash generated from the respective data block and differing from sim hashes generated from other data blocks in relation to differences between the respective data block and the other data blocks.
A computerized apparatus, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:
- assign multiple digests in a deduplication database to multiple buckets, each bucket dedicated to a respective range of digest values;
- upon obtaining a candidate block of data to be deduplicated, generate a candidate digest of the candidate block and search a subset of the buckets for the candidate digest, the subset of the buckets selected for searching based on the candidate digest;
- and
- in response to the searching identifying a target digest that represents a target block that at least partially matches the candidate block, effectuate storage of the candidate block at least in part by providing a reference to the target block,
- wherein each of the multiple digests in the deduplication database represents a respective data block and includes a similarity hash (sim hash), each sim hash generated from the respective data block and differing from sim hashes generated from other data blocks in relation to differences between the respective data block and the other data blocks.
A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a computerized apparatus, cause the computerized apparatus to perform a method of performing data deduplication, the method comprising:
- assigning multiple digests in a deduplication database to multiple buckets, each bucket dedicated to a respective range of digest values;
- upon obtaining a candidate block of data to be deduplicated, generating a candidate digest of the candidate block and searching a subset of the buckets for the candidate digest, the subset of the buckets selected for searching based on the candidate digest;
- and
- in response to the searching identifying a target digest that represents a target block that at least partially matches the candidate block, effectuating storage of the candidate block at least in part by providing a reference to the target block,
- wherein each of the multiple digests in the deduplication database represents a respective data block and includes a similarity hash (sim hash), each sim hash generated from the respective data block and differing from sim hashes generated from other data blocks in relation to differences between the respective data block and the other data blocks.
Dependencies are inferred from the claim text.