Towards Designing an Execution Control System with Metastability Resilience

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?

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).

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.

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.

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?

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.

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!

Our first dynamic policy was reasonable-sounding: each queue independently probes its ticket count up and down, keeping changes that improve the ticket-acquisition rate, an easy-to-observe quantity that intuitively tracks throughput.

However, it turns out under overload, the ticket-acquisition metric lies. A ticket bounds wall-clock time, not the CPU time. With one core and two tickets, each task gets 5ms actual runtime in its 10ms window. (You want some concurrency to avoid IO blocking, and to enable CPU to be productive by switching to another task). Now, consider one core and ten tickets: each task gets about 1 ms of CPU and 9 ms of waiting inside its 10 ms window, then each releases the ticket to re-acquire it later.  Although the ticket acquisition rate scaled by 5x here, the actual progress is capped at most at 10 ms of service per 10 ms, no matter how many tickets you issue. That means, the metric was not actually measuring progress, but it was measuring churn.

So under overload, the long queue, which always has a deep wait set under overload, inflated its tickets to pump its metric. The extra threads crowded the shared CPU, which made the short tasks start to queue up, which caused the short queue inflate its own tickets in response. Each policy's corrective action degraded the other's environment, which triggered more corrective action. The escalation stopped only when the long queue hit its static ticket cap. That cap did not fix the feedback loop, but it just put a ceiling on how bad the loop could get. This is how easy it is for a metastability failure to raise out of two individually sensible controllers. Metastability often happens to reasonably designed systems whose parts are reasonable separately.

The fix we applied is to freeze the long queue's tickets at a low static value and probe only the short queue. This leaves a single decision site: with one controller instead of two, there is no race between competing corrections. However, starving the long queue would waste capacity in light load, so we compensated by making the demotion threshold dynamic, again with one rule. If the short queue is empty, raise the demotion threshold by 10% (let longer tasks enjoy high priority while there is room), and if there are any tasks waiting in short queue lower the threshold by 10% (demote more aggressively, protect the fast lane).

Note what changed. The control signal went from a gameable one (acquisition rate, inflatable by churn) to an ungameable one (is anyone actually waiting). And instead of two controllers fighting over a shared resource, there is one controller and one signal.

Admission control can also interfere

A typical deployment puts an admission control service in front of the database, rejecting requests when a latency signal exceeds a limit. Our experiments also found that admission control and the ECS destructively interfered.

Here is the intuition. Admission control cannot tell short tasks from long, so it sheds indiscriminately, dropping exactly the short tasks the ECS exists to protect. Worse, the latency signal it relies on can be corrupted by the ECS: a genuinely short task that accrues queueing delay gets demoted and exits the system labeled long, so the short-task latency metric looks healthy precisely when short tasks are suffering. Therefore the control loop at the admission control and the ECS, reacting at similar speeds to each other's output, can produce a sawtooth oscillation where goodput never reaches what the ECS achieves alone. These two well-meaning defenses, each individually stabilizing, jointly do worse than either.

After identifying the problem, the fixes are easy. Here are what the potential fixes would look like. Stop guessing from the outside, and have the ECS export a distress signal (short tasks hurting, and my own knobs are exhausted), and let admission control reject only while that signal is up. Or make the outer admission control loop deliberately sluggish, an order of magnitude slower than the ECS's own convergence time, so the two controllers cannot destructive interfere in resonance sawtooth manner (i.e., the outer defense should engage only after the inner defense has demonstrably run out of moves). 

So what?

I have two takeaways from the project.

First, performance IS availability. We are used to treating them as separate concerns, one for the performance team's dashboards and one for the postmortems. But metastability erases that boundary, as it can turn a performance problem into an availability problem under certain conditions. These failures live on a spectrum rather than a binary outcome, and traditional formal methods, which excel at safety and correctness, are not built to capture that complexity.

Second, you should simulate before you deploy. Simulations explore many failure modes quickly, and more importantly they surface behaviors you did not think to test for (nobody writes a unit test for "the metric rewards churn"). And simulation is cheap. One person working a few hours per week can model a lot (especially with MESSI). If you don't do the simulations, the alternative is discovering your feedback loops in production.

The composition problem

I want to end with a decompositional framing investigation of the problem. Both failures we described arose from composition. Each component's corrective action degraded its neighbor's operating conditions, and after a shock, neither could stabilize because neither's assumptions held while the other was also trying to "recover". 

Last week, I reviewed a recent line of work that frames metastability exactly this way, as a sin of composition among individually self-stabilizing components. Each component gets a potential function, a measure of its distance from a good state that its corrective actions are supposed to decrease, plus an explicit statement of the environment it assumes while correcting. A metastable fault arises when components are wired so that one's correction raises another's potential, and the fault becomes a failure when the schedule keeps selecting those destabilizing interactions.

Let's reposition our results back through that lens. Ticket-acquisition rate was an invalid potential function: it improved while the true distance from health grew, because churn inflates it. Wait-set occupancy, the signal behind our threshold fix, is a valid one: it is zero exactly when short tasks are fine, and no amount of churn can fake it. And the fix itself is a layered composition: Freezing the long queue's tickets deleted one controller's ability to disturb the shared resource. Gating the threshold-raise on "short wait set empty, and it has stayed empty" means the upper layer acts only after the lower layer has demonstrably converged. That is healing bottom-up.

The same recipe suggests a principled fix for the admission control interference: have the ECS export a distress bit (short tasks hurting and my own knobs are exhausted) instead of letting admission control infer health from a corruptible latency signal, and make the outer loop deliberately slower than the inner loop's convergence time so the two cannot resonate. 

Note that the theoretical framework tells you what properties a good potential function must have, but it cannot provide you one. And it is tricky to find the right metric. We found the right signal by watching the whole system lie to us in simulation. It would not be possible to find it by local reasoning about components. The theory names the sin of composition, but only the simulation catches you when and how that sin manifests.