Peer-to-peer N-way syncing in decentralized environment

• US 8,321,374 B2
• Filed: 02/11/2009
• Issued: 11/27/2012
• Est. Priority Date: 06/21/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Holt, Joe, Freedman, Gordie, Forstall, Scott
• Primary Examiner(s): Leroux, Etienne
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US12/369,093
• Publication Number:
  US 20090144343A1
• Time in Patent Office: 1,385 Days
• Field of Search: 707/610, 707/638, 707/612, 707/614, 707620-626, 707/635, 707/639
• US Class Current: 707/610
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• 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

An apparatus and method of synchronizing a datum between a plurality of stores is disclosed. A version history is associated with the datum in each store. The version history has one or more entries, and each entry has an identifier and a value. The identifier identifies a store that has modified the datum, and the value indicates a number of modifications to the datum made by the store. When synchronizing the datum between stores, the version histories of the datum are compared to determine whether one version history is subordinate to another version history. The datum in the store having the subordinate version history is then replaced with the datum having the dominant version history. When compared, a conflict resolution by a user is required if the version histories are not identical, if the version histories do not have all the same identifiers, and if one version history does not contain all of the identifiers with equal or greater values of those in the other version history.

Claims

1. A computer-implementable synchronization method, comprising:

initiating, using at least one processor, synchronization between first and second peers, the first peer storing a first version of a datum, the first version of the datum associated with a first history, the second peer storing a second version of the datum, the second version of the dataum associated with a second history;

comparing, using the at least one processor, the first and second histories, the first history identifying a first set of one or more peers that have modified the datum and further indicating a number of modifications associated with each of the one or more peers identified in the first set, the second history identifying a second set of one or more peers that have modified the datum and further indicating a number of modifications associated with each of the one or more peers identified in the second set;

initiating a conflict resolution if the act of comparing indicates

the first set of one or more peers differs from the second set of one or more peers by at least one peer, and

all of the peers identified in the first set, that are also identified in the second set, have modified the datum less than corresponding peers identified in the second set;

determining whether the first and second histories identify subordinate and dominant versions of the datum based on the comparison or the conflict resolution; and

indicating, using the at least one processor, that the subordinate version of the datum is replaceable by the dominant version of the datum.

2. The method of claim 1, further comprising:

replacing the subordinate version of the datum with the dominant version of the datum; and

associating the dominant history with the replaced version of the datum.

3. The method of claim 1, wherein the act of initiating the conflict resolution comprises:

obtaining a user-defined resolution identifying which one of the histories identifies either the subordinate or dominant version of the datum; and

adding the subordinate history to a loser array associated with the dominant history.

4. The method of claim 3, further comprising removing a redundant history from the loser array by:

comparing the dominant history to the loser array; and

deleting all subordinate histories from the loser array that are subordinate to the dominant history.

5. The method of claim 4, further comprising removing a redundant history from the loser array by:

comparing subordinate histories in the loser array to one another; and

deleting all subordinate histories from the loser array that are subordinate to any of the other subordinate histories.

6. The method of claim 1, wherein the act of determining comprises determining that the first history identifies the dominant version of the datum if:

the first set of one or more peers does not differ from the second set of one or more peers; and

all peers identified in the first set have modified the datum at least as much as or more than corresponding peers indicated in the second set.

7. The method of claim 1, wherein the act of determining comprises determining that the first history identifies the dominant version of the datum if:

the first set identifies more peers than the second set;

all of the peers identified in the second set are also identified in the first set; and

all of the peers identified in the second set have modified the datum at least as much as or less than indicated for corresponding peers in the first set.

8. The method of claim 1, wherein the act of determining comprises identifying that at least one of the histories has a loser array, the loser array identifying one or more subordinate histories associated with the datum that have lost a conflict resolution.

9. The method of claim 8, wherein the act of determining comprises:

determining that the at least one history having the loser array identifies the dominant version of the datum if the other history matches one of the subordinate histories identified in the loser array of the at least one history.

10. The method of claim 8, wherein the act of determining comprises:

determining that the at least one history having the loser array identifies the dominant version of the datum if the other history is subordinate to one of the subordinate histories identified in the loser array of the at least one history.

11. The method of claim 1, wherein each of the first and second histories comprises one or more entries, each entry having an identifier and a value associated with the identifier, the identifier identifying one of the peers that has modified the datum, the value indicating the number of modifications made to the datum by the peer identified by the identifier.

12. The method of claim 11, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the peers, and wherein the value comprises a monotonically increasing integer.

13. The method of claim 11, wherein the identifier for a given peer is added to the version history of the datum when the datum is modified by the given peer.

14. The method of claim 11, wherein the value associated with the identifier for a given peer is incremented when the datum is modified at the given peer.

15. The method of claim 1, further comprising:

determining that the first and second version histories are identical; and

maintaining the first and second versions of the datum and the first and second histories at the first and second peers.

16. A non-transitory computer-readable medium having computer executable instructions stored thereon for performing a synchronization method according to claim 1.

17. A computer-implementable synchronization method, comprising:

initiating, using at least one processor, synchronization between first and second peers, the first peer storing a first version of a datum, the first version of the datum associated with a first history, the second peer storing a second version of the datum, the second version of the datum associated with a second history and a loser array, the loser array identifying more than one subordinate histories that have lost a conflict resolution;

determining whether the first history is subordinate to one of the subordinate histories in the loser array by comparing, using the at least one processor, the first history and the loser array; and

indicating, using the at least one processor, that the first version of the datum at the first peer is replaceable by the second version of the datum at the second peer if the first history is identified as being subordinate.

18. The method of claim 17, further comprising:

replacing the first version of the datum with the second version of the datum; and

adding the second history to a loser array associated with the replaced version of the datum.

19. The method of claim 17, wherein the act of determining whether the first history is subordinate comprises determining whether the first history matches one of the subordinate histories in the loser array.

20. The method of claim 17, wherein the first history identifies a first set of one or more peers that have modified the datum and indicates a number of modifications associated with each of the one or more peers identified in the first set, and wherein a group of the more than one subordinate histories in the loser array identifies a second set of one or more peers that have modified the datum and indicates a number of modifications associated with each of the one or more peers identified in the second set.

21. The method of claim 20, wherein the act of determining whether the first history is subordinate comprises determining:

the first set of one or more peers does not differ from the second set of one or more peers; and

all of the peers identified in the second set have modified the datum at least as much as or more than corresponding peers indicated in the first set.

22. The method of claim 20, wherein the act of determining whether the first history is subordinate comprises determining:

the second set identifies more peers than the first set,

all of the peers identified in the first set are also identified in the second set, and

all of the peers identified in the first set have modified the datum at least as much as or less than indicated for corresponding peers in the second set.

23. The method of claim 17, further comprising removing a redundant history from the loser array by:

comparing the dominant history to the loser array; and

deleting all subordinate history from the loser array that are subordinate to the dominant history.

24. The method of claim 17, further comprising removing a redundant history from the loser array by:

comparing subordinate histories in the loser array to one another; and

deleting all subordinate histories from the loser array that are subordinate to any of the other subordinate histories.

25. A non-transitory computer-readable medium having computer executable instructions stored thereon for performing a synchronization method according to claim 17.

26. A computer-implementable synchronization method, comprising:

initiating, using at least one processor, synchronization between first and second peers, the first peer storing a first version of a datum, the first version of the datum associated with a first history, the second peer storing a second version of the datum, the second version of the datum associated with a second history;

determining, using the at least one processor, a conflict between the first and histories by comparing the first and second histories,

obtaining, using the at least one processor, a resolution of the conflict, the resolution identifying one of the histories as a subordinate history associated with a subordinate version of the datum and identifying the other history as a dominant history associated with a dominant version of the datum;

adding the subordinate history to a loser array associated with the dominant history, wherein the loser array identifies more than one subordinate histories that have lost a conflict resolution; and

indicating, using the at least one processor, that the subordinate version of the datum is replaceable by the dominant version of the datum.

27. The method of claim 26, further comprising:

replacing the subordinate version of the datum with the dominant version of the datum; and

associating the dominant history with the replaced version of the datum.

28. The method of claim 26, wherein obtaining the resolution of the conflict comprises initiating a user-defined resolution of the conflict if:

the first set of one or more peers differs from the second set of one or more peers by at least one peer, and

all of the peers identified in one history have not modified the datum at least as much as or more than corresponding peers indicated in the other history.

29. The method of claim 26, wherein obtaining the resolution of the conflict comprises:

determining whether the second history has a loser array identifying one or more subordinate histories that have lost a conflict resolution; and

determining whether the first history is subordinate to one of the subordinate histories identified in the loser array of the second history.

30. The method of claim 29, wherein the act of determining whether the first history is subordinate comprises:

determining whether the first history matches one of the subordinate histories identified in the loser array of the second history.

31. The method of claim 29, wherein the first history identifies a first set of one or more peers that have modified the datum and indicates a number of modifications associated with each of the one or more peers identified in the first set, and wherein a group of the more than one subordinate histories in the loser array identifies a second set of one or more peers that have modified the datum and indicates a number of modifications associated with each of the one or more peers identified in the second set.

32. The method of claim 31, wherein the act of determining whether the first history is subordinate comprises determining:

the first set or one or more peers does not differ from the second set of one or more peers; and

all of the peers identified in the second set have modified the datum at least as much as or more than corresponding peers indicated in the first set.

33. The method of claim 31, wherein the act of determining whether the first history is subordinate comprises determining:

the second set identifies more peers than the first set,

all of the peers identified in the first set are also identified in the second set, and

all of the peers identified in the first set have modified the datum at least as much as or less than indicated for corresponding peers in the second set.

34. The method of claim 26, further comprising removing a redundant history from the loser array by:

comparing the second history to the loser array; and

deleting all subordinate histories from the loser array that are subordinate to the second history.

35. The method of claim 26, further comprising removing a redundant history from the loser array by:

comparing the subordinate histories in the loser array to one another; and

deleting all the subordinate histories from the loser array that are subordinate to any of the other subordinate histories.

37. A non-transitory computer-readable medium having computer executable instructions stored thereon for performing a synchronization method according to claim 26.

36. The method of 26, further comprising removing a redundant history from the loser array automatically when the second history is updated by a change to the datum at the second peer or when synchronizing between peers.