Synchronizing a store with write generations

• US 20040225694A1
• Filed: 06/09/2004
• Published: 11/11/2004
• Est. Priority Date: 10/02/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Michael Ginsberg, Stephen D. Flanagin
• Inventors: Ginsberg, Michael, Flanagin, Stephen D.
• Granted Patent: US 6,970,889 B2
• Time in Patent Office: Days
• US Class Current: 707/201
• 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: G06F 16/275 Synchronous replication
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Systems and methods for synchronizing a device and for ensuring that updates to the device occurring during synchronization are not re-synchronized to the synchronization partner. Generation identifiers (GIDs), which are updated each time a synchronization occurs, are assigned to objects in a store. When synchronization occurs, a sync client uses state information, which is used to indicate which generations have been synchronized, to determine which objects have changed since the last synchronization. The state information includes reserved write GIDs that are only used by a particular sync client that performs writes during a synchronization. Objects having a GID that matches a write GID are not synchronized because they were written by the sync client during the previous synchronization.

Claims

1. In a system including a device that synchronizes with a synchronization partner, wherein objects or changes to objects are written to the device during synchronization, a method for synchronizing the device and the synchronization partner such that the objects or changes to objects written to the device during synchronization are not synced back to the synchronization partner in future synchronizations, the method comprising acts of:

performing a synchronization checkpoint by a sync client of the device to initiate a synchronization between the synchronization partner and the device;

updating a synchronization state in a sync state object using the value of the global GID, wherein the synchronization state includes a Sync To GID, a Sync From GID, and write generations, wherein the write generations include a current write GID and a write generation list;

incrementing a global GID to a new value from the present value;

detecting changed objects based on the synchronization state; and

synchronizing the changed objects, wherein the write generations prevent objects or changes to objects written by the sync client from being synchronized unnecessarily.

2. A method as defined in claim 1, wherein the act of updating a synchronization state further comprises acts of:

assigning a current value of the Sync To GID to the Sync From GID;

assigning the present value of the global GID to the Sync To GID;

transferring a value of the current write GID to the write generation list; and

removing values from the write generation list that are less than or equal to the Sync From GID.

3. A method as defined in claim 1, wherein the act of detecting changed objects based on the synchronization state further comprises acts of:

examining a generation property for each object in the store of the device; and

for those objects that have a generation property whose value is greater than the Sync From GID and less than or equal to the Sync To GID and that is not equal to any GID in the write generation list, representing those objects in a change manifest for synchronization.

4. A method as defined in claim 3, further comprising an act of synchronizing the changed objects represented in the change manifest.

5. A method as defined in claim 1, wherein an object is updated during synchronization with the device, further comprising acts of:

determining if the sync client is performing the update to an object;

if the sync client is performing the update to the object and if the current write GID of the sync client is greater than a public write GID, assigning the current write GID to the generation property of the object; and

if the sync client is performing the update to the object and if the current write GID is less than the public write GID;

transferring the current write GID to the write generation list;

incrementing the global GID to a reserved value; and

assigning the reserved value to the current write GID and to the generation property of the object such that only objects updated by the sync client receive the reserved value in their generation property.

6. A method as defined in claim 5, further comprising an act of persisting the updated sync state object if the synchronization sync state object was updated during the synchronization.

7. A method as defined in claim 1, wherein the act of performing a synchronization checkpoint further comprises an act of passing in the state sync object to the sync client.

8. A method as defined in claim 1, wherein a second sync client performs an update, further comprising an act of allocating a unique current write GID for the second sync client.

9. A method as defined in claim 8, wherein the act of allocating a unique current write GID for the second sync client further comprises an act of incrementing the GID to a next value, wherein the public write GID is not changed.

10. A method as defined in claim 1, wherein the act of incrementing a global GID to a new value from a present value further comprises an act of assigning the new value to a public write GID.

11. A computer program product comprising one or more computer-readable media having computer-executable instructions for implementing a method in a system including a device that synchronizes with a synchronization partner, wherein objects or changes to objects are written to the device during synchronization, wherein the method is a method for synchronizing the device and the synchronization partner such that the objects or changes to objects written to the device during synchronization are not synced back to the synchronization partner in future synchronizations, the method comprising:

performing a synchronization checkpoint by a sync client of the device to initiate a synchronization between the synchronization partner and the device;

updating a synchronization state in a sync state object using the value of the global GID, wherein the synchronization state includes a Sync To GID, a Sync From GID, and write generations, wherein the write generations include a current write GID and a write generation list;

incrementing a global GID to a new value from the present value;

detecting changed objects based on the synchronization state; and

synchronizing the changed objects, wherein the write generations prevent objects or changes to objects written by the sync client from being synchronized unnecessarily.

12-18. -18. (Cancelled)

19. A computer program product comprising one or more computer-readable media having computer-executable instructions for implementing a method in a system including a device that synchronizes with a synchronization partner through a sync client, wherein the method is a method for reserving generation identifiers (GIDs) for updates performed by the sync client such that objects updated to the device during synchronization are not synchronized back to the synchronization partner, the method comprising:

receiving a sync state object by a sync client when a synchronization checkpoint is initiated, wherein the sync state object includes a Sync From GID, a Sync To GID, a current write GID and a write generation list, wherein the write generation list stores reserved GIDs

updating the sync state object such that the Sync To GID is transferred to the Sync From GID, a current value of a global GID is assigned to the Sync To GID, and reserved GIDs in the write generation list that are less than the Sync From GID are purged from the write generation list;

incrementing the global GID, wherein the global GID is assigned to a public write GID; and

when a write is performed by the sync client and the current write GID is less than the public write GID;

transferring the current write GID to the write generation list;

incrementing the global GID to a reserved value; and

assigning the reserved value to both the current write GID and to the generation property of the object.

20-25. -25. (Cancelled)

26. A computer program product comprising one or more computer-readable media having computer-executable instructions for implementing a method in a system including a device that synchronizes with one or more synchronization partners and wherein objects stored on the device can be updated during synchronization with the one or more synchronization partners, wherein the origin of updated objects is unknown and are therefore synced back to the one or more synchronization partners unnecessarily, wherein the method is a method for providing reserved generation identifiers (GIDs) such that the updated objects are not synced back to the one or more synchronization partners unnecessarily, the method comprising:

assigning a global GID to a store of the device, wherein a value of the global GID is assigned to a generation property of each object in the store whenever each object is updated, wherein the value of the GID assigned to the generation property is either a public write GID or a current write GID;

incrementing the global GID each time the store of the device is synchronized;

wherein the synchronization is defined by a Sync To GID and a Sync From GID included in a sync state object associated with the synchronization;

assigning a reserved GID to the generation property of an object in the store of the device when the object is updated by a sync client during synchronization, wherein the reserved GID is derived from the global GID and wherein the reserved GID is only used by the sync client and is stored in the current write GID of the sync state object of the sync client; and

during a next synchronization;

ensuring that an object is not synchronized if the generation property of the object matches the reserved GID stored in the sync state object.

27-38. -38. (Cancelled)

39. A computer program product comprising one or more computer-readable media having computer-executable instructions for implementing a method in a system including a device that synchronizes with a synchronization partner, wherein objects or changes to objects are written to the device during synchronization, wherein the method is a method for synchronization the device and the synchronization partner such that the objects of changes to objects written to the device during synchronization are not synced back to the synchronization partner in future synchronizations, the method comprising:

initiating a sync checkpoint by a sync client;

updating a sync state object of the sync client, wherein the sync state object is persisted after it is updated;

creating a change manifest for use in the synchronization, wherein the change manifest represents objects to be synchronized;

receiving a partner manifest from the synchronization partner; and

updating objects in a store of the device according to the change manifest and the partner manifest, the act of updating objects comprising;

if the sync client has a valid current write GID, assigning the current write GID of the sync client to the GID property of the objects written by the sync client during the synchronization, wherein the current write GID is unique to the sync client;

if the sync client does not have a valid current write GID, allocating a new current write GID for the sync client and assigning the new current write GID to the GID property of the objects written by the sync client during the synchronization; and

persisting the sync state object.