Chubby

Distributed programs often need machines to agree on something small but critical: which of three servers is the leader, where a service's configuration lives, whether a particular piece of work is already taken. Each team implementing its own consensus protocol would be slow and error prone, because consensus is hard to get right. Chubby is Google's answer: a centralized lock service that provides a simple, reliable place to agree, so applications call a service instead of building the machinery themselves.

It is designed for coarse-grained locks, held for hours or days, such as "I am the master of this cluster". It is not designed for fine-grained locks held for fractions of a second, which would overwhelm it. This distinction shapes every design choice: with infrequent lock operations, the service can favor reliability and availability over raw throughput.

To clients, Chubby looks like a small file system. Names are paths like /ls/cell/service/master, organized into directories and files. A file can hold a small amount of data, typically configuration or the identity of a leader. Every file and directory can also act as a lock. Applications open a node, obtain a handle, and perform operations such as read, write, and acquire.

Locks are advisory: Chubby does not enforce them on the data they protect. It only reports who holds the lock. Participants must cooperate. This is simpler than mandatory locks and avoids having Chubby understand every resource.

A deployment is called a cell, usually five replicas running on separate machines. The replicas run a consensus protocol, Paxos, to keep identical copies of the data. At any moment one replica is the master, elected by the others and holding a master lease, a promise from the others not to elect a different master for some seconds. The master serves all client requests. The other replicas just keep their copy up to date and are ready to take over.

A write succeeds when a majority of replicas, three out of five, have recorded it, so the cell tolerates the loss of two machines. Reads are answered by the master alone, which is possible because the lease guarantees no other master exists.

Clients link a library that finds the master by asking any replica, then sends all requests to it. If the master changes, the library finds the new one transparently.

A client's relationship with a cell is a session, maintained by periodic KeepAlive messages. Each session has a lease, a period during which the master promises not to end it. The client's KeepAlive request is held by the master, which replies only shortly before the lease would expire, extending it. This reply also carries notifications to the client. The client is always counting down its own copy of the lease.

If the session ends, because the client stops sending KeepAlives, all locks it held are released, and its handles become invalid. This is how a crashed lock holder stops blocking others: no explicit cleanup is needed.

When a master fails, the replicas elect a new one, which takes a few seconds. During that time clients cannot reach a master. A client whose lease is about to expire does not immediately give up. It enters a grace period, often tens of seconds, in a state called jeopardy: it blocks its application calls and keeps trying to contact the new master. If it succeeds in time, the session survives, and the application only noticed a pause. If not, the session expires. This avoids turning a short master failover into a wave of lost locks across thousands of applications.

Many clients read the same files, such as configuration. To avoid overloading the master, clients cache file data and metadata. To keep caches correct, when a file changes the master first sends invalidations to every client that cached it, waits for acknowledgements, and only then completes the write. Reads are served from cache nearly always, which is why a handful of replicas can serve tens of thousands of clients. The price is that a write may be slowed by clients that are slow to acknowledge.

A client can subscribe to events on a node, delivered asynchronously: file contents modified, a child node added, the master changing, a handle becoming invalid, a lock acquired. Instead of polling a file for changes, a service finds out as soon as a new leader is written.

Leader election with Chubby is a few lines.

open("/ls/cell/service/leader", write)
if tryAcquire(lock):
    // I am the leader
    write(file, myAddress)
else:
    // someone else leads: read the address from the file
    leader = read(file)
    subscribe to changes of the file

The first process to acquire the lock becomes leader and publishes its address in the file. Everyone else reads the file to learn who to talk to. If the leader dies, its session expires, the lock is freed, a waiting process acquires it, and others receive an event about the change. The consensus complexity is hidden behind the lock.

Distributed locks have a nasty weakness. Suppose process A holds a lock, sends a request to a storage server, and then stalls or the message is delayed in the network. Meanwhile A's session expires, process B acquires the lock and starts working. Now A's old request finally arrives at the server, and the server cannot tell that A no longer holds the lock, so it processes a stale operation.

Chubby offers two defenses.

• A sequencer: after acquiring a lock, a holder can request a small token that names the lock and includes a generation number, increasing with each acquisition. The holder attaches it to requests. The server checks it with Chubby or against the highest generation it has seen, and rejects requests carrying an older number. This technique is often called fencing.
• A lock delay: if a lock was released because its holder failed, the lock cannot be acquired again for a short period, such as a minute. This gives delayed messages time to drain before a new holder starts.

A single cell serves a large number of clients because lock operations are infrequent and reads are cached. Even so, thousands of clients can overload a cell, so Google uses proxies that aggregate KeepAlives and cache reads, and splits large deployments into multiple cells, using a cell per data center, with a global one for cross-site needs. Clients are discouraged from storing large data or from using Chubby as a high-rate store.

Chubby is used throughout Google's infrastructure. The Google File System uses it to elect its master and to store configuration. Bigtable uses it to elect its master, to discover tablet servers and to store the location of its root data. It also serves as a name service, a consistent replacement for DNS within the data center, and as a place to store small amounts of important configuration. ZooKeeper and etcd are open source systems that follow the same ideas.

• Gains: applications get strong consistency and leader election without writing consensus code, and failures of lock holders resolve themselves through session expiry.
• Costs: it is a central dependency, so its availability is critical. Clients must be written to cope with failover pauses and lost sessions. Advisory locks require discipline.
• Design lesson: the authors chose a lock service over a consensus library because developers already understand locks and files, and because a service is easier to operate and scale than many copies of a tricky protocol embedded in every application.