System and method for asynchronous store and forward data replication

• US 5,812,793 A
• Filed: 06/26/1996
• Issued: 09/22/1998
• Est. Priority Date: 06/26/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Norin, Scott, Benson, Max Loell, Shakib, Darren Arthur
• Primary Examiner(s): Rinehart, Mark H.
• Application Number:
  US08/673,741
• Time in Patent Office: 818 Days
• Field of Search: 395/182.04, 395/200.31, 395/200.34, 395/200.35, 395/200.43, 395/200.44, 395/200.47, 395/200.48, 395/200.59, 395/200.78, 395/683 , 395/712, 395/726, 395/200.76, 707/8, 707/202, 707/203, 370/390
• US Class Current: 709/201
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• 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: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A system and method for asynchronous store and forward data replication is presented. The system and method utilizes one-way, unacknowledged communication messages between systems in a computer network to transfer locally modified data to other systems having a copy of the data. The asynchronous store and forward data replication system and method utilizes existing computer networks and/or network control software as a transport agent to deliver the communication messages. Utilization of one-way, unacknowledged communication messages allows data replication across foreign networks such as the Internet or other wide area networks.

Claims

1. A method for replicating data among multiple nodes in a network, the method comprising the steps of:

keeping at a local replica node a local copy of a replica object also replicated at one or more other replica nodes in a network;

updating said replica object each time changes are made to said replica object locally or received, via one or more unacknowledged communication messages, from said one or more other replica nodes; and

associating a unique change identifier with every change made to said replica object, wherein the unique change identifier is generated by a method comprising the steps of;

assigning to each replica node in the network a globally unique identifier which is unique across the network; and

concatenating with said globally unique identifier a counter value which is incremented when a new unique change identifier is needed.

2. A method for replicating data as recited in claim 1 further comprising the step of sending to said one or more other replica nodes at least one message comprising a local copy of said replica object which has been changed at said local replica node.

3. A method for replicating data as recited in claim 1 wherein the changes received from said one or more other replica nodes comprise a received copy of the replica object incorporating changes made to said replica object.

4. A method for replicating data as recited in claim 3 further comprising the step of determining whether the received copy of the replica object should replace said local copy of the replica object.

5. A method for replicating data as recited in claim 4 further comprising the step of replacing said local copy of the replica object with said received copy of the replica object if said received copy is a later version of said replica object.

6. A method for replicating data as recited in claim 1 further comprising the step of associating with the replica object a unique identifier so that the replica object can be uniquely identified by all nodes in the network.

7. A method for replicating data as recited in claim 1 wherein the replica object comprises data set properties.

8. A method for replicating data as recited in claim 1 wherein the replica object comprises one or more data objects.

9. In a computer network wherein copies of replica objects are replicated, distributed and stored at one or more replica nodes, a method for replicating data among said one or more replica nodes comprising the steps of:

updating, at each replica node, a locally stored replica object each time changes are made locally to said replica object or received from one or more other replica nodes;

transmitting, periodically from each replica node, a copy of said locally stored replica object incorporating changes made to said replica object, to other replica nodes by way of at least one unacknowledged message; and

associating a unique change identifier with every change made to said replica object, the unique change identifier being changed whenever further changes are made to the replica object such that the unique change identifier continues to be unique, wherein the unique change identifier is created using a method comprising the steps of;

assigning to each replica node in the network a globally unique identifier which is unique across the network; and

concatenating with said globally unique identifier a counter value which is incremented when a new unique change identifier is needed.

10. A method for replicating data as recited in claim 9 further comprising the step of associating a replica list with the replica object, said replica list comprising a list of all replica nodes which have a copy of said replica object.

11. A method for replicating data as recited in claim 9 further comprising the step of associating with the replica object a unique identifier so that the replica object can be identified by all replica nodes in the network.

12. A method for replicating data as recited in claim 9 wherein said locally stored replica object comprises data set properties, said data set properties comprising an identifier for said data set, and a replica list for said data set.

13. An article of manufacture for use in a computer system defining a location in a network where a copy of a designated replica object is replicated, said computer system being logically connected to at least one other computer system through networking means, each computer system comprising a CPU, said article of manufacture comprising:

program storage means, accessible by the CPU, for storing and providing, to the CPU, program code means, said program code means comprising;

means for sending one or more one-way, unacknowledged communication messages comprising a locally changed copy of a replica object to one or more other systems; and

means for receiving one or more one-way, unacknowledged communication messages comprising a copy of the replica object changed at said one or more other systems; and

means for generating a fast unique ID which is unique across all systems in the network, the means for generating a fast unique ID comprising;

means for generating a globally unique ID which uniquely identifies the computer system across all systems in the network; and

means for generating a locally unique ID which is unique among all other locally unique IDs, said locally unique ID being concatenated with said globally unique ID.

14. An article of manufacture as recited in claim 13 wherein the program code means further comprises means for determining when the replica object should be updated.

15. An article of manufacture as recited in claim 14 wherein the means for determining when the replica object should be updated comprises means for associating a unique ID with the locally changed copy of the replica object.

16. An article of manufacture as recited in claim 14 wherein the means for determining when the replica object should be updated comprises means for comparing change histories.

17. An article of manufacture as recited in claim 13 further comprising means for associating a unique ID with the replica object.