Distributed Locks, Leases and Fencing Tokens
On this page
Learning Objective
Explain why a lease-based distributed lock cannot by itself guarantee mutual exclusion, describe the fencing-token pattern that closes the gap, and distinguish locks used for efficiency from locks used for correctness so the right guarantee is chosen deliberately.
Concept Explanation
A distributed lock built on a coordination service looks straightforward: a client creates a lease-bound key, does its work, and releases the key, while the service guarantees only one client can hold the key at a time. That guarantee is genuinely provided and it is genuinely not enough, because it is a statement about what the service believes rather than about what clients do. The gap is created by the same ambiguity that motivates everything else in this course: a client can stop executing without stopping existing. A stop-the-world garbage collection pause, a hypervisor descheduling the VM, a page fault storm, a network partition, or simply a process suspended by the operating system all produce a client that is alive, will resume, and has no idea that time has passed.
Trace what that does to a lock. Client A acquires the lock with a thirty-second lease and begins writing to shared storage. Forty seconds into a stop-the-world pause, A's lease has expired and the coordination service, entirely correctly, has granted the lock to client B, which begins writing. A then resumes, having observed nothing, still holding a lock object in memory that it believes is valid, and completes its write. Two clients have now written to the protected resource concurrently, and the coordination service did nothing wrong at any point. Making the lease longer does not fix this, it only makes the window rarer and failover slower, which is the worst of both trades. The problem is structural: the client learns about expiry only when it next communicates, and by then the damage is done.
The fix, popularised by Martin Kleppmann's 2016 analysis of distributed locking, is the fencing token. The lock service issues a monotonically increasing token with each grant - token 33 to A, token 34 to B - and every write to the protected resource carries its token. The resource remembers the highest token it has accepted and rejects any write carrying a lower one. Now when A resumes and writes with token 33, the storage layer has already accepted token 34 from B and refuses it outright. The essential and frequently missed requirement is that the protected resource must participate: fencing is not something the lock service can enforce alone, because it has no visibility into what clients do while holding the lock. Both major coordination services provide a suitable token for free, since ZooKeeper's znode creation zxid and etcd's revision are both monotonically increasing and globally ordered.
This leads to the single most useful classification when someone proposes a distributed lock: is it for efficiency or for correctness? An efficiency lock exists to avoid duplicated work - preventing two workers from regenerating the same cache entry or sending the same report twice - and if it occasionally fails, the cost is wasted CPU or a duplicate email. A correctness lock exists to prevent data corruption or a double financial transaction, and if it fails the cost is unbounded. Efficiency locks can be built on almost anything, including a single Redis instance, and the occasional failure is an acceptable operating cost. Correctness locks require a consensus-backed service and fencing tokens end to end, and if the protected resource cannot check tokens, then a distributed lock is not the right mechanism at all. In that case the usual alternatives are better: make the operation idempotent so duplicate execution is harmless, use a conditional write on the resource itself so the database rather than a lock provides the exclusion, or route all operations on a given entity through a single owner so no mutual exclusion is needed.
Two related design points are worth naming. A lease is a lock with a time bound and is strictly more useful in a distributed setting than an unbounded lock, because a client crashing while holding an unbounded lock blocks the resource forever, requiring manual intervention. Every practical distributed lock is therefore a lease, which is why expiry and the pause problem are unavoidable rather than an implementation shortcoming. And there is a real trade-off in choosing the lease duration: short leases mean fast failover after a genuine crash and a higher chance of expiring a merely slow client, while long leases mean the opposite. The right approach is to set the lease comfortably above the worst observed pause and rely on fencing tokens to make the residual window harmless, rather than trying to eliminate the window by tuning alone.
| Lock Purpose | Failure Cost | Acceptable Implementation | Fencing Required |
|---|---|---|---|
| Efficiency: avoid duplicate work | Wasted compute, a duplicate email or cache fill | A single Redis instance or any best-effort lock | No, occasional overlap is tolerable |
| Correctness: prevent data corruption | Corrupted state, double charge, lost writes | Consensus-backed service plus fencing tokens end to end | Yes, absolutely and without exception |
| Leader election for a controller | Two controllers acting: usually corruption | Consensus-backed lease with fencing on every write | Yes, unless every action is idempotent |
| Serialising access to an external API | Rate limit breach or duplicate side effect | Depends entirely on whether the API is idempotent | Only if the API can reject stale callers |
Worked Example: A Pause That Defeats a Lock, and the Token That Saves It
The lock failure is invisible in code review because the code is correct in every respect except its assumption that time passes evenly for everyone involved. The fenced version differs by one integer.
# --- UNSAFE: a correct-looking lock that a pause defeats ---
lock = etcd.lock('/locks/account-42', ttl=30)
lock.acquire()
try:
balance = storage.read('account-42')
storage.write('account-42', balance - 100) # no token: unconditional
finally:
lock.release()
# The timeline that breaks it:
# t=0 A acquires the lock (lease 30s). Reads balance = 500.
# t=1 A enters a 45-SECOND stop-the-world GC pause.
# t=31 A's lease expires. etcd deletes the key. This is CORRECT
# behaviour: A has not renewed and is indistinguishable from
# a crashed process.
# t=32 B acquires the lock. Reads 500. Writes 400. Releases.
# t=46 A RESUMES. It has observed nothing. It still holds a lock
# object it believes is valid. It writes 400 (500 - 100).
# Result: two withdrawals of 100 happened; the balance is 400, not 300.
# One withdrawal silently vanished.
#
# Raising the TTL to 60s does not fix this. It makes the window rarer
# and failover after a REAL crash twice as slow - the worst trade
# available. The client cannot learn about expiry while paused.
# --- SAFE: fencing tokens, with the STORAGE LAYER enforcing them ---
# etcd's mod_revision is already monotonic and globally ordered, so it
# works directly as a fencing token. ZooKeeper's czxid does the same.
lease = etcd.lease_grant(ttl=30)
resp = etcd.txn(
compare=[Compare(key='/locks/account-42', target='create_revision', value=0)],
success=[Put('/locks/account-42', my_id, lease=lease)],
)
if not resp.succeeded:
raise LockUnavailable
token = resp.header.revision # monotonic, cluster-wide, never reused
balance = storage.read('account-42')
storage.write('account-42', balance - 100, fencing_token=token)
# --- The part that actually provides the guarantee ---
# This lives in the STORAGE service, not in the client. Without it the
# token is decoration.
def write(key, value, fencing_token):
highest = self.highest_token_seen.get(key, 0)
if fencing_token < highest:
raise StaleTokenError(
f'token {fencing_token} < {highest}; a newer holder has written')
self.highest_token_seen[key] = fencing_token
self.data[key] = value
# Replaying the same timeline:
# t=32 B writes with token 34 -> accepted, highest_token_seen = 34
# t=46 A writes with token 33 -> 33 < 34 -> REJECTED
# A's stale write is refused by the resource itself. The lock service
# never had to detect anything.
# --- When the resource CANNOT check tokens, do not use a lock ---
# Option 1: make the operation idempotent.
storage.apply_once(operation_id='withdraw-8a3f', delta=-100)
# Option 2: let the database provide exclusion via a conditional write.
UPDATE accounts SET balance = balance - 100, version = version + 1
WHERE id = 42 AND version = 17; -- 0 rows affected means someone else won
# Option 3: route all operations for an entity to a single owner, so
# mutual exclusion is a consequence of the architecture, not a lock.Real-World Examples
- Martin Kleppmann's 2016 article "How to do distributed locking", written as a critique of the Redlock algorithm, is the canonical statement of the fencing-token argument and includes the timing diagram showing a client pausing past its lease expiry. The exchange that followed with Redis author Salvatore Sanfilippo is worth reading in full as an example of how the efficiency-versus-correctness distinction reframes the whole disagreement: the two parties largely agreed about the mechanics and differed about which class of lock was being discussed.
- Kubernetes controllers use a Lease object in the coordination.k8s.io API group for leader election, with the holder renewing periodically and other candidates taking over after the lease duration elapses without renewal. The Kubernetes documentation is explicit that this provides no hard guarantee against two controllers acting simultaneously during a pause, which is why the controller pattern is built around reconciling declared state idempotently rather than around performing one-shot imperative actions: idempotent reconciliation makes the residual overlap window harmless without requiring fencing tokens on every downstream write.
Review Questions & Answers
Because the problem is not the length of the window but the client's inability to observe its own expiry. A client paused for any reason cannot check the clock, cannot renew, and cannot learn that the lock was reassigned until it resumes, by which time it may already have written. A longer lease makes the pause less likely to exceed it, so the failure becomes rarer without becoming impossible, and it simultaneously makes recovery from a genuine crash proportionally slower because the lock stays held for longer after the holder dies. That is a strictly worse trade than accepting a shorter lease and making the residual window harmless with fencing tokens.
A fencing token is a monotonically increasing number issued with each lock grant and attached to every write the holder performs. The protected resource records the highest token it has accepted and refuses any write carrying a lower one, so a resumed stale holder is rejected automatically. It must be enforced at the resource because the lock service has no visibility into what clients do while holding the lock: it cannot intercept a write to a storage system or an external API. Only the component actually receiving the write is in a position to compare tokens, which is why a fencing scheme fails entirely if the resource does not participate.
An efficiency lock exists to avoid duplicated work, so its failure costs wasted compute or a duplicate notification and the system remains correct. A correctness lock exists to prevent corruption, double charges, or lost updates, so its failure costs data integrity and the damage can be unbounded. Because the failure costs differ by orders of magnitude, so should the implementation: an efficiency lock can be built on a single Redis instance where the occasional overlap is an acceptable operating cost, while a correctness lock requires a consensus-backed service plus fencing tokens validated by the resource. Naming which kind you are building, out loud, prevents the common error of deploying a best-effort lock in a place where correctness was silently assumed.
A lock cannot provide a real guarantee here, because nothing can reject the write of a stale holder, so a lock would provide the appearance of safety without the substance. The alternatives are all stronger. Use the API's idempotency key mechanism if it offers one, since most payment APIs do, so a duplicate request with the same key is deduplicated by the provider rather than executed twice. Failing that, record intent in your own transactional store first and use a conditional update there to ensure only one caller proceeds, so your database provides the exclusion. Or route all operations for a given entity through a single owner such as a partitioned consumer, making exclusion a property of the architecture rather than of a lock.
Because the controller pattern is built on idempotent reconciliation rather than on imperative one-shot actions. A controller repeatedly compares declared state to observed state and issues the changes needed to close the gap, so two controllers briefly acting during a pause window issue the same convergent updates rather than conflicting ones, and the API server's own optimistic concurrency on resourceVersion rejects a stale writer anyway. The safety comes from the shape of the operations, not from the lease, which is a general and reusable lesson: making the work idempotent is often a more robust answer than trying to make the mutual exclusion perfect.