Distributed lock service

01 · CONTEXT AND REQUIREMENTS

What a distributed lock is for

A distributed lock serves two distinct purposes: efficiency or correctness. In the first, the lock saves unnecessarily repeated work. In the second, it prevents concurrent processes from interfering with each other and corrupting the system's state.

A lock in a distributed system does not behave like a mutex in a multithreaded application: nodes and the network can fail independently, and that is what makes the problem more complicated.

This case uses Chubby, Google's lock service, as a reference. It offers an interface similar to a distributed file system, with advisory locks, and emphasizes availability and reliability, not high performance. It was designed for coarse-grained synchronization and, in particular, for electing a leader among equivalent servers; the Google File System, for example, uses a Chubby lock to designate its master server.

Functional requirements: acquire and release a named lock with mutual exclusion, and release the lock when the client disappears. Non-functional requirements: the service cannot be a single point of failure, and the protected resource must remain safe even when a client acts without knowing it has lost the lock.

02 · THE LEASE PROBLEM

The lock expires, but the client does not know

Every lock needs a deadline: as a lease, it does not stay held forever when the client goes down. The risk is that, if a pause lasts longer than the lease and the client does not notice it has expired, the client makes an unsafe change.

A long garbage-collection pause is just one example. Checking the lock's expiration right before writing does not solve it, because a pause can occur at any point, including between the last check and the write. Packets can also be delayed arbitrarily on Ethernet and IP networks, and a write can reach storage after the lease has already expired.

Chubby describes the same risk in general terms: a process holding lock L issues a request R and fails; another process acquires L and acts before R arrives; if R arrives later, it may be executed without the protection of L and over inconsistent data.

1. Client A asks the lock service for the lock and receives it, with an expiration deadline.

2. Client A is paused, for example by a garbage-collection pause, and does not notice the lease has expired.

3. With the lease expired, client B acquires the lock and acts on the resource.

4. Client A comes back from the pause without noticing the lease expired and still writes: the request may be executed without the lock's protection, over inconsistent data, and the data may end up corrupted.

03 · FENCING

The resource must refuse whoever lost the lock

The fix is to include a fencing token in every write to storage: a number that grows, for example incremented by the lock service each time a client acquires the lock.

1. Client A acquires the lease and receives token 33.

2. Client A enters a long pause and the lease expires.

3. Client B acquires the lease, receives token 34 and sends the write to storage with that token.

4. Client A comes back and sends the write with token 33; storage has already processed a write with a higher token (34) and rejects the request.

This requires the storage server to play an active role: check the tokens and reject writes whose token went backward. With ZooKeeper as the lock service, the zxid or the znode version can serve as a fencing token.

Chubby offers the same mechanism under the name sequencer. The lock holder can request an opaque string that describes the lock's state right after acquisition; it contains the lock name, the acquisition mode and the lock's generation number, which increases when the lock goes from free to held. The server that receives it must test whether it is still valid and, if not, reject the request.

For servers that do not support sequencers, Chubby offers lock-delay, an imperfect but easier mechanism: if the lock becomes free because the holder failed or became unreachable, the lock server prevents other clients from claiming it for a period. The client chooses this period up to a limit, one minute at the time, which keeps a faulty client from leaving the resource unavailable for an arbitrary length of time.

04 · THE SERVICE INSIDE

Replicas, consensus and sessions

Electing a primary among peers is an instance of the problem of distributed consensus. A Chubby cell usually has five replicas, and three must be running for the cell to be up. According to Kleppmann, acquiring a lock is like a compare-and-set operation, which requires consensus.

The replicas use consensus to elect a master, which needs votes from the majority and promises that they will not elect another master during the master lease interval. The replicas keep copies of the database, but only the master initiates reads and writes on it. Writes are propagated to the replicas and acknowledged when they reach the majority; reads are served only by the master, which is safe as long as the master lease has not expired, since no other master can exist.

1. The client queries the replicas listed in DNS to find the master, and the replicas that are not the master reply with its identity.

2. The client directs its requests to the master, which propagates the write, including lock operations, to the replicas and acknowledges it when it reaches the majority.

3. While the client is active, the session is maintained by periodic KeepAlives, and its locks remain valid as long as the session is valid.

4. If the master fails, the replicas run the election when their master leases expire, and a new master is usually elected within a few seconds.

5. When the client's local lease timeout expires, it becomes uncertain about the session, empties its cache and waits out the grace period, 45s by default.

6. The new master picks a new epoch number, which clients must present in every call, and rejects calls with older epochs.

The default lease extension is 12s, and an overloaded master may use larger values to process fewer KeepAlives. The grace period makes it possible to keep sessions alive across failovers that exceed the normal lease timeout.

Leader election with the lock follows a simple script: all candidates open the lock file and try to acquire it; one succeeds and becomes primary, while the others act as replicas, and the primary writes its identity into the file so it can be found. Ideally it also obtains a sequencer and passes it to the servers it communicates with, which must confirm that it is still the primary.

05 · TRADE-OFFS AND PITFALLS

Granularity, availability and correct use

Chubby is intended to offer only coarse-grained locks. According to the paper, it is straightforward for clients to implement their own fine-grained locks; an application can partition its locks into groups and use Chubby's coarse locks to allocate those groups to the application's own lock servers.

When the lock exists only for efficiency and outages are infrequent, occasionally losing a lock is not serious, according to Kleppmann.

Developers also tend to treat the service as if it were always available. They do not notice the difference between a service being up and being available to their applications, and many chose to take their applications down upon receiving the master failover event, greatly reducing the availability of their systems.