Deduplication using nearest neighbor cluster

Patent metadata

Field	Value
Publication number	US-11029871-B2
Application number	US-201916412946-A
Country	US
Kind code	B2
Filing date	May 15, 2019
Priority date	May 15, 2019
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

Disclosed are techniques for data deduplication, which include methods, systems, or computer products for reducing data redundancy in a data storage system comprising searching a cluster of nearest neighbors, wherein the cluster has been created using a locality sensitive hashing algorithm, to determine if a data block has been stored in the data storage system prior to writing the data block. In alternate embodiments, the nearest neighbor clusters could be created using one or more of the following algorithms: k-means clustering algorithm, a k-medoids clustering algorithm, a mean shift algorithm, a generalized method of moment (GMM) algorithm, or a density based spatial clustering of applications with noise (DBSCAN) algorithm.

First claim

What is claimed is:

1. A method of reducing data redundancy in a data storage system comprising;
searching a cluster of nearest neighbors to determine if a data block has been stored in the data storage system prior to writing the data block, wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor.

2. The method of claim 1 , further comprising:
writing the data block if no match is found, else storing mapping information for the data block if a match is found within the cluster of nearest neighbors.

3. The method of claim 1 , wherein the nearest neighbor cluster is created with a machine learning module or an offload engine.

4. The method of claim 1 , wherein the locality sensitive hashing function is a secure hash algorithm 1 (“SHA-1”) or a Message Digest 5 (“MD5”) algorithm.

5. The method of claim 1 further comprising:
compressing one or more data sets within the cluster of nearest neighbors.

6. The method of claim 1 , wherein the cluster of nearest neighbors includes a plurality of master blocks.

7. A system comprising:
one or more processors; and
a memory configured to:
search a cluster of nearest neighbors to determine if a data block has been stored in a data storage system prior to writing the data block, wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor.

8. The system of claim 7 further configured to:
write the data block if no match is found, else storing mapping information for the data block if a match is found within the cluster of nearest neighbors.

9. The system of claim 7 , wherein the nearest neighbor cluster is created with a machine learning module or an offload engine.

10. The system of claim 7 , wherein the locality sensitive hashing function is a secure hash algorithm 1 (“SHA-1”) or a Message Digest 5 (“MD5”) algorithm.

11. The system of claim 7 further configured to:
compress one or more data sets within the cluster of nearest neighbors.

12. The system of claim 7 , wherein the cluster of nearest neighbors includes a plurality of master blocks.

13. A non-transitory, computer readable medium comprising code stored thereon that, when executed, performs the following acts:
searching a cluster of nearest neighbors to determine if a data block has been stored in a data storage system prior to writing the data block, wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor.

14. The non-transitory, computer readable medium of claim 13 , wherein the code stored thereon, when executed, additionally performs the following acts:
writing the data block if no match is found, else storing mapping information for the data block if a match is found within the cluster of nearest neighbors.

15. The non-transitory, computer readable medium of claim 13 , wherein the nearest neighbor cluster is created with a machine learning module or an offload engine.

16. The non-transitory, computer readable medium of claim 13 , wherein the locality sensitive hashing function is a secure hash algorithm 1 (“SHA-1”) or a Message Digest 5 (“MD5”) algorithm.

17. The non-transitory, computer readable medium of claim 13 , wherein the cluster of nearest neighbors includes a plurality of master blocks.

18. A non-transitory, computer readable medium comprising code stored thereon that, when executed, performs the following acts:
searching a cluster of nearest neighbors to determine if a data block has been stored in a data storage system prior to writing the data block wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor; and
compressing one or more data sets within the cluster of nearest neighbors.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Krasner Jonathan
• Singh Sweetesh
• Chalmer Steven

Classifications

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title