Synchronized data deduplication

• US 10,540,327 B2
• Filed: 08/23/2017
• Issued: 01/21/2020
• Est. Priority Date: 07/08/2009
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Ngo, David, Muller, Marcus S.
• Primary Examiner(s): Bibbee, Jared M
• Application Number:
  US15/684,812
• Publication Number:
  US 20180075055A1
• Time in Patent Office: 881 Days
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A system and method for data deduplication is presented. Data received from one or more computing systems is deduplicated, and the results of the deduplication process stored in a reference table. A representative subset of the reference table is shared among a plurality of systems that utilize the data deduplication repository. This representative subset of the reference table can be used by the computing systems to deduplicate data locally before it is sent to the repository for storage. Likewise, it can be used to allow deduplicated data to be returned from the repository to the computing systems. In some cases, the representative subset can be a proper subset wherein a portion of the referenced table is identified shared among the computing systems to reduce bandwidth requirements for reference-table synchronization.

Claims

1. A computer-implemented data deduplication method, the method comprising:

with one or more computing systems of a shared storage system that maintains a deduplicated data store and that is in networked communication with a plurality of client computing systems that are physically separate from the shared storage system and share the deduplicated data store;

determining whether a first data segment included in data generated by an application executing on a first computing system of the plurality of client computing systems is already stored in the shared storage system;

if the first data segment is not already stored in the shared storage system, updating a central reference table of the shared storage system to include an entry corresponding to the first data segment;

determining a first subset of the references in the central reference table for inclusion in a first updated partial instantiation of the central reference table based on one or more of data segment size information and data segment utilization frequency information, the first subset including a reference to the first data segment;

transmitting the first updated partial instantiation of the central reference table from the shared storage system to a second computing system of the plurality of client computing systems such that, subsequent to said transmitting, a partial instantiation of the central reference table local to the second computing system includes the entry corresponding to the first data segment;

determining a second subset of the references in the central reference table for inclusion in a second updated partial instantiation of the central reference table based on one or more of data segment size information and data segment utilization frequency information, the second subset different than the first subset; and

transmitting the second updated partial instantiation of the central reference table to a third computing system of the plurality of client computing systems such that, subsequent to transmission of the first and second updated partial instantiations, a partial instantiation of the central reference table local to the third computing system is different from the partial instantiation of the central reference table local to the second computing system, and does not include the entry corresponding to the first data segment.

2. The method of claim 1, wherein the partial instantiations of the central reference table local to the second and third computing systems are proper subsets of the central reference table.

3. The method of claim 1, wherein said determining the first subset is based on a combination of data segment utilization frequency information and data segment size information.

4. The method of claim 3, wherein the combination comprises a weighted combination of data segment utilization rate and data segment size.

5. The method of claim 1 wherein said determining the first subset is in response to receiving the first data segment from the first computing system at the shared storage system.

6. The method of claim 5 further comprising storing the first data segment in the shared storage system.

7. The method of claim 1 further comprising, subsequent to said transmitting the first updated partial instantiation of the central reference table, receiving a signature corresponding to the first data segment from the second computing system at the shared storage system, without receiving the first data segment itself.

8. A system, comprising:

a shared deduplicated storage repository comprising computer memory; and

a server system including one or more computing devices comprising computer hardware, the server system in networked communication with a plurality of client computing systems which are physically separate from the server system, the server system configured to;

determine whether a first data segment included in data generated by an application executing on a first computing system of the plurality of client computing systems is already stored in the shared deduplicated storage repository;

if the first data segment is not already stored in the shared deduplicated storage repository, update a central reference table of the shared storage system to include an entry corresponding to the first data segment;

select a first subset of the references in the central reference table for inclusion in a first updated partial instantiation of the central reference table based on one or more of data segment size information and data segment utilization frequency information, the first subset including a reference to the first data segment;

transmit the first updated partial instantiation of the central reference table from the server system to a second computing system of the plurality of client computing systems such that, subsequent to the transmission of the updated partial instantiation of the central reference table, a partial instantiation of the central reference table local to the second computing system includes the entry corresponding to the first data segment;

select a second subset of the references in the central reference table for inclusion in a second updated partial instantiation of the central reference table based on one or more of data segment size information and data segment utilization frequency information, the second subset different than the first subset; and

transmit the second updated partial instantiation of the central reference table to a third computing system of the plurality of client computing systems such that, subsequent to transmission of the first and second updated partial instantiations, a partial instantiation of the central reference table local to the third computing system is different from the partial instantiation of the central reference table local to the second computing system, and does not include the entry corresponding to the first data segment.

9. The system of claim 8, wherein the partial instantiations of the central reference table local to the second and third computing systems are proper subsets of the central reference table.

10. The system of claim 8, wherein the server system is further configured to determine additional entries to include in the first subset based on a combination of data segment utilization frequency information and data segment size information.

11. The system of claim 10, wherein the combination comprises a weighted combination of data segment utilization rate and data segment size.

12. The system of claim 8 wherein the server system receives the first data segment from the first computing system prior to determining whether the first data segment included in the data generated by the application is already stored in the shared deduplicated storage repository.

13. The system of claim 12 wherein the server system is further configured to store the first data segment in the shared deduplicated storage repository.

14. The system of claim 8 wherein subsequent to transmission of the first updated partial instantiation of the central reference table to the second computing system, the server system receives from the second computing system a signature corresponding to the first data segment, and wherein the server system is configured to update the central reference table in response to receipt of the signature.