Kestrel Preview: a Dry-Run Pod Scheduler

Kestrel Preview: a Dry-Run Pod Scheduler

The platform team ships Kestrel Preview, a small simulator that answers "where would the real cluster put these pods?" before a team rolls out a manifest. It is only useful if it agrees with the real scheduler, and lately it hasn't. Four incident reports are open against it (Part 1), and the roadmap has anti-affinity (Part 2), priority preemption (Part 3) and capacity-planning replays of thousands of pods (Part 4) queued behind them.

CPU is in millicores, memory in MiB, everything is an integer. There is no clock: the preview is a pure function of the operations so far.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against an empty cluster and returns one result per operation. Every operation is [name, *args]. Errors are returned as strings, never raised.

An unknown operation returns "error: unknown operation"; a wrong number of arguments (or an operation that is not a non-empty list starting with a string) returns "error: invalid arguments".

Node spec: {"cpu", "mem", "zone", "labels"?, "taints"?}. A taint is {"key", "value"?, "effect"} with effect NoSchedule or NoExecute (both keep new pods away). Pod spec: {"requests": {"cpu", "mem"}, "limits"?, "priority"?, "selector"?, "tolerations"?, "labels"?, "affinity"?, "preemption"?}; specs.py documents every field and what is invalid.

Scheduling = filter, then score.

1. *Filter.* A node is feasible for a pod when all of these hold:

• every selector key/value is present in the node's labels (an empty selector matches every node);
• every taint on the node is covered by at least one of the pod's tolerations;
• the pod's requests fit in what is free: used + request <= capacity, for CPU and for memory (an exact fit is allowed). A node's usage is the sum of the requests of the pods bound to it. Limits never count; they only have to be valid (limits >= requests).
• (Part 2) the pod's affinity terms hold.

1. *Score.* For each feasible node compute, with integer division (floor): cpu_pct = (cpu_capacity - cpu_used - cpu_request) * 100 // cpu_capacity, mem_pct = (mem_capacity - mem_used - mem_request) * 100 // mem_capacity (used = before this pod), score = (cpu_pct + mem_pct) // 2. The highest score wins; equal scores go to the node whose name is smallest (plain string order). No floats anywhere.
2. Bind the pod, append the event bind <pod> <node>. If no node is feasible the result is "error: unschedulable" and nothing changes.

Tolerations are {"key", "operator", "value", "effect"} with operator Equal (default) or Exists. A toleration covers a taint when all hold:

• effect is empty or equal to the taint's effect;
• Exists: the toleration's key is empty (it then covers every taint) or equals the taint's key; the taint's value is ignored;
• Equal: key and value equal (a missing value means "", and so does a taint without one).

Worked example

[["add_node", "n-b", {"cpu": 4000, "mem": 8192, "zone": "a"}],
 ["add_node", "n-a", {"cpu": 4000, "mem": 8192, "zone": "b"}],
 ["add_node", "gpu-1", {"cpu": 8000, "mem": 16384, "zone": "a", "labels": {"hw": "gpu"},
   "taints": [{"key": "hw", "value": "gpu", "effect": "NoSchedule"}]}],
 ["submit", "api-1", {"requests": {"cpu": 1000, "mem": 1024}, "limits": {"cpu": 2000, "mem": 2048}}],
 ["submit", "api-2", {"requests": {"cpu": 1000, "mem": 1024}, "limits": {"cpu": 2000, "mem": 2048}}],
 ["submit", "train", {"requests": {"cpu": 6000, "mem": 4096}, "selector": {"hw": "gpu"},
   "tolerations": [{"key": "hw", "operator": "Exists"}]}],
 ["submit", "train-2", {"requests": {"cpu": 6000, "mem": 4096}, "selector": {"hw": "gpu"}}],
 ["node_status", "n-a"],
 ["where", "train"]]

returns

[true, true, true, "n-a", "n-b", "gpu-1", "error: unschedulable",
 {"cpu_used": 1000, "mem_used": 1024, "pods": ["api-1"]}, "gpu-1"]

(api-1 scores 81 on both small nodes, a tie, so n-a wins by name; api-2 then prefers the empty n-b; gpu-1 is tainted, so only pods that tolerate it can land there.)

Part 1: Preview disagrees with the real cluster (INC-4412, INC-4419, INC-4427, INC-4431)

Goal: make the filter and score phases follow the rules above. Reports from teams, verbatim:

1. INC-4412: "Preview says my 3-core batch pod does not fit on a 4-core node that is empty. In prod it schedules (its *limit* is 6 cores, its request is 3). Afterwards node_status shows far more CPU used than I requested."
2. INC-4419: "My pod tolerates hw with Exists. Preview still refuses to place it on the tainted GPU nodes. Our platform pods use a toleration with an empty key and Exists, and those are refused everywhere."
3. INC-4427: "A pod with selector {disk: ssd, zone-class: a} landed on a node that only has disk: ssd."
4. INC-4431: "Two identical empty nodes: preview picks a different one depending on the order I added them, and with nodes of different sizes it sometimes picks a node that, by the numbers, is not the emptiest. Prod always breaks exact ties by node name."

Rules: everything in the section above. tests/test_filters.py has failing tests to start from. specs.py, nodes.py, models.py and generator.py are otherwise trusted.

Part 2: Pod affinity and anti-affinity (PLAT-880)

Goal: teams want replicas spread across zones (or nodes), and caches co-located with their database. Implement affinity_ok so the affinity field of a pod spec is enforced. Terms are already parsed onto the pod (pod.affinity_terms, pod.anti_terms).

A term is {"match": {labels}, "topology": "node" | "zone"}. A *topology domain* is a single node (its name) or a zone (all nodes sharing the zone value of the node). A bound pod is *matched* by a term when selector_matches(term.match, pod.labels) (so an empty match matches every pod). Only bound pods count: pending pods (Part 3) are nowhere.

Rules (all required terms; a node is feasible only if every rule holds for it):

1. *Anti-affinity.* For each term in pod_anti_affinity: no pod bound in the candidate node's domain (same node, or same zone, per topology) may be matched by the term.
2. *Symmetry.* If a bound pod has an anti-affinity term that matches the incoming pod's labels, and the candidate node is in that term's domain *of the bound pod* (its node or its zone), the candidate is rejected too. Existing pods can repel newcomers. Affinity is not symmetric.
3. *Affinity.* For each term in pod_affinity: the candidate node's domain must contain at least one bound matched pod. Exception, so the first replica can start: if *no pod bound anywhere in the cluster* is matched by the term and the incoming pod's own labels match the term, the term is satisfied on every node.
4. A pod never counts against itself; deleting or evicting a pod removes its effect immediately.
5. Part 1 scoring and tie-breaking apply unchanged among the nodes that pass.

Example

[["add_node", "a1", {"cpu": 4000, "mem": 8192, "zone": "east"}],
 ["add_node", "a2", {"cpu": 4000, "mem": 8192, "zone": "east"}],
 ["add_node", "b1", {"cpu": 4000, "mem": 8192, "zone": "west"}],
 ["submit", "db-1", {"requests": {"cpu": 500, "mem": 512}, "labels": {"app": "db"},
   "affinity": {"pod_anti_affinity": [{"match": {"app": "db"}, "topology": "zone"}]}}],
 ["submit", "db-2", <same as db-1>],
 ["submit", "db-3", <same as db-1>],
 ["submit", "cache-1", {"requests": {"cpu": 500, "mem": 512}, "labels": {"app": "cache"},
   "affinity": {"pod_affinity": [{"match": {"app": "db"}, "topology": "zone"}]}}],
 ["submit", "web-1", {"requests": {"cpu": 500, "mem": 512}, "labels": {"app": "web"},
   "affinity": {"pod_affinity": [{"match": {"app": "web"}, "topology": "node"}]}}]]

returns [true, true, true, "a1", "b1", "error: unschedulable", "a2", "a1"]. db-1 takes a1 (all scores tie, name order); db-2 must leave zone east, so b1; db-3 has no free zone. cache-1 may use any node (both zones have a db) and a2 is the emptiest. web-1 is the first web anywhere and matches its own term, so the exception applies and it lands on a1 (three nodes tie on score).

Part 3: Priority preemption (PLAT-902)

Goal: when a high-priority pod fits nowhere, the real cluster evicts lower-priority pods to make room. Implement preempt_for and retry_pending so Preview does the same. Real Kubernetes is more elaborate; this is the rule set Preview uses.

This supersedes the Part 1 rule "no feasible node means unschedulable": a pod that fits nowhere now tries preemption first, and is unschedulable only if preemption finds no viable node. When no lower-priority pod exists to evict, results are the same as before.

Rules

1. *Who may preempt.* Pods with preemption: "PreemptLowerPriority" (the default). A pod with "Never" is simply unschedulable. A pod may only evict pods with strictly lower priority.
2. *Per node.* Skip a node whose selector/taints (the static_ok checks) fail: evicting cannot fix those. Otherwise let candidates be the node's bound pods with lower priority, ordered by (priority ascending, seq descending) (cheapest and newest first; seq is the order of a pod's first successful bind, 1, 2, 3, ...). Remove candidates one at a time in that order until the pod is fully feasible on that node (resources *and* the Part 2 rules, evaluated as if the removed pods were gone). If it is still not feasible with all candidates removed, the node is not viable.
3. *Give back what was not needed.* Take the removed pods in order (priority descending, seq ascending); put each one back if the pod is still feasible with it present. What remains removed are the node's victims.
4. *Choosing the node.* Among viable nodes pick the smallest key (highest victim priority, number of victims, node name). Scores are not used.
5. *Eviction.* Evict victims in order (priority ascending, seq ascending), logging evict <victim> <node> for <pod> for each; then bind the preemptor to the node (bind <pod> <node>).
6. *Requeue.* Then re-place each victim, in order (priority descending, seq ascending), through the normal filter-and-score path without preempting (the preemptor is already bound, so it counts). A victim that fits gets bind <victim> <node> and keeps its seq. A victim that does not fit becomes pending (pending <victim> event); where reports "pending" for it.
7. pending returns the pending pod names ordered (priority descending, seq ascending). delete_pod removes pending pods too. A pending pod's name stays taken (pod exists).
8. retry_pending makes one pass over the pending pods in that same order, each through the normal path without preemption, and returns [[pod, node], ...] for those that were placed, in that order. The rest stay pending.
9. A failed submit (unschedulable) leaves no trace: no seq is used, no event is logged.

Example

[["add_node", "n1", {"cpu": 4000, "mem": 8192, "zone": "a"}],
 ["submit", "old", {"requests": {"cpu": 2500, "mem": 512}}],
 ["submit", "new", {"requests": {"cpu": 500, "mem": 512}}],
 ["add_node", "n2", {"cpu": 1000, "mem": 8192, "zone": "b",
   "taints": [{"key": "dedicated", "value": "x", "effect": "NoSchedule"}]}],
 ["submit", "urgent", {"requests": {"cpu": 2000, "mem": 512}, "priority": 100}],
 ["events", 5], ["pending"], ["where", "old"], ["node_status", "n1"]]

returns [true, "n1", "n1", true, "n1", ["bind old n1", "bind new n1", "evict old n1 for urgent", "bind urgent n1", "pending old"], ["old"], "pending", {"cpu_used": 2500, "mem_used": 1024, "pods": ["new", "urgent"]}]. urgent needs 2000 CPU and only 1000 is free on n1. Candidates in order: new (newer), old. Removing new frees too little; removing old as well is enough. Giving back in order old, new: old cannot return (1500 free < 2000 needed) but new can. Victim: old only. It cannot be re-placed (n1 has 1500 free; n2 is tainted), so it is pending.

Part 4: Capacity-planning replays (PLAT-931, stretch)

Goal: make Preview fast enough to replay large clusters. Two operations already exist; they expand compactly-described workloads using generator.py and submit them through the normal path:

• ["bulk_nodes", {prefix, count, zones, cpu, mem}] adds nodes and returns how many.
• ["bulk_submit", {prefix, count, seed, groups, cpu, mem, priorities}] submits pods one at a time and returns {"bound", "unschedulable", "evictions", "pending", "digest", "final"}. digest fingerprints every submit's result in order; final fingerprints where every pod ended up (see bulk_submit's docstring). Both must come out exactly as the per-pod rules of Parts 1-3 dictate, so placements must be identical, not merely similar. Invalid arguments return "error: invalid arguments"; colliding names return "error: node exists" / "error: pod exists" before anything is added.

Rules

1. Results of every earlier Part are unchanged.
2. Hidden tests replay clusters of about a hundred nodes with over a thousand pods, with preemption and zone anti-affinity in play, in one run; the whole suite has a few seconds. Re-deriving every node's state for every pod is too slow. Keep your fast path consistent with every way a pod can enter or leave a node (submit, delete, eviction, requeue, retry).

Notes

• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour.
• Parts 1-3 is a strong result. Part 4 is a stretch.