Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1999-11-29
2003-04-29
Beausoliel, Robert (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06557111
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed to applications and/or systems which require weakly-consistent, replicated data storage in order to enable continued operation of component subsets in the face of faults and network partitioning events. More particularly, the invention is directed to propagating updates from an originating replica to all other replicas in an efficient manner.
BACKGROUND OF THE INVENTION
In the field of distributed computing, questions of how best to allow multiple users access to a distributed database naturally arise. The answers change depending upon the design goals of the system and the expectations of its users.
In some systems that are designed to accommodate the shared access to data among a number of users, some form of data “replication” is typically implemented. To achieve data replication, systems are commonly partitioned into a number of data “servers”—each server having a complete replica of the system database. These servers process requests from a number of “clients.” Typically, client requests come in the form of Reads and Writes to the system database. Replication of data allows flexibility and availability to clients. If data is completely (and perfectly) replicated across all servers, then a client will always have access to the same system data.
However, the cost of “perfect” replication may be prohibitive—especially in systems that have large numbers of clients and servers. Any change (due to a Write) effected by a client necessarily needs to be immediately propagated to all system servers to ensure perfect replication. If the updates are not “immediately” propagated throughout the system, there exists the possibility that some client will access a data item at a server that has not as yet been updated—thus violating the perfection of the replication.
As a practical matter, perfection, as a system goal, is impossible. Different schemes for the relaxation of this condition have emerged. At one end of the spectrum, a “strongly consistent” distributed database provides that changes are either atomically updated throughout the system or provide for some type of a server-initiated callbacks when inconsistencies occur. Although strongly consistent systems provide a high degree of data consistency, the price often paid is availability. For example, a client of a strongly consistent database requesting data that has recently been updated may have access blocked to that data until it has been updated across all servers.
At the other end, “weakly consistent” databases allow access to servers and data that may not contain all system updates. Such systems typically are characterized by the “lazy” propagation of updates between servers (i.e. updated servers propagate updates to other servers over time); thus the possibility exists for clients to see inconsistent values when reading data from different replicas. The use of weakly consistent replicated data has been driven by the needs existing in distributed environments. Another force driving use of weakly consistent systems has to do with improving performance, so that connecting to a nearby server for a read or write will be faster and smoother than connecting to another server. Clients in contact with a server, can gain useful information even when both client and server are partitioned from the other replicas. Weakly consistent replication systems attempt to ensure that these reads are usually reasonably up-to-date, and that eventually a full-state of synchronization will be reached. Thus, a primary motivation for using weakly consistent systems is to provide distributed replication for reliable, although only weakly consistent, access to shared information even in the face of faults and network partitioning or wide-spread network overload, so that long-term synchronization is achieved among replicas.
Unfortunately, the lack of guarantees concerning the ordering of read and write operations in weakly consistent systems can confuse users and applications. A user may read some value for a data item and then later read an older value. Similarly, a user may update some data item based on reading some other data, while others read the updated item without seeing the data on which it is based. A serious problem with weakly consistent systems is that inconsistencies can appear even when only a single user or application is making data modifications. For example, a mobile client of a distributed database system could issue a write at one server, and later issue a read at a different server. The client would see inconsistent results unless the two servers had synchronized with one another sometime between the two operations.
Despite the above noted disadvantages, weakly consistent systems are popular in situations that do not require total consistency in order to be valuable, due to their high-availability, good scalability, and simplicity of design. These advantages arise from the ability to allow reads and writes to be performed with little or no real-time synchronization among replicas.
To implement weakly consistent designs, systems and algorithms which offer a quick propagation of changes have been developed. However, these quick propagation designs such as multicasting, provide low levels of tolerances and have a “best efforts” standard of reliability.
Other designs are pre-configured to periodically send updates by means of pair-wise interactions to neighboring replicas that had not yet received updates which may have taken place. Such an approach insures that eventually all updates will reach all replicas, assuming that all replicas engage in sufficient pair-wise update exchanges so that a transitive closer on propagation is achieved. However, it may take a considerable amount of time for any given update to reach all the replicas whose local clients might be interested in its value.
Thus, a mechanism is needed for weakly-consistent databases, which are to be replicated that allows for obtaining a design that provides the best of a fast replication system which has a “best efforts” standard of reliability, with a highly reliable replication system, that has a high latency factor.
SUMMARY OF THE INVENTION
A multi-node computer network is provided having a weakly consistent replicated data storage system with an enhanced update mechanism which enables continued operation of network subsets in the face of faults and network partitioning events. Provided is 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. An epidemic update communication facility is provided to send updates by pair-wise interaction to non-updated neighboring replicas, wherein the epidemic update communication facility and the multicast communication update facility are employed together in at least some of the replicas.
With attention to another aspect of the present invention, the multicast update communication facility and the epidemic 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.
With attention to yet another aspect of the present invention, the multicast update communication facility and the epidemic update communication facility are configured in accordance with parameters which cause the multicast update communication facility to influence a rate at which the epidemic update communication facility operates.
REFERENCES:
patent: 4558413 (1985-12-01), Schmidt et al.
patent: 5241675 (1993-08-01), Sheth et al.
patent: 5255387 (1993-10-01), Arnold et al.
patent: 5280612 (1994-01-01), Lorie et al.
patent: 5287496 (1994-02-01), Chen et al.
patent: 5434994 (1995-07-01), Shaheen et al.
patent: 5551027 (1996-08-01), Choy et al.
patent: 5577240 (1996-11-01), Demers et al.
patent: 5581754 (1996-12-01), Terry et al.
patent: 5588147 (1996-12-01), Neeman et al.
patent: 5603026 (1997-02-01), Demers et al.
patent: 5671407
Dourish James P.
Spiteri Mark
Swinehart Daniel
Theimer Marvin
Beausoliel Robert
Duncan Marc
Fay Sharpe Fagan Minnich & McKee LLP
Xerox Corporation
LandOfFree
Multicast-enhanced update propagation in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicast-enhanced update propagation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast-enhanced update propagation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3105949