CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 6 of 8 · 3 min read

Leader failure and failover

Choosing a new leader, and the many ways that can go wrong.

Think of a school where the head teacher falls ill. Someone must be chosen to run the school, the staff must be told, and the old head, if they return, must not try to give orders as well. Choosing the wrong deputy, or having two heads at once, causes chaos.

Failover

Failover is the process of promoting a follower to be the new leader after the old leader fails, redirecting clients' writes to it, and making the other followers copy from it.

Example: the leader's machine loses power. Within 30 seconds, follower B is promoted, and the application sends writes to B.

The book lists the steps in an automatic failover.

  1. Detect that the leader has failed. There is no sure way to tell a crash from a network fault or overload, so most systems use a timeout. If a node does not answer for, say, 30 seconds, it is assumed dead.
  2. Choose a new leader. Either by an election among the remaining replicas, or by a controller node chosen earlier. The best candidate is usually the replica with the most recent data from the old leader, to lose as little as possible. Getting nodes to agree is a consensus problem [getting several nodes to agree on one value, covered in a later level].
  3. Reconfigure the system. Clients send writes to the new leader. If the old leader returns, it must realise it is a follower now.

The book then lists what can go wrong.

  • Lost writes. With asynchronous replication, the new leader may lack some writes of the old leader. If the old leader rejoins, the usual solution is to discard those writes. This can break the promise made to clients that confirmed data is durable.
  • Damage outside the database. The book relates an incident at GitHub. An out-of-date MySQL follower was promoted. Its counter for new primary keys was behind, so it reused keys the old leader had already assigned. Those keys were also used in a Redis store, and the clash caused some private data to be shown to the wrong users.
  • Split brain. Two nodes both believe they are the leader. If both accept writes and nothing resolves conflicts, data is lost or corrupted. Some systems shut one node down when they find two leaders. This is called fencing, or more emphatically "shoot the other node in the head". If it is poorly designed, both nodes can end up shut down.
  • The timeout. A long timeout means a long outage when the leader really fails. A short one causes needless failovers: a load spike or a network hiccup can push the response time over the limit, and a failover under load makes things worse.

A worked example of the timeout. The leader pauses for 20 seconds because of a long clean-up. With a timeout of 10 seconds, a failover starts for a leader that was only slow. The old leader comes back and a new one is already in place. With a timeout of 60 seconds, a real crash leaves the database unable to take writes for 60 seconds plus the election time. At 500 writes per second, that is 30,000 writes that failed or waited. The right value depends on how long pauses last in the system and how costly an outage is.

The book concludes that there are no easy solutions, and that some teams prefer to fail over by hand, even when the software can do it automatically.

Failure Detect by Recovery Main risk
Follower Missed heartbeats Catch up from the log Little
Leader Timeout Failover Lost writes, split brain, wrong timeout
Network between leader and followers Timeout Depends Looks like a leader failure

Check yourself:

  • Why do most systems use a timeout to decide that the leader is dead?
  • What is split brain, and why is it dangerous?