Filtering and Scoring: How a Scheduler Picks One Node Out of Thousands

A cluster with five thousand nodes and a queue of pending workloads has, in principle, five thousand places to put each one. Enumerating and ranking all of them per decision is not affordable, and ranking them without first discarding the illegal ones produces answers that are precisely wrong. The scheduler therefore splits placement into two passes with different jobs: a hard pass that removes every node where the workload cannot run at all, and a soft pass that orders what remains by how good it would be.

The split is the whole design. It is also where most of the operational surprises live, because the two passes have opposite failure semantics. A filter that is too strict leaves work permanently pending. A score function that is wrong leaves work running badly. Only the first is visible as an error.

The scheduling cycle for a single workload

For each workload the scheduler takes from its queue, it runs a cycle that ends in at most one binding decision. The workload is unscheduled at the start; the cycle either places it, decides it is unschedulable, or is preempted by a higher-priority item and retried later.

The first step is a snapshot of cluster state. The scheduler reads node and workload state from its informer caches rather than from the API server, so the snapshot is consistent with the cache at a given moment but not necessarily with the store. That distinction is not academic: two workloads scheduled in the same cycle see the same snapshot, so a decision for the first does not account for the second, and the second may be placed on a node the first just filled. The scheduler avoids this by processing one workload at a time and updating its in-memory copy of the node after each assumed placement, a step called assumption. If the binding later fails, the assumed state is rolled back and the workload re-queued. Without the assumption step, a scheduler running at any useful rate would double-book nodes continuously.

With the snapshot in hand, filtering runs. Each filter is a predicate over one node and one workload: does the node have enough unallocated CPU and memory for the request, does its label set satisfy the required node selector, do its taints tolerate, is the host port free, does the volume’s topology constraint permit it, does the pod’s anti-affinity rule exclude it. Nodes that fail any predicate are dropped. The result is a feasible set, and its size is the only thing the scoring pass has to work with.

Scoring then assigns each surviving node a number, usually normalised to a small integer range, from each enabled score plugin, and combines them by weight. A typical combination is a weighted sum, with the least-allocated strategy favouring the emptiest node and the balanced-allocation strategy favouring the node whose CPU and memory fractions are closest to equal. The highest total wins. Ties are broken by a stable rule, and if the feasible set is empty the workload is marked unschedulable and an event records the predicates that rejected every node.

The final step is binding: a write that names the chosen node, conditional on the workload still being unscheduled. If another scheduler instance bound it first, the write fails and this cycle is discarded. That conditional write is what makes multiple scheduler replicas safe without a lock, and it is the same optimistic-concurrency pattern used everywhere else in the control plane.

Why feasibility must be evaluated per node

The obvious alternative is to invert the loop: for each constraint, compute the set of nodes that satisfy it, and intersect. That is what a query planner would do, and it is wrong here for a specific reason: several of the predicates are not functions of the node alone. Pod anti-affinity depends on which other pods are already placed there. Volume topology depends on where the volume’s backing store lives. Port conflicts depend on the set of host ports in use. Each of those would need its own index, maintained against every change in the cluster, and the index would be stale in exactly the cases that matter.

Evaluating per node instead means each predicate is a cheap function over a node object that the scheduler already holds in cache, and the whole filter pass is one loop over the node list. The cost is O(nodes × predicates) per workload rather than O(predicates × log nodes), which for five thousand nodes and a dozen predicates is on the order of sixty thousand small checks per decision, affordable because each check is a comparison against a cached struct, not a remote call.

The price is paid at scale in a different currency. Filtering every node for every workload is linear in cluster size, so doubling the nodes doubles the per-decision cost. Real schedulers cut this with precomputed node information and by short-circuiting: the resource-fit predicate runs first and rejects most nodes with two integer comparisons, so the expensive predicates see a small candidate set. Ordering predicates by selectivity is the same optimisation as ordering clauses in a query planner, and it is the difference between a scheduler that keeps up and one that does not.

The scoring axes and what they actually optimise

Scoring is where policy lives, and the plugins encode mutually incompatible goals. The two that matter most pull in opposite directions.

Least-allocated spreads workloads: it scores a node higher the more free capacity it has, so a new workload lands on the emptiest node. The effect is to keep every node’s utilisation similar and to preserve room for large workloads that need contiguous capacity. Its cost is fragmentation of a different kind: every node carries a little of everything, so cache locality between related workloads is destroyed and the failure domain of any single node is spread across many services.

Most-allocated packs: it prefers the fullest node that still fits, which concentrates load and leaves whole nodes empty for scale-down or for large workloads. Packing reduces the number of nodes needed for a given load, which is the axis where the money is, and it increases the blast radius of any node failure because the packed node is running more.

Balanced allocation is a third axis entirely, and it is the one that is easy to get wrong. It compares the CPU fraction and memory fraction on a node and prefers the node where they are closest. The point is not fairness but avoidance of a specific pathology: a node with 90 percent of its CPU allocated and 10 percent of its memory is a node that will refuse CPU-heavy workloads while appearing to have plenty of free memory, and the reverse. Balancing the dimensions keeps each node able to accept a workload of any shape.

Weights decide which of these dominates, and the weights are static configuration. A cluster tuned for cost and a cluster tuned for latency need different weights on the same plugins, and there is no setting that is right for both.

Inter-pod affinity and the quadratic it hides

Required pod affinity says a workload must be placed on a node that already runs a workload matching a label selector, optionally within a topology domain such as a zone. It is the mechanism behind co-locating a cache with its client, and its cost is not obvious.

The predicate is not “is there a matching pod on this node”. It is “does the topology domain containing this node contain a matching pod”, which requires counting matching pods per domain. For a cluster with many pods carrying the selector, the naive implementation walks the pod list per node and the filter pass becomes O(nodes × pods). The standard remedy is to precompute, per topology domain, the count of pods matching each selector used by pending workloads, and to invalidate those counts on pod add and delete. That index is small, one counter per (domain, selector) pair, but it must be maintained, and a scheduler that recomputes it per decision will fall behind on large clusters.

The asymmetry between affinity and anti-affinity is worth stating because it drives a common misconfiguration. Required affinity is a constraint on a group; required anti-affinity with a topology key of hostname means at most one matching pod per node, which for a workload with many replicas caps the replica count at the number of nodes. With a topology key of zone it caps replicas at the number of zones. A deployment that asks for both high replica count and hard anti-affinity over a small topology ends up with pods that are permanently pending, and the scheduler’s event explains it only as a list of failed predicates on every node.

Preferred (soft) affinity avoids this by scoring rather than filtering, at the cost of a guarantee: soft affinity is a nudge, and under pressure the scheduler will ignore it.

The cost of a decision and the two-level alternative

One cycle costs a filter pass over all nodes plus a score pass over the feasible set, so per-decision work grows with cluster size while the decision rate grows with the number of pending workloads. The product is why monolithic schedulers have a ceiling.

The alternative, argued in the Omega and Mesos designs, is to let multiple independent schedulers make decisions against shared cluster state with optimistic concurrency, so that parallelism comes from having several decision-makers rather than from making one faster. Omega’s contribution was to show that the conflict rate between concurrent schedulers is low enough that retrying on conflict is cheaper than serialising, provided the schedulers see a consistent enough snapshot. The monolithic design is simpler to reason about and gives globally coherent decisions; the shared-state design scales the decision rate and accepts that some decisions are wasted.

Either way, the filter and score structure survives, because it is the only structure that separates “cannot” from “should not”, and the scheduler’s correctness depends on never confusing the two. What the scheduler does with the leftovers, and why a workload can be legal on every node yet never placed, is the subject of placement constraints and unschedulable states. The inputs to the resource-fit predicate are themselves a design question, taken up in resource requests, limits, and scheduler accounting.