Unboxing Chubby

What you'll learn

• Why Google Built It: The Origin Story

  In the early 2000s, Google was building systems like GFS and BigTable—distributed systems with dozens to thousands of servers, where any machine could fail at any moment. These systems needed a way to agree on critical decisions: - Which…

• The Problems Chubby Solves

  Leader Election GFS has multiple master replicas. One must be the "real" master at any time. All replicas compete to acquire a Chubby lock on a well-known file (e.g., /ls/cell/gfs/master). Whoever holds the lock is the master. When the m…

• Chubby's Design Philosophy

  Coarse-grained locks, not fine-grained. Chubby locks are held for hours or days (e.g., "I'm the master until I crash"), not milliseconds (e.g., "lock this row while I update it"). This reduces load on the Chubby servers—lock acquisition…

• What Chubby Is (and Isn't)

  Chubby is: - A lock service (advisory locks on files) - A small-file storage system (files up to 256KB) - A naming/discovery service (write addresses to files, read them back) - A notification service (get events when files change or loc…

• Core Abstractions: Cells, Replicas, Files, Locks

• Chubby Cell

  A Chubby cell is a cluster—typically 5 servers (called replicas)—that acts as a single logical lock service. Most cells are confined to a single datacenter (low latency). A few "global" cells span multiple datacenters (higher latency, bu…

• Replicas and the Master

  A Chubby cell has 5 replicas (default). One replica is the master, elected via Paxos. The master: - Handles all client requests (reads, writes, lock acquisitions) - Maintains an in-memory database of files, directories, locks, and sessio…

• Files, Directories, and Nodes

  Chubby's namespace is a tree of nodes. Each node is either: - A directory (contains child nodes) - A file (contains data, up to 256KB) Nodes are like Unix inodes, but simpler. No hard links, no symlinks, no device files. Node types: | Ty…

• Metadata: ACLs, Version Numbers, Checksums

  Each node stores metadata: Access Control Lists (ACLs): Chubby uses ACLs for read/write/change-ACL permissions. ACLs are stored as Chubby files in a special /ls/cell/acl/ directory. Nodes inherit their parent directory's ACL on creation.…

• Handles

  Clients open nodes to get handles (like Unix file descriptors). A handle includes: - Check digits (prevent clients from guessing or forging handles) - Sequence number (lets a new master know if the handle was generated by the previous ma…

• Paxos: The Engine Under the Hood

  Chubby uses Paxos for fault-tolerant consensus. Paxos solves the problem: "How do replicas agree on the order of operations, even if some replicas fail or messages are lost?"

• Paxos in 60 Seconds

  Paxos guarantees that a majority of replicas (e.g., 3 out of 5) agree on a sequence of log entries. Once a log entry is committed, it's durable—it will never be lost, even if the master crashes. Paxos has two phases: 1. Prepare/Promise:…

• Master Lease

  The master holds a lease—a time-bound promise from a majority of replicas that they won't vote for another master. The lease typically lasts 10-12 seconds and is renewed via heartbeat messages. While the lease is valid, the master can se…

• Linearizable Reads

  Chubby guarantees linearizable reads: after a write completes, all subsequent reads see the new data. How? - All reads go to the master (replicas don't serve reads). - The master's in-memory state is always up-to-date (it applies log ent…

• The File System Interface: POSIX-like, but Simpler

  Chubby's API resembles Unix filesystem calls, but much simpler.

• Path Format

  Example: Breaking it down: - /ls = lock service (constant prefix) - us = cell name (DNS lookup resolves to replica IPs) - gfs/master = path within the cell's namespace

• Node Operations

  General: - Open(path, mode) → handle Opens a file or directory. Mode can include read, write, lock (exclusive or shared). - Close(handle) Closes the handle. If this is an ephemeral file and no other client has it open, the file is delete…

• What's Missing (Compared to POSIX)

  Chubby doesn't support: - append, seek, pread, pwrite (files are read/written in full) - rename, mv (can't move files between directories) - Hard links or symbolic links - Sparse files, memory-mapped files, extended attributes Why so res…

• Locks: Advisory, Coarse-Grained, and Sequenced

  Every Chubby node can act as a reader/writer lock: | Mode | Who Can Hold It | Use Case | |------|-----------------|----------| | Exclusive | One client at a time | Leader election, single writer | | Shared | Multiple clients simultaneous…

• Lock Acquisition Flow

• Sequencers: Fencing Tokens for Stale Masters

  Distributed systems have a classic problem: stale primary. Imagine: 1. Client A is the GFS master. It holds the Chubby lock /ls/cell/gfs/master. 2. Client A experiences a network partition. It thinks it's still master, but Chubby has dec…

• Lock-Delay: Grace Period for Stale Lock Holders

  Some systems don't support sequencers. To protect them, Chubby has lock-delay. When a lock becomes free (because the holder's session expired), Chubby prevents other clients from claiming the lock for a configurable period (default: 1 mi…

• Sessions and KeepAlive: How Clients Stay Connected

  A session is a long-lived relationship between a client and a Chubby cell. As long as the session is valid: - The client's handles remain valid - The client's locks are held - The client's cached data is consistent If the session expires…

• Session Protocol

  When a client first connects: 1. Client calls any replica (via RPC). 2. Replica replies: "I'm not the master. The master is at IP X." 3. Client connects to the master. 4. Master creates a session and assigns a session lease (default: 12…

• KeepAlive: Heartbeats to Extend the Lease

  To keep the session alive, the client sends KeepAlive RPCs: 1. Client sends KeepAlive to the master. 2. Master blocks the RPC (doesn't reply immediately). 3. When the lease is about to expire, the master replies: "Your new lease expires…

• Jeopardy and Grace Period

  If a client's local lease expires (e.g., the master stopped responding to KeepAlives), the client doesn't immediately give up. It enters jeopardy: - The client flushes its cache (cached data might be stale). - The client disables cache (…

• Chubby Events: Asynchronous Notifications

  Clients can subscribe to events when opening a handle. Chubby delivers events via callbacks in the client library. Examples: | Event | Triggered When | Use Case | |-------|----------------|----------| | File contents modified | SetConten…

• Example: GFS Master Using Events

  The GFS master: 1. Opens /ls/cell/gfs/master with exclusive lock + events: lockacquired, handleinvalid. 2. Tries to acquire the lock. 3. Event lockacquired: Master starts serving client requests. 4. If the master's session expires → even…

• Client-Side Caching: Consistent, Invalidation-Based

  Chubby clients cache aggressively: - File contents - File metadata (ACLs, version numbers) - Directory contents - Handles (if you open the same file twice, the second Open is served from cache) The cache is write-through: writes go to th…

• Cache Invalidation Protocol

  When a client writes to a file: 1. Client sends SetContents(file, data) to the master. 2. Master blocks the write and sends invalidation messages to all clients that have cached the file. 3. Invalidations are piggybacked on KeepAlive rep…

• Caching Locks

  Clients can cache locks. If a client releases a lock but might need it again soon, it holds the lock longer (e.g., a few seconds). If no other client requests the lock, the original client avoids re-acquiring. If another client wants the…

• Caching Handles

  Clients cache open handles. If you call Open("/ls/us/config") twice, the second call is served from the cache (no RPC to the master). Handles are invalidated when the session expires or the file is deleted. ---

• Scaling Chubby: Proxies and Aggressive Caching

  Chubby was designed for "not too many clients"—thousands, not millions. But Google's usage grew. At peak, a single Chubby cell served 90,000+ clients. How did it scale?

• Reducing Client Request Rate

  Nearby cells: Deploy more Chubby cells (one per datacenter or region). Clients use /ls/local/ to connect to the nearest cell. This spreads load and reduces cross-datacenter traffic. Larger lease times: Increase the lease duration from 12…

• Proxies: Read Amplification

  A Chubby proxy is a server that acts as an intermediary: What proxies do: - Handle KeepAlives: If a proxy serves N clients, KeepAlive traffic to the master is reduced by a factor of N (the proxy sends one KeepAlive for all its clients).…

• Partitioning

  Chubby's namespace can be partitioned: - /ls/cell/foo/ is served by one Chubby cell - /ls/cell/bar/ is served by another cell This reduces read/write traffic per cell. But it doesn't help with: - KeepAlive traffic (clients still maintain…

• Storage Backend: A Simple Custom Database

  Chubby doesn't use a general-purpose database (like MySQL or Berkeley DB). It uses a custom key-value store with: Write-ahead logging: All mutations (create, delete, write) are logged before being applied. The log is replicated via Paxos…

• Backup and Recovery

  Backup: The master writes snapshots to GFS every few hours. After a snapshot, the previous transaction log is deleted. At any time, the system state = last snapshot + transaction log since the snapshot. Recovery: If a replica's disk fail…

• Mirroring: Global Configuration Distribution

  Chubby supports mirroring: automatically copying a directory tree from one cell to another. Use case: Google has dozens of datacenters worldwide. A configuration change (e.g., a new ACL) needs to propagate everywhere. Instead of updating…

• Master Failover: How a New Master Takes Over

  When the master crashes or loses its lease:

• Step 1: Election

  Replicas run a Paxos round to elect a new master. The winner is the replica with the most up-to-date log (or, if tied, a deterministic tiebreaker like lowest IP address).

• Step 2: Pick Epoch Number

  The new master assigns itself a new epoch number (incremented from the previous master's epoch). Clients must present the current epoch in all RPCs. The new master rejects RPCs with old epoch numbers. This prevents stale messages from re…

• Step 3: Rebuild In-Memory State

  The new master: - Loads the latest snapshot from disk. - Replays the transaction log since the snapshot. - Rebuilds the in-memory database (files, directories, locks, sessions). - Extends all session leases to the maximum the old master…

• Step 4: Respond to Master-Location Requests

  The new master starts responding to "who is the master?" queries. Clients learn the new master's address.

• Step 5: Allow KeepAlives (But Nothing Else)

  Clients can send KeepAlives to refresh their sessions, but no other operations (no reads, no writes, no lock acquisitions). The master needs to ensure all clients are aware of the failover before proceeding.

• Step 6: Emit Failover Event

  The master sends a failover event to every active session. Clients: - Flush their caches (they might have missed invalidations during the failover). - Acknowledge the failover event (in the next KeepAlive).

• Step 7: Wait for Acknowledgments

  The master waits until each session acknowledges the failover event OR the session's lease expires (in which case the session is terminated).

• Step 8: Resume Normal Operation

  Once all active sessions have acknowledged, the master serves all operations (reads, writes, locks, etc.).

• Step 9: Honor Old Handles

  If a client presents a handle created before the failover, the master reconstructs the handle's state (from the replicated log) and honors the call. This means clients don't need to re-open files after failover.

• Step 10: Garbage-Collect Ephemeral Files

  After ~1 minute, the master deletes ephemeral files that have no open handles. Clients are expected to re-open ephemeral files during this window. Failover time: Typically 5-10 seconds. During this time, reads can go to shadow masters (r…

• Usage Stats: How Google Uses Chubby

  From the Chubby paper (circa 2006): Deployment: - Dozens of Chubby cells deployed across Google's datacenters. - Typical cell: 5 replicas, serving thousands of clients. - Largest cell: 90,000+ clients. Request breakdown (by volume): - Ke…

• Further Reading

  If you want to dive deeper: - Original Chubby paper (Burrows, 2006): "The Chubby lock service for loosely-coupled distributed systems." 14 pages, very readable. - ZooKeeper paper (Hunt et al., 2010): "ZooKeeper: Wait-free coordination fo…

• Final Thoughts

  Chubby is 20 years old (as of 2024), but its lessons are timeless. It teaches you: - Build services for your actual workload. Chubby is perfect for coarse-grained locks and small files. It would be terrible as a database or filesystem. -…