---
title: 'Eviction and Priorities'
source: 'https://academia.sh/en/courses/orchestration/eviction-and-priorities'
course: 'Container Orchestration'
language: en
updated: '2026-09-13T05:08:28+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - 'Models the eviction order under memory pressure and compares three sort rules by their outcomes'
    - 'Counts how many pods making room affects and how many times chaining occurs'
    - 'Measures how many times more disruption the node-selection rule produces for the same outcome'
    - 'Names the item the system cannot see and ties the wrong eviction to that item'
---

# Eviction and Priorities

Modeling behavior under resource pressure: computing the eviction order under memory pressure for pods below their request, above their request, and with no request at all; three sort rules that evict different pods; how many pods a priority-class addition affects when making room and how many times the chain grows longer; and the system evicting the wrong pod because of the item it cannot see.

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.

```js
// 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.

```js
// 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.