Consensus, leases and coordination

Leader election, Raft and Paxos at interview depth, ZooKeeper and etcd, distributed locks and why they are fencing tokens, plus how to avoid needing coordination at all.

Coordination is the most expensive thing a distributed system can do, and the mark of a good answer is knowing which parts of the design genuinely need it. Usually the answer is: one small strongly consistent store for metadata, and everything else built to tolerate not knowing.

What consensus buys

Consensus protocols (Raft, Multi-Paxos, Zab) give a group of nodes an agreed, ordered log of decisions that survives a minority of failures. From that you get a linearizable key-value store, leader election, group membership, and distributed locks.

The cost: every decision needs a round trip to a majority, so writes are limited by the slowest node in the quorum and by the network diameter. A cross-region Raft group has a floor of one inter-region round trip per write — 50–150 ms. That is why consensus stores hold kilobytes of metadata, not your application data.

Raft in the depth an interview wants

• A group of 2f + 1 members tolerates f failures. Three or five members; never an even number.
• One leader at a time. A leader is elected by a majority for a term; terms are monotonically increasing so an old leader's messages are recognisable and rejected.
• Clients send writes to the leader. The leader appends to its log, replicates to followers, and commits once a majority has the entry, then applies it to the state machine.
• Followers time out (randomised, 150–300 ms) and start an election if they hear nothing. Randomised timeouts prevent split votes.
• Reads: from the leader for linearizability, and even then the leader must confirm it is still leader (heartbeat round trip or a lease) before answering, or it can serve stale data after a partition.

Say "Raft" rather than "Paxos" unless asked: it is the one people implement, and the description above is what an interviewer is listening for.

ZooKeeper and etcd

You rarely implement consensus; you use a service that has. What they give you:

• A small, strongly consistent key-value tree with watches.
• Ephemeral nodes tied to a session — they vanish when a member's heartbeat stops, which is what makes membership and liveness work.
• Sequential nodes, which give locks and queues without spinning.
• Watches, so members are notified of changes instead of polling.

Typical uses in a design: which shard is assigned to which server, who is the current leader of a job, feature and rate-limit configuration, and service membership when you are not using a service mesh. Rule of thumb: kilobytes to low megabytes, updates per second not per millisecond.

Leader election in practice

Elect a leader when exactly one process must do something: run a cron, own a shard, compact a log, assign work.

The pattern: contend for a key with a TTL (a lease); the winner refreshes it while alive; if it stops refreshing, the key expires and the next contender takes over. Getting it right means answering two questions:

1. What happens between the lease expiring and the new leader starting? The system must tolerate a gap of at least one lease period.
2. What happens if the old leader was only paused, not dead? It wakes up believing it is still the leader. This is the dangerous case.

Distributed locks are fencing tokens

A lock in a distributed system is not mutual exclusion; it is a hint that expires. A process can hold the lock, stop for a GC pause longer than the TTL, and continue writing while someone else holds it.

The fix is a fencing token: the lock service returns a monotonically increasing number with the lock, the holder passes it to whatever it writes to, and the resource rejects any write carrying a token lower than the highest it has seen. Without a fence, a lock protects nothing under a pause.

Say this out loud when asked for a distributed lock; it is the single best signal of experience in this area.

Designing so you need less coordination

The strong answer is usually to avoid the need:

• Partition by key so that one owner handles one key and coordination is local.
• Idempotent writes with a client-supplied key make duplicate work harmless, which removes the need for exactly-once anything.
• Optimistic concurrency: read a version, write conditional on that version (compare-and-set, If-Match), retry on conflict. Cheap when conflicts are rare.
• CRDTs and commutative operations (counters, sets, last-writer-wins registers) converge without agreement, at the cost of a weaker data model.
• Leases with short TTLs instead of locks for ownership, plus fencing on the write side.

Failure modes to mention

• Split brain: two leaders after a partition. Prevented by majority quorums and fencing, not by heartbeats alone.
• Herds after a leader loss: every follower tries to become leader or reconnect at once. Randomise timeouts and jitter reconnects.
• Cluster loss of quorum: with three nodes, two failures and the cluster is read-only. This is why the coordination store must not be on the request path for everything.
• Clock assumptions: leases rely on bounded clock drift, not on synchronised clocks. Use monotonic clocks for elapsed time and keep the lease much longer than expected drift.

Numbers

• Local Raft write: ~1–5 ms. Cross-region Raft write: 50–150 ms.
• Practical throughput of a single consensus group: thousands of writes per second, not millions — shard into many groups if you need more.
• Session and lease timeouts: seconds (5–15 s typical), deliberately much longer than a GC pause.

In the interview

Name the one component that needs strong consistency ("shard assignment lives in etcd"), keep everything else eventually consistent, and be ready for these follow-ups: what happens when the leader pauses for 30 seconds, how long is the unavailability window during failover, and what makes the lock safe.

Checklist

• Which state is strongly consistent, and how small it is.
• Group size, failure tolerance, and where members live.
• Lease duration, and the behaviour during the gap.
• Fencing tokens on anything a lock protects.
• What the system does when the coordination service is unavailable.