50 Minus N/125: How the Scheduler Decides to Look at 5% of a 10,000-Node Cluster

TL;DR: percentageOfNodesToScore: 0 is not “score every node” — it is the adaptive mode, and the scheduler computes the percentage itself as max(50 - N/125, 5) percent of the cluster, where N is the number of candidate nodes. On top of that sits an absolute floor of 100 feasible nodes (minFeasibleNodesToFind), so small clusters are always fully explored. A 10 000-node cluster therefore gets 5% — 500 nodes. A 125-node cluster gets 49% — but the 100-node floor means it evaluates 100 of 125. And the starting index rotates by the number of nodes processed each cycle, so no node is permanently starved of being examined.

Filtering every node in a 10 000-node cluster on every scheduling cycle is absurd. The Filter plugins are not free — node affinity, taints, resource fit, volume checks — and the number of pods waiting to be scheduled grows with the cluster. So the scheduler stops early. The interesting question is when it stops, and the answer is a hardcoded linear formula with two floors and a rotating cursor.

There are three separate mechanisms here and they are easy to conflate: the percentage that decides how many feasible nodes to hunt for, the absolute floor that overrides the percentage in small clusters, and the rotating start index that makes the sampling fair over time. Read separately, each is simple.

Zero is a mode, not a number

The default is literally zero:

// pkg/scheduler/apis/config/types.go:261-265
const (
	// DefaultPercentageOfNodesToScore defines the percentage of nodes of all nodes
	// that once found feasible, the scheduler stops looking for more nodes.
	// A value of 0 means adaptive, meaning the scheduler figures out a proper default.
	DefaultPercentageOfNodesToScore = 0

and the field’s doc comment spells out what zero means:

// pkg/scheduler/apis/config/types.go:62-70
	// PercentageOfNodesToScore is the percentage of all nodes that once found feasible
	// for running a pod, the scheduler stops its search for more feasible nodes in
	// the cluster. This helps improve scheduler's performance. Scheduler always tries to find
	// at least "minFeasibleNodesToFind" feasible nodes no matter what the value of this flag is.
	// Example: if the cluster size is 500 nodes and the value of this flag is 30,
	// then scheduler stops finding further feasible nodes once it finds 150 feasible ones.
	// When the value is 0, default percentage (5%--50% based on the size of the cluster) of the
	// nodes will be scored. It is overridden by profile level PercentageOfNodesToScore.
	PercentageOfNodesToScore *int32

“5%–50% based on the size of the cluster” is the whole of it. The default is a formula, not a constant.

Note the semantics carefully: the percentage is the number of feasible nodes to find. The scheduler keeps running Filter until it has collected that many feasible nodes, and only those get scored. The Filter pass itself may have examined far more than that many nodes, because a node that fails a filter is not “found”. In a cluster where 95% of the nodes cannot host your pod, the Filter pass visits nearly everything before it accumulates 500 feasible nodes — or gives up and returns a FitError.

The formula

Here is the entire computation:

// pkg/scheduler/algorithm.go:518-543
// numFeasibleNodesToFind returns the number of feasible nodes that once found, the scheduler stops
// its search for more feasible nodes.
func (a *SchedulingAlgorithm) numFeasibleNodesToFind(percentageOfNodesToScore *int32, numAllNodes int32) (numNodes int32) {
	if numAllNodes < minFeasibleNodesToFind {
		return numAllNodes
	}

	// Use profile percentageOfNodesToScore if it's set. Otherwise, use global percentageOfNodesToScore.
	var percentage int32
	if percentageOfNodesToScore != nil {
		percentage = *percentageOfNodesToScore
	} else {
		percentage = a.percentageOfNodesToScore
	}

	if percentage == 0 {
		percentage = max(int32(50)-numAllNodes/125, minFeasibleNodesPercentageToFind)
	}

	numNodes = numAllNodes * percentage / 100
	if numNodes < minFeasibleNodesToFind {
		return minFeasibleNodesToFind
	}

	return numNodes
}

Four things happen in there, in order:

1. If the cluster is smaller than 100 nodes, return the cluster size — score everything, no sampling.
2. Pick the profile-level percentage if there is one, otherwise the global one.
3. If that percentage is zero, replace it with the adaptive value max(50 - N/125, 5).
4. Compute N * percentage / 100 and floor it at 100.

The 125 is a magic constant that encodes a design decision: the scheduler is willing to sample half the cluster when the cluster is tiny, and shrinks that linearly until it hits 5%, which it reaches at N = 5625. From that point on the percentage is fixed at 5% and the absolute number of nodes scored grows linearly with the cluster.

And the two constants come from schedule_one.go:

// pkg/scheduler/schedule_one.go:45-62
const (
	// Percentage of plugin metrics to be sampled.
	pluginMetricsSamplePercent = 10
	// minFeasibleNodesToFind is the minimum number of nodes that would be scored
	// in each scheduling cycle. This is a semi-arbitrary value to ensure that a
	// certain minimum of nodes are checked for feasibility. This in turn helps
	// ensure a minimum level of spreading.
	minFeasibleNodesToFind = 100
	// minFeasibleNodesPercentageToFind is the minimum percentage of nodes that
	// would be scored in each scheduling cycle. This is a semi-arbitrary value
	// to ensure that a certain minimum of nodes are checked for feasibility.
	// This in turn helps ensure a minimum level of spreading.
	minFeasibleNodesPercentageToFind = 5
	// noteLengthLimit is a local copy of NoteLengthLimit in k8s.io/kubernetes/pkg/apis/core/validation, which the API
	// server enforces on notes the scheduler records. A local copy is safe because API validation limits will never
	// become lower than an already released version.
	noteLengthLimit = 1024
)

“semi-arbitrary” is the source’s own word. The reason for the floors is spreading: if the scheduler only ever looked at the same 5 feasible nodes, every pod would pile onto them. A floor of 100 feasible nodes guarantees a minimum diversity of candidates for the scoring plugins to choose from.

The arithmetic

percentage = max(50 - N/125, 5), integer division throughout:

Two regimes are visible. Between roughly 205 and 5625 nodes the absolute count scored falls — 420 at 1000 nodes, 281 at 5625 nodes — because the percentage is shrinking faster than the cluster is growing. Above 5625 nodes the percentage pins at 5% and the count grows linearly again.

Below about 205 nodes, the 100-node floor dominates and the scheduler is effectively examining the whole cluster. That is the point of the floor: the percentage formula would happily return 50 feasible nodes out of a 100-node cluster, which is a 50% sample of a cluster where the marginal cost of checking every node is trivial.

Note also the ordering of the two floors. The percentage floor (5) is applied before the node count is computed, and the node-count floor (100) is applied after. So minFeasibleNodesPercentageToFind can never produce fewer than 100 nodes in a cluster of 2000 or more, and minFeasibleNodesToFind can never produce fewer than 100 nodes in any cluster.

The one shortcut before all of this

numNodesToFind is the caller, and it has an even cheaper case:

// pkg/scheduler/algorithm.go:504-516
// numNodesToFind decides how many feasible nodes Filter should collect, following
// kube-scheduler's percentageOfNodesToScore policy. A profile that neither filters
// through extenders nor scores has no use for a second candidate, so one is enough.
func (a *SchedulingAlgorithm) numNodesToFind(schedFramework framework.Framework, numAllNodes int32) int32 {
	if numAllNodes == 0 {
		return 0
	}

	if !hasExtenderFilters(schedFramework) && !hasScoring(schedFramework) {
		return 1
	}
	return a.numFeasibleNodesToFind(schedFramework.PercentageOfNodesToScore(), numAllNodes)
}

If the profile has no extender filters and no scoring plugins at all, one feasible node is enough — there is nothing to choose between candidates. The percentage machinery is skipped entirely.

The rotating start index

The percentage decides how many nodes to look at. The start index decides which ones, and it exists to stop the sampling from always hitting the same prefix of the node list.

// pkg/scheduler/algorithm.go:75-79
	// nextStartNodeIndex is the starting index in the node list for the next filter
	// pass. Advancing this across scheduling cycles distributes evaluations uniformly
	// across all nodes when percentageOfNodesToScore halts the search early.
	nextStartNodeIndex int
}

The cursor advances by the number of nodes actually processed in the cycle:

// pkg/scheduler/algorithm.go:364-373
	// The budget is computed from the candidate list, which PreFilter may have narrowed —
	// not from allNodes.
	numNodesToFind := a.numNodesToFind(schedFramework, int32(len(nodes)))
	feasibleNodes, err := a.findNodesThatPassFilters(ctx, schedFramework, state, pod, diagnosis, nodes, numNodesToFind)
	// always try to update the a.nextStartNodeIndex regardless of whether an error has occurred
	// this is helpful to make sure that all the nodes have a chance to be searched
	processedNodes := len(feasibleNodes) + diagnosis.NodeToStatus.Len()
	if len(preFilterOutcome.allNodes) > 0 {
		a.nextStartNodeIndex = (a.nextStartNodeIndex + processedNodes) % len(preFilterOutcome.allNodes)
	}

processedNodes is the feasible nodes found plus the nodes that were evaluated and rejected — diagnosis.NodeToStatus holds one entry per node the Filter pass touched. So the cursor moves by roughly the number of nodes examined, which means each cycle starts where the previous one stopped and the whole list is covered in N / processedNodes cycles.

The comment is worth noting: the update happens even if the filter pass errored. Otherwise a failing pod would freeze the cursor and the same prefix would be re-examined forever.

The cursor is consumed by the parallel filter loop:

// pkg/scheduler/algorithm.go:453-457
	checkNode := func(i int) {
		// We check the nodes starting from where we left off in the previous scheduling cycle,
		// this is to make sure all nodes have the same chance of being examined across pods.
		nodeInfo := nodes[(a.nextStartNodeIndex+i)%numAllNodes]
		status := schedFramework.RunFilterPluginsWithNominatedPods(ctx, state, pod, nodeInfo)

One subtlety: nextStartNodeIndex is taken modulo len(preFilterOutcome.allNodes) but applied modulo len(nodes), and nodes is the candidate list that PreFilter may have narrowed. If PreFilter dropped half the cluster, the two lengths differ and the cursor’s phase relative to the candidate list drifts. That is harmless — the modulo in the index expression keeps it in range — but it means the rotation is exact only when PreFilter does not narrow the list.

The node tree hands out nodes in zone order

The list the cursor walks is not arbitrary: it comes from the node tree, which orders nodes round-robin across zones.

// pkg/scheduler/backend/cache/node_tree.go:117-143
// list returns the list of names of the node. NodeTree iterates over zones and in each zone iterates
// over nodes in a round robin fashion.
func (nt *nodeTree) list() ([]string, error) {
	if len(nt.zones) == 0 {
		return nil, nil
	}
	nodesList := make([]string, 0, nt.numNodes)
	numExhaustedZones := 0
	nodeIndex := 0
	for len(nodesList) < nt.numNodes {
		if numExhaustedZones >= len(nt.zones) { // all zones are exhausted.
			return nodesList, errors.New("all zones exhausted before reaching count of nodes expected")
		}
		for zoneIndex := 0; zoneIndex < len(nt.zones); zoneIndex++ {
			na := nt.tree[nt.zones[zoneIndex]]
			if nodeIndex >= len(na) { // If the zone is exhausted, continue
				if nodeIndex == len(na) { // If it is the first time the zone is exhausted
					numExhaustedZones++
				}
				continue
			}
			nodesList = append(nodesList, na[nodeIndex])
		}
		nodeIndex++
	}
	return nodesList, nil
}

The outer loop advances the index within each zone; the inner loop walks the zones. So the list is zone0[0], zone1[0], zone2[0], ..., zone0[1], zone1[1], .... The practical consequence: the first 100 feasible nodes the scheduler finds are spread across every zone in the cluster, not clustered in whichever zone happens to sort first. This is a deliberate anti-bias measure layered on top of the percentage.

Combined with the rotating cursor, the sampling is: start somewhere new each cycle, and the node list itself is zone-balanced.

What the sampling costs you

The trade-off is explicit. Scoring 5% of a 10 000-node cluster instead of 100% means:

• The best node may never be looked at. A pod that would fit perfectly on node 7421 might be scheduled onto node 3 because 7421 was not in the sample. The scoring plugins — NodeResourcesFit, ImageLocality, InterPodAffinity, TopologySpread — only ever rank the candidates they were given.
• Topology spread degrades first. The PodTopologySpread plugin scores based on the domain skew it computes, and it computes it over the candidate set. With a small candidate set, the scheduler has less information about where the pod actually belongs.
• The filter pass is not bounded by the percentage. Only the scoring is bounded. The Filter pass keeps running until it has found enough feasible nodes, so on a cluster where most nodes are unsuitable, the expensive part is not avoided at all.

That last point is the one that surprises people. percentageOfNodesToScore is not a knob on how much work the scheduler does. It is a knob on how many viable candidates the scoring plugins get to choose between.

Wrapping up

The one thing to remember: percentageOfNodesToScore: 0 is the adaptive formula max(50 - N/125, 5) percent, floored at 100 feasible nodes, applied to the candidate list after PreFilter narrowing — not to the raw cluster size. At 10 000 nodes that is 5%, or 500 nodes.

The part people get wrong: the percentage bounds the number of feasible nodes found and scored, not the number of nodes filtered. If your cluster is full of nodes that fail a taint or resource check, the Filter pass still walks nearly all of them and percentageOfNodesToScore buys you nothing. And setting it to 100 to “get better placements” is a real option with a real cost — the Filter and Score extension point latency is recorded in scheduler_framework_extension_point_duration_seconds, so you can see what it costs you before you commit.

What to go do about it: the setting lives in KubeSchedulerConfiguration.percentageOfNodesToScore and can be overridden per profile (KubeSchedulerProfile.percentageOfNodesToScore, which wins over the global value — see pkg/scheduler/algorithm.go:525-531). Set it to an explicit percentage to bypass the adaptive formula entirely, and set it to 100 for a small, latency-sensitive cluster where placement quality matters more than throughput. For a large cluster that keeps complaining about topology spread, raise it before you start disabling the spread plugin, and watch scheduler_pending_pods alongside scheduler_framework_extension_point_duration_seconds{extension_point="Score"} to see whether the extra scoring actually helps.