Automating Database Remediation with Graph Search and State Machines at Stripe
Stripe engineered a sophisticated system to automate database incident recovery, addressing the limitations of their previous hard-coded remediation logic. By modeling their global MongoDB infrastructure as a graph and employing graph search algorithms with state machines, they dynamically compute and execute remediation plans. This approach significantly reduced manual intervention and pager alerts, improving the reliability and operational efficiency of their database fleet.
Read original on InfoQ ArchitectureStripe faced significant operational challenges with manual and hard-coded remediation for their vast MongoDB infrastructure, leading to frequent pager alerts and prolonged downtime. Their original plugin-based system struggled with complex multi-failure scenarios, layout-specific dependencies, and unhandled intermediate states. To overcome this, Stripe reimagined their approach by leveraging graph theory and state machines for automated incident recovery.
Graph-Based Infrastructure Modeling
The core innovation involved modeling the entire MongoDB infrastructure as a graph. In this model:
- Nodes represent individual infrastructure components (e.g., MongoDB shards, replicas, instances).
- Edges capture the relationships and dependencies between these components.
- Node attributes describe the current state of each component.
Key Architectural Shift
This graph representation allows the system to understand the full topology and current health of the database fleet, moving beyond rigid, predefined recovery steps.
Graph Search for Remediation Paths
Instead of hard-coding remediation sequences, Stripe uses graph traversal algorithms to identify valid recovery paths. Initially, they used Breadth-First Search (BFS) but later adopted Dijkstra's algorithm. Dijkstra's offers a significant advantage by prioritizing lower-cost recovery plans, which reduces unnecessary operations and can even find partial remediation paths when a full recovery isn't immediately possible. This adaptability ensures the same logic can handle diverse database layouts and evolving infrastructure.
State Machines and Composable Rules
Remediation logic is modeled as composable rules with explicit state transitions. This state machine approach enables the planning engine to dynamically combine operations, rather than relying on fixed workflows. This allows the system to discover novel recovery procedures as infrastructure evolves, moving beyond the limitations of traditional runbooks which only encode known recovery steps. The system has reduced database-related pager alerts by 30%, saving 200 pages annually and eliminating 12 days of unhealthy shard states.
Stripe plans to extend this framework beyond failure recovery to automate topology changes, blue-green deployments, and orchestrate planned maintenance alongside reactive healing, highlighting the versatility of this architectural pattern for complex distributed infrastructure operations.