US 11,112,985 B2Granted

Detecting data deduplication opportunities using hash distance

AssigneeEMC IP Holding Company LLC

InventorsIvan Bassov, Philippe Armangau, Sorin Faibish, Istvan Gonczi

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques for processing data may include: receiving a candidate data block; computing a distance using a distance function, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block; and determining, using the distance, whether to perform data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block. The distance may be computed using a bit-wise logical exclusive-or operation of the contents of the candidate data block and the target data block. The distance may be computed using a bit-wise logical exclusive-or operation of digests computed for the candidate and target data blocks using a distance preserving hash function. The target and candidate block may be similar if the distance is less than a threshold.

Claims19

Dependent claims

A method of processing data comprising:

receiving, using a processor, a candidate data block;
computing, using a processor, a distance using a distance function, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block, wherein the distance computed by the distance function is less than a second distance computed by the distance function for another pair of data blocks, and the distance denotes that the candidate data block and the target data block have a higher degree of similarity than the another pair of data blocks having the second distance;
determining, using a processor, that the candidate data block is not a duplicate of the target block;
and
responsive to determining the candidate data block is not a duplicate of the target block, determining using a processor whether the distance is less than a threshold distance denoting a threshold level of similarity, and responsive to determining that the distance is less than the threshold distance, performing first processing using a processor including:
determining that the candidate data block and the target block have a level of similarity greater than the threshold level of similarity denoted by the threshold distance;
and
performing partial data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block, wherein said partial data deduplication includes:
determining whether at least one sub-block of the candidate data block matches at least one sub-block of the target data block;
and
responsive to determining at least one sub-block of the candidate data block matches at least one sub-block of the target data block, performing second processing that stores the candidate data block as a partially deduplicated data block with at least one sub-block that is a duplicate of another sub-block of the target data block.

8 more elements

A system comprising:

a processor;
and
a memory comprising code stored thereon that, when executed, performs a method of processing data comprising:
receiving a candidate data block;
computing a distance using a distance function, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block, wherein the distance computed by the distance function is less than a second distance computed by the distance function for another pair of data blocks, and the distance denotes that the candidate data block and the target data block have a higher degree of similarity than the another pair of data blocks having the second distance;
determining that the candidate data block is not a duplicate of the target block;
and
responsive to determining the candidate data block is not a duplicate of the target block, determining whether the distance is less than a threshold distance denoting a threshold level of similarity, and responsive to determining that the distance is less than the threshold distance, performing processing including:
determining that the candidate data block and the target block have a level of similarity greater than the threshold level of similarity denoted by the threshold distance;
and
performing partial data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block, wherein said partial data deduplication includes:
determining whether at least one sub-block of the candidate data block matches at least one sub-block of the target data block;
and
responsive to determining at least one sub-block of the candidate data block matches at least one sub-block of the target data block, performing second processing that stores the candidate data block as a partially deduplicated data block with at least one sub-block that is a duplicate of another sub-block of the target data block.

11 more elements

A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing data comprising:

receiving a candidate data block;
computing a distance using a distance function, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block, wherein the distance computed by the distance function is less than a second distance computed by the distance function for another pair of data blocks, and the distance denotes that the candidate data block and the target data block have a higher degree of similarity than the another pair of data blocks having the second distance;
determining that the candidate data block is not a duplicate of the target block;
and
responsive to determining the candidate data block is not a duplicate of the target block, determining whether the distance is less than a threshold distance denoting a threshold level of similarity, and responsive to determining that the distance is less than the threshold distance, performing processing including:
determining that the candidate data block and the target block have a level of similarity greater than the threshold level of similarity denoted by the threshold distance;
and
performing partial data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block, wherein said partial data deduplication includes:
determining whether at least one sub-block of the candidate data block matches at least one sub-block of the target data block;
and
responsive to determining at least one sub-block of the candidate data block matches at least one sub-block of the target data block, performing second processing that stores the candidate data block as a partially deduplicated data block with at least one sub-block that is a duplicate of another sub-block of the target data block.

8 more elements

A method of processing data comprising:

receiving a candidate data block;
computing, using a distance function, a distance between the candidate data block and a target data block, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block, wherein said computing the distance between the candidate data block and the target data block includes:
computing a first digest for the candidate data block using a distance preserving hash function;
computing a second digest for the target data e block using the distance preserving hash function;
and
computing the distance based on a result of a bit-wise logical exclusive-or operation of the first digest and the second digest;
determining whether the distance between the candidate data block and a target data block is zero;
responsive to determining the distance between the candidate data block and a target data block is zero, determining the candidate data block is a duplicate of the target data block and storing the candidate data block as a duplicate of the target data block;
and
responsive to determining the distance between the candidate data block and a target data block is not zero, performing first processing including:
determining whether the distance is less than a threshold distance denoting a threshold level of similarity;
and
responsive to determining the distance is less than the threshold distance, performing second processing including:
determining that the candidate data block and the target block have a level of similarity greater than the threshold level of similarity denoted by the threshold distance;
and
performing partial data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block, wherein said partial data deduplication includes:
determining whether at least one sub-block of the candidate data block matches at least one sub-block of the target data block;
and
responsive to determining at least one sub-block of the candidate data block matches at least one sub-block of the target data block, performing second processing that stores the candidate data block as a partially deduplicated data block with at least one sub-block that is a duplicate of another sub-block of the target data block.

16 more elements

A system comprising:

one or more processors;
and
one or more memories comprising code stored thereon that, when executed, performs a method of processing data comprising:
receiving a candidate data block;
computing, using a distance function, a distance between the candidate data block and a target data block, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block, wherein said computing the distance between the candidate data block and the target data block includes:
computing a first digest for the candidate data block using a distance preserving hash function;
computing a second digest for the target data e block using the distance preserving hash function;
and
computing the distance based on a result of a bit-wise logical exclusive-or operation of the first digest and the second digest;
determining whether the distance between the candidate data block and a target data block is zero;
responsive to determining the distance between the candidate data block and a target data block is zero, determining the candidate data block is a duplicate of the target data block and storing the candidate data block as a duplicate of the target data block;
and
responsive to determining the distance between the candidate data block and a target data block is not zero, performing first processing including:
determining whether the distance is less than a threshold distance denoting a threshold level of similarity;
and
responsive to determining the distance is less than the threshold distance, performing second processing including:
determining that the candidate data block and the target block have a level of similarity greater than the threshold level of similarity denoted by the threshold distance;
and
performing partial data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block, wherein said partial data deduplication includes:
determining whether at least one sub-block of the candidate data block matches at least one sub-block of the target data block;
and
responsive to determining at least one sub-block of the candidate data block matches at least one sub-block of the target data block, performing second processing that stores the candidate data block as a partially deduplicated data block with at least one sub-block that is a duplicate of another sub-block of the target data block.

19 more elements

A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing data comprising:

receiving a candidate data block;
computing, using a distance function, a distance between the candidate data block and a target data block, wherein the distance denotes a measurement of similarity between the candidate data block and a target data block, wherein said computing the distance between the candidate data block and the target data block includes:
computing a first digest for the candidate data block using a distance preserving hash function;
computing a second digest for the target data e block using the distance preserving hash function;
and
computing the distance based on a result of a bit-wise logical exclusive-or operation of the first digest and the second digest;
determining whether the distance between the candidate data block and a target data block is zero;
responsive to determining the distance between the candidate data block and a target data block is zero, determining the candidate data block is a duplicate of the target data block and storing the candidate data block as a duplicate of the target data block;
and
responsive to determining the distance between the candidate data block and a target data block is not zero, performing first processing including:
determining whether the distance is less than a threshold distance denoting a threshold level of similarity;
and
responsive to determining the distance is less than the threshold distance, performing second processing including:
determining that the candidate data block and the target block have a level of similarity greater than the threshold level of similarity denoted by the threshold distance;
and
performing partial data deduplication of the candidate data block with respect to the target data block to identify at least one sub-block of the candidate data block that is a duplicate of at least one sub-block of the target data block, wherein said partial data deduplication includes:
determining whether at least one sub-block of the candidate data block matches at least one sub-block of the target data block;
and
responsive to determining at least one sub-block of the candidate data block matches at least one sub-block of the target data block, performing second processing that stores the candidate data block as a partially deduplicated data block with at least one sub-block that is a duplicate of another sub-block of the target data block.

16 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/392,964Filed 24 Apr 2019
Published: US 2020/0341666 A129 Oct 2020
Granted: 7 Sep 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

G06F 3/0641
Management of blocks: de-duplication techniques
G06F 3/0608
Specifically adapted to achieve a particular effect: saving storage space on storage systems
G06F 3/0673
In-line storage system: single storage device
G06F 3/0683
In-line storage system: plurality of storage devices

Family

US 2020/0341666 A1Pre-grant publication · published 29 Oct 2020
US 11,112,985 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key