Granted Patent B2

US 11,947,496 · App. 16/882,593 · Granted Apr 2, 2024

Inventors: Chao Lin (Shanghai, CN); Yuting Zhang (Chengdu, CN)

Assignee: EMC IP Holding Company LLC

G06F16/1748G06F11/1451G06F11/1464G06F16/152G06F16/1824G06F2201/80

Abstract

Claims (38)

1. A method for data deduplication in a multi-node storage system, comprising:

receiving a data stream of a backup;

dividing the data stream into a plurality of blocks of the backup;

merging a plurality of the blocks into a super block of the backup;

determining a similarity hash value of the super block, wherein the similarity hash value indicates similarity between the super block and a plurality of super blocks, wherein

determining the similarity hash value of the super block comprises:

determining a signature matrix of the backup in which the super block is included by taking blocks as features through MinHash, wherein the signature matrix is determined by sampling the super block to obtain a portion of the blocks that is less than all of the plurality of blocks in the super block, and determining the signature matrix for the super block by taking the portion of the blocks as features, and

based on the signature matrix, calculating the similarity hash value through locality sensitive hashing;

comparing, using one or more distributed hash tables (DHTs), the similarity hash value of the super block with a similarity hash value range associated with a node of the multi-node storage system to determine whether the similarity hash value is within the similarity hash value range, wherein the similarity hash value range is stored in the one or more DHTs, and wherein the one or more DHTs is used as a cache;

making a determination that the similarity hash value is outside the similarity hash value range;

allocating the super block to the node based on the determination;

updating the similarity hash value range by adding a range number to the similarity hash value to set an upper bound of the similarity hash value range and subtracting the range number from the similarity hash value to set a lower bound of the similarity hash value range; and

storing the super block in a memory of the node, based on allocating the super block to the node and in response to updating the similarity hash value.

2. An electronic device, comprising

a processing unit;

a memory, coupled to the processing unit and comprising instructions stored therein, the instructions causing the electronic device to perform a method when being executed by the processing unit, the method comprising:

receiving a data stream of a backup;

dividing the data stream into a plurality of blocks of the backup;

merging a plurality of the blocks into a super block of the backup;

determining a similarity hash value of the super block, wherein the similarity hash value indicates similarity between the super block and a plurality of super blocks, wherein determining the similarity hash value of the super block comprises:

determining a signature matrix of the backup in which the super block is included by taking blocks as features through MinHash, wherein the signature matrix is determined by sampling the super block to obtain a portion of the blocks that is less then all of the plurality of blocks in the super block, and determining the signature matrix for the super block by taking the portion of the blocks as features, and based on the signature matrix, calculating the similarity hash value through locality sensitive hashing;

comparing, using one or more distributed hash tables (DHTs), the similarity hash value of the super block with a similarity hash value range associated with a node of a multi-node storage system to determine whether the similarity hash value is within the similarity hash value range, wherein the similarity hash value range is stored in the one or more DHTs, and wherein the one or more DHTs is used as a cache;

making a determination that the similarity hash value is outside the similarity hash value range;

allocating the super block to the node based on the determination;

updating the similarity hash value range by adding a range number to the similarity hash value to set an upper bound of the similarity hash value range and subtracting the range number from the similarity hash value to set a lower bound of the similarity hash value range; and

storing the super block in a node memory of the node, based on allocating the super block to the node and in response to updating the similarity hash value.

3. A computer-readable storage medium, wherein machine-executable instructions are stored in the computer-readable storage medium, and the machine-executable instructions cause at least one processor to implement a method when being executed by the at least one processor, the method comprising:

receiving a data stream of a backup;

dividing the data stream into a plurality of blocks of the backup;

merge a plurality of the blocks into a super block of the backup;

determining a similarity hash value of the super block, wherein the similarity hash value indicates similarity between the super block and a plurality of super blocks, wherein determining the similarity hash value of the super block comprises:

determining a signature matrix of the backup in which the super block is included by taking blocks as features through MinHash, wherein the signature matrix is determined by sampling the super block to obtain a portion of the blocks that is less than all of the plurality of blocks in the super block, and determining the signature matrix for the super block by taking the portion of the blocks as features, and

based on the signature matrix, calculating the similarity hash value through locality sensitive hashing;

comparing, using one or more distributed hash tables (DHTs), the similarity hash value of the super block with a similarity hash value range associated with a node of a multi-node storage system to determine whether the similarity hash value is within the similarity hash value range, wherein the similarity hash value range is stored in the one or more DHTs, and wherein the one or more DHTs is used as a cache;

making a determination that the similarity hash value is outside the similarity hash value range;

allocating the super block to the node based on the determination;

updating the similarity hash value range by adding a range number to the similarity hash value to set an upper bound of the similarity hash value range and subtracting the range number from the similarity hash value to set a lower bound of the similarity hash value range; and

storing the super block in a memory of the node, based on allocating the super block to the node and in response to updating the similarity hash value.

Assignments (9)

Priority Claims (1)

Continuity (1)