Weekly Paper Notes — Seminal Paper of the Week for the 2026-07-11 CS paper digest. Area: Distributed Computing / Coordination.

Author: Mike Burrows (Google) Venue: OSDI ‘06 — The Chubby lock service for loosely-coupled distributed systems Canonical link: OSDI ‘06 proceedings · PDF

Why the paper still matters

Twenty years after publication, Chubby is the paper you can point at to explain almost every coordination system in the modern datacenter. ZooKeeper’s API is Chubby’s file-tree-with-watches, made open source. etcd is the same idea shrunk down and rewritten around Raft instead of Paxos. Kubernetes’ leader election, CoreDNS’s config store, the entire lineage of “put your metadata in a strongly-consistent tree and cache aggressively at the client” — Chubby is the paper they all descended from. The paper is also the first honest write-up of what a Paxos deployment actually looks like in production, complete with the compromises, the hacks, and the failure modes nobody talks about in the theory papers.

The reason it has outlasted everything around it is that Burrows made a set of design choices that were unfashionable at the time — coarse-grained locks over fine-grained, a small number of consistent servers over a scalable weak-consistency mesh, an aggressive client-side cache, session-based failure semantics — and every one of those choices turned out to be the right thing to build a datacenter on. Reading the paper now is like reading the founding constitution of coordination-plane engineering.

The setup

Chubby’s job at Google, circa 2006, was to be the coordination substrate underneath GFS and BigTable. Concretely, three things:

  1. Elect masters. GFS had a master; BigTable had a master per cell. Somebody had to run the “who is the current master?” election, and had to do it in a way that survived arbitrary crash patterns.
  2. Publish small pieces of durable, consistent metadata. The identity of the current master, the location of the root tablet, the mapping from cell names to server addresses — the stuff every client needed to bootstrap.
  3. Distribute a name service. DNS was too slow to invalidate; Chubby’s cell-wide invalidation on write was fast enough to serve as the datacenter’s authoritative name-to-address map.

Burrows explicitly designed Chubby not to be a general-purpose lock manager or a scalable data store. Both would have been more theoretically interesting. Neither would have survived contact with the traffic pattern that actually mattered: thousands of clients, each poking Chubby to learn which server to talk to and whether it’s still alive, and each expecting the answer to change on the order of seconds to hours.

The N invariants

Chubby’s design is best understood as a small set of hard invariants that hold together under load. Six of them are worth naming.

1. A cell is five servers running Paxos, not one. A Chubby cell has five replicas. One is the master; the others are followers. A Paxos state machine on top of a local log turns the five machines into a single logically-consistent database. All writes go through the master, are Paxos-committed to a majority, then applied. All reads are served by the master from local state after checking it holds a valid master lease — a time-bounded promise from the other replicas that they will not elect a new master before the lease expires. Master leases turn reads into local operations without any consensus traffic, which is how Chubby survives the fact that its clients read constantly and write rarely.

2. Small files, arranged as a filesystem. Chubby exposes its data as a Unix-like tree: /ls/<cell>/<path>. Each node is either a directory or a small file (kilobytes, not megabytes). Files are the unit of both storage and locking. This choice does two important things at once: it makes the API instantly legible to any programmer, and it makes the locking granularity a design choice at the file level rather than something Chubby has to invent a new abstraction for.

3. Coarse-grained locks, not fine-grained. Chubby locks are held for hours-to-days, not milliseconds. The typical use is “hold the /ls/celery/master lock while you are the master of the celery service.” This is the opposite of a database lock manager. It buys two enormous simplifications: the lock server doesn’t have to handle high-throughput lock traffic, and lock acquisitions can go through the consensus layer without breaking latency budgets. Burrows is emphatic about this in the paper — the coarse-grained choice is what makes Chubby’s whole architecture feasible.

4. Sessions with keep-alives, not connections. A client holds a session with the Chubby cell, refreshed by periodic keep-alives. Sessions time out on a bounded grace period during failover. Every lock, every open file handle, every subscription is scoped to a session. If your session dies, everything you were holding is released. This turns a hard failure-detection problem (is the client alive?) into a simple lease timer, and makes the semantics of failover clean: a new master inherits sessions, extends grace periods, and lets clients reconnect within a bounded window.

5. Events, not polling. Every open handle can subscribe to events on that node — file contents changed, node deleted, lock acquired, master failover. Clients get pushed notifications and update their caches locally. This is the mechanism that lets Chubby be simultaneously strongly consistent on the server and fast to read on the client: the client cache is only ever stale between an invalidation event being sent and being processed, which is milliseconds.

6. The client library does half the work. Chubby’s client library is not a thin RPC wrapper. It maintains the session, the local cache, the event queue, the lock state, the master’s identity, and the reconnection logic on failover. Burrows notes that this is a large amount of code, and that most of Chubby’s bugs live in the library rather than the server. The design choice — push complexity into the client library, keep the server simple and strongly-consistent — is one of the paper’s most durable lessons, and it is exactly the choice ZooKeeper and etcd would later re-make.

The algorithm walk-through

A typical Chubby interaction goes like this. A GFS chunkserver comes up. It opens a Chubby session against its local cell and creates a file at /ls/gfs/chunkservers/<hostname> with its current listen address. It acquires the shared lock on /ls/gfs/chunkservers/directory, which serves as a liveness marker. It subscribes to events on /ls/gfs/master to learn who the current GFS master is.

Meanwhile a GFS master candidate tries to acquire the exclusive lock on /ls/gfs/master. Paxos-committed, so exactly one candidate wins. The winner writes its address to the file. Every subscribing client immediately gets the invalidation event, refreshes the file, and now knows the new master’s address. When the master dies — its session times out — the lock is released, another candidate acquires it, another event fires, and the cluster has re-converged.

At no point in this story does any client talk to another client. All coordination goes through the tree. All notifications come out of the tree. The tree is small — a few thousand files per cell, kilobytes each — and served by five machines. That’s the whole design, and it was enough to run every coordination-hungry service Google had built by 2006.

Why this design has outlasted everything around it

Three reasons.

Coordination is a small workload, and you shouldn’t build it like a big one. The temptation in 2006 was to build a distributed lock manager as if it were a distributed database — sharded, scaled out, eventually consistent, replicated everywhere. Burrows made the opposite call: a small number of consistent servers, aggressive client caching, coarse-grained operations, and a workload that never grows past what five machines can handle. Twenty years of ZooKeeper and etcd deployments have validated this. Nobody has ever wanted a lock service that scales to a million writes per second; everybody wants one that works when the network partitions.

Sessions are the right unit of failure semantics. Almost every distributed system since Chubby has adopted some flavour of the session/lease model: bounded lifetime, keep-alive refresh, grace period on failover, all-or-nothing semantics on session death. Getting this right is what separates a coordination system you can build reliable services on from one where clients slowly leak locks and directories fill up with tombstones.

The API-as-filesystem was a rare good idea. The alternative — invent a new API for locks, another for config, another for name resolution — never dies but never wins. Every service in Google that touched Chubby learned exactly one API, and the same client library served all of them. ZooKeeper copied the tree, etcd copied it more loosely, Consul copied it again. The tree is a durable interface because programmers already know how to reason about it.

Read alongside

  • Lamport, The Part-Time Parliament (1998) and Paxos Made Simple (2001) — Chubby is a Paxos deployment paper as much as it is a lock service paper.
  • Hunt, Konar, Junqueira, Reed, ZooKeeper: Wait-free coordination for Internet-scale systems (USENIX ATC ‘10) — Chubby with the file API preserved and the semantics loosened for open-source consumption.
  • Ongaro, Ousterhout, In Search of an Understandable Consensus Algorithm (Raft, USENIX ATC ‘14) — the consensus protocol that displaced Paxos in the coordination-service niche, and the substrate under etcd.
  • Corbett et al., Spanner: Google’s Globally-Distributed Database (OSDI ‘12) — the paper that extended the “small number of consistent servers underneath everything” pattern from coordination to full-blown storage.
  • Chandra, Griesemer, Redstone, Paxos Made Live (PODC ‘07) — Google’s companion paper to Chubby, on what implementing Paxos actually took.

📄 Chubby paper (OSDI ‘06 PDF) · 📚 USENIX proceedings entry

Part of the Weekly CS Paper Digest series. Seminal picks are foundational papers of any era relevant to the week’s areas; the pool is rotated so it isn’t always AI/ML.