The Chubby lock service for loosely-coupled distributed systems

Mike Burrows, Google Inc.

Abstract

We describe our experiences with the Chubby lock ser- vice, which is intended to provide coarse-grained lock- ing as well as reliable (though low-volume) storage for a loosely-coupled distributed system. Chubby provides an interface much like a distributed file system with ad- visory locks, but the design emphasis is on availability and reliability, as opposed to high performance. Many instances of the service have been used for over a year, with several of them each handling a few tens of thou- sands of clients concurrently. The paper describes the initial design and expected use, compares it with actual use, and explains how the design had to be modified to accommodate the differences.

1 Introduction

This paper describes a lock service called Chubby. It is intended for use within a loosely-coupled distributed sys- tem consisting of moderately large numbers of small ma- chines connected by a high-speed network. For example, a Chubby instance (also known as a Chubby cell) might serve ten thousand 4-processor machines connected by 1Gbit/s Ethernet. Most Chubby cells are confined to a single data centre or machine room, though we do run at least one Chubby cell whose replicas are separated by thousands of kilometres.

The purpose of the lock service is to allow its clients to synchronize their activities and to agree on basic in- formation about their environment. The primary goals included reliability, availability to a moderately large set of clients, and easy-to-understand semantics; through- put and storage capacity were considered secondary. Chubby’s client interface is similar to that of a simple file system that performs whole-file reads and writes, aug- mented with advisory locks and with notification of var- ious events such as file modification.

We expected Chubby to help developers deal with coarse-grained synchronization within their systems, and in particular to deal with the problem of electing a leader from among a set of otherwise equivalent servers. For

example, the Google File System [7] uses a Chubby lock to appoint a GFS master server, and Bigtable [3] uses Chubby in several ways: to elect a master, to allow the master to discover the servers it controls, and to permit clients to find the master. In addition, both GFS and Bigtable use Chubby as a well-known and available loca- tion to store a small amount of meta-data; in effect they use Chubby as the root of their distributed data struc- tures. Some services use locks to partition work (at a coarse grain) between several servers.

Before Chubby was deployed, most distributed sys- tems at Google used ad hoc methods for primary elec- tion (when work could be duplicated without harm), or required operator intervention (when correctness was es- sential). In the former case, Chubby allowed a small sav- ing in computing effort. In the latter case, it achieved a significant improvement in availability in systems that no longer required human intervention on failure.

Readers familiar with distributed computing will rec- ognize the election of a primary among peers as an in- stance of the distributed consensus problem, and realize we require a solution using asynchronous communica- tion; this term describes the behaviour of the vast ma- jority of real networks, such as Ethernet or the Internet, which allow packets to be lost, delayed, and reordered. (Practitioners should normally beware of protocols based on models that make stronger assumptions on the en- vironment.) Asynchronous consensus is solved by the Paxos protocol [12, 13]. The same protocol was used by Oki and Liskov (see their paper on viewstamped replica- tion [19, §4]), an equivalence noted by others [14, §6]. Indeed, all working protocols for asynchronous consen- sus we have so far encountered have Paxos at their core. Paxos maintains safety without timing assumptions, but clocks must be introduced to ensure liveness; this over- comes the impossibility result of Fischer et al. [5, §1].

Building Chubby was an engineering effort required to fill the needs mentioned above; it was not research. We claim no new algorithms or techniques. The purpose of this paper is to describe what we did and why, rather than to advocate it. In the sections that follow, we de- scribe Chubby’s design and implementation, and how it

OSDI ’06: 7th USENIX Symposium on Operating Systems Design and ImplementationUSENIX Association 335

has changed in the light of experience. We describe un- expected ways in which Chubby has been used, and fea- tures that proved to be mistakes. We omit details that are covered elsewhere in the literature, such as the details of a consensus protocol or an RPC system.

2 Design

2.1 Rationale

One might argue that we should have built a library em- bodying Paxos, rather than a library that accesses a cen- tralized lock service, even a highly reliable one. A client Paxos library would depend on no other servers (besides the name service), and would provide a standard frame- work for programmers, assuming their services can be implemented as state machines. Indeed, we provide such a client library that is independent of Chubby.

Nevertheless, a lock service has some advantages over a client library. First, our developers sometimes do not plan for high availability in the way one would wish. Of- ten their systems start as prototypes with little load and loose availability guarantees; invariably the code has not been specially structured for use with a consensus proto- col. As the service matures and gains clients, availability becomes more important; replication and primary elec- tion are then added to an existing design. While this could be done with a library that provides distributed consensus, a lock server makes it easier to maintain exist- ing program structure and communication patterns. For example, to elect a master which then writes to an ex- isting file server requires adding just two statements and one RPC parameter to an existing system: One would acquire a lock to become master, pass an additional inte- ger (the lock acquisition count) with the write RPC, and add an if-statement to the file server to reject the write if the acquisition count is lower than the current value (to guard against delayed packets). We have found this tech- nique easier than making existing servers participate in a consensus protocol, and especially so if compatibility must be maintained during a transition period.

Second, many of our services that elect a primary or that partition data between their components need a mechanism for advertising the results. This suggests that we should allow clients to store and fetch small quanti- ties of data—that is, to read and write small files. This could be done with a name service, but our experience has been that the lock service itself is well-suited for this task, both because this reduces the number of servers on which a client depends, and because the consistency fea- tures of the protocol are shared. Chubby’s success as a name server owes much to its use of consistent client caching, rather than time-based caching. In particular, we found that developers greatly appreciated not having

to choose a cache timeout such as the DNS time-to-live value, which if chosen poorly can lead to high DNS load, or long client fail-over times.

Third, a lock-based interface is more familiar to our programmers. Both the replicated state machine of Paxos and the critical sections associated with exclusive locks can provide the programmer with the illusion of sequen- tial programming. However, many programmers have come across locks before, and think they know to use them. Ironically, such programmers are usually wrong, especially when they use locks in a distributed system; few consider the effects of independent machine fail- ures on locks in a system with asynchronous communi- cations. Nevertheless, the apparent familiarity of locks overcomes a hurdle in persuading programmers to use a reliable mechanism for distributed decision making.

Last, distributed-consensus algorithms use quorums to make decisions, so they use several replicas to achieve high availability. For example, Chubby itself usually has five replicas in each cell, of which three must be run- ning for the cell to be up. In contrast, if a client system uses a lock service, even a single client can obtain a lock and make progress safely. Thus, a lock service reduces the number of servers needed for a reliable client system to make progress. In a loose sense, one can view the lock service as a way of providing a generic electorate that allows a client system to make decisions correctly when less than a majority of its own members are up. One might imagine solving this last problem in a dif- ferent way: by providing a “consensus service”, using a number of servers to provide the “acceptors” in the Paxos protocol. Like a lock service, a consensus service would allow clients to make progress safely even with only one active client process; a similar technique has been used to reduce the number of state machines needed for Byzan- tine fault tolerance [24]. However, assuming a consensus service is not used exclusively to provide locks (which reduces it to a lock service), this approach solves none of the other problems described above.

These arguments suggest two key design decisions: • We chose a lock service, as opposed to a library or

service for consensus, and • we chose to serve small-files to permit elected pri-

maries to advertise themselves and their parameters, rather than build and maintain a second service.

Some decisions follow from our expected use and from our environment: • A service advertising its primary via a Chubby file

may have thousands of clients. Therefore, we must allow thousands of clients to observe this file, prefer- ably without needing many servers.

• Clients and replicas of a replicated service may wish to know when the service’s primary changes. This

OSDI ’06: 7th USENIX Symposium on Operating Systems Design and Implementation USENIX Association336

suggests that an event notification mechanism would be useful to avoid polling.

• Even if clients need not poll files periodically, many will; this is a consequence of supporting many devel- opers. Thus, caching of files is desirable.

• Our developers are confused by non-intuitive caching semantics, so we prefer consistent caching.

• To avoid both financial loss and jail time, we provide security mechanisms, including access control. A choice that may surprise some readers is that we

do not expect lock use to be fine-grained, in which they might be held only for a short duration (seconds or less); instead, we expect coarse-grained use. For example, an application might use a lock to elect a primary, which would then handle all access to that data for a consider- able time, perhaps hours or days. These two styles of use suggest different requirements from a lock server.

Coarse-grained locks impose far less load on the lock server. In particular, the lock-acquisition rate is usu- ally only weakly related to the transaction rate of the client applications. Coarse-grained locks are acquired only rarely, so temporary lock server unavailability de- lays clients less. On the other hand, the transfer of a lock from client to client may require costly recovery proce- dures, so one would not wish a fail-over of a lock server to cause locks to be lost. Thus, it is good for coarse- grained locks to survive lock server failures, there is little concern about the overhead of doing so, and such locks allow many clients to be adequately served by a modest number of lock servers with somewhat lower availability.

Fine-grained locks lead to different conclusions. Even brief unavailability of the lock server may cause many clients to stall. Performance and the ability to add new servers at will are of great concern because the trans- action rate at the lock service grows with the combined transaction rate of clients. It can be advantageous to re- duce the overhead of locking by not maintaining locks across lock server failure, and the time penalty for drop- ping locks every so often is not severe because locks are held for short periods. (Clients must be prepared to lose locks during network partitions, so the loss of locks on lock server fail-over introduces no new recovery paths.)

Chubby is intended to provide only coarse-grained locking. Fortunately, it is straightforward for clients to implement their own fine-grained locks tailored to their application. An application might partition its locks into groups and use Chubby’s coarse-grained locks to allocate these lock groups to application-specific lock servers. Little state is needed to maintain these fine-grain locks; the servers need only keep a non-volatile, monotonically- increasing acquisition counter that is rarely updated. Clients can learn of lost locks at unlock time, and if a simple fixed-length lease is used, the protocol can be simple and efficient. The most important benefits of this

client processes

5 servers of a Chubby cell client

application chubby library

client application

chubby library

. . .

m RPCs m mastermmm

PPPPPq

�����1

Figure 1: System structure

scheme are that our client developers become responsible for the provisioning of the servers needed to support their load, yet are relieved of the complexity of implementing consensus themselves.

2.2 System structure

Chubby has two main components that communicate via RPC: a server, and a library that client applications link against; see Figure 1. All communication between Chubby clients and the servers is mediated by the client library. An optional third component, a proxy server, is discussed in Section 3.1.

A Chubby cell consists of a small set of servers (typi- cally five) known as replicas, placed so as to reduce the likelihood of correlated failure (for example, in different racks). The replicas use a distributed consensus protocol to elect a master; the master must obtain votes from a majority of the replicas, plus promises that those replicas will not elect a different master for an interval of a few seconds known as the master lease. The master lease is periodically renewed by the replicas provided the master continues to win a majority of the vote.

The replicas maintain copies of a simple database, but only the master initiates reads and writes of this database. All other replicas simply copy updates from the master, sent using the consensus protocol.

Clients find the master by sending master location requests to the replicas listed in the DNS. Non-master replicas respond to such requests by returning the iden- tity of the master. Once a client has located the master, the client directs all requests to it either until it ceases to respond, or until it indicates that it is no longer the master. Write requests are propagated via the consensus protocol to all replicas; such requests are acknowledged when the write has reached a majority of the replicas in the cell. Read requests are satisfied by the master alone; this is safe provided the master lease has not expired, as no other master can possibly exist. If a master fails, the other replicas run the election protocol when their master leases expire; a new master will typically be elected in a few seconds. For example, two recent elections took 6s and 4s, but we see values as high as 30s (§4.1).

OSDI ’06: 7th USENIX Symposium on Operating Systems Design and ImplementationUSENIX Association 337

If a replica fails and does not recover for a few hours, a simple replacement system selects a fresh machine from a free pool and starts the lock server binary on it. It then updates the DNS tables, replacing the IP address of the failed replica with that of the new one. The current mas- ter polls the DNS periodically and eventually notices the change. It then updates the list of the cell’s members in the cell’s database; this list is kept consistent across all the members via the normal replication protocol. In the meantime, the new replica obtains a recent copy of the database from a combination of backups stored on file servers and updates from active replicas. Once the new replica has processed a request that the current master is waiting to commit, the replica is permitted to vote in the elections for new master.

2.3 Files, directories, and handles

Chubby exports a file system interface similar to, but simpler than that of UNIX [22]. It consists of a strict tree of files and directories in the usual way, with name components separated by slashes. A typical name is:

/ls/foo/wombat/pouch

The ls prefix is common to all Chubby names, and stands for lock service. The second component (foo) is the name of a Chubby cell; it is resolved to one or more Chubby servers via DNS lookup. A special cell name local indicates that the client’s local Chubby cell should be used; this is usually one in the same building and thus the one most likely to be accessible. The remain- der of the name, /wombat/pouch, is interpreted within the named Chubby cell. Again following UNIX, each di- rectory contains a list of child files and directories, while each file contains a sequence of uninterpreted bytes.

Because Chubby’s naming structure resembles a file system, we were able to make it available to applications both with its own specialized API, and via interfaces used by our other file systems, such as the Google File System. This significantly reduced the effort needed to write basic browsing and name space manipulation tools, and reduced the need to educate casual Chubby users.

The design differs from UNIX in a ways that ease dis- tribution. To allow the files in different directories to be served from different Chubby masters, we do not expose operations that can move files from one directory to an- other, we do not maintain directory modified times, and we avoid path-dependent permission semantics (that is, access to a file is controlled by the permissions on the file itself rather than on directories on the path leading to the file). To make it easier to cache file meta-data, the system does not reveal last-access times.

The name space contains only files and directories, collectively called nodes. Every such node has only one name within its cell; there are no symbolic or hard links.

Nodes may be either permanent or ephemeral. Any node may be deleted explicitly, but ephemeral nodes are also deleted if no client has them open (and, for directo- ries, they are empty). Ephemeral files are used as tempo- rary files, and as indicators to others that a client is alive. Any node can act as an advisory reader/writer lock; these locks are described in more detail in Section 2.4.

Each node has various meta-data, including three names of access control lists (ACLs) used to control reading, writing and changing the ACL names for the node. Unless overridden, a node inherits the ACL names of its parent directory on creation. ACLs are themselves files located in an ACL directory, which is a well-known part of the cell’s local name space. These ACL files con- sist of simple lists of names of principals; readers may be reminded of Plan 9’s groups [21]. Thus, if file F’s write ACL name is foo, and the ACL directory contains a file foo that contains an entry bar, then user bar is permit- ted to write F. Users are authenticated by a mechanism built into the RPC system. Because Chubby’s ACLs are simply files, they are automatically available to other ser- vices that wish to use similar access control mechanisms.

The per-node meta-data includes four monotonically- increasing 64-bit numbers that allow clients to detect changes easily: • an instance number; greater than the instance number

of any previous node with the same name. • a content generation number (files only); this in-

creases when the file’s contents are written. • a lock generation number; this increases when the

node’s lock transitions from free to held. • an ACL generation number; this increases when the

node’s ACL names are written. Chubby also exposes a 64-bit file-content checksum so clients may tell whether files differ.

Clients open nodes to obtain handles that are analo- gous to UNIX file descriptors. Handles include: • check digits that prevent clients from creating or

guessing handles, so full access control checks need be performed only when handles are created (com- pare with UNIX, which checks its permissions bits at open time, but not at each read/write because file de- scriptors cannot be forged).

• a sequence number that allows a master to tell whether a handle was generated by it or by a previous master.

• mode information provided at open time to allow the master to recreate its state if an old handle is presented to a newly restarted master.

2.4 Locks and sequencers

Each Chubby file and directory can act as a reader-writer lock: either one client handle may hold the lock in exclu- sive (writer) mode, or any number of client handles may

OSDI ’06: 7th USENIX Symposium on Operating Systems Design and Implementation USENIX Association338

hold the lock in shared (reader) mode. Like the mutexes known to most programmers, locks are advisory. That is, they conflict only with other attempts to acquire the same lock: holding a lock called F neither is necessary to access the file F , nor prevents other clients from do- ing so. We rejected mandatory locks, which make locked objects inaccessible to clients not holding their locks: • Chubby locks often protect resources implemented by

other services, rather than just the file associated with the lock. To enforce mandatory locking in a meaning- ful way would have required us to make more exten- sive modification of these services.

• We did not wish to force users to shut down appli- cations when they needed to access locked files for debugging or administrative purposes. In a complex system, it is harder to use the approach employed on most personal computers, where administrative soft- ware can break mandatory locks simply by instructing the user to shut down his applications or to reboot.

• Our developers perform error checking in the conven- tional way, by writing assertions such as “lock X is held”, so they benefit little from mandatory checks. Buggy or malicious processes have many opportuni- ties to corrupt data when locks are not held, so we find the extra guards provided by mandatory locking to be of no significant value.

In Chubby, acquiring a lock in either mode requires write permission so that an unprivileged reader cannot prevent a writer from making progress.

Locking is complex in distributed systems because communication is typically uncertain, and processes may fail independently. Thus, a process holding a lock L may issue a request R, but then fail. Another process may ac- quire L and perform some action before R arrives at its destination. If R later arrives, it may be acted on without the protection of L, and potentially on inconsistent data. The problem of receiving messages out of order has been well studied; solutions include virtual time [11], and vir- tual synchrony [1], which avoids the problem by ensuring that messages are processed in an order consistent with the observations of every participant.

It is costly to introduce sequence numbers into all the interactions in an existing complex system. Instead, Chubby provides a means by which sequence numbers can be introduced into only those interactions that make use of locks. At any time, a lock holder may request a se- quencer, an opaque byte-string that describes the state of the lock immediately after acquisition. It contains the name of the lock, the mode in which it was acquired (exclusive or shared), and the lock generation number. The client passes the sequencer to servers (such as file servers) if it expects the operation to be protected by the lock. The recipient server is expected to test whether the sequencer is still valid and has the appropriate mode;

if not, it should reject the request. The validity of a sequencer can be checked against the server’s Chubby cache or, if the server does not wish to maintain a ses- sion with Chubby, against the most recent sequencer that the server has observed. The sequencer mechanism re- quires only the addition of a string to affected messages, and is easily explained to our developers.

Although we find sequencers simple to use, important protocols evolve slowly. Chubby therefore provides an imperfect but easier mechanism to reduce the risk of de- layed or re-ordered requests to servers that do not sup- port sequencers. If a client releases a lock in the normal way, it is immediately available for other clients to claim, as one would expect. However, if a lock becomes free because the holder has failed or become inaccessible, the lock server will prevent other clients from claiming the lock for a period called the lock-delay. Clients may specify any lock-delay up to some bound, currently one minute; this limit prevents a faulty client from making a lock (and thus some resource) unavailable for an arbitrar- ily long time. While imperfect, the lock-delay protects unmodified servers and clients from everyday problems caused by message delays and restarts.

2.5 Events

Chubby clients may subscribe to a range of events when they create a handle. These events are delivered to the client asynchronously via an up-call from the Chubby li- brary. Events include: • file contents modified—often used to monitor the lo-

cation of a service advertised via the file. • child node added, removed, or modified—used to im-

plement mirroring (§2.12). (In addition to allowing new files to be discovered, returning events for child nodes makes it possible to monitor ephemeral files without affecting their reference counts.)

• Chubby master failed over—warns clients that other events may have been lost, so data must be rescanned.

• a handle (and its lock) has become invalid—this typi- cally suggests a communications problem.

• lock acquired—can be used to determine when a pri- mary has been elected.

• conflicting lock request from another client—allows the caching of locks. Events are delivered after the corresponding action has

taken place. Thus, if a client is informed that file contents have changed, it is guaranteed to see the new data (or data that is yet more recent) if it subsequently reads the file.

The last two events mentioned are rarely used, and with hindsight could have been omitted. After primary election for example, clients typically need to commu- nicate with the new primary, rather than simply know that a primary exists; thus, they wait for a file modifi-

OSDI ’06: 7th USENIX Symposium on Operating Systems Design and ImplementationUSENIX Association 339

cation event indicating that the new primary has written its address in a file. The conflicting lock event in theory permits clients to cache data held on other servers, using Chubby locks to maintain cache consistency. A notifi- cation of a conflicting lock request would tell a client to finish using data associated with the lock: it would finish pending operations, flush modifications to a home loca- tion, discard cached data, and release. So far, no one has adopted this style of use.

2.6 API

Clients see a Chubby handle as a pointer to an opaque structure that supports various operations. Handles are created only by Open(), and destroyed with Close().

Open() opens a named file or directory to produce a handle, analogous to a UNIX file descriptor. Only this call takes a node name; all others operate on handles.

The name is evaluated relative to an existing directory handle; the library provides a handle on ”/” that is always valid. Directory handles avoid the difficulties of using a program-wide current directory in a multi-threaded pro- gram that contains many layers of abstraction [18].

The client indicates various options: • how the handle will be used (reading; writing and

locking; changing the ACL); the handle is created only if the client has the appropriate permissions.

• events that should be delivered (see §2.5). • the lock-delay (§2.4). • whether a new file or directory should (or must) be

created. If a file is created, the caller may supply ini- tial contents and initial ACL names. The return value indicates whether the file was in fact created. Close() closes an open handle. Further use of the han-

dle is not permitted. This call never fails. A related call Poison() causes outstanding and subsequent operations on the handle to fail without closing it; this allows a client to cancel Chubby calls made by other threads without fear of deallocating the memory being accessed by them.

The main calls that act on a handle are: GetContentsAndStat() returns both the contents and

meta-data of a file. The contents of a file are read atom- ically and in their entirety. We avoided partial reads and writes to discourage large files. A related call GetStat() returns just the meta-data, while ReadDir() returns the names and meta-data for the children of a directory.

SetContents() writes the contents of a file. Option- ally, the client may provide a content generation number to allow the client to simulate compare-and-swap on a file; the contents are changed only if the generation num- ber is current. The contents of a file are always written atomically and in their entirety. A related call SetACL() performs a similar operation on the ACL names associ- ated with the node.

Delete() deletes the node if it has no children. Acquire(), TryAcquire(), Release() acquire and

release locks. GetSequencer() returns a sequencer (§2.4) that de-

scribes any lock held by this handle. SetSequencer() associates a sequencer with a handle.

Subsequent operations on the handle fail if the sequencer is no longer valid.

CheckSequencer() checks whether a sequencer is valid (see §2.4).

Calls fail if the node has been deleted since the han- dle was created, even if the file has been subsequently recreated. That is, a handle is associated with an instance of a file, rather than with a file name. Chubby may ap- ply access control checks on any call, but always checks Open() calls (see §2.3).

All the calls above take an operation parameter in ad- dition to any others needed by the call itself. The oper- ation parameter holds data and control information that may be associated with any call. In particular, via the operation parameter the client may: • supply a callback to make the call asynchronous, • wait for the completion of such a call, and/or • obtain extended error and diagnostic information.

Clients can use this API to perform primary election as follows: All potential primaries open the lock file and attempt to acquire the lock. One succeeds and becomes the primary, while the others act as replicas. The primary writes its identity into the lock file with SetContents()

so that it can be found by clients and replicas, which read the file with GetContentsAndStat(), perhaps in response to a file-modification event (§2.5). Ideally, the primary obtains a sequencer with GetSequencer(), which it then passes to servers it communicates with; they should confirm with CheckSequencer() that it is still the primary. A lock-delay may be used with services that cannot check sequencers (§2.4).

2.7 Caching

To reduce read traffic, Chubby clients cache file data and node meta-data (including file absence) in a consis- tent, write-through cache held in memory. The cache is maintained by a lease mechanism described below, and kept consistent by invalidations sent by the master, which keeps a list of what each client may be caching. The pro- tocol ensures that clients see either a consistent view of Chubby state, or an error.

When file data or meta-data is to be changed, the mod- ification is blocked while the master sends invalidations for the data to every client that may have cached it; this mechanism sits on top of KeepAlive RPCs, discussed more fully in the next section. On receipt of an invali- dation, a client flushes the invalidated state and acknowl-

OSDI ’06: 7th USENIX Symposium on Operating Systems Design and Implementation USENIX Association340

edges by making its next KeepAlive call. The modi- fication proceeds only after the server knows that each client has invalidated its cache, either because the client acknowledged the invalidation, or because the client al- lowed its cache lease to expire.

Only one round of invalidations is needed because the master treats the node as uncachable while cache inval- idations remain unacknowledged. This approach allows reads always to be processed without delay; this is useful because reads greatly outnumber writes. An alternative would be to block calls that access the node during in- validation; this would make it less likely that over-eager clients will bombard the master with uncached accesses during invalidation, at the cost of occasional delays. If this were a problem, one could imagine adopting a hybrid scheme that switched tactics if overload were detected.

The caching protocol is simple: it invalidates cached data on a change, and never updates it. It would be just as simple to update rather than to invalidate, but update- only protocols can be arbitrarily inefficient; a client that accessed a file might receive updates indefinitely, caus- ing an unbounded number of unnecessary updates.

Despite the overheads of providing strict consistency, we rejected weaker models because we felt that program- mers would find them harder to use. Similarly, mecha- nisms such as virtual synchrony that require clients to exchange sequence numbers in all messages were con- sidered inappropriate in an environment with diverse pre- existing communication protocols.

In addition to caching data and meta-data, Chubby clients cache open handles. Thus, if a client opens a file it has opened previously, only the first Open() call neces- sarily leads to an RPC to the master. This caching is re- stricted in minor ways so that it never affects the seman- tics observed by the client: handles on ephemeral files cannot be held open if the application has closed them; and handles that permit locking can be reused, but can- not be used concurrently by multiple application handles. This last restriction exists because the client may use Close() or Poison() for their side-effect of cancelling outstanding Acquire() calls to the master.

Chubby’s protocol permits clients to cache locks—that is, to hold locks longer than strictly necessary in the hope that they can be used again by the same client. An event informs a lock holder if another client has requested a conflicting lock, allowing the holder to release the lock just when it is needed elsewhere (see §2.5).

2.8 Sessions and KeepAlives

A Chubby session is a relationship between a Chubby cell and a Chubby client; it exists for some interval of time, and is maintained by periodic handshakes called KeepAlives. Unless a Chubby client informs the master

otherwise, the client’s handles, locks, and cached data all remain valid provided its session remains valid. (How- ever, the protocol for session maintenance may require the client to acknowledge a cache invalidation in order to maintain its session; see below.)

A client requests a new session on first contacting the master of a Chubby cell. It ends the session explicitly either when it terminates, or if the session has been idle (with no open handles and no calls for a minute).

Each session has an associated lease—an interval of time extending into the future during which the master guarantees not to terminate the session unilaterally. The end of this interval is called the session lease timeout. The master is free to advance this timeout further into the future, but may not move it backwards in time.

Optimistic Total Order in Wide Area Networks∗

António SOUSA , José PEREIRA, Francisco MOURA, Rui OLIVEIRA

Universidade do Minho, Portugal {als,jop,fsm,rco}@di.uminho.pt

Abstract

Total order multicast greatly simplifies the implementa- tion of fault-tolerant services using the replicated state ma- chine approach. The additional latency of total ordering can be masked by taking advantage of spontaneous order- ing observed in LANs: A tentative delivery allows the ap- plication to proceed in parallel with the ordering protocol. The effectiveness of the technique rests on the optimistic as- sumption that a large share of correctly ordered tentative deliveries offsets the cost of undoing the effect of mistakes.

This paper proposes a simple technique which enables the usage of optimistic delivery also in WANs with much larger transmission delays where the optimistic assumption does not normally hold. Our proposal exploits local clocks and the stability of network delays to reduce the mistakes in the ordering of tentative deliveries. An experimental evalu- ation of a modified sequencer-based protocol is presented, illustrating the usefulness of the approach in fault-tolerant database management.

1. Introduction

Total order multicast greatly simplifies the implementa- tion of fault-tolerant services using the replicated state ma- chine approach [25]. By ensuring that deterministic replicas handle the very same sequence of requests from clients, it is ensured that the state is kept consistent and the interaction with clients is serializable [12]. A particularly interesting application is the database state machine [21] which allows high performance replication of transactional databases.

Implementation of total order multicast is however more costly than other forms of multicast due to the unavoidable additional latency. For instance, in a sequencer based pro- tocol [5, 16] all processes (except the sequencer itself) have to wait for the message to reach the sequencer and for the sequence number to travel back before the message can be delivered.

On the other hand, protocols based on causal history [18, 23, 10] can provide latency proportional to the interarrival delay of each sender and thus lower latency than sequencer based protocols. However, when each sender has a large in-

∗Research supported by FCT, ESCADA proj (POSI/33792/CHS/2000).

terarrival time and low latency is desired, this requires the introduction of additional control messages. This is espe- cially unfortunate in large groups and in wide area networks with limited bandwidth links.

In some protocols, such as those based on consensus [7, 4] or on a sequencer [5, 16], the total order decided is the spontaneous ordering of messages as observed by some pro- cess. In addition, in local area networks (LANs) it can be observed that the spontaneous order of messages is often the same in all processes. The latency of total order pro- tocols can therefore be masked (not reduced) by tentatively delivering messages based on spontaneous ordering, thus allowing the application to proceed the computation in par- allel with the ordering protocol [17]. Later, when the total order is established and if it confirms the optimistic order- ing, the application can immediately use the results of the optimistic computation. If not, it must undo the effects of the computation and restart it using the correct ordering.

The effectiveness of the technique rests on the assumption that a large share of correctly ordered tentative deliveries offsets the cost of undoing the effects of mistakes. This is unfortunate as this makes optimistic delivery useful only in LANs where the latency is much less of a problem than in wide area networks (WANs).

This paper proposes a simple protocol which enables op- timistic total order to be used in WANs with much larger transmission delays where the optimistic assumption does not normally hold. Our proposal exploits local clocks and the stability of network delays to reduce the mistakes in the ordering of tentative deliveries by compensating the vari- ability of transmission delays. This allows protocols which are based on spontaneous ordering to fulfill the optimistic assumption and thus mask the latency.

An experimental evaluation of the technique is presented using a sequencer-based protocol, illustrating the useful- ness of the approach in fault-tolerant database management. When applied to the sequencer based protocol, our tech- nique does not introduce additional messages. The only overhead is that of an additional integer piggybacked on data messages. This compares favorably with both plain sequencer based and causal history based protocols.

The paper is structured as follows. The next section re- calls the problems of total order and optimistic total order multicasts, as well as the reasons preventing spontaneous

1

total order in wide are networks. Section 3 introduces the intuition underlying our proposal and presents a protocol providing optimistic delivery of messages based on a fixed- sequencer total order multicast protocol. In Section 4 we evaluate the performance gains of our approach. In Sec- tion 5 we discuss the paper contribution in general settings as well as applied to a specific application. Section 6 con- cludes the paper.

2. Background

2.1. Totally ordered multicast

Informally, totally ordered multicast (or atomic multicast) ensures that no pair of messages is delivered to distinct des- tination processes in different order. Totally ordered multi- cast greatly simplifies the implementation of fault-tolerant services using the replicated state machine (or active repli- cation) approach [25, 12]: By delivering exactly the same messages in the same order to a set of deterministic repli- cas, their internal state is kept consistent.

More formally, we consider an asynchronous message passing system composed of a finite set of sequential pro- cesses communicating over a fully connected reliable point- to-point network [7]. Processes do not have access to shared memory or to a global clock. A process may only fail by crashing and once a process crashes it does not recover. A process that never crashes is said correct. Totally ordered multicast is defined by primitives to-multicast(m) and to- deliver(m), and satisfies the following properties [14]: Validity. If a correct process to-multicasts a message m,

then it eventually to-delivers m. Agreement. If a correct process to-delivers a message m,

then every correct process eventually to-delivers m. Integrity. For every message m, every process to-delivers

m at most once, and only if m was previously to- multicast.

Total Order. If two correct processes to-deliver two mes- sages m and m′, then they do so in the same order.

Total order multicast has been shown to be equivalent to the generic agreement problem of consensus [7]. Therefore we must assume that in our system the consensus problem is solvable [11, 7], requiring that a majority of processes is correct and that failure detection is of class �S [6]. In some protocols, consensus is explicitly invoked to decide the message sequence [7, 4]. In others, consensus is implicit in a group membership service which supports the actual ordering protocol [5, 15, 10].

There is a plethora of total order protocols for asyn- chronous message passing systems which can be classi- fied according to several criteria [9]. Namely, some or- der the message while disseminating it [3, 2, 15]. Others take advantage of an existing unordered multicast proto- col [5, 16, 7] and work in two stages: First, messages are

p1 • seq(m1) %%

seq(m1) &&

//

p3 • DELIV(m1) //

p2 MCAST(m1)

66

<<

77oooo

• DELIV(m1) //

Figure 1. Sequencer based total order protocol.

disseminated using a reliable multicast protocol Then, an ordering protocol is run to decide which is the correct de- livery sequence of buffered messages. This results in addi- tional latency, when compared to reliable multicast.

An example of a protocol often used in group commu- nication toolkits is the sequencer [5, 16], which uses con- sensus implicitly in the view-synchronous reliable multi- cast protocol used to disseminate messages previously to ordering them. As depicted in Figure 1, a data message is disseminated using unordered reliable multicast. Upon re- ception (depicted as a solid dot), the message is buffered until a sequence number for it is obtained. A single pro- cess (p1 in the example) is designated as the sequencer: it increments a counter and multicasts its value along with the original message’s identification to all receivers as a control message. Data messages are then delivered according to the sequence numbers. A group membership protocol is used to ensure that for any given data message there is exactly one active sequencer.

Besides being a very simple protocol, it offers several ad- vantages, especially in networks with limited bandwidth or in large groups with large and variable message interarrival times: it requires at most a single additional control mes- sage for each data message and any message can always be delivered after two successive message transmission de- lays. The basic protocol is also easily modified to cope with higher message throughput by batching sequence numbers for several messages in a single one [5], reducing the num- ber of control messages at the expense of higher latency.

2.2. Optimistic total order

A reliable multicast protocol can deliver a message af- ter a single transmission delay from the originator to the receiver. This contrasts with the latency of totally ordered multicast1 which is either twice as large, when using a se- quencer based protocol, or proportional to message interar- rival delay in protocols using causal history. However:

• Some protocols, such as the sequencer, produce an or- dering which is the spontaneous ordering observed by some process.

• In local area networks, it can be observed that the spon- taneous ordering of message reception of all processes

1Except in the degenerate situation where a single process is multicas- ting and it can assume the sequencer role.

2

is often very similar, therefore, similar to the final or- dering decided by the sequencer.

Nevertheless, delivery incurs always in the additional la- tency. The optimistic atomic broadcast protocol [22] takes this in consideration to improve average delivery latency of a consensus based total order protocol.

Further latency improvements can be obtained if the ap- plication itself can take advantage of a tentatively ordered delivery. This is called optimistic delivery [17, 26] as it rests on the optimistic assumption that reliable multicast sponta- neously orders messages. It also implies that eventually an authoritative total order is determined, leading to a confir- mation or correction of previously used delivery order. To the interval between the optimistic delivery and the author- itative delivery we call optimistic window. It is during this interval that the application can optimistically do some pro- cessing in advance.

To define optimistic total order multicast we use two different delivery primitives an optimistic opt-deliver(m) that delivers messages in a tentative order and a final fnl- deliver(m) that delivers the messages in their final, or au- thoritative, order. Optimistic total order multicast satisfies the following properties [26]:

Validity. If a correct process to-multicasts a message m, then it eventually fnl-delivers m.

Agreement. If a correct process fnl-delivers a message m, then every correct process eventually fnl-delivers m.

Integrity. For every message m, every process opt- delivers m only if m was previously multicast; and every process fnl-delivers m only once, and only if m was previously multicast.

Local Order. No process opt-delivers a message m after having fnl-delivered m.

Total Order. If two processes fnl-deliver two messages m and m′, then they do so in the same order.

An example of such an application is the database state machine [21] which allows high performance replication of transactional databases and works as follows: transactions are executed optimistically by any of the replicas without locking. The resulting read and write sets are then multicast to all replicas which perform a deterministic certification to ensure that the transaction does not conflict with concur- rent transactions already committed. Total order multicast is used to ensure that the result of the certification process is identical in all replicas, thus ensuring consistency. If the or- der of messages is known in advance by optimistic delivery, this can be used to speed up the certification [17].

Notice that if the optimistic ordering turns out to be wrong, the application has to undo the effect of any pro- cessing it might have done. Therefore, the net advantage of optimistic delivery depends on the balance between the cost of a mistake and the ratio of correctly ordered optimistic de- liveries. In the database state machine, being able to undo

the effects of optimistic delivery just means than the trans- action cannot be effectively committed until authoritative delivery. When the optimistic delivery is wrong, there is a performance penalty: The processing resources used have been wasted.

The tradeoff is thus similar to the one involved in the de- sign of cache memories. However, the protocol designer has no possibility to reduce the cost of a mistake, as this depends solely on the application. The only option is thus to try to maximize the amount of messages which are deliv- ered early but correctly ordered.

2.3. Obstacles to spontaneous total order

A high ratio of spontaneously totally ordered messages which results in good performance of optimistic applica- tions is not trivially achieved, especially in wide area net- works. One reason for this is loopback optimization in the operating system’s network stack. Noticing that the out- going packet is also to be delivered locally, the operating system may use loopback at higher layers of the protocol stack and immediately queue the message for delivery. This allows it to be delivered in advance of packets from other senders which have reached the network first.

Another reason for out of order delivery lies in the net- work itself. Although not frequent, there is a possibility that packets are lost by some but not all destinations. A reliable multicast protocol detects the occurrence and issues a re- transmission. However, the delay introduced opens up the possibility of other packets being successfully transmitted while retransmission is being performed.

An additional issue is the complexity of the network topology. Different packets can be routed by different paths, being therefore subject to different queuing delays or even to being dropped by congested routers. This is especially noteworthy when there are multiple senders. Receivers which are nearer, in terms of hops, to one of them will re- ceive its messages first. Receivers which are nearer of an- other will possibly receive messages in the opposite order.

Notice however that bad spontaneous order in wide area networks is not attributable to large delays themselves, but to the fact that the delays to different destinations are likely to be different, often by two orders of magnitude. Consider Figure 2(a). Messages m1 and m2 are multicast to three different processes, including the senders themselves. The time taken to transmit each message varies with the recipi- ent, for instance, transmission to the sender itself (typically hundreds of microseconds by loopback) takes less time than transmission to other processes (typically up to tens of mil- liseconds over a long distance link). The result is that pro- cess p1 spontaneously orders message m1 first while p2 and p3 deliver m2 first.

Figure 2(b) shows a similar example where message transmission delays are longer but where is it more likely