CSE Roadmap

Common tier · about 3 hours · 6 parts

Part 5 of 6 · 4 min read

Leaders in practice

Use an existing store rather than writing your own, and know the costs.

Leaders in practice

Think of renting a meeting room through a booking system. You do not build the booking system; you use the one that already stops double bookings, and you rebook before your slot ends.

The book advises that you will rarely write leader election from scratch. Use a linearizable key-value store such as etcd or ZooKeeper [a store that behaves as if there were one copy, module 6]. These offer ready pieces, from compare-and-swap to full distributed locks.

The minimum needed is an atomic compare-and-swap with a time to live (TTL). Compare-and-swap updates a key only if its current value matches what the caller expects. The TTL removes the key after a set time unless it is renewed. The recipe:

  1. Each candidate tries to create a key (say leader) with compare-and-swap and a TTL.
  2. The first to succeed is leader. It must renew the key before the TTL runs out.
  3. If it stops renewing, the key expires and another candidate can take over.

This is the lease from module 4. A lock service of this kind gives the same effect as an election.

Lease

A lease is a lock that expires on its own unless the holder renews it.

Example: a worker holds the leader key for 10 seconds and renews it every 3 seconds. If the worker freezes, the key expires after 10 seconds and another worker takes over.

But one leader is still not guaranteed. The book gives the shared file case. A process gets the lock, reads a file, changes it in memory and writes it back. In between, the process could be paused for seconds, the lease expire, and another process become leader. The first process then writes as a leader that no longer is. Checking again just before writing only makes this less likely, it does not remove it. The proper fix is the fencing token of module 4: a number that rises with each lock grant, passed on every write, with the store rejecting any number lower than the last it saw. If the store cannot check tokens, the design must accept that two leaders sometimes exist. If both do an idempotent operation (module 1), no harm is done.

Costs of having a leader. The book lists them:

  • A leader removes concurrency, which simplifies design.
  • It can become a bottleneck once the work exceeds what it can handle.
  • It is a single point of failure with a large blast radius: if election breaks or the leader misbehaves, the whole system suffers.
  • The usual relief is partitioning, with a different leader per partition (many distributed data stores do this), at the price of more complexity.
  • Before adding a leader, check other ways: optimistic locking can give mutual exclusion at the price of wasted work.

A worked example. A job runner has 3 workers. Each tries PUT leader=worker-id IF absent TTL=10s. Worker 2 succeeds and renews every 3 s. At second 20 it freezes for 15 seconds. The key expires at second 30 (last renewal at second 20, plus 10). Worker 1 creates the key, receives fencing token 8 (worker 2 had 7). At second 35 worker 2 wakes and tries to write with token 7. The store has seen 8 and rejects it. Worker 2 renews, finds the key owned by worker 1, and returns to being a follower.

Common mistake

Believing that a lock or a leader check guarantees exclusive access at the moment of the write. Only a check by the resource itself (a fencing token) does.

Interview angle

Answer in your head first, then open it.

How does a cluster detect a dead node?

Heartbeats or pings with a timeout, tuned to measured latency, with a majority confirming. A perfect detector is impossible.

How do you prevent two leaders?

One vote per term and a majority (Raft), plus fencing tokens for outside resources.

What happens in a split vote?

Nobody wins, candidates time out at random different times and retry.

How would you add a leader to a service?

Use etcd or ZooKeeper with a lease, not hand-written code.

Downsides of leaders?

Bottleneck, single point of failure; mitigate with a leader per partition.

Check yourself:

  • Why is checking the lease just before writing not enough?
  • What two operations does a store need to offer so that a lease-based election works?

Words you will meet

Word Plain meaning
Failure detector Part of a system that guesses which peers are alive
Ping A periodic "are you there" request
Heartbeat A periodic "I am here" message
Leader election Choosing one process to be in charge
Safety Nothing bad happens, for example never two leaders
Liveness Something good eventually happens, for example an election ends
Raft A leader election and replication algorithm designed to be easy to understand
Follower, candidate, leader The three states of a Raft process
Term A numbered election period that only increases
Split vote An election round in which no candidate gets a majority
Election timeout How long a follower waits for a heartbeat before standing for election
Compare-and-swap Update a value only if it still equals what was expected
TTL Time to live, after which a key is removed
Lease A lock that expires unless renewed
Fencing token A rising number that lets a resource reject old leaders