Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-01-29
2002-07-16
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S201000, C709S203000, C709S205000, C712S245000
Reexamination Certificate
active
06421701
ABSTRACT:
RELATED APPLICATIONS
The present application Ser. No. 09/184,245 is related to a co-pending application entitled “DETERMINISTIC AND PREEMPTIVE THREAD SCHEDULING AND ITS USE IN DEBUGGING MULTITHREADED APPLICATIONS”, filed Nov. 2, 1998 with the application assigned to the assignee of the present application.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer and information handling systems, and more particularly to replicated servers deployed in a distributed system. Still more particularly, the present invention relates to a method and system for enforcing consistency among replicated servers in a distributed system through the use of multicast and deterministic thread scheduling.
2. Description of the Related Art
Computer networks allow users of data-processing systems to retrieve vast amounts of electronic information heretofore unavailable in an electronic medium. Computer networks are increasingly displacing more conventional means of information transmission, such as newspapers, magazines, and television. A computer network connects a set of machines and allows them to communicate with one another. Typical networked systems utilized widely today follow the client/server architecture. In network computing, a client is a process (roughly a program or task) that requests a service provided by another program, the server. The client process may utilize the requested service without having to “know” the working details of the server's operation or the requested service itself.
It is common nowadays to use remote procedure call (RPC) in implementing servers in a network-computing environment. Furthermore, remote procedure calls are often referred to as remote method invocation systems when the client and servers use an object-oriented paradigm for software implementation and communications. We shall use the terms remote procedure calls and remote method invocations interchangeably. In this model of execution, clients formulate their requests in the form of “procedure calls” or “method invocations” that execute on the server machine. The server implements the required procedure calls and methods. During normal operation, it waits to receive requests from its clients across the network. When the network subsystem delivers such a request to the server, the latter creates a “thread” to execute the client's request and generates an appropriate reply. A thread is a lightweight execution unit that lives in the server process's address space and shares its resources with potentially other threads that are executing other, possibly independent client requests. In this model, the thread starts executing at the procedure call specified by the client's request, and executes until the procedure call returns. The server then sends the value produced by the procedure call back to the client and deallocates the thread. This RPC model of execution has become the centerpiece of distributed computing standards such as the Distributed Computing Environment (DCE), the Common Object Request Broker Architecture (CORBA), and DCOM (Distributed Common Object Model).
Server architectures are often configured to achieve reliability and high availability utilizing replication. In such systems, several processors or machines may be utilized to provide a service, with each machine replicating the service's state. Such machines are referred to as “server replicas” or simply “replicas”. A client may communicate with a subset of the server replicas, where such a subset may include all, some, or only one of the available replicas. A client may select the subset randomly or via pre-defined selection criteria. It is thus necessary that all server replicas maintain identical states in order to ensure a consistent view of the information manipulated by the service, as perceived by the same client or by different clients.
Each replica has its own private implementation of the remote procedures that constitute the service. Execution of a client's request proceeds independently among the different servers and it is important to ensure that the states of the replicas remain consistent despite this independent form of execution. If a server replica fails, the remaining server replicas continue to operate, thereby ensuring uninterrupted service for the clients.
A problem faced by designers in implementing replicated services is to ensure that replicas maintain identical states that reflect client transactions with the service. For example, two different clients may issue two remote procedure calls to update the same record in a database maintained by a replicated service. If the two procedure calls are processed in different orders by two or more replicas, the values of the replicated record may become inconsistent.
There are two properties of RPC systems that may lead two different client requests to execute in two different orders at different server replicas:
First, the network may deliver requests to the server replicas in different orders. For example, if clients A and B send RPC's R and P to server replicas C and D, the thread executing RPC R at server C may start before the thread executing RPC P, if the network delivers R before P at C. Similarly, the thread executing RPC P at server D may start before the thread executing RPC R, if the network delivers P before R at D. Thus, if the network does not deliver the clients' requests in the same order at server replicas C and D, they will execute the requests in different orders and may become inconsistent.
Secondly, the thread scheduler inside each server may schedule the threads that are executing clients' requests in different orders. Conventional thread schedulers use timers to enable scheduling decisions, and since timers cannot be precise across different machines for pedagogical reasons, thread scheduling decisions will not be identical among different server replicas. Thus, even if the network delivers client requests in the same order among all replicas, the thread scheduling may not necessarily obey that order and the executions of the client requests on two different server replicas may thus be different.
All existing distributed computing standards are susceptible to the problem described above. In the past, ordered multicast protocols have attempted to address this problem. They ensure that all server replicas receive the same messages from the network in the same order. Then, execution within each server replica is serialized according to the order specified by the network, such that a request cannot start execution before the previous one finishes. This solution is not satisfactory because it eliminates the benefits of concurrency available within each server and reduces performance drastically. As a result, the resulting performance loss due to replication is large. Furthermore, in the prior art, there was never a coupling between the order specified by the multicast protocol and the execution order of the threads that execute the request. Based on the foregoing, it can be appreciated that a need exists for an improved method and system for implementing an ordering protocol in combination with a thread scheduling mechanism that ensures all replicas of server receive and execute clients' requests in the same order. The subject invention herein solves all of these problems in a new and unique manner that has not been part of the art previously.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide an improved method and system for maintaining the consistency among replicated servers in computer networks.
It is another object of the invention to provide an improved method and system for maintaining the consistency among replicated servers in computer networks where clients and servers communicate via remote procedure calls.
It is yet another object of the invention to provide an improved method and system for maintaining the consistency among replicated servers in computer networks where clients and servers communicate via remo
Banankhah Majid A.
Bracewell & Patterson L.L.P.
International Business Machines - Corporation
Salys Casimer K.
LandOfFree
Method and system for replication support in a remote method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for replication support in a remote method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for replication support in a remote method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2870171