Locks, Leases & Leader Election

Why distributed locks are fundamentally harder

A mutex inside one process works because the operating system can stop a thread. A distributed lock has no such power. It can revoke your permission; it cannot revoke your ability to act.

Between checking that you hold a lock and using it, arbitrary time can pass:

• Stop-the-world garbage collection — multi-second pauses are ordinary in large JVM heaps.
• The hypervisor descheduling your VM.
• A page fault hitting swap, or a stalled disk.
• Network delay between you and the resource.

And per failure models, the lock service cannot distinguish your pause from your death. It must eventually give the lock to someone else, or a crashed client would hold it forever.

Leases, and why they aren't enough

A lease is a lock with an expiry — the standard answer to the crashed-holder problem, and what every practical system uses.

But a lease only fixes liveness (the lock is eventually released). It does not fix safety, because expiry is judged by two different clocks: the lease service's and the client's. The client thinks it has 20 seconds left; the service expired it 10 seconds ago. That gap is exactly the hook above.

Shortening the TTL doesn't fix it — it makes it more likely, since shorter leases expire during shorter pauses.

Fencing tokens: the actual fix

The mechanism that makes this safe, and the single most valuable thing in this lesson.

Every time the lock is granted, the service returns a monotonically increasing token:

Client A acquires lock  →  token 33
A pauses.
Lease expires.
Client B acquires lock  →  token 34
B writes to storage with token 34.  Storage records: last token = 34.
A wakes and writes with token 33.
Storage sees 33 < 34 and REJECTS the write.

The critical shift: the resource enforces the lock, not the lock service. The storage layer only has to remember the highest token it has seen and reject anything lower. That's a trivial requirement, and it's what makes correctness possible at all.

This is the same mechanism as the epoch numbers that stop a returning old leader in single-leader replication — and it's why ZooKeeper exposes zxid and etcd exposes revision numbers. They're fencing tokens.

The Redlock argument, briefly

Redlock is an algorithm for locking across several independent Redis instances, acquiring a majority. It prompted a well-known exchange between Martin Kleppmann and Redis's author, and it's worth knowing because interviewers occasionally raise it.

The objection: Redlock's safety depends on timing assumptions — bounded clock drift, bounded pauses, bounded network delay. In an asynchronous system, none of these hold, so a GC pause or a clock jump can produce two holders. Redlock also provides no fencing token, so the resource cannot detect the situation.

The pragmatic position: if you need a lock for efficiency (avoid doing the same work twice, and duplicating it is merely wasteful), Redlock or even a single Redis SET NX PX is fine. If you need it for correctness (duplicating causes corruption or double-spend), you need a consensus system and fencing tokens — or, better, a design that doesn't need the lock.

Ask which of the two you're in. That framing is the correct answer to the question.

Leader election in practice

Three common implementations, in rough order of robustness:

Consensus store with a lease (etcd, ZooKeeper, Consul). Create a key with a lease and keep it alive with heartbeats; whoever holds it is leader. On crash the lease expires and someone else takes over. Use the store's revision as the fencing token. This is the standard answer.

Database row. UPDATE leader SET holder=?, expires=? WHERE expires < now(). Works, and uses infrastructure you already have. Uses the database's clock for expiry — which is a single clock, so it's better than it sounds — but it needs a fencing column to be safe.

ZooKeeper ephemeral sequential nodes. Each candidate creates an ephemeral sequential node; lowest sequence number wins; each watches only its immediate predecessor to avoid a herd of watches firing at once. Classic, well-understood, and more operational weight than most teams want today.

Whichever you pick, the leader must verify it is still leader before acting, and downstream systems must enforce the fencing token. A leader that assumes it's still leader is the split-brain scenario waiting to happen.

The herd on release

When a lock is released or a leader dies, every waiter wakes and tries simultaneously — hammering the coordination service at the worst moment.

Fixes: queue-based locks where each waiter watches only the one ahead of it (the ZooKeeper recipe above), randomised backoff before retrying, and capping how many candidates contend at all. The same jitter principle as retries in failure models.

Designing coordination away

Coordination is expensive — a round trip on the hot path, a shared dependency, a new failure mode. The senior move is usually to remove the need:

Partition ownership. If each key has exactly one owner by construction — consistent hashing, Kafka partition assignment, sharded workers — then no lock is needed, because only one process ever touches it. This is the most common real answer.

Idempotency. If running a job twice is harmless, you don't need a lock to guarantee it runs once. See idempotency. Frequently cheaper than getting locking right.

Optimistic concurrency. Read a version, do the work, write conditionally on the version being unchanged. No lock held during the work, and the conditional write is the safety check. Excellent when conflicts are rare.

CRDTs. Where the merge function is deterministic and order-independent, concurrent updates need no coordination at all — counters, sets, and collaborative text all have well-known constructions.

Single-writer per partition. Route all writes for an entity through one consumer. Ordering and exclusivity fall out of the routing rather than a lock.

What to take away

• A distributed lock can revoke permission but cannot stop a paused process from acting.
• Leases fix liveness, not safety — client and service judge expiry by different clocks.
• Fencing tokens are the fix: monotonic numbers, enforced at the resource.
• Locks for efficiency can be casual; locks for correctness need consensus plus fencing.
• Leader election: a lease in a consensus store, with its revision as the fencing token.
• Better than any lock: partition ownership, idempotency, optimistic concurrency, CRDTs.