Papers
The Chubby lock service for loosely-coupled distributed systems
Mike Burrows · 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2006, 2006
The problem: coarse-grained coordination among equivalent servers and why a lock service
Chubby is an internal Google service designed for loosely coupled distributed systems made up of many small machines connected by a fast network. It offers coarse-grained locking and reliable, but low-volume, storage through an interface similar to a distributed file system with advisory locks. The design emphasizes availability and reliability, not high performance. The typical use case is electing a primary among equivalent servers: GFS uses a Chubby lock to designate its master server, and Bigtable uses it to elect the master, to discover the servers it controls, and as a well-known, available place to store small amounts of metadata. Before Chubby, many systems elected the primary through ad hoc methods or required operator intervention when correctness was essential. The author explains why a Paxos library would not have been enough: developers often start with prototypes without thinking about high availability and only add replication later, and a lock service is easier to fit into existing programs. In addition, programmers are familiar with locks, and with a lock service even a single client can make progress safely, reducing the number of servers the client's system needs to have. The author stresses that the work was engineering, with no new algorithms.
Architecture: cells, replicas, master with lease, and file interface
A Chubby instance, called a cell, typically has five replica servers, placed so as to reduce correlated failures (for example, on different racks). The replicas use a consensus protocol to elect a master, which needs votes from a majority and promises from the others that they will not elect another master for a few seconds, the so-called master lease. This lease is renewed periodically as long as the master keeps winning the vote. Only the master initiates reads and writes on the replicated database; the other replicas just copy the updates. A write is acknowledged when it reaches a majority of replicas, while reads are served by the master alone, which is safe because, as long as the lease has not expired, no other master can exist. Clients locate the master by querying the replicas listed in DNS. If the master fails, the other replicas run the election when its lease expires; the paper cites recent elections of 6 s and 4 s, with values of up to 30 s. Clients see a tree of files and directories with names like /ls/foo/wombat/pouch, where ls stands for lock service. Each file holds uninterpreted bytes, read and written atomically and in full, and nodes can be permanent or ephemeral; the latter are deleted when no client keeps them open.
Advisory locks, sequencers and lock-delay
Every Chubby file or directory can act as a reader-writer lock: either a single handle holds it in exclusive mode, or any number of handles hold it in shared mode. Locks are advisory: they conflict only with other attempts to acquire the same lock, and holding lock F is neither necessary to access file F nor does it prevent others from accessing it. The author rejected mandatory locks for three main reasons: they protect resources implemented by other services, which would require modifying them; they did not want to force applications to be shut down for debugging or administration; and developers already check for errors with assertions of the form "lock X is held". The hard problem is that delayed or out-of-order messages can make a process that has already lost the lock act improperly. Because the solution of sequence numbers throughout the system is expensive, Chubby offers the sequencer: an opaque byte string that describes the state of the lock immediately after acquisition, containing the lock name, mode, and generation number. The client passes it on to servers, which check whether it is still valid. For servers that do not support sequencers there is an imperfect mechanism, the lock-delay: if the lock is released because the holder failed or became unreachable, the server prevents others from claiming it for a period, limited to at most one minute (the value at the time). The limit exists to prevent a faulty client from leaving a lock, and therefore the resource it protects, unavailable for an arbitrarily long time.
Consistent cache, sessions, KeepAlive, and grace period
To reduce read traffic, clients keep a write-through in-memory cache of file data and metadata, kept consistent by invalidations sent by the master. When a piece of data is about to change, the modification is blocked while the master sends invalidations to all the clients that may have it cached; it proceeds only after each one has acknowledged or let its cache lease expire. The protocol invalidates rather than updates, and the author chose this strict consistency because weaker models would be harder for programmers. The relationship between a client and a cell is a session, maintained by periodic handshakes called KeepAlives. The master blocks the KeepAlive call until close to the expiration of the current lease and then answers it by extending the term; the default extension is 12 s. Events and invalidations travel along in the replies. If the client's local lease expires, the session enters jeopardy: the client flushes and disables the cache and waits out a grace period, 45 s by default. If a KeepAlive succeeds within this interval, the client receives the safe event and carries on; otherwise, the session is considered expired. Thus, short master failures do not bring down sessions, and the application sees at most a delay.
See the ideas at work
Practice the designs that use this paper in the System Design school.