Playback graph for data synchronization

• US 20040199548A1
• Filed: 04/03/2003
• Published: 10/07/2004
• Est. Priority Date: 04/03/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, Michaeljon
• Granted Patent: US 7,308,465 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Embodiments of the present invention pertain to a data structure designed to manage object relationships to actual transactions. The data structure is at least an efficient substitute for a simple ordered transaction log. The data structure allows for pre-playback graph pruning that reduces the overall time required to complete a playback operation. It also allows for more robust error handling when a given transaction fails for non-transport related errors (i.e., the business rules or security rights have changed) by keeping the graph updated on a per-object basis.

Claims

1. A method of synchronizing data shared between multiple applications, the method comprising:

processing a plurality of data modification operations associated with a first application;

constructing a playback graph based on the plurality of data modification operations; and

playing back to a second application a set of data modification operations associated with the playback graph.

2. The method of claim 1, wherein the first and second applications are multiple instances of the same application.

3. The method of claim 1, wherein the first application is implemented on a client device and the second application is implemented on a server.

4. The method of claim 1, wherein the method further comprises eliminating at least one unnecessary data modification operation from the playback graph.

5. The method of claim 1, wherein constructing a playback graph comprises constructing an object update graph that tracks a plurality of data modification operations in association with at least one related object.

6. The method of claim 5, wherein playing back the set of data modification operations comprises playing back to a second application a plurality of data modification operations associated with the object update graph.

7. The method of claim 5, wherein the method further comprises eliminating at least one unnecessary data modification operation from the object update graph.

8. The method of claim 5, wherein constructing a playback graph further comprises constructing an object update graph that tracks at least one object update operation.

9. The method of claim 5, wherein constructing a playback graph further comprises constructing an object update graph that tracks multiple consecutive object update operations.

10. The method of claim 9, wherein constructing an object update graph further comprises merging a plurality of consecutive object update operations so as to enable the elimination of at least one object update operation.

11. The method of claim 10, wherein merging the plurality of consecutive object update operations comprises merging object update operations on an attribute-by-attribute basis.

12. The method of claim 5, wherein constructing a playback graph further comprises constructing an object update graph that tracks at least one object create operation.

13. The method of claim 5, wherein constructing a playback graph further comprises constructing an object update graph that tracks an object create operation that is followed by an object update operation.

14. The method of claim 13, wherein constructing an object update graph further comprises merging the object update operation with the object create operation so as to enable the elimination of the object update operation.

15. The method of claim 14, wherein merging the object update operation with the object create operation comprises merging on an attribute-by-attribute basis.

16. The method of claim 5, wherein constructing a playback graph further comprises constructing an object update graph that tracks an object delete operation with a related base object.

17. The method of claim 16, further comprising deleting at least one data modification operation linked to the related base object.

18. The method of claim 17, further comprising:

encountering an associated object while deleting said at least one data modification operation linked to the related base object; and

determining whether the associated object is a freestanding associated object or a dependent associated object.

19. The method of claim 18, further comprising deleting at least one data modification operation linked to a dependent associated object.

20. The method of claim 18, further comprising re-associating a freestanding associated object.

21. The method of claim 16, further comprising determining whether the related base object was created during an on-line mode or an off-line mode.

22. The method of claim 21, wherein when the related base object was created during an on-line mode, the method further comprises eliminating at least one data modification operation linked to the related base object.

23. The method of claim 21, wherein when the related base object was created during an off-line mode, the method further comprises eliminating at least one data modification operation that occurred during the on-line mode and is linked to the related base object.

24. The method of claim 23, wherein when the related base object was created during an off-line mode, the method further comprises making a notation that additional eliminating of data modification operations are required when the on-line mode is resumed.

25. A method of synchronizing data shared between multiple applications, the method comprising:

creating a first transaction record associated with data modification operations carried out with a first application;

eliminating at least one unnecessary data modification operation from the first transaction record;

creating a second transaction record associated with data modification operations carried out with a second application;

eliminating at least one unnecessary data modification operation from the second transaction record;

merging the first and second transaction records so as to create a combined transaction record; and

playing back to a third application a plurality of data modification operations associated with the combined transaction record.

26. The method of claim 25, wherein at least two of the first, second and third applications are multiple instances of the same application.

27. The method of claim 25, wherein:

creating the first transaction record comprises creating a first playback graph;

eliminating at least one unnecessary data modification operation from the first transaction record comprises eliminating at least one unnecessary data modification operation from the first playback graph;

creating the second transaction record comprises creating a second playback graph;

eliminating at least one unnecessary data modification operation from the second transaction record comprises eliminating at least one unnecessary data modification operation from the second playback graph;

merging the first and second transaction records comprises merging the first and second playback graphs so as to construct a combination playback graph; and

playing back to a third application a plurality of data modification operations associated with the combined transaction record comprises playing back to a third application a plurality of data modification operations associated with the combination playback graph.

28. The method of claim 27, wherein at least two of the first, second and third applications are multiple instances of the same application.

29. The method of claim 25, wherein:

creating the first transaction record comprises constructing a first object update graph that tracks a plurality of data modifications in association with their corresponding objects;

eliminating at least one unnecessary data modification operation from the first transaction record comprises eliminating at least one unnecessary data modification operation from the first object update graph;

creating the second transaction record comprises constructing a second object update graph that tracks a plurality of data modifications in association with their corresponding objects;

eliminating at least one unnecessary data modification operation from the second transaction record comprises eliminating at least one unnecessary data modification operation from the second object update graph;

merging the first and second transaction records comprises merging the first and second object update graphs so as to create a combination object update graph; and

playing back to a third application a plurality of data modification operations associated with the combined transaction record comprises playing back to a third application a plurality of data modification operations associated with the combination object update graph.

30. The method of claim 29, wherein at least two of the first, second and third applications are multiple instances of the same application.

31. A method of synchronizing data shared between multiple applications, the method comprising:

performing a plurality of data modification operations in association with a first application;

maintaining a transaction log that reflects the plurality of data modification operations;

preprocessing the transaction log so as to create a preprocessed transaction log; and

playing back to a second application a plurality of data modification operations associated with the preprocessed transaction log.

32. The method of claim 31, wherein preprocessing the transaction log comprises eliminating at least one unnecessary data modification operation.

33. The method of claim 31, wherein preprocessing the transaction log comprises constructing a playback graph that corresponds to the transaction log.

34. The method of claim 33, wherein playing back the plurality of data modification operations comprises playing back to a second application a plurality of data modification operations associated with the playback graph.

35. The method of claim 33, wherein constructing a playback graph comprises constructing an object update graph that tracks a plurality of data modifications in association with at least one related object.

36. The method of claim 35, wherein playing back the plurality of data modification operations comprises playing back to a second application a plurality of data modification operations associated with the object update graph.

37. The method of claim 33, wherein preprocessing further comprises eliminating at least one unnecessary data modification operation.

38. A method of synchronizing data shared between multiple applications, the method comprising:

performing a plurality of data modification operations in association with a first application;

maintaining a transaction log that reflects the plurality of data modification operations;

creating an object information layer that is independent of the transaction log and records information from the transaction log on an object level; and

playing back to a second application a plurality of data modification operations associated with the object information layer.

39. The method of claim 38, wherein preprocessing the transaction log comprises eliminating at least one unnecessary data modification operation from the transaction log.

40. The method of claim 38, wherein preprocessing the transaction log comprises constructing a playback graph that corresponds to the transaction log.

41. The method of claim 40, wherein playing back the plurality of data modification operations comprises playing back to a second application a plurality of data modification operations associated with the playback graph.

42. The method of claim 40, wherein constructing a playback graph comprises constructing an object update graph that tracks a plurality of data modifications in association with at least one related object.

43. The method of claim 42, wherein playing back the plurality of data modification operations comprises playing back to a second application a plurality of data modification operations associated with the object update graph.

44. The method of claim 40, wherein preprocessing further comprises eliminating at least one unnecessary data modification operation.