Systems and methods for providing relational and hierarchical synchronization services for units of information manageable by a hardware/software interface system

• US 20050044530A1
• Filed: 10/24/2003
• Published: 02/24/2005
• Est. Priority Date: 08/21/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev
• Granted Patent: US 7,483,923 B2
• Time in Patent Office: Days
• US Class Current: 717/122
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/30 Profiles
• CPC Class Codes: H04L 69/08 Protocols for interworking; Protocol conversion
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Several embodiments of the present invention comprise a storage platform that provides a synchronization service that (i) allows multiple instances of the storage platform (each with its own data store) to synchronize parts of their content according to a flexible set of rules, and (ii) provides an infrastructure for third parties to synchronize the data store of the storage platform of the present invention with with other data sources that implement proprietary protocols. However, it is possible that a conflict might arise in a number of synchronization scenarios. For example, A1 and B2 may have been changes made to the same change unit, or A1 might be a deletion to the same change unit that B2 was modifying. While some of these conflicts can be resolved using the conflict resolution options discussed ealier herein, certain conflicts provide particularly difficult challenges, and these challenges and their solutions are discussed herein.

Claims

1. A method for synchronizing a plurality of instances for a data platform, including without limitation a replica or a data source with or without an adapter, and said plurality of instances comprising a sync community, said method comprising:

uniquely enumerating changes in sequence (e.g., increasing numbers) on an instance by instance basis (a change number);

maintaining a vector for each instance, said vector comprising a most recent change number for said instance, as well as a most recent known change number for each other instances from among said plurality of instances that are known to said instance (each a known instance), wherein said vector (comprising change numbers for each known instance) inherently represents all changes that have been made to said instance.

2. The method of claim 1 wherein said change number comprises a unique identification number for said instance and a relative incremental count of changes made to said instance.

3. The method of claim 1 wherein a first instance, to partially synchronize with a second instance, requests changes from said second instance by sending to said second instance its vector, and wherein said second instance, based on the vector it receives from said first instance, sends to said first instance only those changes that said first vector has not yet received.

4. The method of claim 3 wherein said second instance, based on the vector it receives from said first instance, further determines that said first instance has changes that it, said second instance, has not yet received, and sends its own vector to said first instance to request these changes, and wherein said first instance, based on the vector it receives from said second instance, sends to said second instance only those changes that said second vector has not yet received.

5. The method of claim 1 wherein a first instance, when changing a first Item to relate (via a Relationship) to a second Item that was not previously being synchronized (e.g, an out-of-scope Item), to send all change information pertaining to said second Item to a second instance when synchronizing with said second instance so that said second Item in said second instance is synchronized with said second Item in said first instance.

6. The method of claim 1 wherein, when by default operation a parent Item is transmited before a child Item to said parent Item, and wherein a plurality of changes are typically transmitted in sequential order of a plurality of change numbers corresponding to said changes during a synchronization, and wherein between synchronizations a child Item is changed and then a parent Item is changed in a first instance, any change units pertaining to said child Item are sent from said first instance to a second instance during a synchronization only after all change units pertaining to the parent Item are sent.

7. The method of claim 1 wherein, for an Item deleted by a first instance, a tombstone comprising the identification of the Item deleted is created, and said tombstone is sent as part of a synchronization to notify a second instance to identify the Item to be deleted in said second instance.

8. The method of claim 7 wherein, for a first instance having a parent Item and a first child Item to said parent Item, when said child Item is deleted and then said parent Item is deleted, said first instance sending only the change to said parent Item (that is, the tombstone for said parent Item) to a second instance during a synchronization where (a) the deletion of a parent Item automatically results in the deletion of all children Items for said parent or (b) the second instance, receiving the tombstone for the parent Item, proceeds to delete the parent Item and automatically deletes the child Item.

9. The method of claim 1, wherein a first Relationship and a second Relationship of a first instance swap names using a temporary name element such that, in order, (a) the name of the first Relationship is transferred to said temporary name element, (b) the name of the second Relationship is transferred to said first Relationship, and (c) said name stored in the temporary name element is copied to said second Relationship, and wherein said first instance synchronizes with a second instance and sends a duo of change units representing, in order, (i) the new name for said first Relationship and (ii) the new name for said second Relationship, and wherein effecting the first of said duo of changes (a first change) results in an error in the second instance because a result of said first change is for the first Relationship and the second Relationship having the same name (an attempted change), a method by which said second instance proceed to copy said name of the first Relationship to a local temporary name element and:

if, during the synchronization, a subsequent change is received for copying the name of said second Relationship to said first relationship occurs, then performing said change as well as also copying said name in said local temporary name element to said first Relationship; and

if, during the synchronization, a subsequent change is not received for copying the name of said second Relationship to said first relationship occurs, then raising a conflict regarding for the attempted change.

10. The method of claim 1 wherein, for synchronization between a first instance on a storage platform that allows a dangling relative reference and a second instance on a storage platform that does not allow a dangling relative reference that include at least one change to a relative reference and at least one other change (in that order), sending said change to said relative references after said one other changes.

11. A system for synchronizing a plurality of instances for a data platform, including without limitation a replica or a data source with or without an adapter, and said plurality of instances comprising a sync community, said system comprising:

a subsystem for uniquely enumerating changes in sequence (e.g., increasing numbers) on an instance by instance basis (a change number);

a subsystem for maintaining a vector for each instance, said vector comprising a most recent change number for said instance, as well as a most recent known change number for each other instances from among said plurality of instances that are known to said instance (each a known instance), wherein said vector (comprising change numbers for each known instance) inherently represents all changes that have been made to said instance.

12. The system of claim 11 wherein said change number comprises a unique identification number for said instance and a relative incremental count of changes made to said instance.

13. The system of claim 11 further comprising a subsystem wherein a first instance, to partially synchronize with a second instance, requests changes from said second instance by sending to said second instance its vector, and wherein said second instance, based on the vector it receives from said first instance, sends to said first instance only those changes that said first vector has not yet received.

14. The system of claim 13 further comprising a subsystem wherein said second instance, based on the vector it receives from said first instance, further determines that said first instance has changes that it, said second instance, has not yet received, and sends its own vector to said first instance to request these changes, and wherein said first instance, based on the vector it receives from said second instance, sends to said second instance only those changes that said second vector has not yet received.

15. The system of claim 11 further comprising a subsystem wherein a first instance, when changing a first Item to relate (via a Relationship) to a second Item that was not previously being synchronized (e.g, an out-of-scope Item), to send all change information pertaining to said second Item to a second instance when synchronizing with said second instance so that said second Item in said second instance is synchronized with said second Item in said first instance.

16. The system of claim 11 further comprising a subsystem wherein, when by default operation a parent Item is transmited before a child Item to said parent Item, and wherein a plurality of changes are typically transmitted in sequential order of a plurality of change numbers corresponding to said changes during a synchronization, and wherein between synchronizations a child Item is changed and then a parent Item is changed in a first instance, any change units pertaining to said child Item are sent from said first instance to a second instance during a synchronization only after all change units pertaining to the parent Item are sent.

17. The system of claim 11 further comprising a subsystem wherein, for an Item deleted by a first instance, a tombstone comprising the identification of the Item deleted is created, and said tombstone is sent as part of a synchronization to notify a second instance to identify the Item to be deleted in said second instance.

18. The system of claim 17 further comprising a subsystem wherein, for a first instance having a parent Item and a first child Item to said parent Item, when said child Item is deleted and then said parent Item is deleted, said first instance sending only the change to said parent Item (that is, the tombstone for said parent Item) to a second instance during a synchronization where (a) the deletion of a parent Item automatically results in the deletion of all children Items for said parent or (b) the second instance, receiving the tombstone for the parent Item, proceeds to delete the parent Item and automatically deletes the child Item.

19. The system of claim 11, further comprising a subsystem wherein a first Relationship and a second Relationship of a first instance swap names using a temporary name element such that, in order, (a) the name of the first Relationship is transferred to said temporary name element, (b) the name of the second Relationship is transferred to said first Relationship, and (c) said name stored in the temporary name element is copied to said second Relationship, and wherein said first instance synchronizes with a second instance and sends a duo of change units representing, in order, (i) the new name for said first Relationship and (ii) the new name for said second Relationship, and wherein effecting the first of said duo of changes (a first change) results in an error in the second instance because a result of said first change is for the first Relationship and the second Relationship having the same name (an attempted change), a method by which said second instance proceed to copy said name of the first Relationship to a local temporary name element and:

if, during the synchronization, a subsequent change is received for copying the name of said second Relationship to said first relationship occurs, then performing said change as well as also copying said name in said local temporary name element to said first Relationship; and

if, during the synchronization, a subsequent change is not received for copying the name of said second Relationship to said first relationship occurs, then raising a conflict regarding for the attempted change.

20. The system of claim 11 further comprising a subsystem wherein, for synchronization between a first instance on a storage platform that allows a dangling relative reference and a second instance on a storage platform that does not allow a dangling relative reference that include at least one change to a relative reference and at least one other change (in that order), sending said change to said relative references after said one other changes.

21. A computer-readable medium comprising computer-readable instructions for synchronizing a plurality of instances for a data platform, including without limitation a replica or a data source with or without an adapter, and said plurality of instances comprising a sync community, said computer-readable instructions comprising instructions for:

uniquely enumerating changes in sequence (e.g., increasing numbers) on an instance by instance basis (a change number);

maintaining a vector for each instance, said vector comprising a most recent change number for said instance, as well as a most recent known change number for each other instances from among said plurality of instances that are known to said instance (each a known instance), wherein said vector (comprising change numbers for each known instance) inherently represents all changes that have been made to said instance.

22. The computer-readable instructions of claim 21 further comprising instructions for said change number to comprises a unique identification number for said instance and a relative incremental count of changes made to said instance.

23. The computer-readable instructions of claim 21 further comprising instructions for partially synchronizing a first instance with a second instance with said first instance requesting changes from said second instance by sending to said second instance its vector, and wherein said second instance, based on the vector it receives from said first instance, sends to said first instance only those changes that said first vector has not yet received.

24. The computer-readable instructions of claim 23, wherein said second instance, based on the vector it receives from said first instance, further comprises instructions for said second instance to determine that said first instance has changes that it, said second instance, has not yet received, and sends its own vector to said first instance to request these changes, and wherein said first instance, based on the vector it receives from said second instance, sends to said second instance only those changes that said second vector has not yet received.

25. The computer-readable instructions of claim 21 further comprising instructions for a first instance, when changing a first Item to relate (via a Relationship) to a second Item that was not previously being synchronized (e.g, an out-of-scope Item), to send all change information pertaining to said second Item to a second instance when synchronizing with said second instance so that said second Item in said second instance is synchronized with said second Item in said first instance.

26. The computer-readable instructions of claim 21 further comprising instructions for wherein, when by default operation a parent Item is transmited before a child Item to said parent Item, and wherein a plurality of changes are typically transmitted in sequential order of a plurality of change numbers corresponding to said changes during a synchronization, and wherein between synchronizations a child Item is changed and then a parent Item is changed in a first instance, any change units pertaining to said child Item are sent from said first instance to a second instance during a synchronization only after all change units pertaining to the parent Item are sent.

27. The computer-readable instructions of claim 21 further comprising instructions for wherein, for an Item deleted by a first instance, a tombstone comprising the identification of the Item deleted is created, and said tombstone is sent as part of a synchronization to notify a second instance to identify the Item to be deleted in said second instance.

28. The computer-readable instructions of claim 27 further comprising instructions for wherein, for a first instance having a parent Item and a first child Item to said parent Item, when said child Item is deleted and then said parent Item is deleted, said first instance sending only the change to said parent Item (that is, the tombstone for said parent Item) to a second instance during a synchronization where (a) the deletion of a parent Item automatically results in the deletion of all children Items for said parent or (b) the second instance, receiving the tombstone for the parent Item, proceeds to delete the parent Item and automatically deletes the child Item.

29. The computer-readable instructions of claim 21 further comprising instructions for, wherein a first Relationship and a second Relationship of a first instance swap names using a temporary name element such that, in order, (a) the name of the first Relationship is transferred to said temporary name element, (b) the name of the second Relationship is transferred to said first Relationship, and (c) said name stored in the temporary name element is copied to said second Relationship, and wherein said first instance synchronizes with a second instance and sends a duo of change units representing, in order, (i) the new name for said first Relationship and (ii) the new name for said second Relationship, and wherein effecting the first of said duo of changes (a first change) results in an error in the second instance because a result of said first change is for the first Relationship and the second Relationship having the same name (an attempted change), a method by which said second instance proceed to copy said name of the first Relationship to a local temporary name element and:

if, during the synchronization, a subsequent change is received for copying the name of said second Relationship to said first relationship occurs, then performing said change as well as also copying said name in said local temporary name element to said first Relationship; and

if, during the synchronization, a subsequent change is not received for copying the name of said second Relationship to said first relationship occurs, then raising a conflict regarding for the attempted change.

30. The computer-readable instructions of claim 21 further comprising instructions for wherein, for synchronization between a first instance on a storage platform that allows a dangling relative reference and a second instance on a storage platform that does not allow a dangling relative reference that include at least one change to a relative reference and at least one other change (in that order), sending said change to said relative references after said one other changes.