The Chubby Lock Service for Loosely-Coupled Distributed Systems

By the mid-2000s, Google's infrastructure consisted of thousands of machines running distributed systems like GFS, Bigtable, and MapReduce. These systems faced common coordination challenges:

Leader Election: GFS needs a single master at any time. What happens when the master crashes? How do we elect a new one without split-brain?

Configuration Management: Bigtable tablet servers need to know the current master's address. How do we distribute this reliably?

Service Discovery: MapReduce workers need to find the job coordinator. How do we maintain an up-to-date registry?

Distributed Locking: Multiple processes need exclusive access to resources. How do we implement locks that survive failures?

The naive solution—each team implements Paxos—had problems:

Key insight: A lock service is a better abstraction than a consensus library for most developers.

1. Fewer servers: Instead of 5 servers per service, one Chubby cell serves an entire datacenter
2. Familiar interface: Developers understand locks and files; few understand Paxos
3. Dual purpose: The same service provides locks AND stores small metadata (master address, configuration)
4. Battle-tested: One well-engineered service is better than many ad-hoc implementations

A Chubby deployment (called a cell) consists of five servers (replicas) that use Paxos to elect a master. Clients communicate only with the master; replicas serve only to provide fault tolerance.

Cell structure:

• Five replicas: Tolerates two failures (majority of 5 = 3)
• One master: Elected via Paxos, holds master lease (few seconds)
• Replicas: Copy writes via Paxos but don't serve reads
• DNS: Cell hostname resolves to all replica IPs

Client connection flow:

1. Client resolves cell DNS to get all replica IPs
2. Client contacts replicas to find current master
3. Non-masters redirect to master (or client discovers via errors)
4. Client establishes session with master
5. All operations go to master for session lifetime

Master election:

1. Replicas run Paxos to agree on master
2. Master obtains master lease (initially few seconds)
3. Replicas promise not to elect new master during lease
4. Master extends lease via Paxos before expiry
5. If master fails, replicas wait for lease to expire, then elect new master

Chubby presents a simple Unix-like file system interface. This design choice was deliberate—file systems are familiar to developers and naturally support both locking (files as locks) and data storage (files as configuration).

Namespace structure:

• Path prefix: `/ls/<cell-name>/` (ls = lock service)
• Remainder is application-defined
• Similar to Unix: directories contain files or other directories

Node types:

| Type | Persistence | Use Case | |------|-------------|----------| | Permanent | Deleted explicitly | Configuration, master address | | Ephemeral | Deleted when session ends | Service registration, presence |

Node metadata (like Unix inodes): - Instance number: Increases each time node is created - Content generation: Increases on each write - Lock generation: Increases when lock is acquired - ACL generation: Increases when ACLs change - Checksum: 64-bit content hash

API operations:

Key constraints: - Files are small (256KB limit, typically <1KB) - No append, move, or link operations - No partial reads/writes—always entire file - Directories contain only files/directories, no data

Every Chubby node (file or directory) can act as a reader-writer lock. Unlike database locks, Chubby locks are advisory—they don't prevent access to the underlying data, only coordinate willing participants.

The distributed lock problem:

Distributed locks have a fundamental issue: message delays can cause incorrect behavior even with perfect locking.

Sequencers: The solution

Chubby provides sequencers—opaque byte-strings that describe the lock state: - Lock name - Lock mode (exclusive/shared) - Lock generation number

Safe locking pattern:

1. Client acquires lock, gets sequencer
2. Client passes sequencer with every request
3. Server validates sequencer with Chubby (or caches recent sequencers)
4. If sequencer is stale (generation mismatch), reject request

Lock-delay: For servers that can't check sequencers, Chubby implements a lock-delay period (default 1 minute). After lock release, Chubby prevents other clients from acquiring the lock, allowing in-flight requests to complete.

A session is the relationship between a Chubby client and a Chubby cell. Sessions have leases—time periods during which the master guarantees not to terminate the session unilaterally. This enables client-side caching.

KeepAlive protocol:

1. Client sends KeepAlive RPC
2. Master blocks the RPC (doesn't respond immediately)
3. Master responds when:
4. - Lease is about to expire (extend it)
5. - Events need delivery (file changed, lock available)
6. - Cache invalidations needed
7. Response contains new lease duration + events + invalidations
8. Client sends next KeepAlive immediately

Why block KeepAlives?

• Reduces RPC traffic: One outstanding RPC per client, not periodic polling
• Piggybacking: Events and invalidations delivered efficiently
• Lease extension only when needed

Jeopardy period:

When a client loses contact with Chubby:

1. Local lease expires: Client enters "jeopardy"
2. Grace period begins: Client disables cache, blocks operations
3. Grace period (default 45s): Client attempts reconnection
4. If reconnected: Session continues, cache re-enabled
5. If grace expires: Session abandoned, all handles invalid

Client failure detection:

• If client fails (crashes), it stops sending KeepAlives
• Master waits for session lease to expire
• Master then releases all locks and deletes ephemeral files
• Other clients can detect this via events

Chubby clients maintain a write-through cache of file data and metadata. This is critical for scalability—without caching, Chubby would be a bottleneck for thousands of clients reading configuration.

Caching rules:

1. Indefinite caching: Clients cache until invalidated (not TTL-based)
2. Write-through: Writes go to master, which invalidates all cachers before completing
3. Strict consistency: After write completes, all clients see new value
4. KeepAlive piggybacking: Invalidations delivered via KeepAlive responses

What's cached:

| Data | Cached? | Notes | |------|---------|-------| | File contents | Yes | Most important for config files | | File metadata | Yes | Avoids stat() calls | | Directory contents | Yes | For namespace traversal | | Lock state | No | Must check master for safety | | Open handles | Yes (locally) | Recreated on failover |

Why strict consistency works here:

• Chubby data changes rarely (configuration, not operational data)
• Read-heavy workload (1000s of readers, occasional writes)
• Write latency (invalidation round-trip) is acceptable for rare writes
• Correctness requires consistency (stale master address = outage)

Caching enables scale:

Without caching, if 10,000 clients read config every second: - 10,000 RPCs/second to Chubby master - Master becomes bottleneck

With caching: - Initial read: 10,000 RPCs (one-time) - Subsequent reads: 0 RPCs (served from cache) - Config changes: ~10,000 invalidations (rare event)

Chubby clients can subscribe to events on files and directories. Events enable reactive programming—clients respond to changes rather than polling.

Event delivery:

1. Client subscribes to events when opening a file (Open flags)
2. Events are delivered via KeepAlive responses
3. Events are delivered after the action (not before)
4. Events guarantee: if you see event, you can observe the change

Common patterns:

Master election with events:

Service discovery with events:

Event ordering guarantees:

• Events delivered in order per file
• Cache invalidation precedes event delivery
• When you receive event, cache already reflects the change

The most common Chubby use case is master election—ensuring exactly one server acts as master for a service. This pattern underpins GFS, Bigtable, and many other Google systems.

Master election steps:

1. Lock acquisition: All candidates try to acquire exclusive lock on master file
2. Winner writes address: Lock holder writes its network address to the file
3. Clients discover master: Clients read file to find master address
4. Failover: If master crashes, session expires, lock released, next candidate wins
5. Client notification: Clients watching file get event, read new address

Why this works:

• Exclusive lock: Only one server can hold it
• Session binding: Lock released on crash (session timeout)
• Atomic transition: Lock changes hands atomically
• Discovery via file: Same file provides both coordination AND discovery

Important detail: The lock file is permanent

The master file is not ephemeral—it persists across master changes. Only the lock is tied to the session. This ensures: - Master address survives master restart - Clients can read address even during transition - New master writes new address (doesn't recreate file)

When the Chubby master fails, a new master must be elected from the replicas. This process is carefully designed to maintain all session guarantees.

Failover procedure:

1. Old master becomes unavailable (crash, network partition, etc.)
2. Master lease expires at replicas (they were not renewing)
3. Paxos election among replicas chooses new master
4. New master reads Paxos log to reconstruct session state
5. Sessions extended to allow clients to reconnect
6. Clients reconnect (their KeepAlives find new master)

Epoch numbers:

Each master has an epoch number (increments on failover). This prevents old masters from affecting the system:

• Client KeepAlives include expected epoch
• If master epoch is higher, client knows failover occurred
• Old master's responses are rejected (wrong epoch)

Handle reconstruction:

After failover, clients may need to rebuild their handles:

1. Client's in-memory handles reference old master
2. Client sends KeepAlive, discovers new master (epoch changed)
3. Client re-opens files/directories
4. New master recreates handles from durable state
5. Ephemeral files may have been deleted if client's session expired

Failover time: Typically a few seconds. Dominated by: - Detecting old master failure (lease timeout) - Paxos election (usually fast) - New master startup (reading log)

The Chubby master stores all data in a local database, replicated via Paxos to ensure durability and consistency across the cell.

Storage layer:

• Database: Originally Berkeley DB, later replaced with more performant alternatives
• Replication: All mutations go through Paxos for consensus
• Write path: Master receives write → Paxos agreement → Apply to local DB → Respond
• Read path: Master reads from local DB (no Paxos needed)

What's stored in Paxos log:

1. File operations: Creates, deletes, writes
2. Lock operations: Acquires, releases
3. Session operations: Creates, destroys, lease extensions
4. ACL changes: Permission modifications

Consistency model:

• All replicas have identical state (consensus)
• Reads served by master are linearizable
• Writes are durable once Paxos commits

Backup and recovery:

• Periodic snapshots of database
• New replicas bootstrap from snapshot + log replay
• Geographic replication (separate cells) for disaster recovery
• Chubby itself doesn't span datacenters—one cell per DC

A single Chubby cell serves an entire datacenter—potentially tens of thousands of clients. Several mechanisms enable this scale without making Chubby a bottleneck.

Scaling mechanism 1: Client caching

Most Chubby data (configuration files) is read-heavy: - Clients cache indefinitely - Only cache invalidations hit the server - Typical ratio: 10,000 reads per write - Master handles writes only

Scaling mechanism 2: KeepAlive coalescing

Each client has exactly one outstanding KeepAlive: - Not periodic polling (wasteful) - Master blocks response until needed - Piggybacks: lease extension, events, invalidations - One RPC serves multiple purposes

Scaling mechanism 3: Proxies

For very large cells, Chubby supports proxy servers: - Trusted proxy runs on each machine (or rack) - Proxy aggregates sessions from local processes - Single session from proxy to Chubby (instead of per-process) - Reduces Chubby connection count by 10-100x

Scaling mechanism 4: Cell structure

Google runs multiple Chubby cells: - One local cell per datacenter (low latency) - One global cell for cross-DC data (higher latency, higher availability) - Most clients use local cell - Rare cross-DC coordination uses global cell

The paper shares several hard-won lessons from operating Chubby at Google scale. These insights influenced the design of systems like ZooKeeper.

Lesson 1: Developers abuse everything

Initially, Chubby had no quotas. Developers: - Stored larger and larger files - Created complex directory hierarchies - Used Chubby as a general-purpose file system

Fix: Added strict quotas and size limits. 256KB max file size.

Lesson 2: Caching is not optional

Early Chubby clients could disable caching: - Some developers disabled it "for safety" - This caused thundering herd on restarts - Server couldn't handle direct load

Fix: Made caching mandatory. Clients MUST cache.

Lesson 3: Fine-grained locks don't work

Teams requested fine-grained (millisecond) locks: - Short locks don't amortize RPC overhead - Can't benefit from caching - Better served by different systems (database locks)

Fix: Documented that Chubby is for coarse-grained locks only.

Lesson 4: Lack of quotas = abuse

Without quotas, one misbehaving client affects everyone: - One client creating thousands of files - One client reading without caching - One client holding locks indefinitely

Fix: Per-application quotas, rate limiting, monitoring.

Lesson 5: Publish usage guidelines

Many problems came from incorrect usage: - Using Chubby for data it wasn't designed for - Not watching files, instead polling - Not using ephemeral files for presence

Fix: Extensive documentation, usage reviews.

Apache ZooKeeper is the open-source spiritual successor to Chubby. While inspired by Chubby, ZooKeeper made different design choices.

API differences:

| Feature | Chubby | ZooKeeper | |---------|--------|------------| | Primary abstraction | Locks + Files | Znodes + Primitives | | Lock support | Built-in Acquire/Release | Build from ephemeral + sequential znodes | | Watches | Event subscriptions | One-time triggers (re-register) | | Sessions | KeepAlive + lease | Heartbeat + timeout |

Consistency differences:

Chubby: All operations (reads AND writes) go to master - Linearizable reads - Higher latency for reads - Master can be bottleneck

ZooKeeper: Writes go to leader, reads can go to any server - Reads may be stale (sequential consistency per client) - Lower read latency - Better read scaling - Use `sync()` for linearizable reads

Lock implementation:

Chubby: Explicit lock API

ZooKeeper: Build locks from primitives

Tradeoffs: - Chubby: Simpler for lock use cases, consistent, but less flexible - ZooKeeper: More flexible primitives, better read performance, more complex lock implementation

Chubby's influence extends far beyond Google. Its concepts appear in virtually every modern distributed system.

Direct descendants:

Apache ZooKeeper (2008): Yahoo's open-source Chubby-inspired system - Powers Kafka, Hadoop, HBase, Storm - Became the de facto coordination service

etcd (2013): CoreOS's simpler alternative - Uses Raft instead of Paxos - Powers Kubernetes - Simpler API, gRPC interface

Consul (2014): HashiCorp's service mesh coordination - Built-in service discovery - Health checking - Multi-datacenter support

Key concepts that spread:

1. Coordination as a service: Central service for consensus, not per-app
2. Sessions with leases: Failure detection via lease expiration
3. Ephemeral nodes: State tied to session lifetime
4. Watches/events: Reactive notification instead of polling
5. Sequencers/fencing tokens: Protecting against delayed messages

Modern usage: - Kubernetes: etcd stores all cluster state - Kafka: Originally ZooKeeper, now internal Raft (KRaft) - Hadoop ecosystem: ZooKeeper for HDFS HA, HBase coordination - Service meshes: Consul for service discovery and configuration

Chubby's paper formalized how to build coordination services. Every modern distributed system either uses one of its descendants or implements similar concepts internally.