Method for synchronizing data maintained at a plurality of nodes

• US 8,345,707 B2
• Filed: 02/22/2010
• Issued: 01/01/2013
• Est. Priority Date: 06/03/2009
• Status: Active Grant

• Current Assignee: Voxer IP LLC (Voxer, Inc.)
• Original Assignee: Voxer IP LLC (Voxer, Inc.)
• Inventors: Ranney, Matthew J., Stark, Jonathan K.
• Primary Examiner(s): Harper, Kevin C
• Application Number:
  US12/710,264
• Publication Number:
  US 20100309933A1
• Time in Patent Office: 1,044 Days
• Field of Search: None
• US Class Current: 370/464
• 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 user data, comprising:

maintaining user data at a plurality of user 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 user data maintained at the plurality of user 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 user data maintained at the plurality of user data objects;

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

synchronizing the destination tree and the destination user data with the source tree and source user data based on the comparison of the one or more checksum calculations of corresponding nodes in the source tree and the destination tree respectively by 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,

wherein missing nodes or nodes having mismatching checksums value(s) 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 user data maintained at one or more of the plurality of user 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 user data.

3. The method of claim 2, further comprising:

defining a destination view of the user data maintained at one or more of the plurality of user 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 user 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 user data with the source tree and source user 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 user data with the source tree and source user 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 user data in the user data object associated with the selected source node into the user data object associated with the corresponding node in the destination tree if the checksum values are different;

(v) updating the checksum value 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 user data with the source tree and source user 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 user data object with the corresponding node added to the destination tree;

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

(vi) updating the checksum value 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

(ix) 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 user data with the source tree and source user 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, further comprising:

prioritizing the user data maintained at the plurality of user 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.

11. 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.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

14. The method of claim 1, further comprising:

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

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

15. 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.

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

17. 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 user data checksum values for the source user data and the destination user data maintained at the plurality of user data objects associated with the nodes of the source tree and the destination tree respectively.

18. 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.

19. The method of claim 18, 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.

20. The method of claim 19 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 user data objects associated with each of the leaf nodes in the source tree and the destination tree;

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

21. The method of claim 19, 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 user 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 user data checksum value of the user data maintained at the user data objects associated with each of the parent nodes and (ii) the node checksum value of the dependent nodes of the parent nodes respectively.

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

23. The method of claim 1, wherein the user data maintained at the plurality of user data objects comprises one or more of the following types of user 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 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.

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

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

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

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

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

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

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

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

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

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

29. A system for synchronizing user data, the system configured to:

maintain user data at a plurality of user data objects;

assemble 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 user data maintained at the plurality of user data objects;

assemble 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 user data maintained at the plurality of user data objects;

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

synchronize the destination tree and the destination user data with the source tree and source user data based on the comparison of the one or more checksum calculations of corresponding nodes in the source tree and the destination tree respectively by 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,

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

30. The system of claim 29, further configured to:

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

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

31. The system of claim 30, further configured to:

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

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

32. The system of claim 29 wherein the source tree and the destination tree are each assembled using the same algorithm.

33. The system of claim 29, wherein synchronizing the destination tree and the destination user data with the source tree and source user 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.

34. The system of claim 29, wherein synchronizing the destination tree and the destination user data with the source tree and source user 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;

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

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

(vi) 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 user data in the user data object associated with the selected source node into the user data object associated with the corresponding node in the destination tree if the checksum values are different;

(v) updating the checksum value 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.

35. The system of claim 29, wherein synchronizing the destination tree and the destination user data with the source tree and source user 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;

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

(iv) 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 user data object with the corresponding node added to the destination tree;

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

(vi) updating the checksum value 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

(ix) 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.

36. The system of claim 29, wherein synchronizing the destination tree and the destination user data with the source tree and source user 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;

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

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

(vi) 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.

37. The system of claim 36, wherein the system is further configured to assume that 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 synchronized.

38. The system of claim 29, further configured to:

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

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

39. The system of claim 29, further configured to:

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

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

40. The system of claim 39, further configured to:

select a node in the source tree;

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

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

41. The system of claim 40, wherein the synchronization of 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.

42. The system of claim 29, further configured to:

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

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

43. The system of claim 29, further configured to perform 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.

44. The system of claim 43, further configured to perform the synchronization and the second synchronization at the same time.

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

46. The system of claim 29, 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.

47. The system of claim 46, 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.

48. The system of claim 47 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 user data objects associated with each of the leaf nodes in the source tree and the destination tree;

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

49. The system of claim 47, 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 user 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 user data checksum value of the user data maintained at the user data objects associated with each of the parent nodes and (ii) the node checksum value of the dependent nodes of the parent nodes respectively.

50. The system of claim 49, wherein the combination of (i) and (ii) is based on a logical operation.

51. The system of claim 29, wherein the user data maintained at the plurality of user data objects comprises one or more of the following types of user 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 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.

52. The system of claim 29, wherein maintaining the user data at the plurality of user data objects further comprises one of the following:

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

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

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

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

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

53. The system of claim 29, wherein maintaining the user data at the plurality of data objects further comprises maintaining the user data objects in one or more user data object tables.

54. The system of claim 53, further configured to assemble the source tree and the destination tree with source user data and destination user data maintained in one user data object table respectively.

55. The system of claim 53, further configured to assemble the source tree and the destination tree with source user data and destination user data maintained in two or more user data object tables respectively.

56. The system of claim 29, further configured to assemble different source trees and corresponding destination trees from the same user data maintained at the plurality of user data objects respectively.