Distributed lock simulator

Client A takes the lock first and client B waits for it. Both want to write to the storage service. The timeline shows when each client holds a valid lease, when A is paused, and when A still believes it holds the lock after the lease has expired; arrows to the storage lane are writes, and the log lists every step.

• Start with A pauses and fencing off. A stops for longer than its lease, B takes the lock and writes, then A wakes up and overwrites B's data.
• Turn fencing on. The storage now rejects A's write because its token is lower than B's.
• Pick a pause shorter than the lease. A wakes up in time, and nothing goes wrong with or without fencing.
• Choose Redlock. Fencing is unavailable, because its lock value is random. Then try Clock jump, where one Redis node's clock runs ahead and two clients get a majority at once.

A distributed lock is a mutual exclusion lock shared by processes on different machines: before acting on a shared resource, such as a file, a database row or an external API, a process asks a lock service for the lock, and only one process is supposed to hold it at a time. Unlike a mutex inside one program, the holder can crash, be cut off by the network or stop for seconds, and the lock service cannot tell which.

That is why distributed locks are almost always leases, and why a lease on its own does not guarantee that only one process acts at a time.

A lease is a lock that expires after a fixed time unless its holder renews it. If the holder crashes, the lock frees itself and others can make progress. Cary Gray and David Cheriton introduced leases in 1989 for keeping file caches consistent. In etcd a lock is a key attached to a lease that the client keeps alive; in ZooKeeper it is an ephemeral znode that disappears when the client's session times out; in Redis it is a key set with SET key value NX PX ttl.

The catch is that expiry is measured by the lock service's clock, while the holder decides whether it still holds the lock by its own. The etcd documentation is blunt about it: the lease mechanism by itself does not guarantee mutual exclusion, because the server can revoke a lease while the client still believes it owns it.

Martin Kleppmann's 2016 essay "How to do distributed locking" gives the standard example. Client 1 takes the lock and then stops, perhaps for a long garbage-collection pause. Its lease expires; client 2 takes the lock and writes. Client 1 resumes, still believing it holds the lock, and writes too, overwriting client 2's work. Other causes have the same effect: the process is swapped out, the virtual machine is suspended, or the write request sits in a network queue until after the lease has expired.

Checking the lease just before writing does not fix it, because the pause can come between the check and the write. Here, with a 5 s lease and an 8 s pause, etcd without fencing ends with "from A" in storage, the stale write. With a 3 s pause the lease is still valid when A wakes, and nothing goes wrong ("from B" is last, as it should be).

The table runs every service and scenario with a 5 s lease, an 8 s pause or delay, and the storage checking tokens wherever the service provides them:

The fix Kleppmann describes moves the check to the resource. Each time the lock service grants the lock it hands out a number that only ever increases, a fencing token. The client sends the token with every write, and the storage remembers the highest token it has accepted and rejects anything lower. In the simulation, A gets token 33, B gets 34 after A's lease expires, and when A's write with 33 finally arrives the storage has already seen 34 and refuses it.

The token has to come from something with a single ordered history:

• etcd gives every change a revision number from one counter. The etcd documentation describes the revision of the lock key as the fencing token, and conditional transactions on revisions as the way etcd enforces exclusion for its own keys.
• ZooKeeper's lock recipe creates an ephemeral sequential znode under the lock node; the client whose node has the lowest sequence number holds the lock. The znode's creation zxid, or its sequence number, works as a token.
• Chubby, Google's lock service, has sequencers: a byte string describing the lock and its generation number, which servers can check before acting.

Fencing needs the resource's cooperation: a storage system that can compare tokens atomically with the write. Where it cannot, a conditional write (compare-and-set on a version) gives a similar guarantee without a lock at all.

A lock on a single Redis server is lost if that server fails. Redlock, described in the Redis documentation, uses N independent Redis masters (five in the example): the client sets the same key with the same random value on each, and holds the lock if it succeeded on a majority within less than the lock's validity time. The remaining validity is the TTL minus the time spent acquiring.

Kleppmann argued that this is unsafe for correctness for two reasons. It has no fencing token, since the value is random and the independent nodes share no counter. And its safety depends on timing: if one node's clock jumps forward, it can expire a key early, and a second client can then win a majority that includes that node while the first still holds the others. The simulator's Clock jump scenario plays this out.

Salvatore Sanfilippo, Redis's author, replied in "Is Redlock safe?": clock jumps can be avoided by not setting clocks by hand and by having NTP slew the clock gradually rather than step it; the random value can be used with check-and-set on the resource; and the client checks the elapsed time after acquiring the lock. He agreed that a pause after that check leaves the same problem every lease-based lock has. The Redis documentation now links both essays, recommends fencing tokens, and notes that Redis does not use a monotonic clock for key expiry, so a wall-clock change can let more than one process acquire the lock.

Kleppmann's main advice is to ask what the lock is for.

• Efficiency: the lock stops two workers doing the same job, such as sending the same email or recomputing the same report. An occasional duplicate costs a little. A single Redis instance with a TTL is simple and adequate.
• Correctness: two holders at once would corrupt data or break an invariant. Use a lock from a consensus system such as etcd or ZooKeeper, and have the resource check fencing tokens, or design the write to be conditional or idempotent so that a stale holder can do no harm.

Gray and Cheriton described leases in 1989. Mike Burrows's paper on Chubby, Google's lock service built on Paxos, appeared at OSDI in 2006 and introduced sequencers. ZooKeeper, from Yahoo, was presented at USENIX ATC in 2010 by Patrick Hunt, Mahadev Konar, Flavio Junqueira and Benjamin Reed, with locks as a recipe built from its primitives rather than a built-in operation. CoreOS released etcd, based on Raft, in 2013. In February 2016 Kleppmann published his critique of Redlock and Sanfilippo his reply, and Flavio Junqueira followed with a note on how fencing applies to ZooKeeper.