Replication protocol for data stores

• US 20050027817A1
• Filed: 07/31/2003
• Published: 02/03/2005
• Est. Priority Date: 07/31/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev, Terry, Douglas B., Anand, Sanjay, Hudis, Irena, Shah, Ashish B., Jhaveri, Vivek J.
• Granted Patent: US 7,401,103 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: Y10S 707/918 Location
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A protocol for replicating replicas in a sync community. Each replica maintains a knowledge that represents changes that the replica is aware of. Each replica does not typically maintain knowledge about other replicas. The protocol includes messages that include knowledge about changes on the various replicas. Using the knowledge, the replicas can enumerate changes and send the changes using asynchronous messages that do not need to be received in any particular order. The protocol enables filters to ensure that a valid replication is possible using a minimum knowledge argument. The protocol also enables replicas to partially replicate using filtered knowledge.

Claims

1. In a sync community that includes a plurality of replicas, a protocol for replicating a first replica with a second replica, the protocol comprising:

a request changes message from a first replica used to request changes that the first replica is unaware of, wherein the request changes message includes a knowledge argument used to represent a knowledge of the first replica; and

a convey changes message used by the second replica to convey changes to the first replica, wherein the convey changes message includes a change argument and a change ID, wherein the change is to be applied to the first replica and wherein the change ID includes a replica ID that identifies which replica in the sync community that originated the change.

2. A protocol as defined in claim 1, wherein the convey changes message further comprises a made-with-knowledge value that represents the knowledge available to the replica identified by the replica ID at a time when the change was made.

3. A protocol as defined in claim 1, further comprising a complete bundle message sent by the second replica to inform the first replica of the knowledge that the first replica will have by accepting all changes in a group of changes.

4. A protocol as defined in claim 3, wherein the complete bundle message further comprises a count argument and a learned knowledge argument, wherein the count identifies how many convey changes message were sent by the second replica and the learned knowledge represent knowledge that is learned by the first replica if the convey messages indicated by the count argument have been received by and applied to the first replica.

5. A protocol as defined in claim 1, further comprising an advertise changes message that includes a knowledge argument, wherein the first replica uses the advertise changes message to announce to one or more replicas that the first replica has certain changes that can be sent if at least one replica responds with a request changes message.

6. A protocol as defined in claim 1, further comprising an acknowledge change message that is received by the second replica and indicates what happened at the first replica when a particular change was applied, wherein the first replica is not required to send the acknowledge change message.

7. A protocol as defined in claim 1, further comprising a cancel change flow message that the first replica uses to inform the second replica that further convey change messages should not be sent.

8. A protocol as defined in claim 1, further comprising a convey knowledge message, wherein the convey knowledge is sent by the first replica to inform the second replica that the knowledge of the first replica has changed.

9. In a sync community that includes one or more replicas, a method for replicating the one or more replicas, the method comprising a first replica performing:

sending a request changes message to a second replica in a sync community, wherein the request changes message includes a knowledge that represent changes the first replica knows; and

receiving one or more convey changes messages from the second replica, wherein each convey changes message includes at least one change that the first replica does not know based on a comparison by the second replica between the knowledge of the first replica and a knowledge of the second replica.

10. A method as defined in claim 9, wherein receiving one or more convey changes messages from the second replica further comprises:

receiving a change ID for each change in each convey message; and

receiving a made-with-knowledge value for a particular change, wherein the made-with knowledge value represents knowledge available to a particular replica when the particular replica made the particular change.

11. A method as defined in claim 9, further comprising receiving a complete bundle message from the second replica.

12. A method as defined in claim 11, wherein receiving a complete bundle message from the second replica further comprises:

receiving a count in the complete bundle message that indicates how many convey changes messages were sent by the second replica; and

receiving a learned knowledge in the complete bundle message that represents knowledge that the first replica should learn if the first replica received and applied the convey changes message reflected in the count.

13. A method as defined in claim 9, further comprising sending an advertise changes message to one or more replicas including the second replica in the sync community, wherein the advertise changes message includes the knowledge of the first replica and enables each of the one or more replicas to determine whether to replicate with the first replica.

14. A method as defined in claim 13, further comprising receiving a request changes message from a particular replica in response to the advertise changes message.

15. A method as defined in claim 9, further comprising:

receiving a request changes message from the second replica, wherein the request changes message includes the knowledge of the second replica; and

sending at least one convey changes message to the second replica, wherein the at least one convey changes message includes one or more changes, a change ID for each of the one or more changes, and a made-with-knowledge value for at least some of the one or more changes.

16. A method as defined in claim 15, further comprising sending a complete bundle message to the second replica that includes a count and a learned knowledge.

17. A method as defined in claim 9, further comprising sending a convey knowledge message to indicate to the second replica that the knowledge of the first replica has changed.

18. A method as defined in claim 9, further comprising sending a cancel change flow message to indicate that the first replica does not want to receive additional convey changes messages.

19. A method as defined in claim 9, wherein sending a request changes message to a second replica in a sync community further includes including a filter in the request changes message such that only changes satisfying the filter are sent in the convey changes messages.

20. A method as defined in claim 19, further comprising receiving a complete bundle message that includes filtered learned knowledge, wherein the first replica maintains a filtered learned knowledge and a knowledge.

21. A method as defined in claim 9, further comprising receiving a minimum knowledge in at least one of the convey changes messages, wherein the minimum knowledge identifies a minimum knowledge of the first replica in order to ensure that the first replica and the second replica have a valid replication.

22. In a sync community that includes one or more replicas, a method for performing two way replication between a first replica and a second replica in the sync community, the method comprising:

sending a first request changes message to a second replica, wherein the first request changes message includes a knowledge of the first replica that the second replica can use to enumerate first changes that the first replica is unaware of;

receiving first convey changes messages from the second replica, wherein the first convey changes messages comprise the first changes, first change IDs associated with the first changes, and first made-with-knowledge values associated with the first changes;

receiving a second request changes message from the second replica, wherein the second request changes message includes a knowledge of the second replica that the first replica can compare with the knowledge of the first replica to enumerate second changes on the first replica that the second replica is unaware of; and

sending second convey changes messages to the second replica, wherein the second convey changes comprise the second changes, second change IDs associated with the second changes, and second made-with-knowledge values associated with the second changes.

23. A method as defined in claim 22, further comprising receiving a first complete bundle message from the second replica that includes a count of the first convey changes messages and a learned knowledge that reflects knowledge the first replica should learn from the first convey changes messages.

24. A method as defined in claim 22, further comprising sending a second complete bundle message to the second replica that includes a count of the second convey changes messages and a learned knowledge that reflects knowledge the second replica should learn from the second convey changes messages.

25. A method as defined in claim 22, further comprising:

storing the first convey changes messages on a removable medium; and

transporting the removable medium to the second replica such that the second replica can retrieve the first convey changes messages from the removable medium.

26. A method as defined in claim 22, further comprising storing the first convey changes messages on a remote server such that the second replica can retrieve the first convey changes messages from the remote server.

27. A method as defined in claim 22, further comprising applying one or more of the second changes at the first replica.

28. A computer-readable medium having computer-executable instructions for performing the method of claim 22.

29. In a sync community including one or more replicas, a method for communicating changes from a first replica to other replicas in the sync community, the method comprising:

storing a knowledge at the first replica, wherein the knowledge includes one or more change IDs that represent changes that the first replica is aware of; and

sending a convey changes message to a second replica, wherein the convey changes message comprises;

a change argument that represents a particular change;

a change ID argument that is associated with the particular change, wherein the change ID argument identifies a particular replica that assigned a change ID to the particular change;

a made-with-knowledge argument that includes a knowledge that represents changes known by the particular replica that assigned the change ID when the change ID was assigned to the particular change.

30. A method as defined in claim 29, wherein sending a convey changes message to a second replica further comprises:

storing the convey changes message on a removable medium; and

transporting the removable medium to the second replica such that the second replica can retrieve and apply the particular change.

31. A method as defined in claim 29, wherein sending a convey changes message to a second replica further comprises:

storing the convey changes message on a public area in a server where the second replica can retrieve the convey changes message from the public area on the server.

32. A computer program product having computer-executable instructions for performing the method of claim 29.

33. In a sync community that includes one or more replicas, a computer program product for implementing a method for replicating the one or more replicas, the computer program product comprising:

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

sending a request changes message to a second replica in a sync community, wherein the request changes message includes a knowledge that represent changes the first replica knows; and

receiving one or more convey changes messages from the second replica, wherein each convey changes message includes at least one change that the first replica does not know based on a comparison by the second replica between the knowledge of the first replica and a knowledge of the second replica.

34. A computer program product as defined in claim 33, wherein receiving one or more convey changes messages from the second replica further comprises:

receiving a change ID for each change in each convey message; and

receiving a made-with-knowledge value for a particular change, wherein the made-with knowledge value represents knowledge available to a particular replica when the particular replica made the particular change.

35. A computer program product as defined in claim 33, further comprising receiving a complete bundle message from the second replica that includes a count of the number of convey messages sent by the second replica and a learned knowledge that represents knowledge the first replica should learn if the first replica received and applied the number of convey changes messages reflected by the count.

36. A computer program product as defined in claim 33, further comprising sending an advertise changes message to one or more replicas including the second replica in the sync community, wherein the advertise changes message includes the knowledge of the first replica and enables each of the one or more replicas to determine whether to replicate with the first replica.

37. A computer program product as defined in claim 33, further comprising:

receiving a request changes message from the second replica, wherein the request changes message includes the knowledge of the second replica;

sending at least one convey changes message to the second replica, wherein the at least one convey changes message includes one or more changes, a change ID for each of the one or more changes, and a made-with-knowledge value for at least some of the one or more changes; and

sending a complete bundle message to the second replica that includes a count and a learned knowledge.

38. A computer program product as defined in claim 33, wherein sending a request changes message to a second replica in a sync community further includes including a filter in the request changes message such that only changes satisfying the filter are sent in the convey changes messages.

39. A computer program product as defined in claim 38, further comprising receiving a complete bundle message that includes filtered learned knowledge, wherein the first replica maintains a filtered learned knowledge and a knowledge.

40. A computer program product as defined in claim 33, further comprising receiving a minimum knowledge in at least one of the convey changes messages, wherein the minimum knowledge identifies a minimum knowledge of the first replica in order to ensure that the first replica and the second replica have a valid replication.