[Indigo]<Grapevine>Docs>GVSOSP1.bravo!1

Grapevine is a multi-computer system on the Xerox research internet. It provides facilities for the delivery of digital messages such as computer mail; for naming people, machines and services; for authenticating people and machines; and for locating services on the internet. This paper has two goals: to describe the system itself and to serve as a case study of a real application of distributed computing. In part I of this paper we describe the set of services provided by Grapevine and how we divided the data and function of Grapevine among computers on the internet. In part II we present in more detail selected aspects of Grapevine that illustrate novel facilities or implementation techniques, or that provide insight into the structure of a distributed system. In part III we summarize the current state of the system and the lessons learned from it so far.

Grapevine is a system that provides message delivery, resource location, authentication, and access control services in a computer internet. The implementation of Grapevine is distributed and replicated. By distributed we mean that some of the services provided by Grapevine involve the use of multiple computers communicating through an internet; by replicated we mean that some of the services are provided equally well by any of several distinct computers. The primary use of Grapevine is as the delivery mechanism for computer mail, but Grapevine is used in many other ways as well. The Grapevine project was motivated by desires to do research into the structure of distributed systems and to provide our community with better computer mail service.

Figure 1 illustrates the kind of computing environment in which Grapevine was constructed and operates. A large internet of this style, known as the Xerox Research Internet, exists within the Xerox Corporation research and development community. This internet extends from coast to coast in the USA, to Canada, and to England. It contains over 1500 computers on more than 50 local networks.

Most computing is done in personal workstation computers [Alto]; typically each workstation has a modest amount of local disk storage attached. These workstations may be used at different times for different tasks, although generally each is used only by a single individual. The internet connecting these workstations is a collection of Ethernet local networks [Ethernet], gateways, and long distance links (typically telephone lines at data rates of 9600 bps to 56K bps). Also connected to the internet are server computers that provide shared services to the community, such as file storage and printing. The internet is arranged so that a high bandwidth local network connects computers in each local area, while lower bandwidth channels link these areas.

Communication protocols already exist for communicating between computers attached to the internet [Internet]. These protocols provide a uniform means for addressing any computer attached to any local network to send individual packets or establish and use byte streams. The individual packets are typically small (up to 532 bytes), and are sent unreliably (though with high probability of success) and with no acknowledgement. The byte stream protocols provide reliable, acknowledged, transmission of unlimited amounts of data [PUP].

Our primary consideration when specifying Grapevine’s functionality and engineering its implementation was its use as the delivery mechanism for a large, dispersed computer mail system. A computer mail system allows a group of human users to exchange messages of digital text. The sender prepares a message using some sort of text editing facility and names a set of recipients. He then presents it to a delivery mechanism. The delivery mechanism moves the message from the sender to an internal buffer for each recipient, where it is stored along with other messages for that recipient until he wants to receive them. We call the buffer for a recipient’s messages an inbox. When ready, the recipient asks the delivery mechanism to transfer any buffered messages from his inbox to local storage. The user then can read them with an appropriate text display program. The recipient names supplied by the sender may identify distribution lists, allowing the sender to name a related set of recipients, each of whom is to receive the message. We feel that computer mail is both an important application of distributed computing and a good test bed for ideas about how to structure distributed systems.

Buffered delivery of a digital message from a sender to one or more recipients is a mechanism that is useful in many contexts: it may be thought of as a general communication protocol, with the distinctive property that the recipient of the data need not be available at the time the sender wishes to transmit the data. Grapevine separates this message delivery function from message creation and interpretation, and makes the delivery function available for a wider range of uses. Grapevine does not interpret the contents of the messages it transports. It is up to the software clients of Grapevine, various message manipulation programs, to interpret the contents of these messages. Client programs implementing a computer mail user interface will interpret messages as interpersonal, textual memos. Other clients may interpret messages as print files, digital audio, software, capabilities, or data base updates.

Grapevine also offers authentication, access control, and resource location services to clients. For example, a document preparation system might use Grapevine’s resource location service to find a suitable printing server attached to the internet and then the message delivery service to transfer a document there for printing; or a file server might use Grapevine’s authentication and access control services to decide if a read request for a particular file should be honored.

Grapevine’s clients run on various workstation and server computers attached to the internet. Grapevine itself is implemented as programs running on server computers dedicated to Grapevine. A client accesses the services provided by Grapevine through the mediation of a software package running on the client’s computer. The Grapevine computers cooperate to provide services that are distributed and replicated.

We view distributed implementation of Grapevine both as a design goal and as the implementation technique that best meets the other design goals. A primary motivation for the Grapevine project was implementing a useful distributed system to understand some system structures that met a real set of requirements. Once we chose message delivery as the functional domain for the project, the following specific design goals played a significant role in determining system structure.

Grapevine makes its services available to many different clients. Thus, it should make no assumptions about message content. Also, the integrity of these services should not in any way depend on correctness of the clients. Though the use of an unsatisfactory client program will affect the service given to its user, it should not affect the service given to others. These two goals help determine the distribution of function between Grapevine and its clients.

Several goals relate to Grapevine’s reliability properties. A user or client implementor should feel confident that if a message is accepted for delivery then it will either be made available to its intended recipients or returned with an indication of what went wrong. The delivery mechanism should meet this goal in the face of user errors (such as invalid names), client errors (such as protocol violations), server problems (such as disk space congestion or hardware failures), or communication difficulties (such as internet link severance or gateway crashes). While messages may be inaccessible to the intended recipient temporarily, they should never be lost. Failure of a single Grapevine server computer should not mean the unavailability of the Grapevine services to any client.

The typical interval from sending a message to its arrival in a recipient’s inbox should be a few minutes at most. The typical interactive delay perceived by a user when delivering or receiving a message should be a few seconds at most. Since small additions to delivery times are not likely to be perceived by users, it is permissible to improve interactive behavior at the expense of delivery time.

Grapevine should allow decentralized administration. The users of a widespread internet naturally belong to different organizations. Such activities as admission of users, control of the names by which they are known, and their inclusion in distribution lists should not require an unnatural degree of cooperation and shared conventions among administrations. An administrator should be able to implement his decisions by interacting directly with Grapevine rather than by sending requests to a central agency.

Grapevine maintains a registration data base that maps names to information about the users, machines, services, distribution lists, and access control lists that those names signify. This data base is used in controlling the message delivery service; is accessed directly for the resource location, access control and authentication services; and is used to configure Grapevine itself. Grapevine also makes the values in the data base available to clients to apply their own semantics.

A group entry contains a set of RNames of other data base entries (as well as additional information that will be discussed later). Groups are a way of naming collections of RNames. The groups form a naming network with no structural constraints. Groups are used primarily as distribution lists: specifying a group RName as a recipient for a message causes that message to be sent to all RNames in that group (and in contained groups). Groups also are used to represent access control lists and collections of like resources.

An individual entry contains an authenticator (a password), a list of inbox sites, and a connect site (as well as additional information that will be discussed later.) The inbox site list contains the names of message servers, in order of preference, where the individual’s messages may be buffered. The way these multiple inboxes are used is discussed in section 4.2. The connect site is an address for making an internet connection to the individual. Thus, the entry specifies ways of authenticating the identity of and communicating with (by message delivery or internet connection) the named entity. Individuals are used to represent human users and servers, in particular the servers that implement Grapevine. Usually the connect site field is used only for individuals that represent servers. Specifying an individual RName (either a human or a server) as a recipient of a message causes the message to be forwarded to and buffered in an inbox for that RName.

The client presents a message body from the sender for delivery to the recipients. The sender must be the RName of an individual and the password must authenticate that individual (see below). The recipients are individual and group RNames. The individuals correspond directly to message recipients while the groups name distribution lists. After Grapevine acknowledges acceptance of the message the client can go about its other business. Grapevine then expands any groups specified as recipients to produce the complete set of individuals that are to receive the message and delivers the message to an inbox for each.

The authentication function allows any client to determine the authenticity of an individual. An individual/password combination is authentic if the password matches the one in the individual’s registration data base entry. (This password-based authentication scheme is a very weak one. The Grapevine design includes a proper encryption-based authentication function, which is described in section 9.)

The first resource location function returns a group’s membership set. If the group is interpreted as a distribution list, this function yields the individual recipients of a message sent to the distribution list; if the group is interpreted as the name of some service, this function yields the names of the servers that offer the service. For a group representing a service, combining the first function with the second enables a client to discover the internet addresses of machines offering the service, as described in section 5. The third function is used for message delivery and retrieval as described in section 4.

We use a partitioned naming scheme for RNames. The partitions serve as the basis for dividing the administrative responsibility, and for distributing the data base among the Grapevine computers. We structure the name space of RNames as a two-level hierarchy. An RName is a character string of the form F.R where R is a registry name and F is a name within that registry. Registries can correspond to organizational, geographic, or other arbitrary partitions that exist within the user community. A two-level hierarchy is appropriate for the size and organizational complexity of our user community, but a larger community or one with more organizational diversity would cause us to use a three-level scheme. Using more levels would not be a fundamental change to Grapevine.

As indicated earlier, Grapevine is implemented by code that runs in dedicated Grapevine computers, and by code that runs in clients’ computers. The code running in a Grapevine computer is partitioned into two parts, called the registration server and the message server. Although one registration server and one message server cohabit each Grapevine computer, they should be thought of as separate entities. (Message servers and registration servers communicate with one another purely by internet protocols.) Several Grapevine computers are scattered around the internet, their placement being dictated by load and topology. Their registration servers work together to implement the registration service. Their message servers work together to implement the delivery service. As we will see in sections 4 and 5, message and registration servers are each clients of the other’s services.

The registration data base is distributed and replicated. Distribution is at the grain of a registry; that is, each registration server contains either all entries for a registry or no entries for that registry. Typically no registration server contains all registries. Also, each registry is replicated in several different registration servers. Each registration server supports, by publicly available internet protocols, the registration functions described above for names in the registries that it contains. Any server that contains the data for a registry can accept a change to that registry. That server takes the responsibility for propagating the change to the other relevant servers.

If an increase in Grapevine’s capacity is required to meet expanding load, then another Grapevine computer can be added easily without disrupting the operation of existing servers or clients. If usage patterns change, then the distribution of function among the Grapevine computers can be changed for a particular individual, or for an entire registry. As we shall see later this redistribution is facilitated by using the Grapevine data base to describe the configuration of Grapevine itself.

The code that runs in clients’ machines is called the GrapevineUser package. (Actually there are several GrapevineUser packages: one for each language or operating environment. However, their function and characteristics are sufficiently similar that they may be thought of as a single package.) This package has two roles: it implements the internet protocols for communicating with particular Grapevine servers; and it performs the resource location required to choose which server to contact for a particular function, given the data distribution and server availability situation of the moment. GrapevineUser thus makes the multiple Grapevine servers look like a single service. A client using the GrapevineUser package never has to mention the name or internet address of a particular Grapevine server. The GrapevineUser package is not trusted by the rest of Grapevine. Although an incorrect package could affect the services provided to any client that uses it, it cannot affect the use of Grapevine by other clients. The implementation of Grapevine, however, includes engineering decisions based on the known behavior of the GrapevineUser package, on the assumption that most clients will use it or equivalent packages.

With Figure 2 we can consider examples of how Grapevine works. If a user named P.Q were using workstation 1 and wished to send a message to X.Y, then events would proceed as follows. (The mechanisms used in the following scenario are described in more detail in sections 4 and 5.) After the user had prepared the message using a suitable client program, the client program would call the delivery function of the GrapevineUser package on workstation 1. GrapevineUser would contact some registration server, such as A, and use the Grapevine resource location functions to locate any message server, such as B; it would then submit the message to B. For each recipient, B would use the resource location facilities, and suitable registration servers (such as A) to determine that recipient’s best inbox site. For the recipient X.Y, this might be the message server C, in which case B would forward the message to C. C would buffer this message locally in the inbox for X.Y.

When X.Y wishes to use workstation 2 to read his mail, his client program calls the retrieval function of the GrapevineUser package in workstation 2. GrapevineUser uses some registration server (such as D) that contains the Y registry to locate inbox sites for X.Y, then connects to each of these inbox sites to retrieve his messages. Before allowing this retrieval, C uses a registration server to authenticate X.Y. If the message had more recipients, the message server B might consult other registration servers and forward the message to multiple message servers. If some of the specified recipients were distribution lists, B would use the registration servers to obtain the members of the appropriate groups.

The particular facilities provided by Grapevine were chosen because they are required to support computer mail. The functions were generalized and separated so other applications also could make use of them. The designers of other systems are invited to use the Grapevine facilities if they want to. Two important benefits occur, however, if Grapevine becomes the only mechanism for authentication and for grouping individuals by organization, interest, and function. First, if Grapevine performs all authentications, then users have the same name and password everywhere, thus simplifying many administrative operations. Second, if Grapevine is used everywhere for grouping, then the same group structure can be used for many different purposes. For example, a single group can be an access control list for several different file servers and also be a distribution list for message delivery. The groups in the registration data base capture the structure of the user community in one place to be used in many ways.

To submit a message for delivery a client must establish an internet connection to a message server; any operational server will do. This resource location step, done by the GrapevineUser package, is described in section 5. Once such a connection is established, the GrapevineUser package simply translates client procedure calls into the corresponding server protocol actions. If that particular message server crashes or otherwise becomes inaccessible during the message submission then the GrapevineUser package locates another message server (if possible), and restarts the message submission.

The client next presents the RName and password of the sender, a returnTo RName, and a list of recipient RNames. The message server authenticates the sender by using the registration service. If the authentication fails, the server refuses to accept the message for delivery. Each recipient RName is then checked to see if it matches an RName in the registration data base. All invalid recipient names are reported back to the client. In the infrequent case that no registration server for a registry is accessible, all RNames in that registry are presumed for the time being to be valid. The server constructs a property list for the message containing the sender name, returnTo name, recipient list, and a postmark. The postmark is a unique identification of the message, and consists of the time the message was presented for delivery together with the server’s internet address to guarantee uniqueness. Next, the client machine presents the message body to the server. The server puts the property list and message body in reliable storage, indicates that the message is accepted for delivery, and closes the connection. The client may cancel delivery anytime prior to sending the final packet of the message body, for example after being informed of invalid recipients.

The message body is not interpreted by the server; in particular, as mentioned earlier, it need not consist of text. Only the property list is used to direct delivery. A client might obtain the properties by parsing a text message body and require that the parsed text be syntactically separated as a "header", but this happens before Grapevine is involved in the delivery. The property list stays with the message body throughout the delivery process and is available to the receiving client. Grapevine guarantees that the recipient names in the property list were used to control the delivery of the message, and that the sender RName and postmark are accurate.

Once a message is accepted for delivery, the client may go about its other business. The message server, however, has more to do. It first determines the complete list of individuals that should receive the message by recursively enumerating groups in the property list. It obtains from the registration service each individual’s inbox site list. It chooses a destination message server for each on the basis of the inbox site list ordering and its opinion of the present accessibility of the other message servers. The individual names are accumulated in steering lists, one for each message server to which the message should be forwarded and one for local recipients. The message server then forwards the message and appropriate steering list to each of the other servers, and places the message in the inboxes for local recipients. Upon receiving a forwarded message from another server, the same algorithm is performed using the individuals in the incoming steering list as the recipients, all of which will have local inboxes unless the registration data base has changed. If a message is to be added to several local inboxes, the mail server stores the property list and body just once on its local disk and places references to this shared object in the individual inboxes. Such message sharing saves a considerable amount of storage in the server.

With this delivery algorithm, messages for an individual tend to accumulate at the server that is first on the inbox site list. Duplicate elimination, required because distribution lists can overlap, is achieved while adding the message into the inboxes by being sure never to add a message if that same message, as identified by its postmark, was the one previously added to that inbox. This duplicate elimination mechanism fails under certain unusual circumstances such as servers crashing or the database changing during the delivery process, but requires less computation than the alternative of sorting the list of recipient individuals.

In some circumstances delivery will be impossible: for example, a recipient RName may be removed from the registration data base between validation and delivery, or a valid distribution list may contain invalid RNames. Occasionally delivery may not occur within a reasonable time: for example, a network link may be down for several days. In such cases the message server mails a copy of the message to an appropriate RName with a text explanation of what the problem was and who did not get the message. The appropriate RName for this error notification may be the returnTo name recorded in the message’s property list or the owner of the distribution list that contained the invalid name, as recorded in a group entry in the registration data base. Even this error notification can fail, however, and ultimately such messages end up in a "DeadLetter" inbox for consideration by a human administrator.

To retrieve new messages for an individual, a client invokes the GrapevineUser package to determine the internet addresses of all inbox sites for the individual, and to poll each site for new messages by sending it a single inbox check packet containing the individual’s RName. A message server replies to an inbox check packet with a packet containing a boolean with the value TRUE if a non-empty inbox for that RName exists on the server and FALSE otherwise. For each positive response, GrapevineUser connects to the message server and presents the individual’s name and password. If these are authentic, then the message server permits the client to inspect waiting messages one at a time, obtaining first the property list and then the body. There is no guarantee that messages will be retrieved in the order they were presented for delivery. Since the inbox is read first-in, first-out and messages tend to accumulate in the first inbox of an individual’s inbox site list, however, this order is highly likely to be preserved. The postmark allows clients who care to sort their messages into approximate chronological order. The order is approximate because the postmarks are based on the time as perceived by individual message servers, not on any universal time. When a client has safely stored the messages, it may send an acknowledgement to the message server. On receipt of this acknowledgement, the server discards all record of the retrieved messages. Closing the retrieval connection without acknowledgement causes the message server to retain these messages. For the benefit of users who want to inspect new messages when away from their personal workstation, the message server also allows the client to specify that some messages from the inbox be retained and some be discarded.

Replication is used to achieve a highly available message delivery service. Any message server can accept any message for delivery. Complete replication of this acceptance function is important because the human user of a computer mail client may be severely inconvenienced if he cannot present a message for delivery when he wants to. He would have to put the message somewhere and remember to present it later. Fortunately, complete replication of the acceptance function is cheap and simple to provide. Message transport and buffering, however, are not completely replicated. Once accepted for delivery, the crash of a single message server can delay delivery of a particular message until the server is operational again, by trapping the message in a forwarding queue or an inbox. (The message servers are programmed so any crash short of a physical disk catastrophe will not lose information. Writing a single page to the disk is used as the primitive atomic action.) Allowing multiple inboxes for an individual replicates the delivery path. Unless all servers containing an individual’s inbox sites become inaccessible at once, new messages for that individual can get through. We could have replicated messages in several of an individuals’s inboxes, but the expense and complexity of doing so does not seem to be justified by the extra availability it would provide. If the immediate delivery of a message is important then its failure to arrive will be noticed outside the system and it can be sent again because a delivery path for new messages still exists.

One registry in the data base is of particular importance, the registry named GV (for Grapevine). The GV registry is replicated in every registration server; all names of the form *.gv exist in every registration server. The GV registry describes and controls the distribution and replication of the registration database, and allows clients to locate appropriate registration servers for particular RNames.

The groups of the GV registry are the registries themselves; reg is a registry if and only if there exists a group reg.gv. The members of this group are the RNames of the registration servers that contain the registry. The GV registry is represented this way too. Since the GV registry is in every registration server, the membership set for gv.gv includes the RNames of all registration servers.

Each message server is represented as an individual in the MS registry (for message servers). The connect site in this entry is the internet address where clients of this message server can connect to it. (The authenticator and inbox site list in the entry are used also, as we will see later.) It is message server RNames that appear in individuals’ inbox site lists.

The registration data base is used to locate resources. In general, a service is represented as a group in the data base; servers are individuals. The members of the group are the RNames of the servers offering the service; the connect sites of the individuals are the internet addresses for the servers. To contact an instance of the service, a client uses the GrapevineUser package to obtain the membership of the group and then to obtain the connect site of each member. The client then may choose among these addresses, for example on the basis of closeness and availability.

The GrapevineUser package employs such a resource location strategy to find things in the distributed registration data base. Assume for a moment that there is a way of getting the internet address of some operational registration server, say rs1.gv. GrapevineUser can find the internet addresses of those registration servers that contain the entry for RName s.r by connecting to rs1.gv and asking it to produce the membership of r.gv. GrapevineUser can pick a particular registration server to use by asking rs1.gv to produce the connect site for each server in r.gv and attempting to make a connection until one responds. If s.r is a valid name, then any registration server in r.gv has the entry for it. At this point GrapevineUser can extract any needed information from the entry of s.r, for example, the inbox site list.

In practice, these resource location algorithms are streamlined so that although the general algorithms are very flexible, the commonly occurring cases are handled with acceptable efficiency. For example, a client client may assume initially that any registration server contains the data base entry for a particular name; the registration server will return the requested information or a name not found error if this registration server knows the registry, and otherwise will return a wrong server error. A client can try any registration server; only in the case of a wrong server response does the client need to perform the full resource location algorithm.

We are left with the problem of determining the internet address of some registration server in order to get started. Here it is necessary to depend on some more primitive resource location protocol. The appropriate mechanism depends on what primitive facilities are available in the internet. We use two mechanisms. First, on each local network is a primitive name lookup server, which can be contacted by a broadcast protocol. The name lookup server contains an infrequently updated data base that maps character strings to internet addresses. We arrange for the fixed character string GrapevineRServer to be entered in this data base and mapped to the internet addresses of some subset of the registration servers in the internet. The GrapevineUser package can get a set of addresses of registration servers using the broadcast name lookup protocol, and send a distinctive packet to each of these addresses. Any accessible registration server will respond to such packets, and the client may then attempt to connect to whichever server responds. Second, we broadcast a distinctive packet on the directly connected local network. Again, any accessible registration server will respond. This second mechanism is used in addition to the first because, when there is a registration server on the local network, the second method gives response faster and allows a client to find a local registration server when the name lookup server is down. The question of ensuring that we in fact talk only to a registration server and not to an impostor is discussed in section 9.