US 10,540,328 B1Granted

Web-scale distributed deduplication

AssigneeCohesity, Inc.

InventorHariprasad Bhasker Rao Mankude

Life of this patent

Estimating the term…

Abstract

Approaches for parallelized data deduplication. An instruction to perform data deduplication on a plurality of files is received. The plurality of files is organized into two or more work sets that each correspond to a subset of the plurality of files. Responsibility for performing each of said two or more work sets is assigned to a set of nodes in a cluster of nodes. The nodes may be physical nodes or virtual nodes. Each node in the set performs data deduplication on a different work set. In performing data deduplication, each node may store metadata describing where shared chunks of data are maintained in a distributed file system. The shared chunks of data are two or more sequences of bytes which appear in two or more of said plurality of files.

Claims17

Dependent claims

One or more non-transitory machine-readable storage mediums storing one or more sequences of instructions for parallelized data deduplication, which when executed by one or more processors, cause:

in response to receiving an instruction to perform data deduplication on a plurality of files of a big data dataset, organizing said plurality of files into a plurality of work sets based, at least in part, upon file size, wherein each of the plurality of work sets is a corresponding subset of said plurality of files, wherein each corresponding subset having a collective size below a certain predetermined threshold, wherein said data deduplication is a process which reduces an amount of digital storage required to persistently store said big data dataset by removing certain common portions of said files from said digital storage;
assigning a corresponding work set to a corresponding node included in a cluster of nodes, wherein said cluster of nodes itself performs said assignment of responsibility;
and
performing data deduplication in parallel by each of the nodes of the cluster, wherein each of the nodes of the cluster is configured to perform data deduplication on a corresponding assigned work set, wherein performing data deduplication comprises storing metadata describing where shared chunks of data are maintained in a distributed file system, and wherein said shared chunks of data are two or more sequences of bytes which appear in two or more of said plurality of files, wherein said metadata is stored in a parallel database and is accessible from any node of said cluster of nodes and the chunks of data are created from a stream, wherein the boundaries of the chunks of data are identified by using one or more fingerprinting algorithms;
in response to a node of the cluster of nodes finishing performing data deduplication on the corresponding assigned work set, assigning an additional work set to the node of the cluster of nodes, wherein the node of the cluster of nodes is configured to perform data deduplication on the assigned additional work set;
aggregating results of performing said parallel data deduplication in said cluster of nodes;
and
deleting a deduplicated file, wherein metadata associated with the deleted deduplicated file is stored by the nodes of the cluster, wherein the metadata associated with the deleted deduplicated file indicates that the deduplicated file has been deduplicated.

5 more elements

A system for performing parallelized data deduplication, comprising:

one or more processors;
and
one or more non-transitory computer-readable storage mediums storing one or more sequences of instructions, which when executed, cause:
in response to receiving an instruction to perform data deduplication on a plurality of files of a big data dataset, organizing said plurality of files into a plurality of work sets based, at least in part, upon file size, wherein each of the plurality of work sets is a corresponding subset of said plurality of files, wherein each corresponding subset having a collective size below a certain predetermined threshold, wherein said data deduplication is a process which reduces an amount of digital storage required to persistently store said big data dataset by removing certain common portions of said files from said digital storage;
assigning a corresponding work set to a corresponding node included in a cluster of nodes, wherein said cluster of nodes itself performs said assignment of responsibility;
performing data deduplication in parallel by each of the nodes of the cluster, wherein each of the nodes of the cluster is configured to perform data deduplication on a corresponding assigned work set, wherein performing data deduplication comprises storing metadata describing where shared chunks of data are maintained in a distributed file system, and wherein said shared chunks of data are two or more sequences of bytes which appear in two or more of said plurality of files, wherein said metadata is stored in a parallel database and is accessible from any node of said cluster of nodes and the chunks of data are created from a stream, wherein the boundaries of the chunks of data are identified by using one or more fingerprinting algorithms;
in response to a node of the cluster of nodes finishing performing data deduplication on the corresponding assigned work set, assigning an additional work set to the node of the cluster of nodes, wherein the node of the cluster of nodes is configured to perform data deduplication on the assigned additional work set;
aggregating results of performing said parallel data deduplication in said cluster of nodes;
and
deleting a deduplicated file, wherein metadata associated with the deleted deduplicated file is stored by the nodes of the cluster, wherein the metadata associated with the deleted deduplicated file indicates that the deduplicated file has been deduplicated.

7 more elements

A method for parallelized data deduplication, comprising:

in response to receiving an instruction to perform data deduplication on a plurality of files of a big data dataset, organizing said plurality of files into a plurality of work sets based, at least in part, upon file size, wherein each of the plurality of work sets is a corresponding subset of said plurality of files, wherein each corresponding subset having a collective size below a certain predetermined threshold, wherein said data deduplication is a process which reduces an amount of digital storage required to persistently store said big data dataset by removing certain common portions of said files from said digital storage;
assigning a corresponding work set to a corresponding node included in a cluster of nodes, wherein said cluster of nodes itself performs said assignment of responsibility;
performing data deduplication in parallel by each of the nodes of the cluster, wherein each of the nodes of the cluster is configured to perform data deduplication on a corresponding assigned work set, wherein performing data deduplication comprises storing metadata describing where shared chunks of data are maintained in a distributed file system, and wherein said shared chunks of data are two or more sequences of bytes which appear in two or more of said plurality of files, wherein said metadata is stored in a parallel database and is accessible from any node of said cluster of nodes and the chunks of data are created from a stream, wherein the boundaries of the chunks of data are identified by using one or more fingerprinting algorithms;
in response to a node of the cluster of nodes finishing performing data deduplication on the corresponding assigned work set, assigning an additional work set to the node of the cluster of nodes, wherein the node of the cluster of nodes is configured to perform data deduplication on the assigned additional work set;
aggregating results of performing said parallel data deduplication in said cluster of nodes;
and
deleting a deduplicated file, wherein metadata associated with the deleted deduplicated file is stored by the nodes of the cluster, wherein the metadata associated with the deleted deduplicated file indicates that the deduplicated file has been deduplicated.

4 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

One or more non-transitory machine-readable storage mediums storing one or more sequences of instructions for parallelized data deduplication, which when executed by one or more processors, cause:

in response to receiving an instruction to perform data deduplication on a plurality of files of a big data dataset, organizing said plurality of files into a plurality of work sets based, at least in part, upon file size, wherein each of the plurality of work sets is a corresponding subset of said plurality of files, wherein each corresponding subset having a collective size below a certain predetermined threshold, wherein said data deduplication is a process which reduces an amount of digital storage required to persistently store said big data dataset by removing certain common portions of said files from said digital storage;
assigning a corresponding work set to a corresponding node included in a cluster of nodes, wherein said cluster of nodes itself performs said assignment of responsibility;
and
performing data deduplication in parallel by each of the nodes of the cluster, wherein each of the nodes of the cluster is configured to perform data deduplication on a corresponding assigned work set, wherein performing data deduplication comprises storing metadata describing where shared chunks of data are maintained in a distributed file system, and wherein said shared chunks of data are two or more sequences of bytes which appear in two or more of said plurality of files, wherein said metadata is stored in a parallel database and is accessible from any node of said cluster of nodes and the chunks of data are created from a stream, wherein the boundaries of the chunks of data are identified by using one or more fingerprinting algorithms;
in response to a node of the cluster of nodes finishing performing data deduplication on the corresponding assigned work set, assigning an additional work set to the node of the cluster of nodes, wherein the node of the cluster of nodes is configured to perform data deduplication on the assigned additional work set;
aggregating results of performing said parallel data deduplication in said cluster of nodes;
and
deleting a deduplicated file, wherein metadata associated with the deleted deduplicated file is stored by the nodes of the cluster, wherein the metadata associated with the deleted deduplicated file indicates that the deduplicated file has been deduplicated.

5 more elements