Multicast-enhanced update propagation in a weakly-consistant, replicated data storage system

• US 6,557,111 B1
• Filed: 11/29/1999
• Issued: 04/29/2003
• Est. Priority Date: 11/29/1999
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Theimer, Marvin, Swinehart, Daniel, Dourish, James P., Spiteri, Mark
• Primary Examiner(s): Beausoliel, Robert
• Assistant Examiner(s): DUNCAN, MARC M
• Application Number:
  US09/450,173
• Time in Patent Office: 1,247 Days
• Field of Search: 714/4, 714/5, 714/6, 707/8, 707/201, 707/203
• US Class Current: 714/4.4
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• 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
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Epidemic-style update communications facilities are used in conjunction with multicast update communications facilities in weakly-consistent, replicated data storage systems. Epidemic-style communications handle a wide variety of failures at multiple levels of the system using a single, very robust, but also relatively high-latency mechanism. Multicast communication offers much quicker propagation but less fault tolerance using a different mechanism. The epidemic-style communications and multicast communications, combined for use in weakly consistent replicated database systems obtain a design that offers the benefits of both individual approaches.

Claims

1. In a multi-node computer network having a weakly consistent replicated data storage system, an enhanced update mechanism to enable continued operation of network subsets in the face of faults and network partitioning events, the enhanced update mechanism comprising:

a multicast communication update facility configured to propagate updates from an originating replica source in the computer network to all replicas of the computer network at a single time using a best efforts design; and

a pair-wise update communications facility which sends updates by pair-wise interaction to non-updated neighboring replicas, wherein the pair-wise update communications facility and the multicast communication update facility are employed together in at least some of the replicas.

2. The invention according to claim 1 wherein the pair-wise update communications facility is configured to send updates periodically in a batch arrangement.

3. The invention according to claim 1 wherein the multicast communication update facility and the pair-wise update communication facility are configured in accordance with parameters which allow for the facilities to operate in a parallel, non-overlapping manner with respect to each other.

4. The invention according to claim 1 wherein the multicast update communications facility is a scalable, reliable multicast communications protocol.

5. The invention according to claim 1 wherein the multicast update communications facility and the pair-wise update communications facility are configured in accordance with parameters which causes the multicast update communications facility to influence a rate at which the pair-wise update communications facility operates.

6. The invention according to claim 1 wherein the replicas are configured to send out update summary information, and the replicas interested in the summary update information are designed to engage in a reply communication to the replica sending the summary information.

7. The invention according to claim 1 wherein the multicast update communications facility is designed to issue a heartbeat-style message which allows a replica of the replicas in the system to detect when the replica has missed an update.

8. The invention according to claim 7 wherein upon the detection that the replica has missed an update, the replica is further designed to adjust its pair-wise communications parameters.

9. The invention according to claim 8 wherein adjusting of its pair-wise communication parameters includes, a reduction in a time interval for initiation of pair-wise communications with another replica.

10. The invention according to claim 1 further including multiple multicast groups employed to target propagation of updates or to announce updates to subsets of the replicas of the computer network, wherein the computer network includes a large number of replicas with a large amount of update traffic and any given update is of interest to only some subsets of all replicas.

11. The invention of claim 1 wherein the pair-wise communications update facility is an epidemic-style update facility.

12. The invention according to claim 11 wherein the epidemic style update facility is an epidemic protocol.

13. A method of enabling continued operation of network subsets in the face of faults and network partitioning events, in a multi-node computer network having a weakly consistent replicated data storage system, the method comprising:

propagating updates, from an originating replica source of the computer network to all replicas of the computer network via a multicast communication update facility, at a single time using a best efforts design; and

sending updates, by pair-wise interaction to non-updated neighboring replicas of the computer network via a pair-wise update communications facility, wherein the pair-wise update communications facility and the multicast communication update facility are employed together in at least some of the replicas.

14. The method according to claim 13 further including operating the multicast communication update facility and the pair-wise update communication in accordance with parameters which allow for the facilities to operate in a parallel, non-overlapping manner with respect to each other.

15. The method according to claim 13 further including configuring the multicast update communications facility and the pair-wise update communications facility in accordance with parameters which causes the multicast update communications facility to influence a rate at which the pair-wise update communications facility operates.

16. The invention according to claim 13 wherein the replicas are configured to send out update summary information, and the replicas interested in the summary update information are designed to engage in a reply communication to the replica sending the summary information.

17. The invention according to claim 13 wherein the multicast update communications facility is designed to issue a heartbeat-style message which allows a replica of the replicas in the system to detect when the replica has missed an update.

18. The method according to claim 17 wherein upon the detection that the replica has missed an update, the replica is further designed to adjust its pair-wise communications parameters.

19. The method according to claim 17 wherein adjusting of its pair-wise communication parameters includes, a reduction in a time interval for initiation of pair-wise communications with another replica.

20. The method according to claim 13 further including multiple multicast groups employed to target propagation of updates or to announce updates to subsets of the replicas of the computer network, wherein the computer network includes a large number of replicas with a large amount of update traffic and any given update is of interest to only some subsets of all replicas.