Synchronizing a store with write generations

• US 6,856,999 B2
• Filed: 06/12/2001
• Issued: 02/15/2005
• Est. Priority Date: 10/02/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ginsberg, Michael, Flanagin, Stephen D.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Pannala, Sathyanarayan
• Application Number:
  US09/879,384
• Publication Number:
  US 20020040445A1
• Time in Patent Office: 1,344 Days
• Field of Search: 707/103, 707200-203, 707/3, 707/10
• US Class Current: 1/1
• 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 through a sync client, 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 acts of:

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.

2. A method as defined in claim 1 further comprising an act of assigning the current write GID to a generation property of the objects updated by the sync client during synchronization if the current write GID is greater than the public write GID.

3. A method as defined in claim 1, further comprising an act of determining if a write to an object in the store of the device is performed by the sync client.

4. A method as defined in claim 3, wherein the act of determining if an update to an object in the store of the device is performed by the sync client further comprises acts of:

comparing a process identifier of the sync client that performed the synchronization checkpoint with a second process identifier of a process that performed the update to the object; and

determining that the update to the object was performed by the sync client if the process identifier matches the second process identifier.

5. A method as defined in claim 1, further comprising an act of compiling a change manifest, wherein the change manifest represents those objects in the store of the device that are to be synchronized by the sync client during synchronization.

6. A method as defined in claim 5, wherein the act of compiling a change manifest further comprises acts of:

including objects whose generation property is greater than the Sync From GID and loss than or equal to the Sync To GID; and

excluding objects whose generation property is equal to the reserved GIDs stored in the write generation list or to the current write GID.

7. A method as defined in claim 1, further comprising an act or persisting the sync state object.

8. 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, 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 acts of:

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.

9. A method as defined in claim 8, wherein the act of incrementing the global GID further comprises:

an act of transferring the Sync To GID to the Sync From GID;

an act of assigning the global GID to the Sync To GID before the global GID is incremented; and

purging reserved write GIDs from a write generation list that are less than or equal to the Sync From GID, wherein the write generation list is included in the sync state object.

10. A method as defined in claim 8, wherein the act of assigning a reserved GID further comprises acts of:

transferring a current write GID to a write generation list, wherein the current write GID and the write generation list are in the sync state object;

incrementing the global GID to a reserved value;

assigning the reserved value to the current write GID; and

incrementing the global GID to a public value such that objects having a generation property equal to the reserved value could only have been written by the sync client.

11. A method as defined in claim 10, further comprising an act of persisting the sync state object.

12. A method as defined in claim 8, wherein the act of assigning a reserved GID further comprises an act of determining that an update to an object in the store of the device was performed by the sync client if a first produces identifier of a first process performing the update matches a second process identifier of the sync client, which performed the synchronization checkpoint.

13. A method as defined in claim 8, wherein the act of ensuring that an object is not synchronized if the GID property of the object matches the reserved GID stored in the sync state object during the prior synchronization further comprises:

generating a change manifest list for the next synchronization;

including objects in the manifest list whose generation property is greater than the Sync From GID and less than or equal to the Sync To GID; and

excluding objects from the manifest list whose generation property is equal to reserved GIDs included in the current write GID and the write generation list.

14. In a system including a device that synchronizes with a synchronization partner, wherein objects in a store of the device are updated during synchronization, a computer program product for implementing a method for synchronizing the device and the synchronization partner using reserved GIDs such that objects written to the device are not synchronized back to the synchronization partner, the computer program product comprising:

a computer readable medium for carrying computer executable instructions for implementing the method, wherein the method comprises acts of;

initiating a synchronization checkpoint by a sync client to begin synchronization between the device and the synchronization partner;

saving a sync state object, wherein the sync state object includes a synchronization state including a Sync From GID and a Sync To GID;

detecting changed objects using the synchronization state, wherein the synchronization state identifies generations greater than to the Sync From GID and less than or equal to the sync to GID;

updating objects in the store of the device, wherein objects updated by the sync client store a reserved GID that is used only by the sync client in their GID property; and

storing the reserved GID in the sync state object.

15. A computer product as defined in claim 14, the method further comprising acts of:

passing in the sync state object;

updating the sync state object;

incrementing a global GID of the device to a next public value; and

assigning the next public value to a public write GID.

16. A computer program product as defined in claim 15, wherein the act of updating the sync state object further comprises:

an act of changing the sync GID to the value of the Sync To GID;

an act of changing the Sync To GID to the value of the global GID; and

purging reserved GIDs that are stale from a write generations included in the sync state object, wherein the write generations includes a current write GID and a write generation list.

17. A computer program product as defined in claim 14, wherein the act of detecting changed objects further comprises acts of:

excluding those objects whose generation property matches a reserved GID stored in the write generations from being represented in a change manifest; and

including those objects whose generation property is greater than the Sync From GID and less than or equal to the Sync To GID in the change manifest.

18. A computer program product as defined in claim 17, further comprising an act of synchronizing the objects represented in the change manifest.

19. A computer program product as defined in claim 14, wherein the act of updating objects in the store of the device further comprises acts of:

incrementing a global GID of the device to a reserved value, wherein the reserved value of the global GID is only used by the sync client; and

storing the reserved GID in the current write GID of the sync state object.

20. A computer program product as defined in claim 19, further comprising an act of persisting the sync state object.

21. 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 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 acts of:

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

22. A method as declined in claim 21, wherein the act of updating a sync state object further comprises:

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

assigning the present value of a public write GID to the Sync To GID;

if a current write GID exists in the sync state object, transferring a value of the current write GID to a write generation list;

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

incrementing a global GID; and

assigning the global GID to a public write GID for use by applications that are not sync clients.

23. A method as defined in claim 22, wherein the act of creating a change manifest further comprises:

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

for those objects that have a GID 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 the change manifest for synchronization.

24. A method as defined in claim 23, wherein the act of assigning a new current write GID further comprises:

incrementing the global GID to a reserved value;

moving the current write GID to a write generation list; and

assigning the reserved value to the new current write GID.

25. A method as defined in claim 24, wherein a public application makes a change to an object in the store of the device, the method further comprising:

an act of incrementing the global GID to a public value that is assigned to a public write GID;

an act of assigning the public write GID to the GID property of the object such that the new current write GID is only used by the sync client.