System and methods for synchronizing datasets in a communication environment having high-latency or other adverse characteristics

• US 6,460,051 B1
• Filed: 04/09/1999
• Issued: 10/01/2002
• Est. Priority Date: 10/28/1998
• Status: Expired due to Term

• Current Assignee: Intellisync Corporation (Nokia Corporation)
• Original Assignee: Starfish Software, Inc. (Nokia Corporation)
• Inventors: Dube, Bryan, Yu, Chiahua George, LaRue, Chris
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/289,551
• Publication Number:
  US 20020156798A1
• Time in Patent Office: 1,271 Days
• Field of Search: 707/8, 707/10, 707/207, 707/202, 707/203, 707/3, 707/4, 709/248, 709/220, 714/12, 714/15, 714/20
• 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/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

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, in an information processing system, a method for synchronizing a first dataset with at least a second dataset via a communication medium includes a step of storing information that is indicative of a first version of user data of the first dataset, wherein the first version has been involved in prior use for synchronizing with the second dataset. The method further includes steps of identifying a change in the second dataset that is new relative to the first version of the user data of the first dataset; via the communication medium, communicating the change in the second dataset and indicating the first version based on the stored information; determining whether user data currently in the first dataset has changed relative to the first version that was indicated in the communicating and indicating step; deciding whether to commit the communicated change to the first dataset based at least in part on the determining step; and committing the communicated change to the first dataset if the communicated change is decided to be committed in the deciding step.

Claims

1. A method for synchronizing a first dataset in a client with a second dataset, using a synchronizer, the first and second datasets having been previously synchronized during a first synchronization, and the current synchronization method being a second synchronization, the method comprising:

the client sending a first set of changes to the synchronizer that have been made to the first dataset since the first synchronization;

the client allowing additional changes to be made to the first dataset during the second synchronization;

the synchronizer performing conflict resolution on the first set of changes received from the client and on a second set of changes that have been made to the second dataset since the first synchronization;

the synchronizer updating the second dataset with one or more conflict-resolved changes from the first set of changes;

the synchronizer sending one or more conflict-resolved changes from the second set of changes to the client;

the client determining, for each of the conflict-resolved changes received from the synchronizer, whether a recent change has been made to a corresponding record in the first dataset since the first set of changes was sent to the synchronizer, and;

if a recent change has not been made to a corresponding record since the first set of changes was sent to the synchronizer, implementing the conflict-resolved change into the first dataset;

or

if a recent change has been made to a corresponding record since the first set of changes was sent to the synchronizer, performing special handling of the conflict-resolved change to resolve any possible conflicts with the recent change.

2. The method of claim 1, wherein the client determines whether a recent change has been made to a corresponding record in the first dataset since the first set of changes was sent to the synchronizer by noting a version indicator identifying a version of the corresponding record at the time the first set of changes was sent and determining whether a current version of the corresponding record is different from the version at the time the first set of changes was sent.

3. The method of claim 2, wherein the version indicator is a timestamp value indicating the time at which the first set of changes was sent, and the determination of whether a current version of the corresponding record is different from the version at the time the first set of changes was sent is done by comparing the version indicator timestamp with a timestamp indicating the last time that the corresponding record was modified.

4. The method of claim 2, wherein the version indicator is a timestamp value indicating the last time at which a change related to the corresponding record was sent from the client to the synchronizer, and the determination of whether a current version of the corresponding record is different from the version at the time the first set of changes was sent is done by comparing the version indicator timestamp with a timestamp indicating the last time that the corresponding record was modified.

5. The method of claim 2, wherein the version indicator is a timestamp value indicating the last time prior to the time that the change is sent to the synchronizer at which the corresponding record was modified, and the determination of whether a current version of the corresponding record is different from the version at the time the first set of changes was sent is done by comparing the version indicator timestamp with a timestamp indicating the last time that the corresponding record was modified.

6. The method of claim 2, wherein when the client sends changes to the synchronizer, the client also sends a version indicator for each change, indicating the version of the corresponding record at the time that each change is sent, and when the synchronizer sends changes to the client, the synchronizer also returns the version indicators received from the client, for each record corresponding to the changes sent by the synchronizer.

7. The method of claim 6, wherein the version indicator for a record is a timestamp value indicating the last time at which a change pertaining to the record has been sent to the synchronizer.

8. The method of claim 7, wherein the timestamp for the version indicator is based on a local clock of the first dataset.

9. The method of claim 1, wherein the step of performing special handling of the conflict-resolved change involves the client performing a conflict resolution between the conflict-resolved change and the recent change to the corresponding record.

10. The method of claim 1, wherein the step of performing special handling of the conflict-resolved change involves discarding the conflict-resolved change and relying on the synchronizer to perform a conflict resolution at a later time between the recent change to the corresponding record and the conflict-resolved change received from the synchronizer.

11. The method of claim 10 further comprising:

acknowledging the conflict-resolved change in an ordinary manner, if the conflict-resolved change was implemented into the first dataset as a result of the determining step;

or

refraining from acknowledging the conflict-resolved change in the ordinary manner, if the conflict-resolved change was discarded as a result of the determining step.

12. The method of claim 1 wherein:

the client and the first dataset reside on a first device;

the synchronizer and the second dataset reside on a second device; and

the first and second devices are capable of communication via a communication medium.

13. The method of claim 1 wherein the determining step further comprises:

determining whether the conflict-resolved change was sent earlier than a previously-received change involving the corresponding record; and

if the conflict-resolved change is determined to have been sent earlier than the previously-received change, performing special handling of the conflict-resolved change to resolve any possible conflicts between the conflict-resolved change and the previously-received change.

14. A method for a client to interface with a synchronizer to synchronize a first dataset in the client with one or more other datasets, the first dataset and the other datasets each comprising a plurality of data records, the method comprising:

the client sending one or more changes to the synchronizer that have been made to the records of the first dataset, the client noting a version indicator for each record for which a change is sent to the synchronizer for indicating a version of the record; and

the client receiving one or more conflict-resolved changes from the synchronizer for implementation in the first dataset, where for each conflict-resolved change received from the synchronizer the client uses a corresponding version indicator to determine if the corresponding record in the first dataset has changed from the version of the record that was last sent to the synchronizer, and if the corresponding record has not changed, implementing the change in the first dataset, or if the corresponding record has changed, performing special handling to resolve any possible conflicts between the conflict-resolved change and any change to the corresponding record that has been made since the version that was last sent to the synchronizer.

15. The method of claim 14, wherein a version indicator is a timestamp value indicating the last time at which a change related to a corresponding record was sent from the client to the synchronizer, and the determination of whether a corresponding record in the first dataset has changed from the version of the record that was last sent to the synchronizer is done by comparing the version indicator timestamp with a timestamp indicating the last time that the corresponding record was modified.

16. The method of claim 14, wherein when the client sends changes to the synchronizer, the client also sends a version indicator for each change, indicating the version of the corresponding record at the time that each change is sent, and when the client receives changes from the synchronizer, the client also receives the version indicators sent from the client, for each record corresponding to the changes sent by the synchronizer.

17. The method of claim 16, wherein the version indicator for a record is a timestamp value indicating the last time at which a change pertaining to the record has been sent to the synchronizer.

18. The method of claim 14, wherein the step of performing special handling of the conflict-resolved change involves the client performing a conflict resolution between the conflict-resolved change and the corresponding record.

19. The method of claim 14, wherein the step of performing special handling of the conflict-resolved change involves discarding the conflict-resolved change and relying on the synchronizer to perform a conflict resolution at a later time between the conflict-resolved change received from the synchronizer and any change to the corresponding record that has been made since the version that was last sent to the synchronizer.

20. A method for a client to process changes received from a synchronizer in a synchronization system, the client having a client dataset comprising a plurality of data records, each of the changes from the synchronizer pertaining to one of the records in the client dataset, the method comprising:

for each change received from the synchronizer, determining a latest version of the corresponding record of which the synchronizer is aware, and if the corresponding record has changed since the latest version of which the synchronizer is aware, performing special handling to have any possible conflicts between the received change and the corresponding record resolved, or if the corresponding record has not changed since the latest version of which the synchronizer is aware, implementing the received change into the client dataset.

21. The method of claim 20, wherein the client also receives from the synchronizer a version indicator for each change, indicating the latest version of the corresponding record of which the synchronizer is aware.

22. The method of claim 21, wherein a version indicator is a timestamp value indicating a last time at which a change related to the corresponding record was sent from the client to the synchronizer.

23. The method of claim 20, wherein the step of performing special handling of the change received from the synchronizer involves the client performing a conflict resolution between the change received from the synchronizer and the corresponding record.

24. The method of claim 20, wherein the step of performing special handling of the change received from the synchronizer involves discarding the change and relying on the synchronizer to perform a conflict resolution at a later time between the change received from the synchronizer and the corresponding record.