Eviction and Priorities

Every decision so far has been made at the moment of placement: a pod lands on a node and stays there. Resource pressure, by contrast, is born after placement, and the decision-maker is no longer the scheduler. Once a node’s memory fills up, something has to be evicted, the node makes the eviction decision, and its input is the same two numbers from the first lesson: the declared request and the measured usage.

Here, for the first time, the delegated decision is irreversible. A wrongly placed pod fails to place and keeps waiting; a wrongly evicted pod is stopped while it is running. This lesson measures two things: which pod gets evicted under pressure, and, once a priority class is added, how many pods are affected by making room for a high-priority pod. What is measured is a model; the workload is the services of the regional measurement network (the running fiction).

Pressure Does Not Show in the Scheduler’s Ledger

The model has two nodes and seventeen pods. The nightly batch job’s two pods declare no request at all and use 1,400 MiB; billing and the reading collector run a little above their request, the verifier a little below. Eviction is tried with three separate sort rules.

// scheduling/eviction.mjs — eviction order under memory pressure. What gets built is a MODEL.
// When deciding who to evict, a node sees only the declared request and the measured usage.
export const MEMORY = 4096, NODE_COUNT = 2;
export const THRESHOLD = 0.9;            // SS19: memory pressure starts once occupancy exceeds 90%
const SEED = 20260803;

// name, count, request, actual/base factor, declared priority, actual criticality (unseen by the system)
export const SERVICE = [
  ["billing", 3, 512, 1.15, 900, 1], ["verifier", 4, 704, 0.90, 700, 2],
  ["reading-collector", 6, 384, 1.10, 500, 2], ["nightly-batch", 2, 0, 0, 100, 3],
  ["archive-scan", 2, 256, 1.00, 200, 3],   // SS21: a low-priority service that declares a request
];
export const BATCH_ACTUAL = 1400;   // SS20: a batch pod that declares no request uses 1400 MiB

export function workload(billingRequest = 512) {
  let s = SEED % 2147483647;
  const r = () => (s = (s * 48271) % 2147483647) / 2147483647;
  return SERVICE.flatMap(([name, n, req, factor, pri, crit]) =>
    Array.from({ length: n }, (_, i) => {
      const rq = name === "billing" ? billingRequest : req;
      const a = factor === 0 ? BATCH_ACTUAL : Math.round(req * factor * (0.95 + 0.1 * r()));
      return { name: `${name}-${i + 1}`, service: name, request: rq, actual: a, priority: pri, critical: crit };
    }));
}

export const place = (pods, n = NODE_COUNT) => {
  const d = Array.from({ length: n }, (_, i) => ({ name: `d${i}`, request: 0, pods: [] }));
  for (const k of pods) {
    const x = d.find((y) => y.request + k.request <= MEMORY);
    if (x !== undefined) { x.request += k.request; x.pods.push(k); }
  }
  return d;
};

export const usage = (d) => d.pods.reduce((t, k) => t + k.actual, 0);

// Three sort rules. Whoever sorts first gets evicted first.
export const RULE = {
  "highest usage": (a, b) => b.actual - a.actual,
  "request gap": (a, b) => (b.actual - b.request) - (a.actual - a.request),
  "priority + request gap": (a, b) =>
    a.priority - b.priority || (b.actual - b.request) - (a.actual - a.request),
};

export function evict(node, sortFn) {
  const target = MEMORY * THRESHOLD, evicted = [];
  const order = [...node.pods].sort(sortFn);
  while (usage(node) > target && order.length > 0) {
    const k = order.shift();
    node.pods = node.pods.filter((x) => x !== k);
    evicted.push(k);
  }
  return evicted;
}

if (process.argv[1].endsWith("eviction.mjs")) {
  const d = place(workload());
  console.log(`model: ${NODE_COUNT} nodes x ${MEMORY} MiB, ${workload().length} pods ` +
    `(seed ${SEED}); pressure threshold ${MEMORY * THRESHOLD} MiB`);
  d.forEach((x) => console.log(`  ${x.name}: ${x.pods.length} pods, request ${x.request} MiB, ` +
    `actual ${usage(x)} MiB, occupancy ${((usage(x) / MEMORY) * 100).toFixed(1)}%`));
  const s = (x, n = 17) => String(x).padStart(n);
  console.log(`\neviction order on d0 (until it drops to ${(MEMORY * THRESHOLD).toFixed(0)} MiB):`);
  console.log(`${"rule".padEnd(34)}${s("evicted")}${s("freed MiB")}${s("critical loss")}` +
    `${s("occupancy left")}`);
  for (const [ad, sortFn] of Object.entries(RULE)) {
    const x = place(workload())[0];
    const c = evict(x, sortFn);
    console.log(`${ad.padEnd(34)}${s(c.length)}${s(c.reduce((t, k) => t + k.actual, 0))}` +
      `${s(c.filter((k) => k.critical === 1).length)}` +
      `${s(((usage(x) / MEMORY) * 100).toFixed(1) + "%")}`);
  }
  const x = place(workload(640))[0];
  const c = evict(x, RULE["request gap"]);
  console.log(`${"request gap, billing request 640".padEnd(34)}${s(c.length)}` +
    `${s(c.reduce((t, k) => t + k.actual, 0))}${s(c.filter((k) => k.critical === 1).length)}` +
    `${s(((usage(x) / MEMORY) * 100).toFixed(1) + "%")}`);
  console.log(`\nevicted pods (rule: request gap): ` +
    place(workload()).slice(0, 1).flatMap((y) => evict(y, RULE["request gap"]))
      .map((k) => `${k.name}(${k.actual}/${k.request})`).join(", "));
}

model: 2 nodes x 4096 MiB, 17 pods (seed 20260803); pressure threshold 3686.4 MiB
  d0: 9 pods, request 4032 MiB, actual 6898 MiB, occupancy 168.4%
  d1: 8 pods, request 3136 MiB, actual 3266 MiB, occupancy 79.7%

eviction order on d0 (until it drops to 3686 MiB):
rule                                        evicted        freed MiB    critical loss   occupancy left
highest usage                                     3             3452                0            84.1%
request gap                                       3             3401                1            85.4%
priority + request gap                            3             3224                0            89.7%
request gap, billing request 640                  2             2800                0            89.7%

evicted pods (rule: request gap): nightly-batch-1(1400/0), nightly-batch-2(1400/0), billing-2(601/512)

Three Sort Rules, Three Separate Victims

The first two lines shown above explain why the decision falls to the node. In the scheduler’s ledger, d0 is full and consistent: 4,032 of the 4,096 MiB has been allocated, and no further pod is accepted for the remaining 64 MiB. Actual usage, however, is 6,898 MiB — 168.4 percent. The entire gap comes from the two pods that declare no request. The ledger is correct, the node is under pressure, and the component keeping the ledger has no idea.

The three rules evict three separate pods. The highest-usage rule takes the two batch pods and one verifier; it frees 3,452 MiB and loses no critical pod. The request-gap rule — which looks at how far usage exceeds the request — evicts billing after the two batch pods. The listing at the bottom shows why: billing declared 512 MiB and used 601, an 89 MiB overshoot; the reading collector declared 384 and used 422, a 38 MiB overshoot. The rule protects not the pod that declared more honestly, but the one whose declaration sat closer to its own request.

Once the priority class is added, the rule is fixed: one more declaration item per pod is added (seventeen items in all), and the critical loss drops from one to zero. The memory freed is 3,224 MiB instead of 3,401 — less — but in exchange, what gets evicted are the lowest-priority pods.

The fourth line gives the price of this information being a declaration. If billing’s request had been written as 640 instead of 512 — with nothing else changing, only the declaration inflated — the pod would appear to be under its request and would drop to the back of the eviction order: two evictions, zero critical loss. Inflating the request was capacity waste in the first lesson; here it is a protection device, and the system cannot tell the two apart.

Making Room and the Chain

Pressure is not one-directional. When a high-priority pod arrives and no node has room, the system makes room by its own hand: it evicts lower-priority pods. An evicted pod does not vanish; it goes back into the queue and can, in turn, evict one lower than itself. That is how the chain grows.

// scheduling/make-room.mjs — evicting a low-priority pod to make room for a high-priority one, and the resulting chain.
import { MEMORY, workload, place } from "./eviction.mjs";

// SS22: urgent billing pods arriving at midnight: priority 1000, request 700 MiB
const URGENT = (n) => Array.from({ length: n }, (_, i) =>
  ({ name: `urgent-billing-${i + 1}`, service: "urgent-billing", request: 700, actual: 700,
     priority: 1000, critical: 1, depth: 0 }));
const TURN_LIMIT = 60;                 // SS23: the chain is cut off at this turn count

// SS24: two node-selection rules — the node that evicts the fewest pods, or the first node that fits.
function makeRoom(incoming, rule) {
  const d = place(workload());
  const queue = [...incoming];
  let evictions = 0, chained = 0, deepest = 0, turn = 0;
  const unplaced = [];
  while (queue.length > 0 && turn++ < TURN_LIMIT) {
    const k = queue.shift();
    const free = (x) => MEMORY - x.request;
    const direct = d.find((x) => free(x) >= k.request);
    if (direct !== undefined) {
      direct.request += k.request; direct.pods.push(k); continue;
    }
    // For each node: how many pods must be evicted to make room. Only LOWER priority can be evicted.
    const plans = d.map((x) => {
      const candidates = x.pods.filter((p) => p.priority < k.priority)
        .sort((a, b) => a.priority - b.priority || a.request - b.request);
      let freed = free(x); const evicted = [];
      for (const p of candidates) { if (freed >= k.request) break; freed += p.request; evicted.push(p); }
      return { x, evicted, ok: freed >= k.request };
    }).filter((p) => p.ok);
    if (plans.length === 0) { unplaced.push(k); continue; }
    const p = rule === "fewest evicted"
      ? plans.reduce((a, b) => (b.evicted.length < a.evicted.length ? b : a))
      : plans[0];
    for (const c of p.evicted) {
      p.x.pods = p.x.pods.filter((y) => y !== c);
      p.x.request -= c.request; evictions++;
      if (k.depth > 0) chained++;
      c.depth = (k.depth ?? 0) + 1;
      deepest = Math.max(deepest, c.depth);
      queue.push(c);
    }
    p.x.request += k.request; p.x.pods.push(k);
  }
  const placed = incoming.filter((g) => d.some((x) => x.pods.includes(g))).length;
  return { evictions, chained, deepest, unplaced: unplaced.length, placed, turn: turn - 1 };
}

const s = (x, n = 16) => String(x).padStart(n);
console.log("making room: the urgent pod count is scanned (free capacity d0 64 MiB, d1 960 MiB)");
console.log(`${"rule".padEnd(16)}${"urgent".padEnd(8)}${s("urgent placed")}${s("evicted")}` +
  `${s("chained")}${s("deepest")}${s("unplaced")}`);
for (const rule of ["fewest evicted", "first fit"])
  for (const n of [1, 2, 3, 4, 5]) {
    const o = makeRoom(URGENT(n), rule);
    console.log(`${rule.padEnd(16)}${String(n).padEnd(8)}${s(o.placed)}${s(o.evictions)}` +
      `${s(o.chained)}${s(o.deepest)}${s(o.unplaced)}`);
  }

// The item the system does not see: actual criticality. The criticality mix of the evicted pods.
const o = makeRoom(URGENT(3), "first fit");
console.log(`\nfor three urgent pods, the 'first fit' rule: ${o.evictions} evictions, ${o.chained} chained, ` +
  `${o.unplaced} pods stranded; under the 'fewest evicted' rule, ` +
  `${makeRoom(URGENT(3), "fewest evicted").evictions} evictions`);
console.log(`declared priority items: 17 pods + the incoming urgent pods; measured criticality items: 0`);

making room: the urgent pod count is scanned (free capacity d0 64 MiB, d1 960 MiB)
rule            urgent     urgent placed         evicted         chained         deepest        unplaced
fewest evicted  1                      1               0               0               0               0
fewest evicted  2                      2               2               0               1               2
fewest evicted  3                      3               4               0               1               4
fewest evicted  4                      4               6               0               1               6
fewest evicted  5                      5              10               2               2               7
first fit       1                      1               0               0               0               0
first fit       2                      2               6               2               2               2
first fit       3                      3               9               4               2               4
first fit       4                      4              12               6               2               6
first fit       5                      5              15               8               2               7

for three urgent pods, the 'first fit' rule: 9 evictions, 4 chained, 4 pods stranded; under the 'fewest evicted' rule, 4 evictions
declared priority items: 17 pods + the incoming urgent pods; measured criticality items: 0

Same Outcome, Three Times the Disruption

A single urgent pod evicts nothing; the free request headroom is enough. From the second pod on, making room begins, and the two node-selection rules produce the same outcome at very different cost. The fewest-evicted rule makes two evictions for two urgent pods; the first-fit rule makes six evictions for the same two pods, two of which are chained. At five urgent pods the gap is ten evictions against fifteen, and the stranded-pod count is seven under both rules. The outcome is the same, the disruption is three times as large. Node selection looks like a placement detail, and it directly determines how many pods get restarted.

The chained column shows the delegation’s second cost: when an evicted pod returns to the queue, it triggers an eviction of its own, and the chain reaches a depth of at most two. The depth staying at two is not a design success but an accident. The ladder has six distinct priority values, and each rung can only evict rungs below it; the chain is cut off at the second step because the pods on the ladder’s bottom rung declare no request, and evicting them frees no room in the ledger at all. If the same model had a realistic request written onto the bottom pods, the chain would run one step longer — meaning the chain’s length is determined as much by the declaration itself as by the priority design.

The third and quietest result is the stranded pods. While five urgent pods get placed, seven pods are left without a node, and they never come back, because no evictable pod with lower priority remains. The nightly batch job’s pods never make room in this table at all: because they declare no request, evicting them frees zero MiB in the ledger. In reality 1,400 MiB is freed, but the room-making decision looks at the request, not at usage.

The decision rests on the seventeen pods’ priority declarations and the priorities of the incoming pods. The measured criticality item is zero. The system evicts billing not because it thinks billing is unimportant, but because it holds no item at all about its importance; a priority class is a declaration that fills this gap, and no measurement tests whether that declaration is true. When every pod is written with the highest priority, the ordering disappears entirely and the system falls back to the request gap.

Summary

• Memory pressure does not show in the scheduler’s ledger: d0’s ledger has allocated 4,032 of 4,096 MiB and is consistent, actual usage is 168.4 percent, and the gap comes from the two pods that declare no request.
• Three sort rules evict three separate pods: the highest-usage rule frees 3,452 MiB and loses no critical pod, the request-gap rule frees 3,401 MiB and evicts one critical pod, and once priority is added the critical loss drops to zero.
• The request-gap rule rewards whoever inflates their request: had billing’s declaration been 640 instead of 512, evictions would drop from three to two and critical loss from one to zero, with nothing actually changing.
• In making room, the node-selection rule determines not the outcome but the cost: for two urgent pods, the fewest-evicted rule makes two evictions and the first-fit rule makes six; at five pods it is ten against fifteen, with the stranded count at seven under both.
• Chaining tops out at a depth of two, bounded by the number of rungs in the priority ladder; pods that declare no request free zero MiB in the ledger and are therefore never used to make room.
• The decision rests on seventeen priority declarations, and the measured criticality item is zero; the source of a wrong eviction is not a bad rule but the absence of a single measurement that carries business value.

Next Step

These two lessons have shared out the cluster’s fixed capacity: who gets in where, and who gets evicted once it is tight. A third option was never asked — changing the replica count. The regional measurement network’s reading collector sees a load that fluctuates over the day, and as long as the replica count stays fixed, the price of that fluctuation is either spare capacity or a queue. This decision, too, can be delegated to a controller: a metric is watched, compared against a target, and the replica count is adjusted. The next lesson writes that controller and counts how the oscillation grows as the metric’s delay increases.