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

• US 7,483,923 B2
• Filed: 10/24/2003
• Issued: 01/27/2009
• Est. Priority Date: 08/21/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev
• Primary Examiner(s): Pham; Khanh B
• Application Number:
  US10/692,508
• Publication Number:
  US 20050044530A1
• Time in Patent Office: 1,922 Days
• Field of Search: 707 1- 10, 707/100, 707/102, 707/201, 709/236
• US Class Current: 1/1
• 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 earlier 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, said method comprising:

storing a plurality of items in a first instance of a data platform, each item stored in the first instance includes at least one change unit, wherein the data platform is configured to track changes to change units;

storing, by the first instance of the data platform, a change to a first change unit of a first item, wherein the first item is a child of a parent item and the first item and the parent item are included in the plurality of items;

storing, by the first instance of the data platform after the change to the first change unit of the first item, a change to a parent change unit of the parent item;

uniquely enumerating, by the first instance of the data platform, changes to change units in sequential order, wherein each change unit is identified by a change number;

maintaining, by the first instance of the data platform, a separate vector, wherein the separate vector corresponds to the enumerated change units in sequential order, and a most recent known change number of a second instance of the data platform, wherein the separate vector represents all changes that have been made to the first instance of the data platform;

receiving, by the first instance of the data platform from the second instance of the data platform, a synchronization request, wherein the synchronization request includes a second vector associated with the second instances of the data platform;

determining, by the first instance of the data platform, that the second instance of the data platform does not include the change to the first change unit of the first item and the change to the parent change unit of the parent item in accordance with the second vector; and

transmitting, by the first instance of the data platform, the change to the parent change unit of the parent item prior to transmitting the change to the first change unit of the first item.

2. The method of claim 1 wherein said change number comprises a unique identification number and a relative incremental count.

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

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

5. The method of claim 1 wherein a first instance of the data platform, when changing a first Item to relate via a Relationship to a second Item that was not previously being synchronized, to send all change information pertaining to said second Item to the second instance of the data platform when synchronizing with said second instance of the data platform.

6. 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 of the data platform to identify the Item to be deleted in said second instance of the data platform.

7. The method of claim 6 wherein, for a first instance of the data platform 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 of the data platform sending only the change to 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 of the data platform, receiving the tombstone for the parent Item, proceeds to delete the parent Item and automatically deletes the child Item.

8. The method of claim 1, wherein a first Relationship and a second Relationship of a first instance of the data platform 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 of the data platform synchronizes with a second instance of the data platform 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 change of said duo of changes results in an attempted change having 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, a method by which said second instance of the data platform 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, 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, then raising a conflict regarding for the attempted change.

9. The method of claim 1 wherein, for synchronization between a first instance of the data platform on a storage platform that allows a dangling relative reference and a second instance of the data platform 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, sending said change to said relative references after said one other changes.

10. A computer-readable storage medium comprising computer-readable instructions for synchronizing a plurality of instances for a data platform, said computer-readable instructions comprising instruction for:

storing a plurality of items in a first instance of a data platform, each item stored in the first instance includes at least one change unit, wherein the data platform is configured to track changes to change units;

storing, by the first instance of the data platform, a change to a first change unit of a first item, wherein the first item is a child of a parent item and the first item and the parent item are included in the plurality of items;

storing, by the first instance of the data platform after the change to the first change unit of the first item, a change to a parent change unit of the parent item;

uniquely enumerating, by the first instance of the data platform, changes to change units in sequential order wherein each change unit is identified by a change number;

maintaining, by the first instance of the data platform, a separate vector, wherein the separate vector corresponds to the enumerated change units in sequential order, and a most recent known change number of a second instance of the data platform, wherein the separate vector represents all changes that have been made to the first instance of the data platform;

receiving, by the first instance of the data platform from the second instance of the data platform, a synchronization request, wherein the synchronization request includes a second vector associated with the second instances of the data platform;

determining, by the first instance of the data platform, that the second instance of the data platform does not include the change to the first change unit of the first item and the change to the parent change unit of the parent item in accordance with the second vector; and

transmitting, by the first instance of the data platform, the change to the parent change unit of the parent item prior to transmitting the change to the first change unit of the first item.

11. The computer-readable storage medium of claim 10 further comprising instructions for said change number to comprises a unique identification number for said instance of the data platform and a relative incremental count of changes made to said instance.

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

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

14. The computer-readable storage medium of claim 10 further comprising instructions for a first instance of the data platform, when changing a first Item to relate via a Relationship to a second Item that was not previously being synchronized, to send all change information pertaining to said second Item to a second instance of the data platform when synchronizing with said second instance of the data platform so that said second Item in said second instance of the data platform is synchronized with said second Item in said first instance of the data platform.

15. The computer-readable storage medium of claim 10 further comprising instructions for wherein, for an Item deleted by a first instance of the data platform, 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 of the data platform to identify the Item to be deleted in said second instance of the data platform.

16. The computer-readable storage medium of claim 15 further comprising instructions for wherein, for a first instance of the data platform 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 of the data platform sending only the change to said parent Item to a second instance of the data platform 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 of the data platform, receiving the tombstone for the parent Item, proceeds to delete the parent Item and automatically deletes the child Item.

17. The computer-readable storage medium of claim 10 further comprising instructions for, wherein a first Relationship and a second Relationship of a first instance of the data platform 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 of the data platform synchronizes with a second instance of the data platform 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 change of said duo of changes results in an attempted change having an error in the second instance of the data platform because a result of said first change is for the first Relationship and the second Relationship having the same name, a method by which said second instance of the data platform 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, 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, then raising a conflict regarding for the attempted change.

18. The computer-readable storage medium of claim 10 further comprising instructions for wherein, for synchronization between a first instance of the data platform on a storage platform that allows a dangling relative reference and a second instance of the data platform 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, sending said change to said relative references after said one other changes.