Catalog My learning Blog
Raft and Paxos Explained: Consensus, ZooKeeper and etcd · Phase 3 · Lesson 15 · 11 min read

Distributed Locks, Leases and Fencing Tokens

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: A Pause That Defeats a Lock, and the Token That Saves It
  4. Real-World Examples
  5. Review Questions & Answers

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 PurposeFailure CostAcceptable ImplementationFencing Required
Efficiency: avoid duplicate workWasted compute, a duplicate email or cache fillA single Redis instance or any best-effort lockNo, occasional overlap is tolerable
Correctness: prevent data corruptionCorrupted state, double charge, lost writesConsensus-backed service plus fencing tokens end to endYes, absolutely and without exception
Leader election for a controllerTwo controllers acting: usually corruptionConsensus-backed lease with fencing on every writeYes, unless every action is idempotent
Serialising access to an external APIRate limit breach or duplicate side effectDepends entirely on whether the API is idempotentOnly 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.

SQL
# --- 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.
A timeline showing a client pausing past its lease expiry while a second client acquires the lock and writes, followed by the same timeline with fencing tokens where the protected resource rejects the resumed client because it has already accepted a higher token.
A timeline showing a client pausing past its lease expiry while a second client acquires the lock and writes, followed by the same timeline with fencing tokens where the protected resource rejects the resumed client because it has already accepted a higher token.

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.
WarningA distributed lock guarantees only that the lock service believes one client holds it, not that only one client is acting, because a paused or partitioned client cannot learn that its lease expired. Classify every proposed lock as efficiency or correctness: efficiency locks tolerate occasional overlap, while correctness locks require fencing tokens that the protected resource itself validates. If the resource cannot reject stale tokens, choose idempotency, a conditional write, or single-owner routing instead of a lock.

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.