PEER-TO-PEER N-WAY SYNCING IN DECENTRALIZED ENVIRONMENT

• US 20090144343A1
• Filed: 02/11/2009
• Published: 06/04/2009
• Est. Priority Date: 06/21/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: HOLT, JOE, Freedman, Gordie, Forstall, Scott
• Granted Patent: US 8,321,374 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 synchronization between first and second stores using at least one processor, the first store storing a first version of a datum and having a first history associated therewith, the second store storing a second version of the datum and having a second history associated therewith;

determining whether the first and second histories identify subordinate and dominant versions of the datum by comparing the first and second histories with the at least one processor, the first history identifying a first set of one or more stores that have modified the datum and indicating a number of modifications associated with each of the one or more stores identified in the first set, the second history identifying a second set of one or more stores that have modified the datum and indicating a number of modifications associated with each of the one or more stores identified in the second set; and

indicating with 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 comparing comprises initiating a conflict resolution if—

the first and second sets do not identify all the same stores as having modified the datum, and

all of the same stores identified in one set have not modified the datum as much as or more than indicated in the other set.

4. The method of claim 3, 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.

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

comparing the dominant history to the loser array; and

deleting any subordinate history from the loser array that is subordinate to the dominant history.

6. 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 any one of the subordinate histories from the loser array that are subordinate to any of the other subordinate histories.

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—

both the first and second sets identify all of the same stores as having modified the datum, and

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

8. 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 stores than the second set,

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

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

9. 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.

10. The method of claim 9, 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.

11. The method of claim 9, 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.

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

13. The method of claim 12, 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 stores, and wherein the value comprises a monotonically increasing integer.

14. The method of claim 12, wherein the identifier for a given store is added to the version history of the datum when the datum is modified at the given store.

15. The method of claim 12, wherein the value associated with the identifier for a given store is incremented when the datum is modified at the given store.

16. 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 stores.

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

18. A computer-implementable synchronization method, comprising:

initiating synchronization between first and second stores using at least one processor, the first store storing a first version of a datum and having a first history associated therewith, the second store storing a second version of the datum and having a second history and a loser array associated therewith, the loser array identifying one or more 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 the first history and the loser array with the at least one processor; and

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

19. The method of claim 18, further comprising:

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

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

20. The method of claim 18, 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.

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

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

determining that the first history is subordinate if—

at least one of the second sets identifies all of the same stores as having modified the datum as identified in the first set, and

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

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

determining that the first history is subordinate if—

at least one of the second sets identifies more stores than the first set,

all of the stores identified in the first set are also identified in the at least one second set, and

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

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

comparing the dominant history to the loser array; and

deleting any subordinate history from the loser array that is subordinate to the dominant history.

25. The method of claim 18, further comprising removing a redundant history from the loser array by—

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

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

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

27. A computer-implementable synchronization method, comprising:

initiating synchronization between first and second stores using at least one processor, the first store storing a first version of a datum and having a first history associated therewith, the second store storing a second version of the datum and having a second history associated therewith;

determining a conflict between the first and histories by comparing the first and second histories with the at least one processor;

obtaining a resolution of the conflict using the at least one processor, 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; and

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

28. The method of claim 27, 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.

29. The method of claim 27, wherein obtaining the resolution of the conflict comprises initiating a user-defined resolution of the conflict if—

the first and second histories do not identify all the same stores as having modified the datum, and

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

30. The method of claim 27, 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.

31. The method of claim 30, 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.

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

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

determining that the first history is subordinate if—

the first set identifies all of the same stores has having modified the datum as identified in at least one of the second sets, and

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

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

determining that the first history is subordinate if—

at least one of the second sets identifies more stores than the first set,

all of the stores identified in the first set are also identified in the at least one second set, and

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

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

comparing the second history to the loser array; and

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

36. The method of claim 27, further comprising removing a redundant history from the loser array by—

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

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

38. A computer-readable medium having computer executable instructions stored thereon for performing a synchronization method according to claim 27.

37. The method of 27, 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 store or when synchronizing between stores.