METHOD FOR SYNCHRONIZING DATA MAINTAINED AT A PLURALITY OF NODES

• US 20100309933A1
• Filed: 02/22/2010
• Published: 12/09/2010
• Est. Priority Date: 06/03/2009
• Status: Active Grant

• Current Assignee: Voxer IP LLC (Voxer, Inc.)
• Original Assignee: Rebelvox LLC (Voxer, Inc.)
• Inventors: STARK, Jonathan K., RANNEY, Matthew J.
• Granted Patent: US 8,345,707 B2
• Time in Patent Office: Days
• US Class Current: 370/503
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

A method for synchronizing data maintained at a plurality of data objects. The method involves assembling source and destination trees, each of the source and destination trees including a root node and one or more dependent nodes associated with source and destination data maintained at the plurality of data objects respectively. After the trees are assembled, a checksum calculation is performed for the nodes of the source tree and the destination tree based on the associated source data and the associated destination data maintained at the plurality of data objects respectively. The destination tree and the destination data are synchronized with the source tree and source data based on the comparison of the checksum calculations of corresponding nodes in the source tree and the destination tree. Missing nodes or nodes having mismatching checksums in the destination tree are identified and either added or modified to match the corresponding node or nodes in the source tree, while the data in the source data objects are fetched and copied by the destination data object corresponding to the added and/or modified nodes in the destination tree.

Claims

1. A method for synchronizing data, comprising:

maintaining data at a plurality of data objects;

assembling a source tree, the source tree including a source root node and one or more dependent source nodes, the nodes of the source tree associated with source data maintained at the plurality of data objects;

assembling a destination tree, the destination tree including a destination root node and one or more dependent destination nodes, the nodes of the destination tree associated with destination data maintained at the plurality of data objects;

performing one or more checksum calculations for the nodes of the source tree and the destination tree based on the associated source data and the associated destination data maintained at the plurality of data objects respectively; and

synchronizing the destination tree and the destination data with the source tree and source data based on the comparison of the one or more checksum calculations of corresponding nodes in the source tree and the destination tree respectively,

wherein missing nodes or nodes having mismatching checksums in the destination tree are added or modified to match the corresponding node or nodes in the source tree.

2. The method of claim 1, further comprising:

defining a source view of the data maintained at one or more of the plurality of data objects; and

assembling the source tree, including the source root node and the one or more source dependent nodes, representative of the defined source view of the data.

3. The method of claim 2, further comprising:

defining a destination view of the data maintained at one or more of the plurality of data objects; and

assembling the destination tree, including the destination root node and the destination dependent nodes, representative of the defined destination view of the data.

4. The method of claim 1 wherein the source tree and the destination tree are each assembled using the same algorithm.

5. The method of claim 1, wherein synchronizing the destination tree and the destination data with the source tree and source data based on the one or more comparisons of the checksum calculations of corresponding nodes in the source tree and the destination tree further comprises:

comparing checksum values for the source root node and the destination root node; and

assuming the source tree and the destination tree are synchronized if the checksums values for the source root node and the destination root node are the same.

6. The method of claim 1, synchronizing the destination tree and the destination data with the source tree and source data based on the one or more comparisons of the checksum calculations of corresponding nodes in the source tree and the destination tree further comprises:

ascertaining when the checksum values for the source root node and the destination root node are different; and

traversing the source tree and the destination tree when the ascertained checksum values for the source root note and the destination root note are different by;

(i) selecting a dependent node in the source tree;

(ii) ascertaining if there is a corresponding node in the destination tree corresponding to the selected node in the source tree;

(iii) ascertaining if the corresponding node in the destination tree has a different checksum value than the selected node in the source tree;

(iv) copying the data in the data object associated with the selected source node into the data object associated with the corresponding node in the destination tree if the checksum values are different;

(v) updating the checksum of the corresponding node in the destination tree to match the selected node in the source tree;

(vi) updating and comparing the checksum values for the source root node and the destination root node after performing (i) through (v);

(vii) successively repeating (i) through (vi) until the checksum values of the source root node and the destination root node match; and

(viii) terminating the traversal of the source tree and the destination tree when the checksum values for the source root node and the destination root node match.

7. The method of claim 1, wherein synchronizing the destination tree and the destination data with the source tree and source data based on the one or more comparisons of the checksum calculations of corresponding nodes in the source tree and the destination tree further comprises:

ascertaining when the checksum values for the source root node and the destination root node are different; and

traversing the source tree and the destination tree when the ascertained checksum values for the source root note and the destination root note are different by;

(i) selecting a dependent node in the source tree;

(ii) ascertaining if there is a corresponding node in the destination tree corresponding to the selected node in the source tree;

(iii) adding the corresponding node to the destination tree if there is no corresponding node in the destination tree;

(iv) associating a data object with the corresponding node added to the destination tree;

(v) copying the data in the data object associated with the selected source node into the data object associated with the added node in the destination tree;

(vi) updating the checksum of the added corresponding node in the destination tree to match the selected node in the source tree;

(vii) updating and comparing the checksum values for the source root node and the destination root node after performing (i) through (vi); and

(viii) successively repeating (i) through (vii) until the checksum values of the source root node and the destination root node match; and

(iix) terminating the traversal of the source tree and the destination tree when the checksum values for the source root node and the destination root node match.

8. The method of claim 1, wherein synchronizing the destination tree and the destination data with the source tree and source data based on the one or more comparisons of the checksum calculations of corresponding nodes in the source tree and the destination tree further comprises:

ascertaining when the checksum values for the source root node and the destination root node are different;

traversing the source tree and the destination tree when the ascertained checksum values for the source root note and the destination root note are different by;

(i) selecting a dependent node in the source tree;

(ii) ascertaining if there is a corresponding node in the destination tree corresponding to the selected node in the source tree;

(iii) comparing the checksums values of the selected source node in the source tree and the corresponding node in the destination tree if there is a corresponding node in the destination tree; and

(iv) assuming the selected node in the source tree and the corresponding node in the destination tree are synchronized if the compared checksum values are the same.

9. The method of claim 8, further comprising assuming any source and destination nodes, dependent on the selected node in the source tree and the corresponding node in the destination tree having matching checksum values, are also synchronized.

10. The method of claim 1, wherein synchronizing the destination tree and the destination data with the source tree and source data based on the one or more comparisons of the checksum calculations of corresponding nodes in the source tree and the destination tree further comprises traversing the nodes of the source tree using an optimization algorithm to identify the nodes of the destination tree likely to be missing and/or have mismatching checksum values relative to the corresponding nodes of the source tree.

11. The method of claim 1, further comprising:

prioritizing the data maintained at the plurality of data objects in a priority order; and

performing the synchronization of the nodes of the source tree and the destination tree in the priority order.

12. The method of claim 1, further comprising:

ascertaining a select portion of the source tree and the destination tree; and

synchronizing the differences between only the select portion of the source tree and the destination tree.

13. The method of claim 12, further comprising:

selecting a node in the source tree;

synchronizing the node or nodes of the source tree and the destination tree at the selected node and above the selected node; and

not synchronizing the node or nodes of the source tree and the destination tree below the selected node.

14. The method of claim 13, wherein synchronizing the node or nodes of the source tree and the destination tree above the selected node further comprises:

copying the checksum value of the selected source tree node at the corresponding selected destination tree node; and

setting a flag indicating that the node or nodes below the selected nodes of the source and destination trees have not been synchronized.

15. The method of claim 1, further comprising:

ascertaining if data intended for synchronizing one or more destination data objects is stale; and

not updating the destination tree or accepting the stale data at the one or more destination data object for stale data.

16. The method of claim 1, further comprising performing a second synchronization between the source tree and the destination tree, wherein during the second synchronization, the destination tree is the source tree and the destination tree is the source tree.

17. The method of claim 16, further comprising performing the synchronization and the second synchronization at the same time.

18. The method of claim 1, wherein performing the one or more checksum calculations for the nodes of the source tree and the destination tree further comprises computing data checksum values for the source data and the destination data maintained at the plurality of data objects associated with the nodes of the source tree and the destination tree respectively

19. The method of claim 1, wherein each of the one or more nodes in the source tree and the destination tree is further characterized as one of the following:

(i) a parent node having one or more dependent nodes;

or

(ii) a leaf node having no dependent nodes.

20. The method of claim 19, wherein performing the one or more checksum calculations for the nodes in the source tree and destination tree, including parent nodes and leaf nodes, further comprises calculating a node checksum value for each of the nodes in the source tree and destination tree respectively.

21. The method of claim 20 wherein calculating the node checksum value for each node characterized as a leaf node in the source tree and the destination tree further comprises:

identifying the data objects associated with each of the leaf nodes in the source tree and the destination tree;

calculating the node checksum using a checksum algorithm on the data maintained at the identified data objects associated with each of the leaf nodes in the source tree and the destination tree respectively.

22. The method of claim 20, wherein calculating the node checksum value for each node characterized as a parent node in the source tree and the destination tree further comprises:

identifying the data objects associated with each of the parent nodes and the dependent nodes of the parent nodes in the source tree and the destination tree respectively; and

calculating the node checksum value for each of the parent nodes based on a combination of (i) a data checksum of the data maintained at the data objects associated with each of the parent nodes and (ii) the node checksum of the dependent nodes of the parent nodes respectively.

23. The method of claim 22, wherein the combination of (i) and (ii) is based on a logical operation.

24. The method of claim 1, wherein the data maintained at the plurality of data objects comprises one or more of the following types of data:

(a) voice media;

(b) video media;

(c) text media;

(d) sensor data;

(e) image media;

(f) the media of a conversation;

(g) a conversation list;

(h) a list of contacts;

(i) participants of a conversation;

(j) presence status of the participants of a conversation;

(k) a user domain;

(l) groups of contacts;

(m) records of media that has been reviewed;

(n) groups of conversations;

(o) device nodes;

(p) lists of streams of media of conversations;

(q) streams of media;

or

(r) any predefined data.

25. The method of claim 1, wherein maintaining the data at the plurality of data objects further comprises one of the following:

(a) maintaining the data at the plurality of data objects at a storage location;

(b) maintaining the data at the plurality of data objects on a computing device;

(c) maintaining the data at the plurality of data objects on a communication device;

(d) maintaining the data at the plurality of data objects in a database;

(e) any combination of (a) through (d).

26. The method of claim 1, wherein maintaining the data at the plurality of data objects further comprises maintaining the data objects in one or more data object tables.

27. The method of claim 26, further comprising assembling the source tree and the destination tree with source data and destination data maintained in one data object table respectively.

28. The method of claim 26, further comprising assembling the source tree and the destination tree with source data and destination data maintained in two or more data object tables respectively.

29. The method of claim 1, further comprising assembling different source trees and corresponding destination trees from the same data maintained at the plurality of data objects respectively.