The Chubby lock service (Burrows, OSDI 2006)

Mike Burrows, Google, OSDI 2006, 16 pages. A coarse-grained lock service and small-file store for loosely-coupled distributed systems, built on Paxos and used to elect the GFS master and several of Bigtable’s.

This is the implementation account consensus has been asking for. That page ended with “the theory is here and the implementations are not.” Chubby is the theory in production, with a decade-old but concrete set of numbers attached, and the paper is unusually willing to describe what it got wrong.

The design in one paragraph

A Chubby cell is typically five replicas, placed to avoid correlated failure. They elect a master by consensus; the master must win a majority plus promises not to elect a different master for a few seconds — the master lease. Only the master reads and writes the database; replicas copy its updates through the consensus protocol. Writes are acknowledged once a majority has them. Reads are served by the master alone, which is safe precisely because the lease guarantees no other master can exist. Clients find the master via DNS and then talk only to it. A failed master means waiting out the leases: a new one is typically elected in a few seconds, and two recent elections took 6s.

The lease converts the quorum requirement into a time requirement for reads, which is how a consensus-backed system serves reads at one machine’s speed without giving up linearizability.

Why a lock service and not a Paxos library

The paper opens by arguing against the obvious alternative, and Google had built the alternative: “Indeed, we provide such a client library that is independent of Chubby.” They shipped the service anyway. Four reasons, and they are about organisations as much as systems.

Availability gets added late. Services begin as prototypes and acquire replication and primary election after they have clients. Restructuring an existing program as a replicated state machine is a rewrite; using a lock is not. The paper quantifies it: electing a master that then writes to an existing file server takes “just two statements and one RPC parameter” — acquire a lock, pass the lock acquisition count with the write, and have the file server reject writes carrying a lower count. That last clause is a fencing token, and it is the whole defence against a delayed packet from a deposed master.

Elected primaries need to advertise themselves, so the service must store small amounts of data, which is why a lock service acquired a file interface.

And the quorum argument, which is the deepest one. A consensus library needs a majority of the application’s own servers to be up before that application can make progress. With a lock service, “even a single client can obtain a lock and make progress safely.” The quorum has not gone anywhere — it has been relocated into a service that specialises in maintaining one, and rented out. That is the same move part-time-parliament makes at the algorithm level, made once at Google scale so that nobody else has to make it.

The surprise: it became a name service

“Even though Chubby was designed as a lock service, we found that its most popular use was as a name server.”

60% of open files are naming-related. The cause is caching semantics rather than features. DNS discards entries on a TTL, and picking that TTL trades replacement latency against server load — with 3,000 processes talking to each other at a 60s TTL, “to maintain the DNS caches of a single job… would require 150 thousand lookups per second,” against a contemporary DNS server handling about 50 thousand. DNS load variability “had been a serious problem for Google before Chubby was introduced.”

Chubby instead uses explicit invalidation, so a constant rate of session KeepAlives holds an arbitrary number of cache entries indefinitely while nothing changes. One 2-CPU master served 90,000 directly-connected clients.

The lesson generalises past this system: a consistent cache with invalidation beats a time-based cache whenever the cost of a stale entry and the cost of polling are both high. And the paper is honest that the fit is imperfect — name resolution needs timely notification rather than full consistency, so Chubby is stronger than the job requires, and a 3,000-process job start once generated 9 million requests and “could bring the Chubby master to its knees” until lookups were batched ~100 at a time.

The operational numbers

From a snapshot of a typical cell. Almost nothing else in this corpus is measured, so these are recorded in full:

22k direct clients + 32k proxied, 12k open files, 230k cached-file entries over 24k distinct files — about 10 clients per cached file.
90% of stored files are under 1 KB, 0.2% over 10 KB. This is configuration and metadata, not storage.
RPC traffic is 93% KeepAlive. GetStat 2%, Open 1%, SetContents 680 ppm, Acquire 31 ppm. A lock service whose lock acquisitions are three-hundredths of a percent of its traffic.
Few clients hold locks and shared locks are zero, consistent with locking being used for primary election rather than mutual exclusion.
61 outages over 700 cell-days. Most under 15s, 52 under 30s; the paper notes most applications are unaffected below 30s. The remaining nine: network maintenance (4), suspected connectivity (2), software errors (2), overload (1).
Six data losses in a few dozen cell-years — four database software errors, two operator errors, none from hardware. And: “Ironically, the operational errors involved upgrades to avoid the software errors.”
Mean request latency is a small fraction of a millisecond until overload, which arrives around >90,000 active sessions.

That last pair is the most transferable finding here. In a system engineered specifically for reliability, every data loss came from software or the people operating it, and half the operator errors came from trying to fix the software. Hardware, the thing replication is nominally for, caused none.

Provenance

T1 — a peer-reviewed OSDI paper, read locally from the PDF. It is nonetheless a first-party account: Google describing its own system, with no comparison against an alternative and no external replication. The numbers are a 2006 snapshot of one company’s infrastructure and should be read as shape, not as current fact. The arriving link carried a Facebook fbclid parameter, stripped here.

paxos (the algorithm underneath) · part-time-parliament (its original paper, and the library Chubby argues against) · paxos-made-simple · consensus (the implementation half of its standing gap) · byzantine-generals-problem (the failure model Chubby, like Paxos, declines to defend against) · consistency-models · leslie-lamport · operational-databases

Cross-spoke. The operational half — outage budgets, what actually causes data loss, overload behaviour — is ../platform-ops-wiki’s subject; this page holds the architecture and cites the numbers, and that spoke should take up the 61-outages and six-data-losses figures if it builds a body on failure causes. Mike Burrows is named once here and deferred as an entity, as SRI International and Digital Equipment Corporation were.