Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Distributed Systems Theory

System Design HLD-08.07

Distributed locks and fencing tokens

Why distributed locks need leases, how a paused process breaks them, how fencing tokens make storage reject stale holders, and the caveats of Redis locks.

Advanced 12 min Last reviewed

The big idea

Inside one process, a lock is simple: a thread takes a mutex, does its work, releases it, and if the thread dies the process dies with it. Across machines, none of that holds. A distributed lockA lock held through a shared service so that only one process across many machines does a piece of work, or touches a resource, at a time. lives in a separate service, and the holder can crash, hang or lose its network connection while the lock still says it is in charge.

So distributed locks expire. That fixes crashes but opens a quieter hole: a holder that is merely paused comes back after its lock has expired and been given to someone else, still believing it holds the lock. Now two processes write at once, which is the exact thing the lock was meant to prevent. The fix is not a better lock. It is making the resource itself check: every grant carries an increasing number, and the resource refuses anyone holding an older one.

Think of a hotel key card. When you check out late, the front desk issues a new card to the next guest, and the door lock is reprogrammed to accept only the newest card. Your old card still looks fine in your pocket, but the door, not your belief, decides.

How it works

Step 1: Locks need leases

Suppose a lock had no expiry. Client A takes it, then its machine loses power. The lock service cannot tell a dead client from a slow one ( Why distributed systems are hard ), so it would wait forever and every other client would block behind a ghost. That is why every practical distributed lock is a leaseA time-limited grant of leadership or ownership that must be renewed before it expires.: it is granted for a fixed time, say 10 seconds, and the holder must renew it before then or lose it.

Leases make liveness possible. They also introduce a hidden assumption: that the holder notices its lease is about to run out and stops working before it does.

Step 2: Process pauses break that assumption

A process can stop running for seconds without crashing and without knowing it stopped. Common causes:

  • Garbage collection: a "stop the world" collection in a large heap can freeze every thread for seconds.
  • Virtual machine pauses: the hypervisor suspends or live-migrates the VM.
  • Swapping and page faults: memory pages come back from slow disk.
  • Operating system scheduling or a SIGSTOP: the process simply is not scheduled.
  • Network delay: the write leaves the client in time but sits in a queue and arrives late.

A pause can land anywhere, including between "check that my lease is valid" and "write to storage". Checking the clock just before writing does not help, because the pause can strike right after the check. From the client's point of view no time passed at all.

A paused lock holder is fenced off by storage Sequence diagram with four actors. Client A acquires the lock with token 33, then pauses for 15 seconds in garbage collection. Its 10 second lease expires. Client B acquires the lock with token 34 and writes to storage with token 34. Client A wakes and writes with token 33. Storage, having already seen token 34, rejects the stale write. Client A Lock service lease 10 s Client B Storage remembers max token acquire lock granted, token 33 GC pause: 15 s lease expires acquire lock granted, token 34 write(token 34) write(token 33) REJECTED: 33 < 34 Figure 1. A's lease expires during its pause and B gets the lock with a higher token. When A wakes and writes with token 33, storage has already seen 34 and rejects it. Step through the timeline.
  1. acquire lock Client A asks the lock service for the lock.
  2. granted, token 33 The lock service grants a 10 second lease and hands out fencing token 33.
  3. GC pause: 15 s Client A freezes in a garbage collection pause. It cannot renew its lease and does not know time is passing.
  4. lease expires Ten seconds pass with no renewal, so the lease expires and the lock is free.
  5. acquire lock Client B asks for the lock and gets it.
  6. granted, token 34 Each new grant carries a higher token, so B receives token 34.
  7. write(token 34) B writes with token 34. Storage accepts it and records 34 as the highest token seen.
  8. write(token 33) A wakes up, still believes it holds the lock, and sends its write with the old token 33.
  9. REJECTED: 33 < 34 Storage sees 33 is older than 34 and rejects the write. The stale holder is fenced off, and B's data is safe.

Step 3: Fencing tokens

A fencing tokenA number that increases with every lock grant; the protected resource rejects requests carrying a token lower than the highest it has already accepted. closes the hole. The lock service attaches a number to every grant, and the number strictly increases: 33, then 34, then 35. The client sends its token with every request to the protected resource. The resource remembers the highest token it has accepted and rejects any request with a lower one.

Run both versions of the scenario from Figure 1:

fencing.pyruns with python3 (standard library)
class LockService:
    """Grants a lease with an increasing fencing token."""
    def __init__(self):
        self.token, self.holder, self.expires = 0, None, 0
    def acquire(self, client, now, ttl=10):
        if self.holder is None or now >= self.expires:
            self.token += 1
            self.holder, self.expires = client, now + ttl
            return self.token
        return None

class Storage:
    """Rejects writes carrying an older token than one it has already seen."""
    def __init__(self, fenced):
        self.fenced, self.max_token, self.data = fenced, 0, []
    def write(self, client, token, value):
        if self.fenced and token < self.max_token:
            return f"REJECTED {client} (token {token} < {self.max_token})"
        self.max_token = max(self.max_token, token)
        self.data.append(value)
        return f"ok {client} wrote {value!r}"

for fenced in (False, True):
    locks, store = LockService(), Storage(fenced)
    t_a = locks.acquire("A", now=0)                   # A gets the lock, token 1
    # ... A pauses for 15 s (garbage collection); its 10 s lease expires ...
    t_b = locks.acquire("B", now=12)                  # B gets the lock, token 2
    print(f"fencing {'on ' if fenced else 'off'}:", store.write("B", t_b, "B's update"), "|",
          store.write("A", t_a, "A's stale update"))  # A wakes up, still thinks it holds the lock
    print("   final data:", store.data)

Output

fencing off: ok B wrote "B's update" | ok A wrote "A's stale update"
   final data: ["B's update", "A's stale update"]
fencing on : ok B wrote "B's update" | REJECTED A (token 1 < 2)
   final data: ["B's update"]

Without fencing, A's stale write lands on top of B's and silently corrupts the data. With fencing, storage rejects it. Notice what changed: not the lock, but the storage. Correctness now lives where the data lives, and it does not depend on anyone's clock or on the client noticing it was paused.

Step 4: Where the tokens come from

The token must come from something that already orders grants safely, which is why lock services built on consensus are a natural fit ( Consensus: Raft ):

  • ZooKeeper: the transaction id (zxid) of the lock node's creation, or the node's version number, increases with every change.
  • etcd: every write gets a cluster-wide revision number; the revision at which you created your lock key works as a token.
  • A database row: a version column incremented by UPDATE locks SET version = version + 1 ... RETURNING version.

The resource side needs one check. If it is a database, that can be a conditional write: UPDATE ... WHERE fence_token < :token. If it is an external API that cannot check tokens, you cannot fence it, and you should design for that (see below).

Going deeper

Redis-based locks

The popular single-node Redis lock is one command:

SET lock:invoice-42 <random-value> NX PX 30000

NX sets the key only if it does not exist, and PX 30000 gives it a 30 second expiry. The random value identifies the holder; to release, a small Lua script deletes the key only if it still holds your value, so you never release a lock someone else now owns. This is fine for one Redis server, but if that server fails over to a replica before the key was replicated, a second client can acquire the same lock.

Redlock, an algorithm described in the Redis documentation, tries to fix that by acquiring the lock on a majority of independent Redis servers (for example 3 of 5) within a time budget, and treating the lock as valid for the TTL minus the time spent acquiring it and an allowance for clock drift. The caveats, raised publicly by distributed systems researchers:

  • No fencing token. The random value identifies a holder but does not increase, so storage cannot use it to reject stale writes. A paused client breaks Redlock exactly as in Figure 1.
  • Timing assumptions. Safety relies on bounded network delay, bounded pauses and clocks that advance at roughly the same rate. A clock jump on one Redis server can expire a key early and let a second client win a majority.

Efficiency locks versus correctness locks

Ask what happens if the lock occasionally fails and two holders run at once.

  • Efficiency: the lock avoids duplicate work, such as two workers regenerating the same report. A rare double run costs some compute. A simple Redis lock with a TTL is a reasonable choice.
  • Correctness: a double run corrupts data, double-charges a customer or loses money. Use a consensus-backed lock service and fencing tokens checked by the resource, or avoid the lock altogether with a conditional write or an idempotent operation.

When the resource cannot fence

Some resources, such as a third-party payment API, will not check your token. Then the lock alone can never guarantee single execution. Make the operation itself safe to repeat with an idempotency key the provider deduplicates, or route all writes through one owner that does check tokens.

Trade-offs

OptionWins whenLoses when
Single Redis SET NX with TTL Avoiding duplicate work cheaply when an occasional double run is harmless Correctness under failover, process pauses or clock jumps
Redlock (majority of Redis nodes) Surviving one Redis node failure for efficiency locks Safety under pauses and clock jumps; it provides no fencing token
Consensus lock service + fencing tokens Correctness: the resource rejects stale holders regardless of timing Needs etcd or ZooKeeper and a resource that can check tokens
No lock: conditional writes or idempotency A single resource that supports compare-and-set or deduplication Coordinating work across several resources at once

Common mistakes

  • Taking a lock with no expiry, so one crashed client blocks everyone forever.
  • Checking "is my lease still valid?" right before writing and assuming that is safe; the pause can come after the check.
  • Using a random lock value or a timestamp as a fencing token; it must strictly increase.
  • Releasing a lock with a plain DEL instead of compare-and-delete, deleting another client's lock.
  • Using a lock meant for efficiency to protect money or data integrity.

In the wild

Fencing is old and widespread. Google's Chubby lock service hands out "sequencers" that servers check before acting on a request, the same idea as a fencing token. HDFS NameNode high availability uses epoch numbers in its quorum journal so that a deposed NameNode cannot keep writing to the shared edit log. ZooKeeper and etcd recipes use version and revision numbers as tokens, and Kubernetes leader election records leases and transitions in a Lease object stored in etcd.

Check yourself

  1. Why does a distributed lock need an expiry at all?

    Show answer

    B. Because the lock service cannot tell a crashed holder from a slow one, so without expiry a crash blocks everyone forever Expiry gives liveness: if the holder dies, the lock eventually frees. The price is that a slow holder can lose the lock without knowing.

  2. Client A checks its lease has 5 seconds left, then writes. Is that safe?

    Show answer

    B. No, a pause can happen between the check and the write, so the write may arrive after the lease expired Pauses can strike anywhere, including right after the check. Only a check at the resource, at write time, closes the gap.

  3. Storage has accepted token 41. A write arrives with token 40. What should happen?

    Show answer

    B. Reject it, because a newer holder has already written A lower token proves the sender's lock was superseded. Storage rejects it without needing to know about clocks or leases.

  4. Why can't the random value in a Redis lock serve as a fencing token?

    Show answer

    B. It identifies a holder but does not increase, so storage cannot tell which holder is newer Fencing needs ordering. A random value only says who you are, not whether you were superseded.

  5. Two workers occasionally regenerate the same cached report. Which lock fits?

    Show answer

    B. A simple Redis lock with a TTL, since a rare double run is harmless This is an efficiency lock. Paying for consensus and fencing only makes sense when a double run causes real damage.

Recap

  • Distributed locks must be leases, or a crashed holder blocks everyone forever.
  • Expiry plus process pauses (GC, VM, swap, network delay) means a holder can act after losing its lock.
  • Fencing tokens increase with every grant, and the resource rejects any token older than one it has seen.
  • Correctness lives at the resource; client-side lease checks cannot close the gap.
  • Redis locks are fine for efficiency; for correctness use a consensus-backed service with fencing, or conditional writes.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy