Granted Patent B2

US 8,417,674 · App. 12/947,513 · Granted Apr 9, 2013

Abstract

Claims (17)

1. A method for using a source deduplicating store to update a target deduplicating store with information representing how data objects change over time, said method comprising:

at the source deduplicating store, organizing unique content of each data object as a plurality of content segments and storing the content segments in a data store, wherein the source deduplicating store contains unique content and avoids storing duplicate content;

at the source deduplicating store, for each data object, creating an organized arrangement of hash structures, wherein each structure, for a subset of the hash structures, includes a hash signature for a corresponding content segment and is associated with a reference to the corresponding content segment, wherein the logical organization of the arrangement represents the logical organization of the content segments as they are represented within the data object;

at the source deduplicating store, for each data object, maintaining an organized arrangement of temporal structures to represent a corresponding data object over time, wherein each structure is associated with a temporal state of the data object and wherein the logical arrangement of structures is indicative of the changing temporal states of the data object, and wherein each temporal state is associated with a set of hash structures representing all content of the data object that has changed relative to a prior temporal state;

at the target deduplicating store, organizing unique content of each data object as a plurality of content segments and storing the content segments in a data store, wherein the target deduplicating store contains unique content and avoids storing duplicate content;

at the target deduplicating store, for each data object, maintaining an organized arrangement of hash structures, that is at least a subset of the hash structures at said first deduplicating store;

at the target deduplicating store, for each data object, maintaining an organized arrangement of temporal structures to represent a corresponding data object over time, wherein said organized arrangement of temporal structures is at least a subset of the temporal structures at said source deduplicating store, representing a subset of the temporal states;

in response to a request to update the target deduplicating store with information from said source deduplicating store, finding a temporal state that is common to the source and target deduplicating stores and that is within temporal proximity of the current state of the source deduplicating store; and

compiling a set of hash signatures for the content that has changed from the common state to the current temporal state of the source deduplicating store and sending that set of hash signatures to the target deduplicating store so it can update its organized arrangement of hash structures to represent the content of the data object up to the current temporal state of the source deduplicating store,

so that after the update, each of the source and target deduplicating stores includes representations of the data object indicating how the data object has changed over time.

2. The method of claim 1 , further including maintaining a history of the hash signatures that each deduplicating store contains, and for hash signatures in the set of hash signatures that are new to the target deduplicating store, sending the corresponding content segments from the source deduplicating store so that the target deduplicating store may update its data store with the new content.

3. The method of claim 1 , wherein the temporal state that is in proximity to the current state of the target deduplicating store is a nearest neighbor state of the current state.

4. The method of claim 1 , wherein the temporal state that is in proximity to the current state of the target deduplicating store is an ancestor state of the current state.

5. The method of claim 1 , wherein the temporal state that is in proximity to the current state of the target deduplicating store is a child state of the current state.

6. The method of claim 3 , wherein the nearest neighbor state is the state which is connected by a set of edges whose sum is lower than the sum of any other set of edges.

7. The method of claim 1 , wherein the logical arrangement of structures is a tree data structure that contains branching.

8. The method of claim 2 , further comprising recording, at the current state, to what states the content segments corresponding to the current temporal state has been sent.

Assignments (8)