System and method for efficient multi-master replication

• US 20040148317A1
• Filed: 01/23/2003
• Published: 07/29/2004
• Est. Priority Date: 01/23/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sundararajan, Narasimhan, Narayanan, Charumathy
• Granted Patent: US 7,152,076 B2
• Time in Patent Office: Days
• US Class Current: 707/201
• CPC Class Codes: G06F 16/275 Synchronous replication
• 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

Each replica in a group of replicas of a data set is assigned a unique identifier and maintains an independent counter. When a change is made to an element in the data set, a change bucket, is assigned to the changed data element. The change bucket includes the identifier of the replica at which the change was made and the count of the counter of the replica at which the change was made at the time of the change. Each replica also maintains an array of change buckets each corresponding to the most recent changes replicated from the other replicas in the group. When replicas synchronize, the replicas exchange and compare replication state vectors to identify changes present at a replica and not present at another replica. Once such changes are identified, they and their corresponding change buckets are sent to the other replica to be replicated. Once new changes are replicated, the replicas join their replication state vectors to reflect that they are synchronized.

Claims

1. A method for synchronizing a first replica of a data set and a second replica of the data set, each of the first and second replicas having an associated identifier and counter whereby, for each change made to an element in the data set, a change bucket is assigned to the element, the change bucket including an associated identifier and a count of an associated counter at the time of the change, the method comprising:

receiving at the second replica a first replication state vector maintained at the first replica, the first replication state vector including a first change bucket corresponding to a most recent change made at the first replica and a second change bucket corresponding to a most recent change made at the second replica and replicated at the first replica;

comparing at the second replica the first replication state vector and a second replication state vector maintained at the second replica, the second replication state vector including a first change bucket corresponding to a most recent change made at the first replica and replicated at the second replica and a second change bucket corresponding to a most recent change made at the second replica;

identifying changes to be replicated at the first replica, the changes to be replicated at the first replica each having a change bucket with the identifier of the second replica and a count greater than the count of the second change bucket of the first replication state vector and less than or equal to the count of the second change bucket of the second replication state vector; and

sending to the first replica the changes to be replicated at the first replica and their corresponding change buckets.

2. The method of claim 1, wherein a change is one of a modification, an insertion, and a deletion of an element.

3. The method of claim 1, further comprising:

receiving at the first replica the changes to be replicated at the first replica and their corresponding change buckets; and

replicating the changes to be replicated at the first replica.

4. The method of claim 3, further comprising:

receiving at the first replica the second replication state vector; and

assigning the second change bucket of the second replication state vector to the second change bucket of the first replication state vector.

5. The method of claim 1, further comprising:

receiving at the first replica the second replication state vector;

comparing at the first replica the first replication state vector and the second replication state vector;

identifying changes to be replicated at the second replica, the changes to be replicated at the second replica each having a change bucket with the identifier of the first replica and a count greater than the count of the first change bucket of the second replication state vector and less than or equal to the count of the first change bucket of the first replication state vector; and

sending to the second replica the changes to be replicated at the second replica and their corresponding change buckets.

6. The method of claim 5, further comprising:

receiving at the second replica the changes to be replicated at the second replica and their corresponding change buckets; and

replicating the changes to be replicated at the second replica.

7. The method of claim 6, further comprising assigning the first change bucket of the first replication state vector to the first change bucket of the second replication state vector.

8. A computer readable medium for synchronizing a first replica of a data set and a second replica of the data set, each of the first and second replica having an associated identifier and counter whereby, for each change made to an element in the data set, a change bucket is assigned to the element, the change bucket including an associated identifier and a count of an associated counter at the time of the change, the computer readable medium comprising computer executable instructions for performing the following steps:

receiving at the second replica a first replication state vector maintained at the first replica, the first replication state vector including a first change bucket corresponding to a most recent change made at the first replica and a second change bucket corresponding to a most recent change made at the second replica and replicated at the first replica;

comparing at the second replica the first replication state vector and a second replication state vector maintained at the second replica, the second replication state vector including a first change bucket corresponding to a most recent change made at the first replica and replicated at the second replica and a second change bucket corresponding to a most recent change made at the second replica;

identifying changes to be replicated at the first replica, the changes to be replicated at the first replica each having a change bucket with the identifier of the second replica and a count greater than the count of the second change bucket of the first replication state vector and less than or equal to the count of the second change bucket of the second replication state vector; and

sending to the first replica the new changes made at the second replica and their corresponding change buckets.

9. The computer readable medium of claim 8, wherein a change is a one of a modification, an insertion, and a deletion of an element.

10. The computer readable medium of claim 8, further comprising computer executable instructions for performing the steps of:

receiving at the first replica the changes to be replicated at the first replica and their corresponding change buckets; and

replicating the changes to be replicated at the first replica.

11. The computer readable medium of claim 10, further comprising computer executable instructions for performing the following steps:

receiving at the first replica the second replication state vector; and

assigning the second change bucket of the second replication state vector to the second change bucket of the first replication state vector.

12. The computer readable medium of claim 8, further comprising computer executable instructions for performing the following steps:

receiving at the first replica the second replication state vector; and

comparing at the first replica the first replication state vector and the second replication state vector;

identifying changes to be replicated at the second replica, the changes to be replicated at the second replica each having a change bucket with the identifier of the first replica and a count greater than the count of the first change bucket of the second replication state vector and less than or equal to the count of the first change bucket of the first replication state vector; and

sending to the second replica the new changes made at the first replica and their corresponding change buckets.

13. The computer readable medium of claim 12, further comprising computer executable instructions for performing the steps of:

receiving at the second replica the changes to be replicated at the second replica and their corresponding change buckets; and

replicating the changes to be replicated at the second replica.

14. The computer readable medium of claim 13, further comprising computer executable instructions for assigning the first change bucket of the first replication state vector to the first change bucket of the second replication state vector.

15. A system for data replication, comprising:

a first computing device comprising a memory for storing a data set, a first identifier, and a first counter whereby, for each change made to an element in the data set at the first replica a change bucket is assigned to the element, the change bucket including the first identifier and a count of the first counter at the time of the change;

a second computing device comprising a memory for storing a data set, a second identifier, and a second counter whereby, for each change made to an element in the data set at the second replica a change bucket is assigned to the element, the change bucket including the second identifier and a count of the second counter at the time of the change;

a first replication state vector maintained at the first computing device, the first replication state vector including a first change bucket corresponding to a most recent change made at the first replica and a second change bucket corresponding to a most recent change made at the second replica and received at the first replica; and

a second replication state vector maintained at the second computing device, the second replication state vector including a first change bucket corresponding to a most recent change made at the first replica and received at the second replica and a second change bucket corresponding to a most recent change made at the second replica.

16. The system of claim 15, wherein the data set is a relational data table.

17. The system of claim 15, wherein the first counter and the second counter are independently maintained.

18. The system of claim 15, wherein a change is one of a modification, an insertion, and a deletion of an element.

19. The system of claim 15, wherein the first computing device further comprises a first processor for performing the following steps:

receiving at the first replica the second replication state vector;

comparing at the first replica the first replication state vector and the second replication state vector;

identifying changes to be replicated at the second replica, the changes to be replicated at the second replica each having a change bucket including the identifier of the first replica and a count greater than the count of the first change bucket of the second replication state vector; and

sending to the second replica the changes to be replicated at the second replica and their corresponding change buckets.

20. The system of claim of claim 19, wherein the first processor is for further performing the following steps:

receiving at the first replica changes to be replicated at the first replica, the changes to be replicated at the first replica each having a change bucket including the identifier of the second replica and a count greater than the count of the second change bucket of the first replication state vector; and

replicating the changes to be replicated at the first replica.

21. The system of claim 20, wherein the first processor is for further performing the step of assigning the second change bucket of the second replication state vector to the second change bucket of the first replication state vector.

22. The system of claim 15, wherein the second computing device further comprises a second processor for performing the following steps:

receiving at the second replica the first replication state vector;

comparing at the second replica the first replication state vector and the second replication state vector;

identifying changes to be replicated at the first replica, the changes to be replicated at the first replica each having a change bucket including the identifier of the second replica and a count greater than the count of the second change bucket of the first replication state vector; and

sending to the first replica the changes to be replicated at the first replica and their corresponding change buckets.

23. The system of claim of claim 22, wherein the second processor is for further performing the following steps:

receiving at the second replica changes to be replicated at the second replica, the changes to be replicated at the second replica each having a change bucket including the identifier of the first replica and a count greater than the count of the first change bucket of the second replication state vector; and

replicating the changes to be replicated at the second replica.

24. The system of claim 23, wherein the second processor is for further performing the step of assigning the first change bucket of the first replication state vector to the first change bucket of the second replication state vector.