Evict the guilty, not the innocent

I.The problem

A node dies. Its pods are evicted and reapply for space that no longer exists. With spare capacity any policy succeeds; the interesting case is shortage, and Kubernetes offers two answers to it.

The default scheduler is blind to importance. It seats whatever fits, first come first served, and never evicts anybody, so a low-value pod that got there first keeps a seat a critical service needs.

PriorityClass preemption reads rank, and only rank. It saves the highest-priority pods and throws healthy lower-priority pods out to make room. The ordering is lexicographic, so no number of importance-8 pods outweighs one importance-9 pod, whereas for most operators importance adds up.

Both share a deeper flaw. An importance label says what a pod is worth, not whether it will serve. A crash-looping pod labelled critical holds scarce recovery capacity for the whole horizon and delivers nothing, and any scheduler that trusts the label inherits that lie.

II.What I built

I treated recovery as a selection problem rather than an ordering one: fit the most total importance into the space that is left. That is a knapsack, and at recovery scale it is solved exactly, by branch and bound over a node-or-leave-out choice per pod. The solver's own exactness certificate is enforced rather than assumed, so a truncated search is refused instead of quietly reported as optimal, and an integer-programming fallback runs when branch and bound exhausts its budget. Capacity is a hard invariant re-checked outside the policy, so a buggy policy can be suboptimal but never unsafe.

The AI leg is deliberately small. Eight signals the kubelet already reports for a service's existing replicas feed a logistic regression that estimates the probability a newly placed replica will be Ready over the horizon: the Ready fraction, the crash-loop fraction, the restart rate, the worst restart count, the fraction with a non-zero last exit code, median pod age, and a never-Ready flag with its age. That estimate multiplies into the value the knapsack maximises.

So the scheduler maximises expected delivered importance instead of labelled importance. A service with too few observations gets no discount at all, which means that on a healthy cluster this arm's decisions are identical to the label-trusting one.

The same discount is what makes eviction defensible. Run over occupied capacity as well as free, the rule evicts a running pod only when it has been measured failing to serve and the swap clears a fixed margin, half the smallest unit on the importance scale. Keeping everything is always feasible, so the arm is never worse than not evicting in its own estimated objective. PriorityClass evicts whatever ranks lowest; this arm evicts only what it has measured failing.

Eviction has a side effect I had not anticipated and that the literature does not name. Evicting a crash-looper hands its controller a fresh replacement with a clean record, so a scheduler that only re-reads current status re-trusts the replacement and evicts a healthy pod to seat it again. The fix is belief persistence: the scheduler keeps its measured estimate for an evicted service and prices the respawn with it until fresh evidence supersedes it. The belief yields to measurement, never to a clock.

III.Method

Everything reported comes from Amazon EKS. A local kind cluster of the same shape rehearsed every mechanism first and is never a source of a reported number.

Two failure conditions. Stop: an abrupt EC2 power-off of one workload node, with Kubernetes' real unreachable toleration, on a cluster packed so that the survivors are short. Pod kill: a seeded deletion of 30% of replica slots with zero grace, which frees the victims' own capacity and so isolates recovery ordering and speed rather than shortage.

Workloads are drawn from the Alibaba 2018 cluster trace, twelve services per block, with nine importance grades. The grade is the weight, so a grade-9 replica counts nine times a grade-1 replica, and the same integers serve as the solver's objective and the metric's weights. Every comparison is within-block: all four arms see the same workload, the same victim node and the same pinned starting placement, verified by fingerprint before aggregation, in Latin-square order.

The primary metric is weighted completion at the horizon: the importance-weighted count of Ready replicas as a fraction of the healthy cluster's. Healthy pods evicted are reported beside every score, because the score charges a denied pod the same as an evicted one and I wanted the collateral visible on its own axis.

The analysis plan was registered before any confirmatory data and froze when the first noise floor was measured. For each cell: a stage-one floor, the untreated default arm repeated six to eight times; the minimum detectable effect that floor buys at the affordable block count; then the blocks. A result below the certified detectable effect is claimed in neither direction. A cell whose floor fails is demoted to descriptive readings, which happened once.

IV.Results

A. The foundation: selection against order

Over eighteen real node kills with honest services, the selection rule beat the importance-blind default by 5.8 points (95% interval 4.2 to 7.5, t = 7.43, p < 10⁻⁶), eighteen wins of eighteen, with its median first bind six seconds later because the batching is charged against it. PriorityClass led on the single completion axis, 3.6 points over selection, and paid 86 healthy evictions to do it against selection's zero. That trade is the frontier the whole study reads: completion against healthy pods destroyed.

B. The headline: labels that lie

In the always-down world every grade-9 service crash-loops permanently, so the top-graded claimants are the fakes. One test, fixed before the cell's data: the AI arm against its own decision core, the label-trusting knapsack. The difference was 12.9 points (95% interval 6.4 to 19.4, t = 5.52, p = 0.005), the AI ahead in every block, against a certified detectable effect of 1.4 points. The offline prior, written down weeks before the run, was 12.7. The AI arm kept 94.0% of important work running with seven healthy evictions across the cell. PriorityClass kept 83.2% with 28.

C. Who got evicted

All 39 evictions the AI arm made across the two lying-services cells, from the decision log. 23 struck services its evidence priced below 0.25, one a flaky service at 0.23, and 16 were healthy pods: grade 1 or 2 batch pods, plus a single grade 3. No healthy pod above grade 3 was evicted in either world. Every eviction carries an exact enumeration certificate. The arm reached its registered cap of four evictions per run in nine of the ten runs, so the cap bounded both its gain and its collateral.

D. The trap, and the control

In a queue whose highest-labelled claimants are all fakes, the label-trusting knapsack finished last, below the blind default. With a queue watching every vacancy, rank hands each seat to the best label, and when the best labels are lies that is worse than ignoring them. The AI arm returned to the top, narrowly: 1.6 points over the default, three blocks of five, and no test is attached.

With 30% of pods killed and room to spare, every scheduler recovered everything. The selection arm sat 0.31 points of downtime above the others, the measured cost of its planning batch when choosing buys nothing. The wins in every other cell come from the shortage.

E. How much model the decision needs

On the recorded decisions of both lying cells, trusting labels seated 23.4 importance units per cycle in the always-down world. A tuned one-feature threshold rule, that rule with fitted leaf probabilities, and the full logistic model each seated 28.4, against an oracle 28.8. Measuring at all is the step that pays. The logistic model ships because it is the smallest rung that is also calibrated.

V.Threats to validity

Scale

Three workload nodes, one cloud, one instance type, one trace-derived workload. An offline simulator projects larger clusters and no finding rests on it, though its predicted arm orderings matched the campaign's exactly in both cells where that could be checked.

Staging

Shortage is engineered and the lying services are registered kinds, not natural failures. The estimator was trained on a four-behaviour taxonomy and tested against injected instances of it, so the second question measures in-distribution estimation.

Instrument constants

The eviction cap of four per run and the 0.5 margin were pre-set and bound in eighteen of the AI arm's twenty runs, so its gain and its collateral are floors, not the arm's ceiling. A later simulated probe placed the margin off the tuned frontier on the permissive side.

A noisy cell

The graded lying-services floor was eleven times noisier than the honest one, so that cell is descriptive by the registered demotion and carries no test.

The proxy

Ready is an API-side signal, not proof of serving. Per-tier request failure rates from the load generator bound the drift; at the median they do not flatter the treatment arms.

The value model

Value accrues while serving, so the model addresses long-running services and not run-to-completion jobs. The findings are conditional on importance adding up: in offline replay, selection stops dominating order near a grade-to-grade weight ratio of 1.35.

VI.What I took from it

Two things travel beyond the dissertation. The first is that a controller acting irreversibly on measured evidence destroys the evidence that justified the action, and has to remember. Kubernetes' own descheduler has this bug in the open: its restart-count plugin evicts a pod and thereby resets the count it was reading. Circuit breakers and mesh outlier detection have the same shape and end their hold-out on a timer. Here it ends on measurement.

The second is the method. Every number on this page traces to a run record through a receipts index, the analysis plan was committed before the data with every amendment dated, and a result below the floor's detectable effect is not claimed in either direction. It is the same rule the rest of this site runs on: a number is shown with what produced it, or not at all.

Artefacts

1. [1]PaperIEEE format, eight core pages. ECS8056, Queen's University Belfast.
2. [2]Analysis planRegistered before the confirmatory data, with every amendment dated. It froze when the primary noise floor was measured.
3. [3]Receipts indexClaim → script → artifact, for every quantitative claim. Every number on this page has a row.
4. [4]Run records199 recorded runs on EKS. Each carries its seed, workload hash, victim, pinned start fingerprint and health-model hash.
5. [5]CodePython 3.14. Scheduler, experiment driver, workload generator, stats, and the test suite. Private until the viva; ask me for a walkthrough.