22C:116, Lecture 24, Spring 1999

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Clients, Servers and Remote Procedures

    When a client calls on a server to perform some operation, it is very tempting to make the analogy with a procedure call. Conceptually, the server offers the client one or more procedures; when the client calls one of these procedures, the server performs the desired action.

    In fact, this is a form of data abstraction. In languages like C++ or Ada, the representation of an object (in Ada, a package) may be hidden from users of that object. If a user wishes to operate on the object, the user must call on one of the procedures that provide the public interface to the object (in object oriented languages such as C++, these are sometimes called methods).

    If an object is implemented locally, calls to the procedures making up the public interface to the object may be made using simple procedure calls. If an object is implemented on a remote machine, it is desirable to view the operations on the object as being performed by procedure calls to that remote machine. Obviously, such calls must be implemented using messages passed over the network that interconnects the machines in question! Nonetheless, we can go a long way towards hiding this from users of the procedures in question.

    Consider the following view of the system, as the user prefers to see it:

    User         |     |    Remote System
                 |     |
      :          |     |
      :          | Net |      Procedure P(in A; out B)
    Call P(X,Y)  |     |        :
      :          |     |      Return
      :          |     |
    
                   or
      :          |     |    Object X
      :          |     |      Method P(in A)
    X.P(Y)       |     |        :
      :          |     |      Return
      :          |     |
    
    Users typically want to ignore the presence of the network and just write code that calls P. Initially, we will ignore the possibility that P is a method of an object and focus on the issue of control transfer for remote procedure calls; keeping in mind that calls to methods of objects are usually implemented as procedure calls, it is not difficult to generalize to calls to methods of remote objects.

    Our goal is to allow the author of the procedure P on the remote machine and the author of the code that calls P on the local machine to ignore the presence of the network, as much as is possible, and write their code as if P and its caller ran on the same machine.

    Assuming that the parameter X is being sent to P, and that the parameter Y is to be changed by P, clearly there must be at least two messages sent over the network. The first message, from the user to the remote system, carries the parameter X and indicates a call to P. The second message, from the remote system back to the user, carries the result of the call to P, including the new value of Y.

    These messages constitute the core of a remote procedure call communication protocol.

  2. Hiding the Network from the Users

    It is common to package the remote procedure call protocol with two pieces of stub code, a client stub that hides the network from the user, and the server stub that hides the network from the remote procedure. Thus, instead of calling a remote procedure P, the user calls a local procedure P that acts as the local agent for the remote procedure. This is the client stub. At the server end, the server stub is a main program that substitutes for the remote code and calls the real procedure P in response to messages from the client stub. Thus, the following picture emerges:

    User's Machine              Server Machine
    
    User      Stub       |   |  Stub        Server
                         |   |
      :       Proc P(X,Y)|   |  Repeat       Proc P(X,Y)
      :     /   Send(X)  |Net|    Receive(X)/  :
    Call P(X,Y) and      |   |    Call P(X,Y)  code
      :     \   Receive(Y)   |    Send(Y)   \  :
      :       Return     |   |  Forever      Return
    
    Note that the minimal client stub sends one message to the server stub and awaits one reply message before returning control to the user's code. The minimal server stub repeatedly awaits service requests from various clients, calls the actual code on the client's behalf, and sends the results.

    Here, we have completely ignored how the messages to and from the server are addressed; in a real network, of course, we must take care to address the messages properly, for example, including a return address in the message with X so that the server can send Y back to the right calling process.

    The network protocols typically used to connect client and server are usually at or above the session or transport layers! Thus, messages are addressed not to a particular machine, but to a particular process, or perhaps an incoming message port of a particular process, as on DEMOS. In fact, the protocol used by a DEMOS client to communicate with a DEMOS server is an excellent example of a very simple client server protocol.

    At the opposite extreme, the commonly used protocol to communicate between world wide web clients and servers (called HTTP, the Hypertext Transfer Protocol) involves opening a session from client to server, where the session is implemented using the Terminal Connection Protocol, part of the Internet's TCP/IP protocol suite. Once the bidirectional communication channel that implements the session is established, the client sends the outgoing parameters (the name of a web page) to the server, and then awaits the results (the text of the web page) on the same session's communications link.

    Exercise: Write code using the DEMOS message passing primitives (see Lecture 23) for the client and server stubs for a remote procedure call. Assume that the client has an appropriate link to the server, and make sure that the client creates a new link for each remote procedure call. One feature of DEMOS was that links had a special access right, multiple use; if this right was not present, the link would self-destruct after a single use. Your solution should make effective use of this behavior to prevent servers from reusing old links to clients after a remote procedure call has been completed. Discuss how your answer must be extended if the parameter list of the remote procedure includes multiple links that must be passed in or out.

    Exercise: What parameter passing modes make sense for parameters to remote procedures? Call by reference? Call by value? Call by value/result? Call by name? If you allow thunks to be implemented by remote procedures, does this change your answer?

  3. Lost Messages

    In a centralized system, most failures cause the entire system to stop working. Such a system is called a fail-hard system, or in the extreme case, where all failures cause a system to stop, fail-stop system. When a rare failure causes only some parts of the system to stop, it is sufficiently uncommon to become the subject of folklore. The infamous floating point error in the first generation of Intel's Pentium chips is a good example. In contrast, with distributed systems and networks, partial failures are common and must be dealt with. Such systems are fail-soft.

    The biggest problem an RPC protocol may encounter is lost messages. In the basic protocol, there are two messages, an outgoing message indicating a call to a remote procedure, and a reply message indicating a return from a remote procedure.

    Either of these messages may be lost, and the first question this raises is how to detect message loss. Perhaps the only realistic alternative for this purpose is to start a timer when the call message is transmitted and then wait a reasonable length of time. What is a reasonable delay clearly depends on the application! If the delay expires before a reply is received, the message is considered to be lost.

    The second question that arises is what to do if a message is lost. Only the client stub knows a loss occurred, and there is little choice. It must retransmit the request. (If there are multiple equivalent servers, it may address a different server on the retry.) This results in the following basic outline for the client stub:

    Procedure P(in X; out Y) -- Client Stub
      RA = return network address
      Repeat
        Send (X,RA) to RPC server
        Await either reply(Y) or timeout
      Until not timeout
    Return
    
    If the lost message was the request, this will correctly send a duplicate request to the server, and if this gets through, the server will correctly perform the service and send a reply.

    If the lost message was a reply, though, the second request will cause the server to repeat the service. For a read-only service, this will not cause problems, but for some read-write services, repeating the service is a mistake. The operation of writing a particular sector of a paricular file can be repeated without problems, but the operation of appending a buffer to a file, if repeated, causes the file to be corrupted. Operations which are safe to repeat are called idempotent operations because the sequence PPP has the same effect as P alone.

    A more complex protocol is required for non idempotent operations! The key is that the server must have sufficient information to determine whether a request is new one or a duplicate of a request previously acted on. To assure this, the request must include a new field, for example, a unique request identifier. The client stub using this will typically be something like the following:

    Procedure P(in X; out Y) -- Client Stub
      RA = return network address
      Compute transaction ID
      Repeat
        Send (X,RA,ID) to RPC server
        Repeat
          Await reply(Y,ID') or timeout
        Until timeout or (ID = ID')
      Until not timeout
      Assert that ID = ID'
    Return
    
    New complexity was added here because of the possiblity that the reply received was a duplicate reply to a previous request. This duplicate reply will contain the wrong transaction ID, and this allows it to be ignored. Such a duplicate reply can be created, for example, by a reply that was sufficiently delayed in transit that a duplicate request was sent.

    The server must maintain a cache of transaction IDs and the replies sent in response to them. If a new request is received with an ID that matches a cached ID, the corresponding reply is retransmitted. If a request is received with a new ID, the associated action is taken and, in addition to returning the reply, a copy is cached.

    This raises the problem of how to limit the memory requirements of the server's cache? With this protocol, it is never necessary to cache more than one reply on behalf of any particular remote client process, so if the transaction ID includes a process ID field, this allows the cache to be cleaned. In a large distributed system, such as the World-Wide-Web on the Internet, this is still insufficient.

    The solution is to find the upper bound on the total time a clients will wait for a reply. If client i never makes more than Ni retries, and if the interval between retries is Ti, what you want is max[i](NiTi). The server never needs to cache any replies for longer than this interval! How long should clients wait before they give up? This may depend on the application, but it should not be longer than the expected worst case time to repair the server in the event of a hard failure in the server's machine. Therefore, the server can always retire cache entries after the expected worst case repair time. Conveniently, for critical applications, this repair time is usually much shorter than it is for noncritical applications, where sloppy error recovery is typically acceptable.

    Exercise: Write the fault tolerant server stubs that go with each of the client stubs presented above.