Towards Designing an Execution Control System with Metastability Resilience
Skip to main content
Towards Designing an Execution Control System with Metastability Resilience
Get link
Other Apps
August 02, 2026
This week, I presented this paper at ICCCN'26. This is joint work with Aleksey Charapko (University of New Hampshire) and my MongoDB colleagues Matt Broadstone, Daniel Gomez Ferro, and Akshat Vig. The paper investigates how to build a metastability tolerant execution control system (ECS) for a database.
Why?<br>Modern databases are complex networked systems serving mixed workloads: short queries (that want an answer in milliseconds) sitting next to analytics jobs (that want the CPU for multiple seconds). The arrival rate of requests is effectively unbounded, but of course, the server's resources are not. And, unfortunately, elastic scaling does not save you here. Scaling takes minutes, whereas, overload takes seconds. Admission control tries to guard the front door (more on this later), but the component that mediates contention once requests reach the backend is the execution control system (ECS).<br>Unlike a closed system OS scheduler, which strives for fairness and completeness by giving runtime for every thread, faced with an open environment the ECS can only afford to protect short latency-sensitive queries and shed the excess, pushing the burden of waiting back across the network to the clients. This doesn't mean that long tasks are starved, as they can retry until capacity permits execution.<br>However, shedding load across a network is risky business. Clients do not see the server slow down, instead they time out and retry aggressively. Moreover, workloads are also unpredictable. A query that looks short may hang on a lock or blow up into a scan. The combination of delayed signals, retries, and misclassification makes the cloud databases a fertile ground for failures.<br>The specific failure we worry about here is metastability: the system gets pushed into a degraded state, and the degraded state sustains itself even after the original trigger is removed. The mechanisms you build for resilience (the retries and the queues) turn into positive feedback loops after a trigger (overload, cache failure, etc). This is not a rare exotic problem. Since production systems would have already been hardened to handle the obvious failures, what remains is these hard-to-detect emergent failures. The OSDI'22 study, where Aleksey was a coauthor, collected 22 metastable incidents across 11 organizations and found that at least 4 of the 15 major AWS outages in the preceding decade were metastable failures, with durations running from 1.5 to 73 hours. Retries were the sustaining mechanism in more than half of the studied incidents. There is no single reset button in a distributed system, so the ECS must break the feedback loop without things escalating into metastable failures.
What?<br>The ECS mechanism looks deceptively simple. A ticket is a permit to occupy a thread, and there are fixed ticket pools that cap concurrency. If a task cannot get a ticket, it queues up. There are two queues: high priority for short tasks, low priority for long ones. Since you cannot classify a task's cost a priori (the query optimizer's estimate is merely a suggestion), every task starts in the high-priority queue and gets demoted only when it proves itself long by exceeding the brief execution time assigned to short tasks. The queues are bounded, and when they fill, we shed tasks. Shed happens (pun intended!) either at the entry or at mid-stream at the demotion time.
However, the trouble starts in the execution of the policy, deciding how many tickets each queue gets and where the demotion threshold sits. Production systems are too complex, and metastable failures are too well hidden during normal operation, so these prevent us to tune things by trial and error. So we need to trace how overload propagates through queues and retry logic before deployment.<br>To address this problem, we (well, Aleksey Charapko) built MESSI (MEtaStability SImulator), a discrete-event simulator written in Go. MESSI models a system as a graph: Logic Nodes hold the decision logic (where this work goes next), and Processors simulate execution (delays for both service time and queuing time). The runtime is scriptable, so you can inject failures, slowdowns, and configuration changes mid-run and watch how the system responds. MESSI proved to be crucial for our exploration of the ECS design space, which is full of interacting variables and hidden feedback loops. Without cheap rapid iteration we would not have isolated the mechanisms that matter for metastability tolerance. (I talked about MESSI earlier last month, when making a case for simulation-driven resilience for agentic data systems.)
We discovered a metastable behavior!<br>Our first dynamic policy was reasonable-sounding: each queue independently probes its ticket count up and down,...