Distributed Locks, Leases and Fencing Tokens — Distributed Systems in Practice — Failures, Time, Consensus and Correctness

Let me go back to the story from Lesson 6: a scheduler that ran on several pods, used a “leader lock” in a database to make sure only one pod sent reminder SMS, and still sent duplicates whenever the leader had a long GC pause.

When I explain that bug to people, the first reaction is usually, “So use a proper lock, like Redis SET NX with an expiry.” That’s what most teams do. And it has exactly the same problem. In this lesson I’ll show you that with a real test, and then show the fix, which most lock tutorials leave out.

What We Want From a Lock

On one machine, a mutex is simple: one thread holds it, others wait, and if the process dies, the lock dies with it.

Across machines, we want the same thing: at most one worker does X at a time. Common reasons:

Only one pod should run the nightly settlement job.
Only one worker should process invoice #42 at a time.
Only one instance should be the “rider assigner” for Bengaluru.

There are two different reasons you might want this, and it matters which one you have:

Efficiency: doing the work twice is wasteful but harmless. Two pods both rebuilding the same cache entry. If the lock fails occasionally, you just waste some CPU.
Correctness: doing the work twice causes real damage. Two workers both paying out the same refund, or both writing different versions of the same file. If the lock fails even once, you have a bug.

Hold on to this distinction. The answer to “is a Redis lock good enough?” depends entirely on it.

Locks Must Expire, and That’s the Problem

A distributed lock can’t work like a local mutex, because the holder can crash without releasing it. If the lock never expires, everyone waits forever. So distributed locks are really leases: you hold the lock for a limited time (say 10 seconds), and you must finish or renew before it runs out.

The standard Redis lock:

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

NX: only set if the key doesn’t exist (so only one worker gets it).
PX 10000: expire after 10 seconds (so a crashed worker doesn’t block everyone).
<random-value>: a unique value per holder, so you only delete your own lock when you’re done.

Releasing safely needs a small Lua script, because “check it’s mine, then delete” must be atomic:

if redis.call('get', KEYS[1]) == ARGV[1] then
    return redis.call('del', KEYS[1])
else
    return 0
end

Without that check, here’s what happens: your lock expires, someone else takes it, and then you finish and DEL the key, releasing their lock. Now a third worker can get in too.

So far so good. Now, the problem.

Real Test: Two Workers, One Lock

What if the holder doesn’t crash, but pauses? Processes pause more often than people think:

A garbage collection pause in Java, Go or .NET. Usually milliseconds, but with a big heap under memory pressure, several seconds.
The VM gets paused or its CPU stolen by a noisy neighbour.
The process is stuck on a slow disk write or a page fault.
Someone (or a test, like mine) sends the process SIGSTOP.

During the pause, the process can’t do anything, including notice that its lease has expired. When it wakes up, it continues from exactly where it was, and it still believes it holds the lock.

I tested this with real Redis. Worker A takes a 2-second lock on invoice:42 and then pauses for 3 seconds (I used time.sleep(3) to stand in for a GC pause). Worker B starts 0.2 seconds later and waits for the lock. Both write to a shared “storage” list when they have the lock:

Real Redis test: worker A gets lock:invoice:42 with a 2 second TTL and token 1, then pauses for 3 seconds. Worker B waits from 0.2 seconds, and at 2 seconds the lock expires and B gets it with token 2 and writes. At 3 seconds A wakes up and writes too, and the write is accepted. The lock in Redis was held by A until 2 seconds, then by B. Result: storage got both writes, B(token 2) then A(token 1), so A's older write landed last and overwrote B's. Checking whether you still hold the lock first doesn't help because the pause can happen right after the check

=== fencing tokens: False ===
+ 0.0s A: got lock, fencing token 1
+ 0.0s A: paused (GC / slow disk / VM steal) for 3s
+ 2.0s B: got lock, fencing token 2
+ 2.0s B: write ACCEPTED; still own lock? True
+ 3.0s A: write ACCEPTED; still own lock? False
storage writes: ['B(token 2)', 'A(token 1)']

Both workers wrote. Worse, A’s write came last. If these were “save the invoice PDF” or “set the payout status”, A’s stale version overwrote B’s newer one.

“Just check that you still hold the lock before writing”

That’s the obvious fix, and it doesn’t work:

if redis.get("lock:invoice:42") == my_token:   # check: yes, still mine
    # <-- a 3-second GC pause can happen RIGHT HERE
    storage.write(invoice)                     # lock expired during the pause

The pause can happen between the check and the write. Any check done by the client is already stale by the time the write arrives. Making the lease longer only makes it less likely, not impossible. The client cannot protect itself from its own pauses. Something on the other side has to.

The Fix: Fencing Tokens

The idea (described clearly by Martin Kleppmann in his well-known critique of Redis locking) is to move the check to the storage, which doesn’t pause when the client does:

Every time the lock is granted, the lock service also hands out a fencing token: a number that only ever increases.
The client sends its token with every write.
The storage remembers the highest token it has accepted, and rejects any write with a lower token.

Fencing tokens: the lock service grants the lock along with an increasing token from INCR fence:counter. Worker B writes with token 4 and worker A, waking from its pause, writes with token 3. Storage has seen max token 4, so token 4 is accepted and token 3 is rejected. Real run with the same pause: B got lock token 4 and its write was accepted; A's write was rejected as a stale token, and storage contains only B's write. etcd and ZooKeeper provide tokens through revision and zxid. The storage must check the token, for example with a WHERE fence_token less than the token condition. If storage can't check tokens, make the operation idempotent

Same test, with fencing (the token came from INCR fence:counter on each grant, and the “storage” was a small Lua script that compared tokens):

=== fencing tokens: True ===
+ 0.0s A: got lock, fencing token 3
+ 0.0s A: paused (GC / slow disk / VM steal) for 3s
+ 2.0s B: got lock, fencing token 4
+ 2.0s B: write ACCEPTED; still own lock? True
+ 3.0s A: write REJECTED (stale token); still own lock? False
storage writes: ['B(token 4)']

A woke up, tried to write with token 3, and the storage said no, because it had already seen token 4. The pause didn’t matter.

In a SQL database, the storage-side check is just a condition on the update:

UPDATE invoices
SET pdf_url = 's3://.../inv-42-v2.pdf', fence_token = 4
WHERE id = 42 AND fence_token < 4;      -- 0 rows updated = a newer holder already wrote

Where do tokens come from?

etcd gives you one for free. Every key has a mod_revision (and a create revision) that increases cluster-wide with every change. When you acquire a lock key, its revision is your fencing token.
ZooKeeper has the zxid and sequential node numbers, which serve the same purpose.
A database sequence or INCR on the lock service, as in my test, works if the lock service itself is reliable.

When the storage can’t check tokens

Often the thing you’re protecting is a third-party API (a payment gateway, an SMS provider) that knows nothing about your tokens. Then fencing isn’t possible, and you fall back on Lesson 2: make the operation idempotent with a key derived from the job (for example refund-for-order-42), so that if two workers both do it, the external system only acts once.

Redis, Redlock and the Debate

If you search for distributed locks, you’ll find Redlock: an algorithm by the Redis author for taking a lock on a majority of several independent Redis servers, so the lock survives one Redis failing. You’ll also find a long public debate about whether it’s safe.

The short, practical version of that debate:

Redlock protects against a Redis server failing. It does not protect against client pauses. Without fencing tokens, the test above fails with Redlock too.
Redlock’s safety also depends on clocks and timing assumptions (bounded pauses, bounded clock drift) that, as we saw in Lesson 3, don’t always hold.
Redis replication is asynchronous. With a single Redis primary and a replica, if the primary dies after granting a lock but before replicating it, the promoted replica doesn’t know about the lock, and someone else can take it.

My recommendation, which matches what most experienced people I know end up with:

For efficiency locks (avoid duplicate work, where an occasional double run is harmless): a single Redis SET NX PX with a safe unlock is perfectly fine. Simple, fast, widely understood.
For correctness locks: use a consensus-based store (etcd, ZooKeeper, Consul) and fencing tokens checked by the storage. Or better, avoid needing a lock at all.

Leases in etcd

etcd’s lease model is the cleanest way I know to build a correct lock or leader election:

import etcd3

client = etcd3.client()
lease = client.lease(ttl=10)
ok, responses = client.transaction(
    compare=[client.transactions.create("/locks/invoice-42") == 0],
    success=[client.transactions.put("/locks/invoice-42", "worker-7", lease),
             client.transactions.get("/locks/invoice-42")],
    failure=[],
)
if ok:
    _, meta = responses[1][0]
    fencing_token = meta.mod_revision       # increases with every grant, cluster-wide
    do_work(fencing_token, keep_alive=lease.refresh)

The lease is kept alive by refreshing it. If the process dies or pauses too long, the lease expires and etcd deletes the key, so another worker can take it. And the mod_revision gives you a fencing token that is guaranteed to increase, backed by Raft. (Many client libraries wrap this in a ready-made Lock or Election helper; the etcd Go client has concurrency.Mutex and concurrency.Election.)

In Kubernetes, you get the same thing through Lease objects in the coordination.k8s.io API, which is how controllers and operators do leader election.

Often, You Don’t Need a Lock

Locks are a tool of last resort. Many “we need a distributed lock” situations have simpler, safer answers:

“Only one worker should process this job.” Use a queue with competing consumers (each message goes to one consumer), or claim rows in the database with SELECT ... FOR UPDATE SKIP LOCKED. The database transaction is the lock, and it’s released automatically if the worker dies.
“Don’t oversell stock.” Use a conditional update: UPDATE stock SET qty = qty - 1 WHERE item_id = 7 AND qty > 0. If zero rows changed, it’s sold out. No lock needed.
“Don’t create two accounts for one phone number.” Use a unique constraint and handle the conflict.
“Don’t apply the same update twice.” Use idempotency keys (Lesson 2) or version numbers with compare-and-set (Lesson 3).
“Only one instance should run the cron job.” Use a scheduler that runs it once (Kubernetes CronJob with concurrencyPolicy: Forbid), and make the job idempotent anyway.

The database is often the best “lock service” you already have, because it gives you transactions and constraints, and those are checked at the storage, which is exactly where fencing says the check belongs.

Pitfalls to Avoid

Locks without expiry. One crashed holder blocks everyone forever.
Deleting the lock without checking it’s yours. You may release someone else’s lock.
Trusting a client-side “do I still hold it?” check. A pause right after the check breaks it.
Correctness depending on a Redis lock without fencing. Real test: both workers wrote, and the stale write won.
Very long leases “to be safe”. A crashed holder then blocks work for that long, and pauses can still be longer.
Assuming Redlock fixes pauses. It fixes Redis server failures, not client pauses.
Reaching for a lock when a constraint, conditional update or queue would do.

Quick Recap

Distributed locks must expire, so they’re really leases.
A holder that pauses longer than its lease keeps acting as the owner. Real test: two workers both wrote with a Redis lock, and the older write landed last.
Fencing tokens fix it: increasing numbers per grant, checked by the storage. Real test: the stale write was rejected.
Use Redis locks for efficiency; use etcd/ZooKeeper plus fencing for correctness.
Prefer database constraints, conditional updates, SKIP LOCKED and idempotency over locks where possible.

Next lesson: messaging. At-most-once, at-least-once, and what people really mean by “exactly once”, with a real consumer that credited ₹5,500 too much cashback.