Stripe Automates Database Remediation with Graph Search and State Machines

A recent engineering effort at Stripe has led to the development of a system that automates database incident recovery. The team achieved this by modeling their global infrastructure as a graph, which enables them to use graph search algorithms in conjunction with state machines to compute and execute remediation plans automatically.

The previous hard-coded, plugin-based remediation system did not scale well due to its limitations. It required manual intervention for fragile dependencies, complex multi-failure scenarios, layout-specific logic, and unhandled intermediate states. This resulted in a significant number of pager alerts, with the control plane paged operators 124 times for misconfigured shards and 32 times for single-node-down scenarios complicated by additional health issues within a six-month window.

Critical operations like index builds and planned maintenance were frequently blocked for an average of one hour per incident. To address these limitations, Stripe’s engineering team decided to model their MongoDB infrastructure as a graph, where nodes represent infrastructure components, edges capture their relationships, and node attributes describe their current state.

The new system relies on graph traversal to identify valid recovery paths, allowing the same remediation logic to adapt automatically to different database layouts and evolving infrastructure. This approach eliminates the need for hard-coded remediation sequences and enables the system to dynamically respond to changing conditions.

Initially, Stripe used breadth-first search (BFS) to find valid remediation paths but later adopted Dijkstra’s algorithm to prioritize lower-cost recovery plans. Dijkstra’s algorithm explores all reachable states rather than just the goal state, allowing for partial remediation when no complete path exists. The algorithm returns the path to the least misconfigured state in such cases.

The team has also implemented a composable rules framework with explicit state transitions, enabling the planner to combine operations dynamically as infrastructure evolves. This approach enables the system to adapt to changing conditions and automate topology changes, blue-green deployments, and planned maintenance alongside reactive healing.

Stripe’s experience highlights the potential of using graph search and state machines for automating database remediation. The team plans to extend this framework beyond failure recovery to other areas of infrastructure management. Scott MacVicar, head of developer infrastructure at Stripe, notes that operating a global database fleet means accepting hardware degradation and unhealthy shards as daily occurrences.

The challenge is not just fixing issues but doing so without burning out on-call engineers. The engineering team’s efforts demonstrate the importance of automating repetitive tasks to reduce manual intervention and improve overall system reliability.