Systems and methods for replicating data stores

• US 20050086272A1
• Filed: 07/31/2003
• Published: 04/21/2005
• Est. Priority Date: 07/31/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Lev Novik Et Al. To Microsoft Corporation
• Inventors: Novik, Lev, Terry, Douglas B., Shah, Ashish, Anand, Sanjay, Wu, Yunxin, Hudis, Irena
• Granted Patent: US 7,440,981 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

Systems and methods for replicating replicas in a sync community. Each replica in the sync community stores knowledge that represents changes the replica is aware of. Because each replica has its own knowledge, each replica does not need to know how many replicas are in the sync community or the topology of the sync community. By sending the knowledge with a request for changes, a replicating replica can enumerate the changes to replicate by comparing its knowledge with the received knowledge. After replication, the knowledge is updated. Knowledge may also include made-with-knowledge change IDs that permit each resolution to identify what a replica was aware of when a particular change was made. The made-with-knowledge values are used to detect conflicts during replication.

Claims

1. In a sync community that includes a plurality of replicas, wherein each replica is able to make changes to data independently of other replicas in the sync community, a method for replicating a replica in the sync community, the method comprising a first replica performing:

receiving a knowledge vector from a second replica in a sync community, wherein the knowledge vector represents changes to data that the second replica is aware of;

comparing the knowledge vector of the second replica with versions associated with changes in the first replica to identify changes on the first replica that are not known by the second replica; and

sending the identified changes to the second replica.

2. A method as defined in claim 1, the first replica having a knowledge vector that represents changes to data that the first replica is was are of, further comprising sending the knowledge vector of the first replica to the second replica.

3. A method as defined in claim 1, wherein sending the identified changes wherein the second replica identified the other changes by comparing the knowledge vector of the first replica with versions associated with the other changes in the second replica.

4. A method as defined in claim 1, wherein comparing the knowledge vector of the second replica with versions associated with changes in the first replica to identify changes on the first replica that are not known by the second replica further comprises performing conflict detection.

5. A method as defined in claim 4, wherein performing conflict detection further comprises:

receiving a first made-with-knowledge value from the second replica, wherein the first made-with-knowledge value is associated with a first change and represents changes that the replica that assigned the first made-with-knowledge value was aware of when the first made-with-knowledge value was assigned;

sending a second made-with knowledge value to the second replica, wherein the second made-with-knowledge value is associated with a second change and represents changes the replica that assigned the second made-with-knowledge value was aware of when the second made-with-knowledge value was assigned; and

determining that a conflict exists if a change ID of the first change is not included in the second made-with-knowledge value and a change ID of the second change is not included in the first made-with-knowledge value.

6. A method as defined in claim 1, further comprising updating a knowledge vector of the second replica.

7. A method as defined in claim 6, further comprising storing an exception list that includes change IDs that correspond to changes received from the first replica.

8. A method as defined in claim 7, wherein each change ID includes a replica ID that is associated with a particular replica in the sync community and a version.

9. In a sync community that includes a plurality of replicas, wherein each replica is able to make changes to data independently of other replicas in the sync community, a method for replicating a replica in the sync community, the method comprising:

maintaining a first knowledge at a first replica, wherein the first knowledge includes change IDs that are associated with at least changes in the first replica;

enumerating changes at the first replica that are not known at a second replica by comparing a second knowledge of the second replica that includes change IDs with the change IDs that are associated with changes in the first replica; and

sending the enumerated changes to the second replica.

10. A method as defined in claim 9, further comprising receiving changes from the second replica that the second replica enumerated by comparing the first knowledge with the second knowledge.

11. A method as defined in claim 9, further comprising detecting conflicts between the first replica and the second replica by:

determining whether the first replica was aware of a change made to a particular item by the second replica when the first replica made a separate change to the particular item; and

determining whether the second replica was aware of the separate change made to the particular item by the first replica when the second replica made the change to the particular item.

12. A method as defined in claim 9, wherein maintaining a first knowledge at a first replica further comprises including made-with-knowledge values in the first knowledge, wherein each made-with-knowledge value is associated with a certain change and each made-with-knowledge value identifies changes that the replica that assigned the made-with-knowledge value was aware of when the made-with-knowledge value was associated with the certain change.

13. A method as defined in claim 9, further comprising updating the second knowledge to reflect changes received from the first replica and applied to the second replica.

14. A method as defined in claim 9, further comprising including an exception list in the first knowledge during replication such that changes received by the second replica are included in the second knowledge if the replication is not completed.

15. A method as defined in claim 14, further comprising representing the knowledge as a knowledge vector.

16. A method as defined in claim 14, further comprising replicating a replica through a surrogate replica such that all changes made by the replica have a change ID assigned by the surrogate replica.

17. A computer program product having computer-executable instructions for performing the method of claim 9.

18. In a sync community that includes one or more replicas, a method for replicating the one or more replicas such that each replica does not have to be aware of all replicas in the sync community or of a topology of the sync community, the method comprising a replica performing:

storing a knowledge vector at the replica, wherein the knowledge vector includes one or more change IDs that represent changes the replica knows;

during replication, comparing the knowledge vector with a knowledge vector of a second replica to identify first changes that the second vector does not know, wherein the second vector also compares the knowledge vectors to identify second changes at the second replica that the first replica does not know;

sending the first changes to the second replica; and

receiving the second changes from the second replica.

19. A method as defined in claim 18, further comprising including made-with-knowledge values in the knowledge vector such that the replica can determine if a particular change at the replica is in conflict with a change on the second replica.

20. A method as defined in claim 18, further comprising updating the knowledge vector after replication.

21. A method as defined in claim 18, further comprising including an exception list in the knowledge vector, wherein each entry in the exception list corresponds to a change received from the second replica.

22. A method as defined in claim 21, further comprising updating the knowledge vector when a change occurs at the first replica.

23. In a sync community that includes one or more replicas that replicate data, a method for detecting conflicts during replication between a first replica and a second replica in the sync community, the method comprising:

storing a first plurality of changes at a first replica, wherein each change in the first plurality of changes is associated with a change ID and a made-with knowledge value;

receiving a second plurality of changes from a second replica, wherein each change in the second plurality of changes is associated with a change ID and a made-with-knowledge value; and

comparing the made-with-knowledge values of the second plurality of changes with the first plurality of changes to determine if a particular change in the first plurality of changes was made with knowledge of changes in the second plurality of changes;

comparing the made-with-knowledge values of the first plurality of changes with the second plurality of changes to determine if a particular change in the second plurality of changes was made with knowledge of changes in the first plurality of changes; and

detecting a conflict if any of the first plurality of changes was made without knowledge of changes in the second plurality of changes or if any of the second plurality of changes was made without knowledge of changes in the first plurality of changes.

24. A method as defined in claim 23, further comprising resolving the conflict in favor of a change stored on a server.

25. A method as defined in claim 23, further comprising deciding the conflict following a deterministic rule.

26. A method as defined in claim 23, further comprising deciding the conflict in favor of a change that was made chronologically later in time.

27. A method as defined in claim 23, further comprising performing a conflict resolution that that merges portions of changes together.

28. A computer program product having computer-executable instructions for performing the method of claim 23.

29. In a sync community that includes a plurality of replicas, wherein each replica is able to make changes to data independently of other replicas in the sync community, a computer program product for implementing a method for replicating a replica in the sync community, the computer program product comprising:

a computer-readable medium having computer executable instructions for performing the method, the method comprising;

receiving a knowledge vector from a second replica in a sync community, wherein the knowledge vector represents changes to data that the second replica is aware of;

comparing the knowledge vector of the second replica with a knowledge vector of the first replica to identify changes on the first replica that are not known by the second replica; and

sending the identified changes to the second replica.

30. A computer program product as defined in claim 29, wherein receiving a knowledge vector from a second replica in a sync community further comprises sending the knowledge vector of the first replica to the second replica.

31. A computer program product as defined in claim 29, wherein sending the identified changes to the second replica further comprises receiving other changes from the second replica, wherein the second replica identified the other changes by comparing the knowledge vector of the first replica with the knowledge vector of the second replica.

32. A computer program product as defined in claim 29, wherein comparing the knowledge vector of the second replica with a knowledge vector of the first vector to identify changes on the first replica that are not known by the second replica further comprises performing conflict detection.

33. A computer program product as defined in claim 32, wherein performing conflict detection further comprises:

receiving a first made-with-knowledge value from the second replica, wherein the first made-with-knowledge value is associated with a first change and represents changes that the second replica was aware of when the first change was made;

sending a second made-with knowledge value to the second replica, wherein the second made-with-knowledge value is associated with a second change and represents changes the first replica was aware of when the second change was made; and

determining that a conflict exists if a change ID of the first change is not included in the second made-with-knowledge value and a change ID of the second change is not included in the first made-with-knowledge value.

34. A computer program product as defined in claim 29, further comprising updating a knowledge vector of the first replica.

35. A computer program product as defined in claim 34, further comprising storing an exception list that includes change IDs that correspond to changes received from the second replica.

36. A computer program product as defined in claim 35, wherein each change ID includes a replica ID that is associated with a particular replica in the sync community and a version.