Anurag’s Read

How Stripe uses graph search and state machines to auto-remediate a global database fleet.

It reframes database repair as a graph search problem and explains why a fixed state machine broke down. The details on safety rules, simulation that shares code with production, and Dijkstra weights transfer to any automation that must pick a safe order of actions.
Score
8.7
Verdict
Must read
Blog and date
Stripe,
Original length and level
12 min, advanced
Topics
databases, automation, reliability, algorithms
Read the original

Context

Stripe's Document Database fleet has about 2,000 MongoDB shards and 40+ shard layouts. These shards processed $1.9T in payments in 2025. A person needed about 15 minutes to order the fixes for a degraded shard. Running the operations took up to 3 hours. The first automation was a hard-coded state machine with plugins in a fixed order. Combined failures broke it, and it paged operators.

Architecture

A planner models a shard as a graph. Each node is a shard state. Each edge is one atomic operation. Operations include vote and priority changes, hide and unhide, node rebuild, and oplog resize. The start is the observed ground reality, and the goal is the Source of Truth (SOT). The planner generates successor states, drops invalid ones, and searches for the cheapest path.

Temporal runs the chosen operations as durable workflows. A CommonContext interface lets the same code run in production or in simulation.

Mechanisms

M1

Invalid states

Safety invariants mark states invalid. An even voting count is invalid. A minority of healthy voters is invalid, because it risks write availability. A node with priority 1 and zero votes is invalid.

M2

BFS then Dijkstra

BFS returns the shortest path in operation count, but it returns nothing when the full goal is unreachable. Dijkstra explores all reachable states. When the goal is unreachable, it returns the path to the least misconfigured state. It fixes what it can and leaves the rest to an operator. The edge weight equals state misconfiguration times estimated operation time. Relative costs are 3 for a config update, 19 for an oplog update, and 101 for a node rebuild.

M3

Misconfiguration score

Each rule is a function of the current state and the SOT that returns an integer. Rules cover down node, voting, priority, oplog resize, hidden status, and availability zone imbalance. A curried closure, GetMisconfigFunc, binds the SOT once and sums the rules fast. Logs show each rule's part at each step.

M4

CommonContext simulation

Remediation steps are Temporal activities that do real I/O, so a search over them would take minutes per path. CommonContext offers ExecuteActivity, ExecuteLocalActivity, ExecuteWorkflow, and WithExternalDeps. In production it calls Temporal. In simulation, WithExternalDeps injects simulated providers with in-memory shard state. Operations become pure state changes, and hundreds of transitions run per second.

Design decisions

No.ChoseInstead ofWhy
D1Search over operation sequencesStatic ordered plugins and greedy single fixesPlugins had circular dependencies, missed multiple failures, and tied safety checks to each layout.
D2Use Dijkstra with weighted edgesBFS onlyBFS fails when no full healthy path exists, and Dijkstra gives partial remediation.
D3Run the real business logic in simulationA separate plannerOne code path stops the planner and the executor from drifting apart.

Key numbers

  • The fleet has about 2,000 shards, 40+ layouts, and $1.9T in 2025 payments.
  • Over six months the old system paged 124 times for misconfigured shards and 32 times for single-node cases.
  • The new system cut pager volume by about 30%, roughly 200 pages per year.
  • Shards save about 12 days per year in unhealthy states.
  • A node rebuild costs 101, about 33 times a config change at 3.

Failures and limits

  • The old system deadlocked on circular plugin dependencies, multiple failures, and states left by canceled workflows. Each new layout took about a week.
  • The new scoring weights are relative, and the post shows no validation. The post shows no incident review of the new system.

Lessons you can use

  • Treat remediation as a search problem with explicit invariants. Return the best partial fix when a full fix is not reachable.
  • Run the same code in plan and execute modes. Use durable workflows for operations that last hours.

Glossary

ShardOne slice of a database that holds part of the data.
QuorumThe majority of voting nodes needed to accept writes.
OplogThe MongoDB log of writes that replicas copy.
TemporalA workflow engine that keeps long tasks running through crashes and deploys.