Peer-to-Peer Syncing in a Decentralized Environment

• US 20090006498A1
• Filed: 09/10/2008
• Published: 01/01/2009
• Est. Priority Date: 06/21/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Freedman, Gordie
• Granted Patent: US 8,495,015 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/256 in federated or virtual databases

Abstract

An apparatus and method of synchronizing a datum between a plurality of stores uses version vectors associated with the datum in each store. Each version vector 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 vectors of the datum are compared to determine whether one version vector is subordinate to another version vector. The datum in the store having the subordinate version vector is then replaced with the datum having the dominant version vector. When compared, a conflict resolution by a user is required if the version vectors are not identical, if the version vectors do not have all the same identifiers, and if one version vector does not contain all of the identifiers with equal or greater values of those in the other version vector.

Claims

1. A synchronization method, comprising:

comparing version vectors when synchronizing a datum between stores, each of the version vectors being associated with a copy of the datum in one of the stores and identifying one or more stores that have modified the associated copy of the datum; and

determining whether a conflict exists if neither one of the version vectors can be determined as subordinate to or dominant over the other version vector based on the version vectors alone,

wherein if the conflict exists, the method comprises;

obtaining a resolution of the conflict resolving one of the copies of the datum as being subordinate to or dominant over the other copy of the datum,

merging the version vectors from both the subordinate and dominant copies of the datum together into a resulting version vector without appending one of the version vectors to the other, and

associating the resulting version vector with the dominant copy of the datum in both of the stores.

2. The method of claim 1, wherein determining whether a conflict exists comprises determining whether both of the version vectors identify all of the same stores as having modified the datum.

3. The method of claim 2, wherein if both of the version vectors identify all of the same stores as having modified the datum, the act of determining further comprises:

determining whether all of the same stores identified in a first of the version vectors have modified the datum as much as or more than a second of the version vectors.

4. The method of claim 2, wherein if both of the version vectors do not identify all of the same stores as having modified the datum, the act of determining further comprises:

determining whether all of the stores identified in a first of the version vectors are also identified in a second of the version vectors; and

determining whether all of the same stores identified in the first version vector have modified the datum as much as or more than the second version vector.

5. The method of claim 1, wherein determining whether a conflict exists comprises initiating the conflict if the version vectors are not identical, if the version vectors do not identify all the same stores as modifying the datum, and if all of the same stores identified in one version vector have not modified the datum as much as or more than the other version vector.

6. The method of claim 1, wherein obtaining a resolution of the conflict comprises receiving a user selection indicating one of the copies of the datum as being subordinate to or dominant over the other copy of the datum.

7. The method of claim 1, wherein merging the dominant and subordinate version vectors together into a resulting version vector comprises including each of the stores identified in both the subordinate and dominant version vectors into the resulting version vector.

8. The method of claim 7, wherein merging comprises:

including, for each of the identified stores in the resulting version vector, an indication representing a highest number of times that the identified store has modified the datum.

9. The method of claim 8, wherein merging comprises:

incrementing the indication in the resulting version vector for the identified store having the dominant version vector.

10. The method of claim 1, wherein each of the version vectors includes an indication of the last store that originated the copy of the datum or that has modified the copy of the datum, and wherein merging the subordinate and dominant version vectors together into a resulting version vector comprises including an indication in the resulting version vector that the store having the dominant version vector is the last store that has modified the copy of the datum.

11. The method of claim 10, wherein the indication comprises a unique identifier associated with the last store that has modified the copy of the datum.

12. The method of claim 1, wherein each of the version vectors comprises one or more entries, each of the entries having an identifier and a value, the identifier identifying one of the stores that has modified the datum, the value indicating a number of modifications 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.

14. The method of claim 12, wherein the value comprises a monotonically increasing integer.

15. The method of claim 12, wherein merging the subordinate and dominant version vectors together into a resulting version vector comprises:

including each of the identifiers from both the subordinate and dominant version vectors in the resulting version vector; and

including, for each of the identifiers in the resulting version vector, a highest value for the associated identifier from either the subordinate or dominant version vector.

16. The method of claim 12, wherein merging comprises:

incrementing the highest value in the resulting version vector for the identifier of the store having the dominant version vector.

17. The method of claim 12, further comprising initiating the conflict if the version vectors are not identical, the version vectors do not have all the same identifiers, and one of the version vectors does not contain all of the identifiers with equal or greater values of those in the other version vector.

18. The method of claim 1, wherein determining whether a conflict exists comprises determining that the version vectors are identical, and wherein the method further comprises maintaining the copies of the datum and the version vectors in both of the stores.

19. The method of claim 1, wherein if the conflict does not exist, the method comprises:

determining one of the version vectors as a subordinate version vector and the other of the version vector as a dominant version vector based on the comparison,

replacing the copy of the datum having the subordinate version vector with the copy of the datum having the dominant version vector, and

associating the dominant version vector with the copies of the datum at both of the stores.

20. A computer-readable device having computer executable instructions stored thereon for performing a method of synchronizing a datum between a plurality of stores according to claim 1.

21. A first device capable of synchronizing, the first device comprising:

memory for storing a first copy of a datum and a first version vector associated with the first copy, the first version vector identifying one or more stores that have modified the first copy;

a processor in communication with the memory and configured to;

compare the first version vector to a second version vector when synchronizing the datum with a second device, the second version vector identifying one or more stores that have modified a second copy of the datum, and

determine whether a conflict exists if neither one of the version vectors can be determined as subordinate to or dominant over the other version vector based on the version vectors alone,

wherein if the conflict exists, the processor is configured to;

obtain a resolution of the conflict resolving one of the copies of the datum as being subordinate to or dominant over the other copy of the datum, and

associate a resulting version vector with a resulting copy of the datum in the memory, the resulting version vector merging the first and second version vectors together without appending one of the version vectors to the other, the resulting copy being the copy of the datum resolved as dominant.

22. A synchronization method, comprising:

associating a first atom with a first copy of a datum in a first store, the first atom associated with a first version vector and being consistent with a first scheme of the first store, the first version vector identifying one or more stores that have modified the first copy of the datum;

comparing the first version vector with a second version vector when synchronizing the datum between the first store and a second store by cross-referencing the first version vector associated with the first atom to the second version vector associated with a second atom, the second atom being associated with the second copy of the datum and being consistent with a second scheme of the second store;

determining from the comparison whether the first version vector is subordinate to or dominant over the second version vector; and

updating the copies of the datum based on the determination.

23. The method of claim 22, wherein if the first version vector is subordinate, the act of updating comprises replacing the first copy of the datum with the second copy of the datum from the second store.

24. The method of claim 23, wherein updating comprises maintaining the second copy of the datum at the second store.

25. The method of claim 22, wherein cross-referencing comprises maintaining a table at the first store associating one or more version vectors to one or more first atoms consistent with the first scheme and to one or more second atoms consistent with the second scheme.

26. The method of claim 22, wherein comparing comprises:

determining that the second atom is not known at the first store;

receiving the second version vector from the second store in place of the second atom; and

comparing the first version vector associated with the first atom to the second version vector received from the second store.

27. The method of claim 26, further comprising updating the first store by associating the second atom previously unknown at the first store with the first atom at the first store already associated with the second version vector received from the second store.

28. The method of claim 26, further comprising:

determining that the second version vector is not known at the first store;

generating a new first atom at the first store consistent with the first scheme; and

associating the new first atom at the first store with the second atom and the second version vector received from the second store.

29. The method of claim 28, further comprising sending the new first atom to the second store to associate the new first atom with the first atom and the second version vector at the second store.

30. A computer-readable device having computer executable instructions stored thereon for performing a method of synchronizing a datum between a plurality of stores according to claim 22.

31. A first device capable of synchronizing, the first device comprising:

first memory for storing associations between one or more version vectors and one or more atoms, each of the one or more version vectors identifying one or more stores that have modified the datum;

second memory for storing a first copy of a datum associated with a first version vector and a first of the one or more atoms, the first atom being consistent with a first scheme of the first device; and

a processor in communication with the first and second memories and configured to;

cross-reference the first version vector associated with the first atom to a second version vector associated with a second atom when synchronizing the datum between the first device and a second device, the second atom being consistent with a second scheme of the second device,

compare the first version vector to the second version vector,

determine from the comparison whether the first version vector is subordinate to or dominant over the second version vector, and

handle the first copy of the datum based on the determination.

32. A synchronization method, comprising:

associating a first version vector with a first copy of a datum at a first store, the first version vector including one or more first atoms, each of the one or more atoms identifying one of the stores that have modified the datum, the first atoms being consistent with a first scheme of the first store;

comparing the first version vector with a second version vector when synchronizing the datum between the first store and a second store by cross-referencing the first atoms in the first version vector to second atoms in the second version vector, the second atoms being consistent with a second scheme of the second store;

determining from the comparison whether of the first version vectors is subordinate to or dominant over the second version vector; and

updating the copies of the datum based on the determination.

33. The method of claim 32, further comprising replacing the first copy of the datum with a second copy of the datum from the second store if the first version vector is subordinate.

34. The method of claim 33, further comprising associating a new version vector with the second copy of the datum on the first store, the new version vector corresponding to the second version vector and having the first atoms consistent with the first scheme of the first store.