Patent ID: 11947496
Assignee: EMC IP HOLDING COMPANY LLC
Field: nan (nan)
Classification: CPC nan | IPC G

Claim 2:
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.