US 2021/0064589 A1Published application

Scale out chunk store to multiple nodes to allow concurrent deduplication

AssigneeVMware, Inc.

InventorsWenguang WANG, Junlong GAO, Marcos K. AGUILERA, Richard P. SPILLANE, Christos KARAMANOLIS, Maxime AUSTRUY

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present disclosure provides techniques for scaling out deduplication of files among a plurality of nodes. The techniques include designating a master component for the coordination of deduplication. The master component divides files to be deduplicated among several slave nodes, and provides to each slave node a set of unique identifiers that are to be assigned to chunks during the deduplication process. The techniques herein preserve integrity of the deduplication process that has been scaled out among several nodes. The scaled out deduplication process deduplicates files faster by allowing several deduplication modules to work in parallel to deduplicate files.

Claims20

Dependent claims

A method of deduplicating a plurality of files using a plurality of slave nodes, the method comprising:

receiving, at a first slave node of the plurality of slave nodes, a first portion of the plurality of files, wherein each slave node of the plurality of slave nodes is assigned a different portion of the plurality of files;
placing the first portion of the plurality of files in a queue stored at the first slave node;
and
deduplicating, by the first slave node, the first portion of the plurality of files on a file by file basis in order of the queue, comprising:
retrieving the corresponding file from the queue;
determining that a hash of a content of a chunk of the corresponding file does not exist in a chunk hash data structure, the chunk hash data structure comprising a first plurality of key-value mappings between a first plurality of keys and a first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk;
based on determining the hash does not exist in the chunk hash data structure, attempting to add an entry into the chunk hash data structure, the entry comprising the hash of the content of the chunk of the corresponding file;
during the attempting, if the hash of the content of the chunk of the corresponding file still does not exist in the chunk hash data structure:
adding the entry into the chunk hash data structure;
and
proceeding with deduplication of the corresponding file;
and
during the attempting, if the hash of the content of the chunk of the corresponding file does exist in the chunk hash data structure:
refraining from adding the entry into the chunk hash data structure to prevent duplicate entries in the chunk hash data structure;
stopping deduplication of the corresponding file;
and
moving the corresponding file to a later position in the queue.

14 more elements

A non-transitory computer readable medium comprising instructions to be executed in a processor of a computer system, the instructions when executed in the processor cause the computer system to carry out a method of deduplicating a plurality of files using a plurality of slave nodes, the method comprising:

receiving, at a first slave node of the plurality of slave nodes, a first portion of the plurality of files, wherein each slave node of the plurality of slave nodes is assigned a different portion of the plurality of files;
placing the first portion of the plurality of files in a queue stored at the first slave node;
and
deduplicating, by the first slave node, the first portion of the plurality of files on a file by file basis in order of the queue, comprising:
retrieving the corresponding file from the queue;
determining that a hash of a content of a chunk of the corresponding file does not exist in a chunk hash data structure, the chunk hash data structure comprising a first plurality of key-value mappings between a first plurality of keys and a first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk;
based on determining the hash does not exist in the chunk hash data structure, attempting to add an entry into the chunk hash data structure, the entry comprising the hash of the content of the chunk of the corresponding file;
during the attempting, if the hash of the content of the chunk of the corresponding file still does not exist in the chunk hash data structure:
adding the entry into the chunk hash data structure;
and
proceeding with deduplication of the corresponding file;
and
during the attempting, if the hash of the content of the chunk of the corresponding file does exist in the chunk hash data structure:
refraining from adding the entry into the chunk hash data structure to prevent duplicate entries in the chunk hash data structure;
stopping deduplication of the corresponding file;
and
moving the corresponding file to a later position in the queue.

14 more elements

A computer system comprising:

a plurality of files;
a plurality of slave nodes;
a chunk hash data structure;
and
at least one processor, wherein the at least one processor is programmed to carry out a method of deduplicating the plurality of files using the plurality of slave nodes, the method comprising:
receiving, at a first slave node of the plurality of slave nodes, a first portion of the plurality of files, wherein each slave node of the plurality of slave nodes is assigned a different portion of the plurality of files;
placing the first portion of the plurality of files in a queue stored at the first slave node;
and
deduplicating, by the first slave node, the first portion of the plurality of files on a file by file basis in order of the queue, comprising:
retrieving the corresponding file from the queue;
determining that a hash of a content of a chunk of the corresponding file does not exist in the chunk hash data structure, the chunk hash data structure comprising a first plurality of key-value mappings between a first plurality of keys and a first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk;
based on determining the hash does not exist in the chunk hash data structure, attempting to add an entry into the chunk hash data structure, the entry comprising the hash of the content of the chunk of the corresponding file;
during the attempting, if the hash of the content of the chunk of the corresponding file still does not exist in the chunk hash data structure:
adding the entry into the chunk hash data structure;
and
proceeding with deduplication of the corresponding file;
and
during the attempting, if the hash of the content of the chunk of the corresponding file does exist in the chunk hash data structure:
refraining from adding the entry into the chunk hash data structure to prevent duplicate entries in the chunk hash data structure;
stopping deduplication of the corresponding file;
and
moving the corresponding file to a later position in the queue.

19 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/552,880Filed 27 Aug 2019
Published: 4 Mar 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 16/1748
Redundancy elimination performed by the file system: de-duplication implemented within the file system, e.g. based on file segments
G06F 16/215
Design, administration or maintenance of databases: improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or…
G06F 16/137
File access structures, e.g. distributed indices: hash-based
G06F 16/2255
Indexing structures: hash tables