System and methods for synchronizing datasets when dataset changes may be received out of order

• US 6,449,622 B1
• Filed: 04/15/1999
• Issued: 09/10/2002
• Est. Priority Date: 03/08/1999
• Status: Active Grant

• Current Assignee: Intellisync Corporation (Nokia Corporation)
• Original Assignee: Starfish Software, Inc. (Nokia Corporation)
• Inventors: Yu, Chiahua George, Dube, Bryan, LaRue, Chris
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/293,571
• Time in Patent Office: 1,244 Days
• Field of Search: 707/8, 707/201, 707/202, 707/203, 707/10, 707/205, 707/204, 707/100, 707/200, 714/6, 714/13, 711/130, 711/9, 711/4, 711/113, 711/162, 711/202, 709/213, 709/204, 709/221
• 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: Y10S 707/922 Communications
• 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
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A system and methods for synchronizing information in datasets via a communication medium are provided that are suitable for synchronizing even across communication mediums that are susceptible to high latency, non-FIFO (non-First-In-First-Out) delivery order, or other adverse characteristics. According to an aspect of the invention, a computer-implemented method is for synchronizing user data in a first dataset with user data in at least a second dataset via a communication medium. The user data in the first dataset and the user data in the second dataset are capable of having been independently modified prior to the synchronization. The method includes sending a dataset change from the first dataset, receiving the dataset change via the communication medium, and determining whether the received dataset change, hereinafter referred to as the just-received change, was sent earlier than another dataset change, hereinafter referred to as the previously-received change, from the first dataset that was received earlier than the receiving step. The method further includes performing synchronization of the first and the second datasets based at least in part on the determining step. The performing step includes refraining from propagating the just-received change into the second dataset, if the just-received change is determined in the determining step to have been sent earlier than the previously-received change. The performing step further includes propagating the just-received change into the second dataset, at least to an extent needed for reconciling the just-received change with the second dataset, otherwise.

Claims

1. A computer-implemented method for synchronizing user data in a first dataset with user data in at least a second dataset via a communication medium, wherein the user data in the first dataset and the user data in the second dataset are capable of having been independently modified prior to the synchronization, the method comprising:

sending a dataset change from the first dataset;

receiving the dataset change via the communication medium;

determining whether the received dataset change, hereinafter referred to as the just-received change, was sent earlier than another dataset change from the first dataset that was received earlier than the receiving step, wherein the other dataset change is hereinafter referred to as the previously-received change; and

performing synchronization of the first and the second datasets based at least in part on the determining step, wherein the performing step comprises;

if the just-received change is determined in the determining step to have been sent earlier than the previously-received change, refraining from propagating the just-received change into the second dataset; and

otherwise, propagating the just-received change into the second dataset, at least to an extent needed for reconciling the just-received change with the second dataset.

2. The method of claim 1 wherein:

the first dataset resides on a first device and the second dataset resides on a second device; and

the first and second devices are coupled to communicate with one another via the communication medium only occasionally.

3. The method of claim 2 wherein:

the sending step comprises sending the dataset change from the first device via the communication medium;

the receiving step comprises receiving the dataset change at the second device via the communication medium; and

the determining step is performed at the second device.

4. The method of claim 1 wherein the communication medium is a wireless or wireline communication medium that is susceptible to non-FIFO delivery order.

5. The method of claim 4 wherein:

the just-received change involves a data record of the first dataset; and

the previously-received change of the determining step also involves the first data record, wherein the propagating step is taken, and the refraining step is not taken, if the just-received change was sent earlier than a dataset change from the first dataset that was received earlier than the receiving step but that does not involve the data record.

6. The method of claim 1, wherein:

the sending step comprises sending an indicator of send order;

the receiving step comprises receiving the indicator of send order; and

the determining step comprises determining, based at least in part on the received indicator of send order, whether the just-received change was sent earlier than the previously-received change.

7. The method of claim 6 wherein:

the indicator of send order includes a first timestamp,

an indicator of send order associated with the previously-received change includes a second timestamp; and

the determining step comprises determining that the just-received change was sent earlier than the previously-received change if the first timestamp is earlier than the second timestamp.

8. The method of claim 7 wherein the first and second timestamp are indicative of times at which the just-received change and the previously changes were respectively sent.

9. The method of claim 7 wherein:

the just-received change involves a data record of the first dataset and reflects a version of the data record; and

the first timestamp is of a time at which the data record was last modified in the first dataset into the version reflected by the just-received change.

10. The method of claim 7 wherein the first timestamp and the second timestamp are according to a first clock used to record modification times in the first dataset, and the step of determining that the just-received change was sent earlier than the previously-received change if the first timestamp is earlier than the second timestamp needs not compare timestamps that are according to mutually different clocks.

11. The method of claim 10 wherein the second dataset includes records reflecting values entered by a user at a time indicated in the second dataset according to a second clock, wherein time readings of the first clock and time readings of the second clock cannot readily be converted into a common time zone.

12. The method of claim 10 wherein the first clock is a non-real-time clock.

13. The method of claim 6 wherein the communication medium is a distant wireless communication medium.

14. The method of claim 6 wherein the just-received change and the previously-received change include user appointment data or user contact data.

15. The method of claim 1 wherein the just-received change and the previously-received change include at least one member of the set consisting of a record addition, a record update, and a record deletion.

16. The method of claim 1 wherein:

the just-received change involves a data record of the first dataset and reflects a version of the data record, hereinafter referred to as the just-reflected version;

the method further comprises, prior to the receiving step, maintaining information that indicates a version of the data record, hereinafter referred to as the latest-known version, that is reflected by a latest-sent one of changes already received from the first dataset involving the data record;

the previously-received change reflects the latest-known version, and the determining step comprises using the maintained information to determine that the just-received change was sent earlier than the previously-received change if the just-reflected version is older than the latest-known version.

17. The method of claim 16 wherein:

a data record of the second dataset corresponds to the data record of the first dataset; and

the maintaining step comprises maintaining the information that indicates the latest-known version of the data record of the first dataset until the determining step, even if the data record of the second dataset is changed, prior to the receiving step, not due to synchronization with the first dataset.

18. The method of claim 16 wherein the maintained information includes an indication of a send time at which a change, received prior to the receiving step, that reflects the latest-known version was sent from the first dataset.

19. The method of claim 16 wherein:

the second dataset includes a plurality of data records known to correspond to a plurality of data records of the first dataset other than the data record;

the method further comprises maintaining information that indicates, for each of the plurality of data records of the second dataset, a version of a corresponding one of the plurality of data records of the first dataset, which version is reflected by a latest-sent one of changes already received from the first dataset involving the corresponding one of the plurality of data records of the first dataset.

20. The method of claim 19 wherein:

the first dataset resides on a first device and the second datasets resides on a second device; and

the steps of maintaining information comprise maintaining a status field for each of the plurality of data records of the second dataset on the second device.

21. The method of claim 19 wherein the status fields need not be updated during ordinary, non-synchronization viewing or modification of the client dataset by the user.

22. The method of claim 1 wherein the communication medium includes a member of the set consisting of an electronic mail network and a wireless paging network.

23. The method of claim 1 wherein the just-received change and the previously-received change include at least one member of the set consisting of a record update containing user-entered information and a record deletion.

24. The method of claim 1 wherein the performing synchronization step further comprises:

sending a dataset change from the second dataset;

receiving the dataset change from the second dataset via the communication medium;

determining whether the received dataset change from the second dataset was sent earlier than another dataset change from the second dataset that was received earlier than the step of receiving the dataset change from the second dataset; and

performing synchronization of the first and the second datasets based at least in part on the step of determining whether the received dataset change from the second dataset was sent earlier than the other dataset change from the second dataset.

25. The method of claim 24 wherein:

the first dataset resides on a first device with a first processor and the second dataset resides on a second device with a second processor; and

the first and second devices are capable of communicating with each another via the communication medium;

the step of sending the dataset change from the first dataset is performed by the first device;

the step of receiving the dataset change from the first dataset is performed by the second device;

the step of determining whether the just-received change was sent earlier than the previously-received change is performed by the second device;

the step of sending the dataset change from the second dataset is performed by the second device;

the step of receiving the dataset change from the second dataset is performed by the first device; and

the step of determining whether the received dataset change from the second dataset was sent earlier than the other dataset change from the second dataset is performed by the first device.

26. A computer-implemented method for synchronizing user data in a first dataset with user data in at least a second dataset via a communication medium, wherein the user data in the first dataset and the user data in the second dataset are capable of having been independently modified prior to the synchronization, the method comprising:

sending a dataset change from the first dataset;

receiving the dataset change via the communication medium;

determining whether the received dataset change, hereinafter referred to as the just-received change, was sent earlier than another dataset change from the first dataset that was received earlier than the receiving step, wherein the other dataset change is hereinafter referred to as the previously-received change; and

performing synchronization of the first and the second datasets based at least in part on the determining step, wherein the performing step comprises;

if the just-received change is determined in the determining step to have been sent earlier than the previously-received change, refraining from propagating the just-received change into the second dataset; and

otherwise, propagating the just-received change into the second dataset, at least to an extent needed for reconciling the just-received change with the second dataset;

wherein;

the sending step comprises sending an indicator of send order;

the receiving step comprises receiving the indicator of send order; and

the determining step comprises determining, based at least in part on the received indicator of send order, whether the just-received change was sent earlier than the previously-received change;

and wherein the method further comprises;

prior to the receiving step, receiving the previously-received change, whereby the previously-received change becomes previously-received, and also receiving an indicator of send order associated with the previously-received change; and

storing information to indicate send order, based on the received indicator of send order associated with the previously-received change;

wherein the determining step comprises determining, based at least in part on the received indicator of send order and the stored information, whether the just-received change was sent earlier than the previously-received change.

27. The method of claim 26 wherein:

the just-received change involves a data record of the first dataset and reflects a version of the data record; and

the step of storing the information to indicate send order comprises storing information that is indicative of a version of the data record that is reflected by a latest-sent one of changes already received from the first dataset involving the data record.

28. The method of claim 27 further comprising, if the just-received change is determined in the determining step to have been sent later than the previously-received change, updating the stored information to indicate send order, based on the received indicator of send order that was sent in the sending step, for future use in receiving and processing further dataset changes.

29. A system for synchronizing user data in a first dataset with user data in at least a second dataset via a communication network, wherein the user data in the first dataset and the user data in the second dataset are capable of having been independently modified prior to the synchronization, the system comprising:

means for sending a dataset change from the first dataset;

means for receiving the dataset change via the communication network;

means for determining whether the received dataset change, hereinafter referred to as the just-received change, was sent earlier than another dataset change from the first dataset that was received earlier than was the just-received change, wherein the other dataset change is hereinafter referred to as the previously-received change; and

means for performing synchronization of the first and the second datasets based at least in part on whether the just-received change was sent earlier than the previously-received change.

30. The system of claim 29 wherein means for sending a dataset change includes means for sending a record update or a record deletion.

31. The system of claim 29 wherein the means for performing synchronization is configured to refrain from propagating the just-received change into the second dataset to thereby modify user data in the second dataset, if the just-received change was determined by the determining means to have been sent earlier than the previously-received change.

32. The system of claim 31 wherein the means for performing synchronization is configured to propagate the just-received change into the second dataset, at least to an extent for reconciling the just-received change with the second dataset, if the just-received change was determined by the determining means not to have been sent earlier than the previously-received change.

33. The system of claim 32 wherein:

the just-received change involves a data record of the first dataset;

the previously-received change is any change from the first dataset that was received earlier than was the just-received change and that also involves the data record; and

the means for performing synchronization propagates the just-received change into the second dataset, at least to an extent for reconciling the just-received change with the second dataset, if the just-received change was sent earlier than a dataset change from the first dataset that was received earlier than was the just-receiving change but that does not involve the data record.

34. The system of claim 29 wherein the communication network includes an electronic mail network or a wireless paging network.

35. A system for synchronizing a first dataset residing on a first device with a second dataset residing on a second device, wherein the first and second devices are capable of mutual communication via a communication network, the system comprising:

a first synchronization interface configured to access the first dataset and to send synchronization messages reflecting user information of the first dataset via the communication network;

status information associated with the second dataset about past synchronization activity between the first and second datasets; and

a second synchronization interface configured to access the second dataset, to access and maintain the status information, and to receive synchronization messages reflecting user information of the first dataset via the communication network, wherein the second synchronization interface is further configured;

to refrain from altering user information in the second dataset in response to a received synchronization message, hereinafter referred to as the just-received message, sent by the first synchronization interface if the just-received message was sent earlier but received later than another synchronization message from the first dataset, hereinafter referred to as the earlier-received message; and

to alter user information in the second dataset in response to the just-received message, at least to an extent for reconciling the first and second datasets, if the just-received message was not both sent earlier and received later than the earlier-received message.

36. The system of claim 35 wherein:

the first synchronization interface comprises a synchronization engine configured for synchronizing the first dataset with the second dataset as well as a third dataset; and

the second synchronization interface comprises a synchronization accessor configured for synchronizing the second dataset with the first dataset.

37. The system of claim 35 wherein:

the first synchronization interface is configured, when sending a synchronization message reflecting a data record of the first dataset, to include a version indicator of the reflected data record; and

the second synchronization interface is configured to determine whether the just-received synchronization message was sent earlier but received later than the earlier-received message based on the version indicator and the status information.

38. The system of claim 37 wherein:

the first dataset uses a first clock;

the version indicator and the status information include information based on timestamps from the first clock; and

the second synchronization interface is configured to determine whether the just-received message was sent earlier but received later than the earlier-received message based on the version indicator and the status information without needing to compare any timestamp from the first clock with any timestamp based on any clock other than the first clock.

39. The system of claim 37 wherein the version indicator indicates a send time based on a first clock used by the first device.

40. The system of claim 37 wherein:

the status information includes a version indicator, hereinafter referred to as the known-last version indicator, for a data record of the first dataset as reflected by a latest-sent one of received messages from the first dataset; and

the second synchronization interface is configured maintain the known-last version indicator even if a data record of the second dataset that corresponds to the data record of the first dataset has since been overwritten with information from a source other than the first dataset.

41. The system of claim 35 wherein:

the just-received message reflects a first data record of the first dataset;

the earlier-received message also reflected the first data record; and

the second interface is configured to alter user information in the second dataset in response to the just-received message, at least to an extent for reconciling the first and second datasets, if the just-received message was both sent earlier and received later than another synchronization message from the first dataset that reflects a data record of the first dataset other than first data record.

42. The system of claim 35 wherein the communication network includes a message-based wireless or wireline network.