Stream-based data deduplication with cache synchronization

Abstract

Stream-based data deduplication is provided in a multi-tenant shared infrastructure but without requiring “paired” endpoints having synchronized data dictionaries. Data objects processed by the dedupe functionality are treated as objects that can be fetched as needed. As such, a decoding peer does not need to maintain a symmetric library for the origin. Rather, if the peer does not have the chunks in cache that it needs, it follows a conventional content delivery network procedure to retrieve them. In this way, if dictionaries between pairs of sending and receiving peers are out-of-sync, relevant sections are then re-synchronized on-demand. The approach does not require that libraries maintained at a particular pair of sender and receiving peers are the same. Rather, the technique enables a peer, in effect, to “backfill” its dictionary on-the-fly. On-the-wire compression techniques are provided to reduce the amount of data transmitted between the peers.

What is claimed is as follows: 
     
         1 . A system, comprising:
 a parent data processing node;   a child data processing node;   computer program code configured to execute on the parent and child data processing nodes, the computer program code configured to:
 as a stream traverses the parent data processing node, break the stream into chunks; 
 for a particular chunk of the stream, determine, at the parent data processing node and using a directed cyclic graph (DCG) associated with the parent data processing node, a likelihood that the child data processing node already has the chunk; 
 based on the determination, send, from the parent data processing node to the child processing node, one of: the chunk, a reference to the chunk, and a compact data structure representing a sequence of chunks as identified in the directed cyclic graph associated with the parent data processing node; 
 as the stream begins to be decoded at the child data processing node, and for at least one reference or compact data structure in the stream, determine whether the reference or the compact data structure, as the case may be, is associated with a chunk stored in the child data processing system using a directed cyclic graph (DCG) associated with the child data processing node; 
 when the reference or compact data structure is associated with a chunk stored, incorporate data associated with the chunk back into the stream; and 
 when the reference is associated with a chunk or the compact data structure that is missing, perform an on-demand request to the parent data processing node to obtain data corresponding to the chunk or the compact data structure.