Handling collisions during synchronization of data between client and server computers

• US 7,032,033 B1
• Filed: 11/30/2001
• Issued: 04/18/2006
• Est. Priority Date: 11/30/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ledoux, Eric, Kollmorgen, Paul L.
• Primary Examiner(s): Thompson, Marc D.
• Assistant Examiner(s): Phan, Tam T.
• Application Number:
  US09/997,801
• Time in Patent Office: 1,600 Days
• Field of Search: 709/248, 709/203, 709/205, 707/203, 707/201, 711/141, 711/122
• US Class Current: 709/248
• 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/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Data stored on a server are synchronized with corresponding data on a plurality of client computers. To facilitate synchronization of the data, the data for a class of nodes on the server are provided with a version identifier (a serial number) that is incremented each time the data are modified on the server. During synchronization, the version identifier for the data stored on the client is transferred to the server, and the nodes stored on the client are updated by downloading nodes modified on the server since the last synchronization. Data on the client that have been modified are then uploaded to the server. Collisions between nodes of the data that have been modified on two different clients are detected, and a user is given an opportunity to resolve a collision.

Claims

1. A method for maintaining synchronization of data stored on a server, where components of the data are discrete objects that are separately modifiable on clients that are coupled to the server over a network and wherein modification to the components of the data on the clients can be uploaded to the server, comprising the steps of:

(a) associating a version identifier with the data, said version identifier being incremented each time that a change to any component of the data occurs on the server;

(b) each time that a component of the data is modified on the server, assigning to the component the value of the version identifier that was current at the time the component was modified on the server, other of the plurality of components comprising the data, which were not then modified, retaining a version identifier previously assigned thereto; and

(c) detecting a proactive collision between a component of the data just downloaded to any client and a modified version of said component that was previously downloaded and modified by a user on said client, as a function of the values of version identifiers associated with the component downloaded and the modified version of the component, causing an indication of the proactive collision to be provided to the user, enabling the user to resolve the proactive collision.

2. The method of claim 1, further comprising the step of detecting reactive collisions between corresponding components of the data that are concurrently uploaded to the server from a plurality of clients if uploading of a corresponding component by one client is completed before that by another client, detection of a reactive collision causing the step (c) to be repeated for the other client.

3. The method of claim 2, wherein each time that a reactive collision is detected, causing step (c) to be repeated for the other client results in a proactive collision being detected between the component on the server just uploaded by said one client and the corresponding component that was being uploaded by the other client.

4. The method of claim 1, wherein the step of detecting a proactive collision comprises the step of automatically determining if the value of the version identifier of the component of the data just downloaded is different than the value of the version identifier of the modified component.

5. The method of claim 1, wherein if there is an indication of that a proactive collision has occurred, the step of enabling the user to resolve the proactive collision comprises one of the steps of:

(a) overwriting the modified version of the component with the component that was just downloaded; and

(b) uploading the modified version of the component to the server, so that a corresponding component on the server that was changed since the previous version of the component was downloaded and subsequently modified by the user, is overwritten with the modified version.

6. The method of claim 1, further comprising the steps of:

(a) enabling a new component of the data to be created on the client; and

(b) enabling the new component to be uploaded to the server.

7. The method of claim 6, further comprising the step of maintaining on each client:

(a) a server cache in which components most recently downloaded from the server are stored; and

(b) a client store in which components of the data that have been modified on the client, but not yet uploaded to the server are stored.

8. The method of claim 1, wherein each time that a client connects in communication with the server, further comprising the steps of:

(a) downloading from the server to the client, each component for which the version identifier of said component on the server is greater than that of a corresponding component on the client;

(b) downloading an identification of each component of the data on the server, if a component has been deleted from the data on the server after the client was last synchronized with the server;

(c) automatically overwriting each component on the client that has not been modified with a corresponding component that was downloaded from the server, if the version identifier for the component that was just downloaded is greater than that of the component already on the client; and

(d) automatically deleting each component on the client that was deleted on the server since the client was last synchronized with the server.

9. The method of claim 1, further comprising the step of maintaining on the server a unique identification for each object comprising the data stored on the server.

10. The method of claim 1, further comprising the step of enabling the modifications to be made by a user to the components of the data on a client while the client is not coupled to the server over the network, the modifications being subsequently uploaded to the server while the client is then coupled to the server over the network.

11. A memory medium having machine instructions that are readable by a computing device, for performing the steps recited in claim 1.

12. A method for maintaining synchronization of data stored on a server, said data being accessible by a plurality of clients at times coupled in communication with the server and able to download the data to be modified and to upload changes to the data to the server, said data including a plurality of nodes, comprising the steps of:

(a) assigning to the data a version identifier that is incremented each time any node of the data is modified on the server;

(b) associating a value of the version identifier with each node, said value that is thereby associated corresponding to that of the version identifier then assigned to the data when the node was last modified on the server;

(c) enabling nodes that have been modified on the server since said nodes were previously downloaded by any client, to be downloaded to said client;

(d) enabling nodes that were downloaded from the server by any client to be modified on said client, producing modified nodes;

(e) enabling the modified nodes to be uploaded from each client to the server;

(f) detecting and providing an indication on each client of any proactive collision between a node that has just been downloaded from the server to the client and a corresponding node that was previously downloaded by the client and has been modified on the client, the proactive collision being detected as a function of the version identifiers associated with the node that has just been downloaded and the node that has been modified on the client;

(g) detecting any reactive collision between corresponding modified nodes that were separately modified on two or more clients and which are being uploaded by the two or more clients, as a function of the version identifiers associated with the nodes that are being uploaded; and

(h) if a reactive collision is detected in step (g), repeating steps (e)–

(h).

13. The method of claim 12, wherein the step of detecting the reactive collision occurs when the server detects that the version identifier of a node being uploaded by a client is different than a corresponding node now on the server, indicating that another client completed uploading of the corresponding node now on the server while said client was uploading said node.

14. The method of claim 12, wherein before each download of nodes from the server to the clients occurs, further comprising the steps on each client, of:

(a) conveying the version identifier for a class of nodes on the client to the server to indicate a version of the nodes in the class that were last downloaded from the server to the client;

(b) sending any nodes on the server to client, for which the version identifier associated therewith indicates the node on the server is a later version than the version identifier of the class on the client; and

(c) providing an indication of nodes remaining on the server if any node has been deleted on the server after the client was last synchronized with the server.

15. The method of claim 14, further comprising the step of automatically overwriting each node not yet modified on the client with a corresponding node downloaded from the server and deleting each node on the client that was indicated as having been deleted on the server.

16. The method of claim 12, further comprising the step of maintaining on each client:

(a) a cache in which are stored a latest version of nodes most recently downloaded from the server; and

(b) a storage containing all nodes modified on the client, but not yet uploaded to the server.

17. The method of claim 12, wherein if there is an indication of a proactive collision being detected on a client, further comprising the step of enabling a user to elect one of the steps of:

(a) overwriting the modified node on the client with the corresponding node just downloaded from the server; and

(b) upload the modified node to the server, overwriting the corresponding node on the server.

18. The method of claim 12, further comprising the step of enabling new nodes to be uploaded from any of the clients to the server.

19. The method of claim 12, wherein the step of enabling the nodes that were downloaded from the server by any client to be modified on said client includes the step of enabling the nodes to be modified while the client is not connected to the server.

20. A memory medium having machine instructions that are readable by a computing device, for performing the steps recited in claim 12.

21. A method for maintaining synchronization of data transferred between a storage computing device and a plurality of remote computing devices that are at times coupled in data communication with the storage computing device to enable modification of the data, said data including a plurality of nodes that can be independently modified, the method comprising the steps of:

(a) assigning an identifier to the data;

(b) changing the identifier each time that any node of the data is modified on the storage computing device so that the identifier indicates a version of the data that are currently stored on the storage computing device at that time;

(c) associating a value of the identifier with each node stored on the storage computing device, said value indicating the version of the data at the time when the node was last modified on the storage computing device, other of the plurality of nodes comprising the data, which were not then modified, retaining a version identifier previously assigned thereto;

(d) downloading a current identifier associated with the data and with each of the plurality of nodes being downloaded to any of the plurality of remote computing device that has requested transfer of any of the data from the storage computing device, for modification on the remote computing device, said current identifier for each of the nodes being downloaded being retained in association with the nodes that are downloaded to indicate a version of the nodes that were thus downloaded;

(e) enabling the nodes downloaded to be modified on any remote computing device having rights to do so;

(f) at each subsequent time that one of the plurality of remote computing devices to which the nodes were downloaded in step (e) is coupled in data communication with the storage computing device for synchronizing the data, transferring the version indicator associated with the data that are retained on said one of the plurality of remote computing devices to the storage computing device;

(g) while synchronizing the data, downloading from the storage computing device to said one of the plurality of remote computing devices, each node of the data for which the identifier associated with the node on the storage computing devices indicates that said node is a later version than indicated by the identifier associated with data previously downloaded from the storage computing device to said one of the remote computing devices, thereby updating the nodes on said one of the plurality of remote computing devices, but retaining any modified nodes;

(h) detecting whether a node just downloaded in step (g) was modified on the storage computing device since a time that said node was previously downloaded and then modified to produce a modified node on said one of the plurality of remote computing devices, by comparison of the identifiers associated with the corresponding nodes, and if so, providing an indication thereof to a user of said one of the plurality of remote computing devices;

(i) enabling modified nodes to be uploaded to the storage computing device, along with the identifiers associated with the modified nodes; and

(j) detecting whether a newer modified node has been uploaded to the storage computing device before uploading of a modified node in step (i) is completed, and if so, repeating steps (h)–

(j).

22. The method of claim 21, further comprising the step of enabling the user of said one of the plurality of remote computing devices to respond to said indication by electing one of the steps of:

(a) overwriting the modified node on said one of the remote computing devices with the node just downloaded; and

(b) uploading the modified version to the storage computing device, thereby overwriting the corresponding node on the storage computing device with the modified node and causing a change in the identifier associated with the data on the storage computing device.

23. The method of claim 21, wherein during synchronizing, further comprising the step of downloading from the storage computing device to said one of the remote computing devices a list identifying all nodes on the storage computing device, if a node has been deleted on the storage computing device after any nodes were downloaded to said one of the remote computing devices from the server computing device, causing nodes that were deleted on the server computing device to also be deleted on said one of the remote computing devices.

24. The method of claim 21, wherein on each of the plurality of remote computing devices, further comprising the steps of:

(a) maintaining a cache for storing the nodes just downloaded from the storage computing device and the identifier associated with the nodes; and

(b) maintaining a storage for each node that is modified on the remote computing device.

25. The method of claim 21, wherein during synchronization, any node that has not been modified on said one of the remote computing devices since a previous synchronization is automatically overwritten with a corresponding node downloaded from the storage computing device.

26. The method of claim 21, wherein the step of enabling the nodes that are downloaded from the storage device to be modified by any remote computing device having the rights to do so includes the step of enabling the nodes to be modified while the remote computing device is not connected to the storage device.

27. A memory medium having machine instructions that are readable by a computing device, for performing the steps recited in claim 21.

28. A system for maintaining synchronization of data, comprising:

(a) a server computing device;

(b) client computing devices that are able to couple in communication with the server computing device over a network, to download the data, modify the data, and upload changes in the data to the server computing device over the network;

(c) the server computing device and each client computing device comprising;

(i) a memory in which are stored machine instructions, the memory on the server computing device also storing the data, said data including a plurality of nodes, the memory on the client computing devices also separately storing nodes of the data downloaded from the server computing device and nodes that have been modified on the client computing device;

(ii) a processor that in is coupled to the memory, said processor on the server computing device executing the machine instructions, causing the processor on the server computing device to;

(1) assign a version identifier to the data, and increment the version identifier each time any node of the data is modified on the server computing device;

(2) associate a value of the version identifier with each node, said value that is thereby associated corresponding to that of the version identifier then assigned to the data when the node was last modified on the server computing device, other of the plurality of nodes comprising the data, which were not then modified, retaining a version identifier previously assigned thereto;

(3) in response to a download request from a client computing device, download to said client computing device nodes that have been modified on the server computing device since said nodes were previously downloaded to the client computing device;

(4) in response to an upload request from a client computing device, upload modified nodes from the client computing device to the server computing device over the network; and

(5) detect any reactive collision between corresponding modified nodes that were separately modified on two or more client computing devices and which are being uploaded by the two or more client computing devices at substantially the same time, as a function of the version identifiers associated with the nodes that are being uploaded; and

(iii) wherein said processor on each client computing device executes the machine instructions stored in its memory, causing the processor on the client computing device to;

(1) selectively download from the server computing device nodes that have been modified on the server computing device since said nodes were previously downloaded to the client computing device;

(2) enable a user to modify nodes on the client computing device, producing the modified nodes;

(3) enable nodes that were downloaded from the server computing device by any client computing device to be modified on said client computing device, producing modified nodes;

(4) selectively upload modified nodes from any client computing device to the server computing device over the network; and

(5) detect and provide an indication on each client computing device of any proactive collision between a node that has just been downloaded from the server computing device to the client computing device and a corresponding node that was previously downloaded by the client computing device and has been modified by a user on the client computing device, the proactive collision being detected as a function of the version identifiers associated with the node that has just been downloaded and the node that has been modified on the client computing device.

29. The system of claim 28, wherein machine instructions cause the processor of the server computing device to detect the reactive collision when the version identifier of a node being uploaded by a client computing device is different than a corresponding node now on the server computing device, indicating that another client computing device completed uploading of the corresponding node now on the server computing device while said client computing device was uploading said node.

30. The system of claim 28, wherein before each download of nodes from the server computing device to the client computing devices occurs, the machine instructions executing on the processor of the client computing device cause:

(a) the version identifier for the data on the client computing device to be conveyed to the server computing device, to indicate a version of the nodes that were last downloaded from the server computing device to the client computing device;

(b) request download to the client computing device of any nodes on the server computing device for which the version identifier associated with the node indicates that the node on the server computing device is a later version than the corresponding node on the client computing device; and

(c) request download of an identification of each node on the server computing device, if any node was deleted from the server computing device since data were last downloaded from the server computing device to the client computing device for purposes of synchronization.

31. The system of claim 30, wherein the machine instructions executed by the processor on each client computing device further cause said processor to automatically overwrite each node not yet modified on the client computing device with a corresponding node downloaded from the server computing device and to delete each node on the client computing device that has been deleted and is no longer on the server computing device.

32. The system of claim 28, wherein if a client computing device detects a proactive collision, the machine instructions stored in the memory of the client computing device cause the processor of the client computing device to enable a user to selectively cause the client computing device to do one of:

(a) overwrite the modified node on the client computing device with the corresponding node just downloaded from the server computing device; and

(b) upload the modified node to the server computing device, overwriting the corresponding node on the server computing device.

33. The system of claim 28, wherein the machine instructions executing on the processor of each client computing device enable a user to create a new node and to upload the new node to the server computing device when the client computing device is next synchronized with the server computing device.

34. The system of claim 28, wherein the machine instructions executed by the processor of the client computing device to enable modification of the nodes while the client computing device is not connected to the server computing device.