Scheduling Constraints

The previous lesson’s scheduler asked a single question: does the remaining request suffice. Placement has other sides, and none of them concern capacity. Having the verifier run on nodes with a fast disk, keeping two copies of the same service from piling onto one node, keeping billing on the same node as the verifier, guaranteeing a surviving copy after a zone is lost — each of these turns a node with sufficient capacity into an ineligible one.

These constraints turn the scheduler into a constraint solver. The decision stays the same (which pod goes to which node), but it is now made within a search space: for each pod, the eligible node set is computed first, and then one node is chosen from that set. If the set empties out, no decision can be made and the pod does not get placed. This is what this lesson measures: how much the set narrows as constraints are added, and at what point it empties out.

The model is nine nodes spread across three zones; the workload is three services of the regional measurement network (the running fiction). No real cluster runs.

The Constraint Solver and the Eligible Node Set

Four kinds of constraint are added cumulatively. Label selection requires one of the node’s labels, affinity requires the presence of another service, anti-affinity requires the absence of the same service, and topology spread bounds the replica-count difference across zones. The selection rule is the same as in the previous lesson: the first node in the eligible set.

The constraints are written with our own small schema. A node declaration carries two labels: zone and disk type. A pod declaration places a constraint with three fields — the disk field requires the node’s disk label, the antiAffinity field asks for a node with no copy of the same service, the affinity field asks for a node where the named service is present. Topology spread belongs to the solver, not the pod, and is tuned with a spread count. The solver reads nothing beyond these fields; whatever it does not read, however real it is on the node, lies outside the decision.

// scheduling/constraint.mjs — the scheduler as a CONSTRAINT SOLVER. Not a real cluster, a model.
// Constraints are added cumulatively; the shrinking of the eligible node set is measured at each stage.
export const ZONE = ["b1", "b2", "b3"];
// SS7: three zones x three nodes, 1500 cpu units per node
// SS8: a fast disk only on the first node of each zone
export const NODES = ZONE.flatMap((b, i) =>
  [0, 1, 2].map((j) => ({ name: `${b}-d${j}`, zone: b, disk: j === 0 ? "fast" : "standard",
                          capacity: 1500 })));

// SS9: workload — the verifier wants a fast disk, billing wants the verifier's node
export const WORKLOAD = [
  { service: "verifier", replicas: 6, unit: 650, disk: "fast", antiAffinity: true },
  { service: "billing", replicas: 3, unit: 300, affinity: "verifier", antiAffinity: true },
  { service: "reading-collector", replicas: 9, unit: 420 },
];

export const expandPods = (load = WORKLOAD) => load.flatMap((s) =>
  Array.from({ length: s.replicas }, (_, i) => ({ ...s, name: `${s.service}-${i + 1}` })));

// SS10: topology spread — a service's replica-count difference across zones is at most 1
export const SPREAD = 1;

export function solve(constraint, load = WORKLOAD, nodes = NODES) {
  const state = nodes.map((d) => ({ ...d, used: 0, pods: [] }));
  const zoneCounts = new Map();          // service -> zone -> count
  const unplaced = [];
  const eligibleCounts = [];
  const count = (s, b) => (zoneCounts.get(s) ?? {})[b] ?? 0;

  for (const k of expandPods(load)) {
    const eligible = state.filter((d) => {
      if (d.used + k.unit > d.capacity) return false;
      if (constraint.label && k.disk && d.disk !== k.disk) return false;
      if (constraint.antiAffinity && k.antiAffinity && d.pods.some((x) => x.service === k.service)) return false;
      if (constraint.affinity && k.affinity && !d.pods.some((x) => x.service === k.affinity))
        return false;
      if (constraint.topology) {
        const min = Math.min(...ZONE.map((b) => count(k.service, b)));
        if (count(k.service, d.zone) + 1 - min > SPREAD) return false;
      }
      return true;
    });
    eligibleCounts.push(eligible.length);
    if (eligible.length === 0) { unplaced.push(k); continue; }
    const d = eligible[0];               // first-fit node: the rule never looks back
    d.used += k.unit; d.pods.push(k);
    const m = zoneCounts.get(k.service) ?? {};
    m[d.zone] = (m[d.zone] ?? 0) + 1; zoneCounts.set(k.service, m);
  }
  return { state, unplaced, eligibleCounts, zoneCounts };
}

export const distribution = (o, service) =>
  ZONE.map((b) => (o.zoneCounts.get(service) ?? {})[b] ?? 0);

const STAGE = [
  ["capacity only", {}],
  ["+ label selection", { label: 1 }],
  ["+ affinity", { label: 1, affinity: 1 }],
  ["+ anti-affinity", { label: 1, affinity: 1, antiAffinity: 1 }],
  ["+ topology spread", { label: 1, affinity: 1, antiAffinity: 1, topology: 1 }],
];

if (process.argv[1].endsWith("constraint.mjs")) {
  const total = WORKLOAD.reduce((t, s) => t + s.replicas, 0);
  console.log(`model: ${NODES.length} nodes / ${ZONE.length} zones, ${total} pods, ` +
    `fast-disk nodes ${NODES.filter((d) => d.disk === "fast").length}`);
  const s = (x, n = 15) => String(x).padStart(n);
  console.log(`${"stage".padEnd(22)}${s("avg eligible")}${s("min eligible")}${s("placed")}` +
    `${s("unplaced")}${s("busy nodes")}`);
  for (const [ad, constraint] of STAGE) {
    const o = solve(constraint);
    const avg = o.eligibleCounts.reduce((t, x) => t + x, 0) / o.eligibleCounts.length;
    console.log(`${ad.padEnd(22)}${s(avg.toFixed(2))}${s(Math.min(...o.eligibleCounts))}` +
      `${s(total - o.unplaced.length)}${s(o.unplaced.length)}` +
      `${s(o.state.filter((d) => d.pods.length > 0).length)}`);
  }
  console.log(`\nper-service zone distribution (${ZONE.join("/")}):`);
  console.log(`${"stage".padEnd(22)}${s("verifier")}${s("billing")}${s("collector", 16)}`);
  for (const [ad, constraint] of STAGE) {
    const o = solve(constraint);
    console.log(`${ad.padEnd(22)}${s(distribution(o, "verifier").join("/"))}` +
      `${s(distribution(o, "billing").join("/"))}${s(distribution(o, "reading-collector").join("/"), 16)}`);
  }
}

model: 9 nodes / 3 zones, 18 pods, fast-disk nodes 3
stage                    avg eligible   min eligible         placed       unplaced     busy nodes
capacity only                    5.83              3             18              0              7
+ label selection                3.83              1             18              0              7
+ affinity                       3.17              0             15              3              6
+ anti-affinity                  4.28              0             15              3              6
+ topology spread                3.00              0             15              3              6

per-service zone distribution (b1/b2/b3):
stage                        verifier        billing       collector
capacity only                   6/0/0          0/3/0           0/7/2
+ label selection               2/2/2          3/0/0           4/5/0
+ affinity                      2/2/2          0/0/0           6/3/0
+ anti-affinity                 1/1/1          1/1/1           7/2/0
+ topology spread               1/1/1          1/1/1           3/3/3

The Narrowing Is Not One-Directional

The first table shows the expected narrowing: the average number of eligible nodes per pod drops from 5.83 to 3.83 with label selection, then to 3.17 with affinity. The minimum-eligible-nodes column is sharper — label selection shrinks the set to a single node for one pod, and once affinity is added the set empties out and three billing pods fail to place. The reason is in the second table: once the verifier’s copies fill the three fast-disk nodes two apiece, no room is left on those nodes for billing. The affinity constraint does not ask for room, but it requires room to be left.

The next row is the lesson’s inverted result. Once the anti-affinity constraint is added, the average eligible-node count does not fall; it rises from 3.17 to 4.28. The reason the search space widens even as the constraint count grows is this: anti-affinity limits the verifier to one copy per node, so three copies become unplaceable, and the capacity they no longer hold enlarges the eligible set for the pods that follow. The number of placed pods stays at fifteen, but its composition changes: billing’s three pods now get placed, and three of the verifier’s copies do not. One constraint rescues one service while dropping another, and the total count does not show it.

In the topology-spread row the placed count is again fifteen, and the average eligible set is 3.00. The only thing that changes is the last column: the reading collector’s zone distribution goes from 7/2/0 to 3/3/3. This constraint drops no pod at all; it only reshapes placement — and its payoff only becomes visible once a zone is lost.

Zone Loss, Unsolvability, and a Wrong Label

// scheduling/zone.mjs — topology spread's payoff on a zone loss, constraints that make each
// other unsolvable, and an incorrect label declaration. The model comes from the previous file.
import { ZONE, NODES, WORKLOAD, solve, distribution } from "./constraint.mjs";

const FULL = { label: 1, affinity: 1, antiAffinity: 1, topology: 1 };
const NO_TOPOLOGY = { label: 1, affinity: 1, antiAffinity: 1 };
const s = (x, n = 12) => String(x).padStart(n);
const SERVICES = ["verifier", "billing", "reading-collector"];

// SS12: a zone loss means all three nodes in that zone become unreachable at once.
console.log("replicas surviving a zone loss (placed / after the loss):");
console.log(`${"setting".padEnd(16)}${"loss".padEnd(8)}` +
  ["verifier", "billing", "collector"].map((x) => s(x, 14)).join("") +
  s("total remaining", 18));
for (const [ad, constraint] of [["no topology", NO_TOPOLOGY], ["with topology", FULL]]) {
  const o = solve(constraint);
  for (const loss of ZONE) {
    const remaining = SERVICES.map((sv) => {
      const d = distribution(o, sv), i = ZONE.indexOf(loss);
      return [d.reduce((t, x) => t + x, 0), d.reduce((t, x, j) => t + (j === i ? 0 : x), 0)];
    });
    console.log(`${ad.padEnd(16)}${loss.padEnd(8)}` +
      remaining.map(([t, k]) => s(`${t} / ${k}`, 14)).join("") +
      s(remaining.reduce((t, [, k]) => t + k, 0), 18));
  }
}

// Constraints making each other unsolvable: verifier has 6 replicas, 3 fast-disk nodes, each node
// takes at most one replica. The third row is unsolvable; the last row widens the node label.
const FAST6 = NODES.map((d, i) => ({ ...d, disk: i % 3 < 2 ? "fast" : "standard" }));
const VERIFIER_ONLY = WORKLOAD.filter((x) => x.service === "verifier");
console.log("\nverifier at 6 replicas, constraint combinations:");
console.log(`${"combination".padEnd(38)}${s("fast nodes")}${s("placed")}${s("unsolvable")}`);
for (const [ad, constraint, dgm] of [
  ["unconstrained", {}, NODES],
  ["label selection only", { label: 1 }, NODES],
  ["anti-affinity only", { antiAffinity: 1 }, NODES],
  ["label + anti-affinity", { label: 1, antiAffinity: 1 }, NODES],
  ["label + anti-affinity, 6 fast nodes", { label: 1, antiAffinity: 1 }, FAST6],
]) {
  const o = solve(constraint, VERIFIER_ONLY, dgm);
  console.log(`${ad.padEnd(38)}${s(dgm.filter((d) => d.disk === "fast").length)}` +
    `${s(6 - o.unplaced.length)}${s(o.unplaced.length)}`);
}

// SS11: a label is a declaration, not a measurement. What happens if a node's label is wrong.
console.log("\nwhen a label declaration is corrupted (full constraint set):");
console.log(`${"declaration".padEnd(34)}${s("placed", 14)}${s("unplaced", 14)}${s("busy nodes", 14)}`);
for (const [ad, dgm] of [
  ["correct", NODES],
  ["b2-d0 missing its fast label", NODES.map((d) => d.name === "b2-d0" ? { ...d, disk: "standard" } : d)],
  ["b3-d1 mistakenly labeled fast", NODES.map((d) => d.name === "b3-d1" ? { ...d, disk: "fast" } : d)],
]) {
  const o = solve(FULL, WORKLOAD, dgm);
  console.log(`${ad.padEnd(34)}${s(18 - o.unplaced.length, 14)}${s(o.unplaced.length, 14)}` +
    `${s(o.state.filter((d) => d.pods.length > 0).length, 14)}`);
}
const labelItems = NODES.length * 2;
const podItems = WORKLOAD.reduce((t, x) =>
  t + x.replicas * ((x.disk ? 1 : 0) + (x.antiAffinity ? 1 : 0) + (x.affinity ? 1 : 0)) + 1, 0);
console.log(`\ndeclarations read by the constraint solver: ${labelItems} node labels + ` +
  `${podItems} pod constraints = ${labelItems + podItems}; none of them are measurements`);

replicas surviving a zone loss (placed / after the loss):
setting         loss          verifier       billing     collector   total remaining
no topology     b1               3 / 2         3 / 2         9 / 2                 6
no topology     b2               3 / 2         3 / 2         9 / 7                11
no topology     b3               3 / 2         3 / 2         9 / 9                13
with topology   b1               3 / 2         3 / 2         9 / 6                10
with topology   b2               3 / 2         3 / 2         9 / 6                10
with topology   b3               3 / 2         3 / 2         9 / 6                10

verifier at 6 replicas, constraint combinations:
combination                             fast nodes      placed  unsolvable
unconstrained                                    3           6           0
label selection only                             3           6           0
anti-affinity only                               3           6           0
label + anti-affinity                            3           3           3
label + anti-affinity, 6 fast nodes              6           6           0

when a label declaration is corrupted (full constraint set):
declaration                               placed      unplaced    busy nodes
correct                                       15             3             6
b2-d0 missing its fast label                  13             5             5
b3-d1 mistakenly labeled fast                 16             2             6

declarations read by the constraint solver: 18 node labels + 21 pod constraints = 39; none of them are measurements

Three Measurements

Zone loss. Without topology spread, the outcome depends on which zone is lost: if b1 goes down, only two of the nine reading collectors remain; if b3 goes down, all nine remain. The total surviving replica count swings between six and thirteen, and nobody chose which number would come out. With topology spread, all three rows are identical: whichever zone goes down, six collectors and ten replicas in total survive. What the constraint buys is not the average but the worst case — the worst case rises from six to ten, the best case falls from thirteen to ten.

Unsolvability. The second table shows in numbers that two constraints, harmless alone, are unsolvable together. Label selection alone places all six replicas, anti-affinity alone places all six replicas, and the two together place only three, leaving three replicas unsolvable. What collides is not the constraints themselves but a number: anti-affinity wants as many separate nodes as there are replicas, while label selection narrows the eligible node count to three. The last row gives the fix in numbers too — once the fast-disk node count is raised to six, all six of the six replicas get placed. The unsolvability is not in the declaration; it is in the cluster’s hardware.

A wrong label. The third table exposes the kind of information the constraints rest on. None of the thirty-nine declarations is a measurement: eighteen node labels were written by a person, and so were the twenty-one pod constraints. When a node’s fast-disk label goes missing, the placed count drops from fifteen to thirteen; the error is visible, because something fails to place.

The real problem is in the next row. When a node without a fast disk is mistakenly labeled fast, the placed count rises to sixteen. In the solver’s ledger, the situation has improved; in reality, a verifier copy is running on a slow-disk node, and no counter reports it. The scheduler does not measure the node’s disk; it reads its label. The source of the wrong decision is, once again, not the information item itself but the fact that the item is a declaration.

Summary

• As constraints are added, the average number of eligible nodes per pod drops from 5.83 to 3.83, then to 3.17; under the affinity constraint the set empties out and three billing pods fail to place.
• Adding a constraint does not always narrow the search space: the anti-affinity constraint raises the average from 3.17 to 4.28, because the capacity the three unplaceable verifier copies no longer hold is left over for the pods that follow.
• The same placed count can hide different compositions: while fifteen pods get placed, one constraint rescues three of billing’s pods while dropping three of the verifier’s.
• Topology spread fixes the worst case without dropping a single pod: surviving replicas on a zone loss move from the 6–13 range to a fixed ten, and the reading collector’s distribution becomes 3/3/3 instead of 7/2/0.
• Two constraints are harmless alone and unsolvable together: six replicas, three fast-disk nodes, and a one-copy-per-node rule yield three unsolvable pods; the unsolvability ends once the fast-node count rises to six.
• None of the thirty-nine items the solver reads is a measurement; a mis-written label raises the placed count from fifteen to sixteen and makes the error invisible.

Next Step

The constraints so far write what the pod wants from the node. The reverse direction was never written: which pod the node will accept. In the regional measurement network, the nightly batch job consumes the whole disk and all the memory, and a service copy that lands on the same node slows down for the whole night. The way to set these nodes aside for the batch job is not to write one more constraint into every pod; it is to place a taint on the node itself and let only the pods that carry a matching toleration arrive. The next lesson measures this separation and the idle ratio of the set-aside capacity.