System and methods for synchronizing two or more datasets

• US 6,295,541 B1
• Filed: 08/18/1998
• Issued: 09/25/2001
• Est. Priority Date: 12/16/1997
• Status: Expired due to Term

• Current Assignee: Intellisync Corporation (Nokia Corporation)
• Original Assignee: Starfish Software, Inc. (Nokia Corporation)
• Inventors: Bodnar, Eric O., Kirani, Shekhar, Dube, Bryan, LaRue, Chris, Suresh, Sethuraman
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/136,215
• Time in Patent Office: 1,134 Days
• Field of Search: 707/3, 707/4, 707/8, 707/10, 707/201, 707/101, 709/238, 709/500, 709/248, 714/12, 714/15, 714/20
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• 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/99954 Version management

Abstract

Synchronization system and associated methods provide synchronization of an arbitrary number of datasets, including more than two datasets. To achieve this, a reference dataset is used to store a super-set of the latest or most-recent data from all user datasets to provide a repository of information that is available at all times. Therefore, if the user later wishes to synchronize a new user dataset, such as one in a server computer that stores user information, the system already has all the information necessary for synchronizing the new dataset, regardless of whether any of the other datasets are then available. Further, to simplify use, a unified user interface is provided that allows the user to easily determine which of his or her datasets are currently set to be synchronized and allows the user to conveniently alter the current settings to select one, two, or even more than two clients for synchronization. Various “conflict” or “duplicate” resolution strategies are described for intelligently handling complexities resulting from allowing synchronization for an arbitrary number of datasets and allowing synchronization using even data from datasets that are not available. Architectural support for “plug-in” client accessors and type modules is also provided. This allows support to be added for new datasets or new types of data merely by developing and plugging in new, compact client accessors or type modules, without updating or replacing the core synchronization engine.

Claims

1. In an information processing system, a method for synchronizing an arbitrary number of multiple datasets residing on different devices, the method comprising:

accepting a designation of an arbitrary number of multiple datasets comprising more than two datasets from different devices to be synchronized, wherein at least one of the designated datasets includes one record to be synchronized with all others of the designated datasets;

in response to said designation, creating a reference dataset that is used to store a super-set of most-recent data from all of the designated datasets, said reference dataset having records that are uniquely identified in a manner that is independent of how records are identified in any given one of the designated datasets, thereby providing a repository of information that is available independent of unavailability of one of said devices at a given point in time; and

in response to the designation and based on the information stored by said reference dataset, synchronizing all of the designated datasets without requiring further designating of datasets to be synchronized, wherein, after the step of synchronizing, each of the designated datasets includes a record that corresponds to, and is in a synchronized state with, the one record.

2. The method of claim 1 wherein the number of designated datasets is N, and the step of synchronizing the N designated datasets comprises performing a sequence of binary reconciliations, each involving at least one of the N designated datasets, to obtain at least one dataset that is globally-synchronized, wherein any globally-synchronized dataset includes propagated changes, if any exist and were not discarded due to conflict resolution, from each of the N designated datasets, and any dataset by definition includes changes, if any, propagated from itself.

3. The method of claim 2 wherein the step of synchronizing the N designated datasets further comprises, after the step of performing the sequence of binary reconciliations, synchronizing each dataset, of the N designated datasets, that is not yet globally-synchronized with another dataset that is already globally-synchronized.

4. The method of claim 3 wherein a reference dataset is involved in each of at least N−

1 binary reconciliations in the sequence of binary reconciliations.

5. The method of claim 3 wherein the sequence of binary reconciliations comprises at most N binary reconciliations, wherein at least (N−

1) of the at most N binary reconciliations each involves at least one of the N designated datasets.

6. The method of claim 3 wherein:

the sequence of binary reconciliations includes a first binary reconciliation involving a first dataset and a second, later binary reconciliation;

the first dataset includes a record that has a modification time; and

the step of performing the sequence of binary reconciliations comprises causing, during the first binary reconciliation, a recording of the modification time such that the modification time is available for use after start of the second binary reconciliation.

7. The method of claim 6 wherein:

the second binary reconciliation involves a second and a third dataset, each of which is not the first dataset; and

the step of performing the sequence of binary reconciliations further comprises comparing the recorded modification time to another time in resolving a conflict between a record from the second dataset and a record that is already in a synchronized state with regard to the first record.

8. The method of claim 1 wherein the step of synchronizing the more than two designated datasets comprises:

providing a synchronizer dataset that contains records, wherein the synchronizer dataset reflects a result of an earlier synchronization;

comparing each of the more than two designated datasets to the synchronizer dataset to identify an addition, update, or deletion of a record in the each designated dataset;

changing at least two of the designated datasets based on the identified addition, update, or deletion of a record; and

changing the synchronizer dataset based on the identified addition, update, or deletion of a record.

9. An information processing system for synchronizing an arbitrary number of multiple datasets from different devices, the system comprising:

means for accepting a designation of an arbitrary number of datasets comprising more than two datasets from different devices to be synchronized, wherein at least one of the designated datasets includes one record to be synchronized with all others of the designated datasets;

means, responsive to said designation, for creating a reference dataset that is used to store a super-set of most-recent data from all of the designated datasets, said data comprising records uniquely identified within the reference dataset in a manner that is independent of how data is identified within the designated datasets, for providing a repository of information that is available independent of unavailability of one of said devices at a given point in time; and

means for synchronizing, in response to the designation and based on the information stored by said reference dataset, the more than two designated datasets without requiring further designating of datasets to be synchronized, wherein, after the step of synchronizing, each of the more than two designated datasets includes a record that corresponds to, and is in a synchronized state with, the one record.

10. A computer program product for use with a computer system comprising:

a computer-readable storage medium;

computer code on the storage medium for instructing the computer system to accept a designation of an arbitrary number of datasets comprising more than two datasets from different devices to be synchronized, wherein at least one of the designated datasets includes one record to be synchronized with all others of the designated datasets;

computer code on the storage medium, responsive to said designation, for creating a reference dataset that is used to store a super-set of most-recent data from all of the designated datasets, said data comprising records uniquely identified within the reference dataset in a manner that is independent of how data is identified within the designated datasets, for providing a repository of information that is available independent of unavailability of one of said devices at a given point in time; and

computer code on the storage medium for instructing the computer system to synchronize, in response to the designation and based on the information stored by said reference dataset, the more than two designated datasets without requiring further designating of datasets to be synchronized, wherein, after the step of synchronizing, each of the more than two designated datasets includes a record that corresponds to, and is in a synchronized state with, the one record.

11. A method capable of synchronizing more than two designated datasets, the method comprising:

providing a synchronizer dataset that contains records, wherein the synchronizer dataset reflects a result of an earlier synchronization of the designated datasets, and wherein each record in the synchronizer dataset is identified by a globally-unique record identifier that is independent of how any corresponding records from the designated datasets are identified;

creating a table that associates each globally-unique record identifier to any corresponding records residing on the designated datasets;

using said synchronizer dataset and said table, comparing values derived from each of the more than two designated datasets to values derived from the synchronizer dataset to identify a change of a record in the each designated dataset since an earlier synchronization involving the each designated dataset; and

changing at least two of the designated datasets based on the identified change of a record.

12. The method of claim 11 wherein the step of comparing each of the designated datasets to the synchronizer dataset comprises, for each of the designated datasets, comparing values derived from records from the each designated dataset to values derived from the synchronizer dataset to determine whether any records of the each designated dataset are updates or additions, or whether any record of the each designated dataset has been deleted, since a prior synchronization involving the each designated dataset.

13. The method of claim 12 wherein the step of comparing values derived from records comprises determining a particular record in the each designated dataset to be an update, if the particular record possesses a modification time that is later than a particular time.

14. The method of claim 13 wherein the particular time is a priority time associated with the corresponding record in the synchronizer dataset.

15. The method of claim 14 wherein the priority time is indicative of a modification time, herein referred to as the original priority time, of a record in a particular dataset, wherein values derived from the record in the particular dataset were used to change the corresponding record in the synchronizer dataset due to an earlier synchronization.

16. The method of claim 13 wherein the particular time is a time established based on a most recent earlier synchronization that involved the each designated dataset.

17. The method of claim 18 wherein the particular time is indicative of a time no earlier than a latest modification time, from any record of the each designated dataset, that existed prior to and was seen during the most recent earlier synchronization that involved the each designated dataset.

18. The method of claim 12 further comprising resolving conflicts among at least determined updates or deletions corresponding to a single record of the synchronizer dataset.

19. The method of claim 18 wherein:

the step of providing a synchronizer dataset comprises providing status information regarding contents of at least a particular dataset, of the designated datasets, according to an earlier synchronization involving the particular dataset; and

the step of comparing values derived from records further comprises;

determining a particular record in the each designated dataset to be an addition, if the particular record has no corresponding record in the synchronizer dataset; and

determining that the particular dataset includes a deletion, if the particular dataset no longer includes a valid record that corresponds to a particular record in the synchronizer dataset, wherein the particular dataset did have such a valid record at the end of an earlier synchronization, according to the status information.

20. The method of claim 19 wherein the step of comparing values derived from records further comprises:

comparing a CRC-type result derived from the particular record in the each designated dataset with a CRC-type result derived from the particular record during the earlier synchronization involving the each designated dataset; and

determining the particular record in the each designated dataset to be an update, if the CRC-type results differ.

21. The method of claim 19 wherein the step of comparing values derived from records comprises determining the particular record in the each designated dataset to be an update only if the particular record in the each designated dataset possesses a modification time that is later than a particular time.

22. The method of claim 19 further comprising:

comparing at least one value derived from a determined addition of a record with values derived from at least one other record to determine whether the determined addition represents a duplication of records.

23. The method of claim 22 further comprising:

comparing at least one value derived from a determined update of a record with values derived from at least one other record to determine whether the determined update represents a duplication of records; and

resolving any determined duplication of records.

24. The method of claim 19 further comprising, for at least one of the designated datasets:

identifying a change of a record in the synchronizer dataset since an earlier synchronization involving the at least one designated dataset; and

changing the at least one designated dataset based on the identified change in the synchronizer dataset.

25. The method of claim 24 wherein the step of resolving conflicts comprises resolving conflicts among a plurality of determined updates or deletions corresponding to the single record of the synchronizer dataset, wherein the plurality of determined updates or deletions includes an update or deletion identified in the synchronizer dataset and an update or deletion identified in one of the designated datasets.

26. The method of claim 24 wherein the step of resolving conflicts comprises resolving conflicts among more than two updates or deletions that correspond to the single record of the synchronizer dataset by giving precedence to one of the more than two updates or deletions over others of the more than two updates or deletions.

27. The method of claim 11 wherein at least one of the designated datasets is a non-participant in the earlier synchronization the result of which is reflected in the provided synchronizer dataset.

28. The method of claim 11 wherein all of the designated datasets are non-participants in the earlier synchronization the result of which is reflected in the provided synchronizer dataset.

29. The method of claim 28 further comprising, in the earlier synchronization, changing a first record in the synchronizer dataset;

and after the earlier synchronization, in synchronizing the designated datasets;

identifying the changed first record in the synchronizer dataset to be an addition, update, or deletion; and

changing the designated datasets based on the first record in the synchronizer dataset.

30. A system for synchronizing more than two designated datasets, the system comprising:

means for providing a synchronizer dataset that contains records, wherein the synchronizer dataset reflects a result of an earlier synchronization and wherein each record in the synchronizer dataset is identified by a globally-unique record indentifier that is independent of how any corresponding records form the designated datasets are identified;

means for creating a table that associates each globally-unique record identifier to any corresponding records residing on the designated datasets;

using said synchronizer dataset and said table, comparing values derived from means, responsive to said synchronizer dataset and said table, for comparing each of the more than two designated datasets to the synchronizer dataset to idenifty an addition, update, or deletion of a record in the each designated dataset since an earlier synchronization involving the each designated dataset;

means for updating at least two of the designated datasets based on the identified addition, update, or deletion of a record; and

means for updating the synchronizer dataset based on the identified addition, update, or deletion of a record.