Replication optimization system and method

• US 6,049,809 A
• Filed: 10/30/1996
• Issued: 04/11/2000
• Est. Priority Date: 10/30/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shen, Shioupyn, Straube, Dave D., Miller, Arnold S., Raman, Balan S.
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/739,948
• Time in Patent Office: 1,259 Days
• Field of Search: 707/201, 707/202, 707/203, 707/200, 707/204, 707/1, 707/3, 711/141, 380/25
• US Class Current: 1/1
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A system and method of efficiently replicating data structures in a distributed system of replicas. Each replica in the distributed system maintains a cursor indicative of the extent to which other replicas in the system are consistent with one another. By examining the information in its cursor, a destination replica requesting replication from a source replica is able to determine the extent to which it has been made consistent with that source replica via indirect paths, thus potentially improving the starting point of replication. The source replica similarly examines its cursor to potentially improve the starting point of replication with respect to the starting point requested by the destination replica. In this manner, redundant information transmitted from a source replica when replicating a destination replica is reduced. The reduction in the amount of transmitted replication data is particularly appreciable when the replication topology of the system is changed such as by adding a new connection between existing replicas or by adding a new replica to the system.

Claims

1. In a distributed computer system, a method of replicating data structures to replicas in the system, comprising the steps of:

maintaining a cursor at a source replica representative of the extent that the source and at least two other replicas in the system are consistent with each other;

receiving a request at the source replica to replicate a destination replica, the request including a starting point from which replication is desired;

evaluating the cursor to determine a value indicative of the extent to which the destination replica has been made consistent with the source replica;

comparing the determined value with the received starting point; and

transmitting information from the determined value if the determined value with respect to the received starting point reduces the amount of replication information needed to make the destination replica consistent with the source replica.

2. The method of claim 1 wherein the source replica and destination replica are not initially connected to one another via a direct connection, and further comprising the step of establishing a direct connection therebetween.

3. The method of claim 1 wherein the received starting point and determined value comprise numbers which monotonically increase in value, and the step of comparing the determined value with the received value comprises the step of selecting the larger of the two values.

4. The method of claim 3 wherein the received starting point and determined value comprise update sequence numbers representative of operations performed at disk volumes comprising the replicas.

5. The method of claim 3 wherein a plurality of indirect replication paths exist between the source replica and the destination replica, and wherein the step of evaluating the cursor to determine a value comprises the steps of obtaining a plurality of values corresponding to the extent to which the source has been made consistent with the destination over each of the plurality of indirect paths.

6. The method of claim 1 further comprising the step of transmitting the cursor from the source replica to the destination replica.

7. In a distributed computer system of interconnected replicas wherein data structures are replicated from source replicas to destination replicas, a replication system at a source, comprising:

a memory including a cursor stored therein, the cursor including information representative of the extent that at least three replicas in the system are consistent with each other;

means for communicating with a destination replica, said means receiving a replication request from the destination replica including a starting point from which to replicate;

an optimization mechanism for evaluating the cursor to determine a value indicative of the extent to which the destination replica has been made consistent with the source, and further including means for comparing the determined value with the received starting point to determine if the determined value reduces the amount of replication information needed to make the destination replica consistent with the source replica; and

a replication facility connected to the optimization means and the communication means for transmitting replication information to the destination replica based upon the determined value if the determined value reduces the amount of replication information needed to make the destination replica consistent with the source replica.

8. The replication system of claim 7 wherein the communication means further transmits the cursor from the source replica to the destination replica.

9. The replication system of claim 7 wherein the received starting point and determined value comprise numbers which monotonically increase in value, and wherein the optimization means compares the determined value with the starting to point to determine if the determined number is larger.

10. The replication system of claim 9 wherein a plurality of indirect replication paths exist between the source replica and the destination replica, and wherein the optimization means evaluates the cursor to obtain a plurality of values corresponding to the plurality of indirect paths.

11. In a distributed computer system, a method of replicating data structures among more than two replicas in the system, comprising the steps of:

maintaining information at a destination replica including a first value indicative of the extent that the destination replica has been made consistent with a source replica by a direct connection thereto, and a second value indicative of the extent that the destination replica has been made consistent with the source replica by an indirect connection through at least one other replica between the source replica and the destination replica;

comparing the first value with the second value to determine if the second value will reduce the amount of replication information needed to make the destination replica consistent with the source replica; and

requesting replication from the source replica by providing the second value to the source replica when the comparison indicates that the second value will reduce the amount of replication information needed to make the destination replica consistent with the source replica, or by providing the first value to the source replica when the comparison indicates that the second value will not reduce the amount of replication information needed to make the destination replica consistent with the source replica.

12. The method of claim 11 wherein the source replica and destination replica are not initially connected to one another via a direct connection, and further comprising the step of establishing a direct connection therebetween.

13. The method of claim 11 wherein the first value comprises a number indicative of a previous point of replication with the source replica.

14. The method of claim 11 wherein first and second values comprise numbers which monotonically increase in value, and the step of comparing the determined value with the received value comprises the step of selecting the larger of the two values.

15. The method of claim 14 wherein the received starting point and determined value comprise update sequence numbers representative of operations performed at disk volumes comprising the replicas.

16. The method of claim 11 further comprising the step of receiving information at the destination replica from the source replica, the information comprising a cursor indicative of the extent other replicas in the system are consistent with each other as compiled by the source.

17. The method of claim 16 further comprising the step of updating information at the destination based upon the cursor received from the source.

18. In a distributed computer system of interconnected replica nodes, a method of replicating objects so as to be consistent among the replica nodes comprising the steps of:

maintaining a replica-object cursor at each replica node, each replica-object cursor including an identity for each connection between at least three replica nodes in the distributed system and a value associated therewith indicating the extent of replication of a node over that connection, and,

at a destination node,

selecting a source node for replication, accessing the cursor maintained in the destination node to determine which value indicates the extent that the destination node is replicated relative to the selected source node, communicating with the selected source node to provide the determined value thereto and to request replication information therefrom starting from at least the determined value, receiving replication information from the source node and receiving a copy of the cursor maintained by the source node in response to the communication, replicating objects in the destination replica according to the received replication information, and updating the values in the cursor maintained in the destination node according to the values within the copy of the cursor received from the source node.

19. In a distributed computer system of interconnected replica nodes, a method of replicating objects so as to be consistent among the replica nodes comprising the steps of:

maintaining a replica-object cursor at each replica node, each replica-object cursor including an identity for each connection between at least three replica nodes in the distributed system and a value associated therewith indicating the extent of replication of a node over that connection, and,

at a destination node,

receiving a request for replication from a destination node, accessing the cursor maintained in the source node to determine which value indicates the extent that the requesting destination node is replicated relative to the source node, communicating with the destination to provide replication information thereto starting from at least the determined value, and transmitting a copy of the cursor maintained by the source node to the destination node.

20. In a distributed computer system of interconnected replica nodes, a method of replicating objects so as to be consistent among the replica nodes comprising the steps of:

maintaining a replica-object cursor at each replica node, each replica-object cursor including an identity for each connection between at least three replica nodes in the distributed system and a value associated therewith indicating the extent of replication of a node over that connection;

selecting, at a destination node, a source node for replication, accessing the cursor maintained in the destination node to determine a first value indicative of the extent that the destination node is replicated relative to the selected source node, communicating with the selected source node to provide the first value thereto and to request replication information therefrom starting from at least the first value;

receiving, at the source node, the first value and the request for replication, accessing the cursor maintained in the source node to determine a second value indicative of the extent that the requesting destination node is replicated relative to the source node, comparing the first value with the second value to determine which value indicates a further extent of replication, communicating with the destination to provide replication information thereto starting from either the first or second value depending on which value indicated a further extent of replication, and transmitting a copy of the cursor maintained by the source node to the destination node; and

receiving, at the destination node, the replication information from the source node and receiving a copy of the cursor maintained by the source node in response to the communication, replicating objects in the destination replica according to the received replication information, and updating the values in the cursor maintained in the destination node according to the values within the copy of the cursor received from the source node.

21. In a distributed computer system of interconnected replica nodes, a framework for maintaining information in the system indicative of the extent that objects are replicated among the replica nodes, comprising:

a replica-object cursor at each replica node, each replica-object cursor including an identity for each connection between at least three replica nodes in the distributed system and a value associated therewith indicating the extent of replication of a node over that connection;

means for transmitting a copy of the replica-object cursor from each replica node in the system to at least two other replica nodes in the distributed system connected thereto;

means at each replica node for receiving copies of the replica-object cursors from at least two other replica nodes in the distributed system connected thereto; and

means at each replica node for updating the replica-object cursor maintained therein according to the information within the copies of the received replica-object cursors.

22. The system of claim 21 wherein the replica-object cursor maintained at a node is updated such that the values therein are replaced with values that indicate a further extent of replication over a connection.