Start practising

SYSTEM DESIGN · CONCEPTS · DISTRIBUTED SYSTEMS · EPISODE 31

Distributed Locks and Leader Election

How several servers agree that only one of them does something: why a local mutex is not enough, locks with leases and TTLs, why a paused process can still corrupt data, fencing tokens, leader election with ZooKeeper or etcd, the Redis lock debate, and when to avoid locks altogether.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 11

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

The problem

A mutex in your code only works inside one process. Two servers share no memory, only a network. So both decide to run the job. You need a lock that lives outside both of them, in a service every server agrees on.

Why a mutex is not enough
  • a mutex works inside ONE
  • process
  • two servers share nothing
  • but the network
  • need: a lock that lives
  • outside both, that every
  • server agrees on

Acquire

The basic lock: create a key only if it doesn't exist. Worker one succeeds and runs the job; worker two finds it taken and waits or skips. When done, worker one deletes the key, but only if it still holds its own value, so it never deletes someone else's lock.

Acquire
SET lock:billing w1
    NX        ← only if absent
    PX 30000  ← expires in 30 s

w1: OK      → runs the job
w2: nil     → waits / skips

release: delete ONLY if the
value is still w1

Leases

If worker one crashes holding the lock, nobody can ever run the job again. So every distributed lock is a lease: it expires after, say, thirty seconds unless the holder renews it. For long jobs, the holder sends a heartbeat every ten seconds to extend it.

Leases (TTL)
  • what if w1 crashes while
  • holding the lock?
  • without expiry: locked forever
  • lease: the lock expires
  • after 30 s unless renewed
  • long job? renew (heartbeat)
  • every 10 s

The pause

Now the subtle part. Worker one holds the lock, then freezes for forty seconds: a garbage-collection pause, a paused VM. Its lease expires and worker two takes the lock. Worker one wakes up, still believing it holds the lock, and writes. Two writers. Expiry alone can't prevent this, because the paused process doesn't know time passed.

The dangerous case
  • w1 holds the lock
  • w1 freezes 40 s
  • (GC pause, VM paused, swap)
  • lease expires → w2 acquires
  • w1 wakes up, still thinks
  • it holds the lock, writes
  • two writers. Expiry alone
  • cannot prevent this.

Fencing

The fix is a fencing token. Each time the lock is granted, the lock service returns a number that only goes up. Worker one got thirty-three, worker two got thirty-four. Every write carries its token, and the storage rejects any token lower than the highest it has seen. The zombie's write with thirty-three bounces.

Fencing tokens
each grant returns a number
that only goes up

w1 got token 33
w2 got token 34

storage remembers the highest
token seen (34) and rejects
any write carrying 33

Leader election

Leader election is the same idea, held for a long time: one node is the leader as long as it keeps renewing its lease. Use etcd, ZooKeeper or Consul for this. They run a consensus protocol internally, so the lock itself survives a server dying. Kubernetes controllers and Kafka elect their leaders exactly this way.

Leader election
  • same idea, long-lived:
  • one node is "leader" while
  • it keeps renewing its lease
  • etcd / ZooKeeper / Consul:
  • consensus inside (episode 34)
  • so the lock itself survives
  • node failures
  • Kafka, Kubernetes, HBase
  • all elect leaders this way

Redis locks

What about Redis? Ask why you need the lock. If it's for efficiency, avoiding duplicate work where an occasional double run is harmless, a single Redis key with NX and an expiry is fine. If it's for correctness, money or uniqueness, use a consensus-backed store and fencing tokens. Redlock, the multi-Redis algorithm, is famously debated for exactly this pause problem.

What about Redis?
  • single Redis SET NX PX:
  • fine for efficiency locks
  • (avoid duplicate work; an
  • occasional double run is OK)
  • for correctness locks
  • (money, uniqueness):
  • use a consensus store +
  • fencing tokens
  • Redlock is debated; know why

Alternatives

Often the best lock is no lock. A unique constraint in the database guarantees one booking per seat. A conditional update, 'update where version equals seven', does optimistic locking. Idempotent jobs from episode twenty-nine make double runs harmless. And a queue partition per key gives one owner per entity naturally.

Avoid the lock?
  • often a better design:
  • unique constraint in the DB
  • (one booking per seat)
  • conditional write / version:
  • UPDATE … WHERE version = 7
  • idempotent jobs (episode 29)
  • single partition owner
  • (queue partition per key)

Say it like this

The interview answer. Take a lock in a consensus-backed store like etcd, with a lease that the holder renews. Pass a fencing token with every write, and have the storage reject older tokens, because pauses happen. Then mention the alternatives: unique constraints, conditional writes and idempotency, which often remove the need for a lock.

In the interview
  • "How do you make sure only
  • one worker runs it?"
  • lock in etcd / ZooKeeper,
  • with a lease + renewals
  • fencing token checked by
  • the storage
  • or avoid it: unique constraint,
  • conditional write, idempotency

Interview questions

Why can’t you use a normal mutex across servers?

A mutex only coordinates threads that share memory in one process. Separate servers share nothing but the network, so the lock must live in an external service that all of them consult.

Why must a distributed lock have a TTL (lease)?

If the holder crashes or is cut off, a lock without expiry would never be released, blocking everyone forever. A lease expires unless the holder keeps renewing it.

How can two clients both believe they hold a lock?

The holder pauses (garbage collection, VM suspension, network delay) longer than the lease, the lock expires and is granted to another client, then the first resumes unaware that its lease ended and acts on the resource.

What is a fencing token?

A monotonically increasing number returned with each lock grant and sent with every operation. The protected resource remembers the highest token it has seen and rejects operations carrying a lower one, blocking stale holders.

How is leader election related to locking?

Leader election is a long-lived lock: one node holds a lease that marks it as leader and keeps renewing it; if it stops, the lease expires and another node acquires it. Stores like etcd, ZooKeeper and Consul provide this.

Is a Redis lock safe?

A single-instance Redis lock with SET NX PX is fine for efficiency, where an occasional duplicate is acceptable. For correctness, prefer a consensus-based store and fencing tokens; the multi-node Redlock algorithm is debated because it does not protect against process pauses.

How can you avoid needing a distributed lock?

Use database unique constraints, conditional or versioned writes (optimistic concurrency), idempotent operations, or route all work for one key to a single owner such as a queue partition.

Why do etcd and ZooKeeper suit locks better than a single cache?

They replicate state with a consensus protocol, so lock state survives individual node failures and they provide features like sessions, watches and monotonically increasing revisions usable as fencing tokens.