ADAPTIVE COLLABORATIVE DE-DUPLICATION

• US 20120150954A1
• Filed: 12/09/2010
• Published: 06/14/2012
• Est. Priority Date: 12/09/2010
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: TOFANO, Jeffrey Vincent
• Granted Patent: US 8,849,898 B2
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

Example apparatus, methods, and computers support adaptive, collaborative de-duplication. One example method includes controlling a computer to compute a correlation between a processing state associated with collaborative data deduplication performed by the computer and an environmental state associated with a collaborative data deduplication environment with which the computer interacts. With the correlation in hand, the method then includes controlling the computer to adapt how the computer participates in collaborative data deduplication based, at least in part, on the correlation. The adaptations can include changing what processing is performed on the computer and what data is stored on the computer.

Claims

1. A data deduplication client apparatus, comprising:

a processor;

a memory; and

an interface to connect the processor, the memory, and a set of logics, the set of logics comprising;

a conditions logic configured to control the data deduplication client apparatus to identify a current condition in a collaborative data deduplication environment;

a performance logic configured to control the client apparatus to identify a data deduplication performance criterion for the client apparatus; and

an adaptation logic configured to selectively reconfigure one or more of, collaborative data deduplication processing performed by the client apparatus, and deduplication related storage performed by the client apparatus, where the selective reconfiguring occurs upon determining that the current condition and the performance criterion do not match a desired deduplication performance profile for the client apparatus.

2. The apparatus of claim 1, where the current condition in the collaborative data deduplication environment concerns one or more of,

a current condition in the client apparatus,

a current condition in a first deduplication server with which the client apparatus is performing collaborative deduplication,

a current condition in a second deduplication server with which the client apparatus is considering performing collaborative deduplication,

a current condition in a first communication path between the client apparatus and the first server,

a current condition in a second communication path between the client apparatus and the second server, and

a current condition in a third communication path between the client apparatus and the first server.

3. The apparatus of claim 2, where the current condition in the client apparatus concerns one or more of, processing cycles available on the client apparatus, memory available on the client apparatus, disk space available to the client apparatus, randomness of data being received at the client apparatus, randomness of the workload at the client apparatus, ingest protocol in place on the client apparatus, and entropy of data to be collaboratively deduplicated by the client apparatus and a collaborating server.

4. The apparatus of claim 2, where the current condition in the first deduplication server concerns one or more of, processing cycles available on the first server, memory available on the first server, disk space available to the first server, a first deduplication approach available on the first server, the randomness of data being ingested at a client computer, the randomness of a workload at the client, and a first deduplication reduction factor achieved by the first server during collaborative deduplication performed with the client apparatus, where the first deduplication reduction factor describes one or more of, the reduction of stored data, and the reduction of transmitted data.

5. The apparatus of claim 2, where the current condition in the second deduplication server concerns one or more of, processing cycles available on the second server, memory available on the second server, disk space available to the second server, a second deduplication approach available on the second server, and a second deduplication reduction factor achieved by the second server during collaborative deduplication performed with a different client apparatus, and where the second deduplication reduction factor describes one or more of, the reduction of stored data, and the reduction of transmitted data.

6. The apparatus of claim 2, where the current condition in the first communication path concerns one or more of, bandwidth available in the first communication path, cost per byte to transmit data over the first communication path, cost per packet to transmit data over the first communication path, latency on the first communication path, error rate on the first communication path, and security on the first communication path,

where the current condition in the second communication path concerns one or more of, bandwidth available in the second communication path, cost per byte to transmit data over the second communication path, cost per packet to transmit data over the second communication path, latency on the second communication path, error rate on the second communication path, and security on the second communication path, and

where the current condition in the third communication path concerns one or more of, bandwidth available in the third communication path, cost per byte to transmit data over the third communication path, cost per packet to transmit data over the third communication path, latency on the third communication path, error rate on the third communication path, and security on the third communication path.

7. The apparatus of claim 1, where the data deduplication performance criterion concerns one or more of, cost to deduplicate data, time to deduplicate data, security of deduplicated data, resources consumed at the client apparatus, and a deduplication reduction factor.

8. The apparatus of claim 1, where the desired deduplication performance profile is a function of one or more of, cost compared to deduplication reduction achieved, time compared to deduplication reduction achieved, and resources compared to deduplication reduction achieved.

9. The apparatus of claim 8, where there are separate data deduplication performance criteria for different workloads associated with archive based deduplication, with nearline based deduplication, and with online based deduplication.

10. The apparatus of claim 1, where the collaborative data deduplication processing performed by the client apparatus includes one or more of, boundary identification, boundary placement, chunking, hashing, sampling, making a duplicate determination, making a similarity determination, and preparing server hints.

11. The apparatus of claim 10, where reconfiguring the client apparatus by adapting the collaborative deduplication processing performed by the client apparatus comprises changing one or more of, what processing is performed on the client apparatus, how much raw data is pushed from the client apparatus, to which server raw data is pushed, from which server data is pulled, the granularity of server hints, and what server hints are provided to a server.

12. The apparatus of claim 1, where deduplication related storage performed by the client apparatus comprises storing, in one or more permuted data structures on the client apparatus, one or more of, raw data, chunked data, a hash for a chunk of data, a sample for a chunk of data, information concerning a deduplication decision for a chunk of data, and a server hint for a chunk of data, where the server hint facilitates a server performing deduplication processing for the chunk of data.

13. The apparatus of claim 12, where reconfiguring the client apparatus by adapting deduplication related storage performed by the client apparatus comprises changing one or more of, the size of a permuted data structure on the client apparatus, the ordering of a permuted data structure on the client apparatus, the type of data stored on the client apparatus, how frequently data stored on the client apparatus is accessed, what event triggers accessing data stored on the client apparatus, what even triggers manipulating data stored on the client apparatus, and the granularity of items for which data is stored.

14. The apparatus of claim 1, where the collaborative data deduplication environment is a computing cloud.

15. The apparatus of claim 1, comprising:

a deduplication logic configured to perform the collaborative deduplication processing performed by the client apparatus.

16. A computer-implemented method, comprising:

controlling a computer to compute a correlation between a processing state associated with collaborative data deduplication performed by the computer and an environmental state associated with a collaborative data deduplication environment with which the computer interacts; and

controlling the computer to adapt how the computer participates in collaborative data deduplication based, at least in part, on the correlation.

17. The computer-implemented method of claim 16, where adapting how the computer participates in collaborative data deduplication comprises adapting one or more of, how boundary identification is performed, how boundary placement is performed, how chunking is performed, how hashing is performed, how sampling is performed, how a duplicate determination is made, how a similarity determination is made, how server hints are prepared, what deduplication processing is performed on the client, how much raw data is pushed from the client into the collaborative data deduplication environment, to which server in the collaborative data deduplication environment raw data is pushed, from which server in the collaborative data deduplication environment data is pulled, and what server hints are provided to a server in the collaborative data deduplication environment.

18. The computer-implemented method of claim 17, where adapting how the computer participates in collaborative data deduplication comprises adapting one or more of, how much raw data is stored on the computer, how much chunked data is stored on the computer, whether a hash for a chunk of data is stored on the computer, whether a sample for a chunk of data is stored on the computer, how much information concerning a deduplication decision for a chunk of data is stored on the computer, how many server hints for a chunk of data are stored on the computer, the size of a permuted deduplication data structure on the client, the ordering of a permuted deduplication data structure on the client, the type of data stored on the client, the frequency of how often data stored on the client is accessed, what event triggers accessing data stored on the client, what even triggers manipulating data stored on the client, and the granularity of items for which data is stored.

19. The computer-implemented method of claim 18, where the collaborative data deduplication is one or more of, cloud based, and client/server based.

20. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a client apparatus participating in adaptive, collaborative data de-duplication control the client apparatus to perform a method, the method comprising:

controlling the client to compute a set of correlations between a set of processing states available for collaborative data deduplication to be performed by the client and a set of environmental states associated with a collaborative data deduplication environment with which the client interacts;

controlling the computer to select a member of the set of processing states based, at least in part, on the set of correlations; and

controlling the computer to engage in collaborative data deduplication according to the member of the set of processing states.