How Stripe uses graph search to repair database fleets

// the short version

A replicated database keeps each shard on several machines and lets exactly one

// what to take away

• Replica-set repairs are constrained state transitions, not a linear checklist of commands.
• Stripe models legal configurations as graph nodes and safe operations as edges between them.
• Shortest-path search can produce a repair plan while excluding unsafe states from consideration.

// transcript

Somewhere right now, a database is holding an election. Not a metaphor. Machines are casting votes, and if the vote fails, your payment doesn't go through. Stripe fixes the failed ones with a maze-solving algorithm. First, the vote. Every serious database keeps each piece of data on several machines at once, so a machine dying loses nothing. But copies only help if they agree, so exactly one takes writes. That's the leader. The rest copy it. The leader is a machine, and machines die. If the survivors just carried on, two might each take different writes, and now there are two versions of the truth. That is the one thing a database must never do. So when the leader goes quiet, the survivors hold an election. A candidate wins by collecting a majority of the votes. The majority is the whole trick. Any two majorities of the same group share at least one machine, so if a network fault splits five machines into three and two, only the side with three can elect anyone. Two leaders isn't forbidden by a rule. It's forbidden by arithmetic. It only works while a majority is alive and voting. Lose too many machines, or misconfigure who votes, and a shard, one slice of the data, can't elect anyone. The database isn't down. It just can't agree on who's in charge. Stripe's first answer was a ranked list of fixers, most important first. But the order is a lie. The vote fixer won't run while a machine is down, and it outranks the fixer that brings machines back, so a shard with both problems deadlocks. In six months that paged a human more than a hundred times. So they threw the list away and drew a graph instead. Every node is one configuration of the shard: who's up, who votes, who leads. Every edge is a single operation you're allowed to run. A configuration that breaks a safety rule isn't a node you're forbidden to visit. It isn't on the graph at all. Which turns repair into routing: find a path from here to healthy. Their first search was breadth first: everything one operation away, then two, then three, which finds the fewest steps and orderings nobody ranked: fix the vote first, because it restores a majority and unlocks the rebuilds. But breadth first wants the goal or nothing. A shard with a machine nothing can talk to has no path to perfect health, so it came back empty, even though the missing vote beside it was one operation away. So they swapped it for Dijkstra and put a price on every edge: how wrong the state you're leaving is, times how long the operation takes. A vote change costs seconds. A rebuild costs an hour. So it stops hunting for perfect and returns the closest state it can reach: fix the vote, and leave the unreachable machine for a person. Pages dropped by 30 percent. Nobody writes the repair steps any more. They describe what healthy means, and the search works out how to get there.