The Hostname Fast Path: Inter-Pod Affinity Without the Cluster-Wide Topology Map

TL;DR: The classic inter-pod-affinity algorithm builds a map[topologyPair]int64 over every pod in the cluster during PreFilter, then in Filter iterates over every label of every candidate node doing map lookups. When all of the pod’s affinity terms use the kubernetes.io/hostname topology key, that global map is unnecessary — the answer depends only on the pods on the candidate node itself. The InterPodAffinityHostnameFastPath feature gate (alpha since 1.37) takes that shortcut: no map, no label iteration, just a scan of the node’s own pods.

Inter-pod affinity is the scheduler plugin most likely to make your cluster slow. A pod with requiredDuringSchedulingIgnoredDuringExecution affinity to another pod forces the scheduler to answer a question about the whole cluster for every candidate node: “is there a pod anywhere that matches my selector, and is it in my topology domain?”

The classic answer is to precompute. In PreFilter, walk every node and every pod in the cluster and build a map from (topologyKey, topologyValue) to a count of matching pods. Then in Filter, for each candidate node, look up (topologyKey, node.Labels[topologyKey]) for every label on the node and reject if any count is zero.

That is O(cluster) work in PreFilter and O(labels on node) work per candidate. Both are fine at small scale and both are terrible at scale.

The expensive shape

The plugin’s own header comment describes the classic algorithm and the optimisation, and it is worth reading in full because it enumerates every case:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:47-59
// Overview of InterPodAffinityHostnameFastPath optimization:
// The InterPodAffinityHostnameFastPath feature optimizes performance of PreFilter and Filter for required
// (anti) affinity that exclusively uses the kubernetes.io/hostname topology.
//
// In the general case, an existing pod anywhere in the cluster can affect whether an incoming pod
// schedules on a particular node (for example, if they need to share the same "zone"). To handle this,
// the standard algorithm performs a heavy, cluster-wide topology map construction during PreFilter to
// track matching pods across all topologies. During Filter, the scheduler must then iterate over every label
// on a candidate node and perform hash map lookups to verify constraints against this global map.
//
// However, when rules use the `kubernetes.io/hostname` topology key, they only care about pods on that
// exact local node. By decoupling hostname-scoped rules, we can completely bypass the expensive topology
// map construction in PreFilter and the node-label iteration loops in Filter.

The global map has three flavours: existingClusterWideAntiAffinityCounts (existing pods that would reject the incoming pod), clusterWideAffinityCounts (existing pods that satisfy the incoming pod’s affinity) and clusterWideAntiAffinityCounts (existing pods that conflict with the incoming pod’s anti-affinity). All three are map[topologyPair]int64.

Classifying terms by scope

The optimisation starts by sorting the incoming pod’s terms into buckets by topology key:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:227-251
func (s *preFilterState) classifyTermsBasedOnScope() {
	if s.allHostScoped() {
		s.hostScopedAffinityTerms = s.podInfo.GetRequiredAffinityTerms()
	} else {
		s.clusterWideAffinityTerms = s.podInfo.GetRequiredAffinityTerms()
	}

	for _, t := range s.podInfo.GetRequiredAntiAffinityTerms() {
		if t.TopologyKey == v1.LabelHostname {
			s.hostScopedAntiAffinityTerms = append(s.hostScopedAntiAffinityTerms, t)
		} else {
			s.clusterWideAntiAffinityTerms = append(s.clusterWideAntiAffinityTerms, t)
		}
	}
}

// allHostScoped determines if we can bypass expensive global topology scans. If all affinity terms are host-scoped, we only need to check the local node's pods, which is much faster.
func (s *preFilterState) allHostScoped() bool {
	for _, t := range s.podInfo.GetRequiredAffinityTerms() {
		if t.TopologyKey != v1.LabelHostname {
			return false
		}
	}
	return true
}

Note the asymmetry already visible here: affinity terms are all-or-nothing (they go into hostScopedAffinityTerms or clusterWideAffinityTerms, never both), while anti-affinity terms are split term by term.

The reason is the logical structure of the two rules, and the comment above classifyTermsBasedOnScope states it precisely:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:215-223
// For affinity, we are deciding if a candidate node is valid for the incoming pod to land on.
// A node becomes valid if it (or its wider topology, like a zone) already hosts pods that match the incoming pod's rules.
// The algorithm searches for a SINGLE existing pod in that topology that matches ALL of the incoming pod's affinity rules at once.
// Because we must find this "single multi-matching pod" in the wider topology, we cannot evaluate the host-scoped and non-host-scoped terms independently; we must keep them grouped together in `clusterWideAffinityTerms`.
//
// For anti-affinity, we check with an OR of "Violated" (Violated A OR Violated B) to determine if a node violates ANY anti-affinity constraints of the incoming pod.
// Regardless of other terms, hostname-scoped anti-affinity can always be checked locally to avoid global scans for those specific terms.
// For example, if a pod has both hostname and zone anti-affinity rules, we can reject the node immediately if it violates the hostname rule, without checking the zone rule.
// Since a violation of either is sufficient to reject a node, they don't need to be checked together.

This is the single most important idea in the whole feature.

Affinity is a conjunction. The pod needs one existing pod that satisfies all of its affinity terms simultaneously. If one term is kubernetes.io/hostname and another is topology.kubernetes.io/zone, then the pod that satisfies both must be on the same node and in the same zone as the candidate — and you cannot find it by checking the candidate node’s pods and the zone’s pods separately. So the two terms cannot be split, and one non-hostname-scoped term drags the entire affinity evaluation back to the global map.

Anti-affinity is a disjunction. The node is rejected if it violates any anti-affinity term. So if the hostname-scoped term is violated, the node is rejected regardless of what the zone-scoped term says — you can check the hostname term locally and short-circuit. Splitting is safe.

That asymmetry is why allHostScoped() only inspects affinity terms, and why a pod with one hostname affinity term and one zone affinity term gets no benefit at all.

The local check

With the terms classified, the Filter phase does the obvious thing for hostname-scoped affinity:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:722-741
// nodePodsSatisfyAffinity performs a fast-path check to see if the target node already hosts at least one pod that satisfies the affinity rules (or if the pod satisfies self-affinity).
// It is used exclusively when ALL affinity terms on the incoming pod have the kubernetes.io/hostname topologyKey, in which case the global check is not required.
// Term matching is evaluated dynamically against the local node's PodInfo list because precomputing counts globally for every individual node would consume excessive resources.
func nodePodsSatisfyAffinity(state *preFilterState, nodeInfo fwk.NodeInfo) bool {
	if len(state.hostScopedAffinityTerms) == 0 {
		return true
	}
	if _, ok := nodeInfo.Node().Labels[v1.LabelHostname]; !ok {
		// Topology label kubernetes.io/hostname must be present on the node for the terms to match.
		return false
	}

	for _, existingPod := range nodeInfo.GetPods() {
		if podMatchesAllAffinityTerms(state.hostScopedAffinityTerms, existingPod.GetPod()) {
			return true
		}
	}
	// existing matching pod not found, check if self-affinity is satisfied
	return satisfiesSelfAffinityCheck(state, nodeInfo)
}

The mirror image for anti-affinity:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:684-704
// nodePodsConflictWithAntiAffinity returns true if the target node already hosts pods that conflict with the incoming pod's host-scoped anti-affinity rules.
// It is used for anti-affinity terms with the kubernetes.io/hostname topologyKey.
// Term matching is evaluated dynamically based on the node's PodInfo list because calculating pre-computed counts globally for every individual node would consume excessive resources.
func nodePodsConflictWithAntiAffinity(state *preFilterState, nodeInfo fwk.NodeInfo) bool {
	if len(state.hostScopedAntiAffinityTerms) == 0 {
		return false
	}
	if _, ok := nodeInfo.Node().Labels[v1.LabelHostname]; !ok {
		// Topology label kubernetes.io/hostname must be present on the node for the terms to match.
		return false
	}

	for _, existingPod := range nodeInfo.GetPods() {
		for _, term := range state.hostScopedAntiAffinityTerms {
			if term.Matches(existingPod.GetPod(), nil) {
				return true
			}
		}
	}
	return false
}

Note the different loop structure, and it is not accidental. Affinity uses podMatchesAllAffinityTerms — a single pod must match every term. Anti-affinity uses a nested loop — any pod matching any term rejects the node.

The Filter phase picks between them:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:832-856
	if state.enableInterPodAffinityHostnameFastPath {
		if len(state.hostScopedAffinityTerms) > 0 {
			if !nodePodsSatisfyAffinity(state, nodeInfo) {
				return fwk.NewStatus(fwk.UnschedulableAndUnresolvable, ErrReasonAffinityRulesNotMatch)
			}
		} else if len(state.clusterWideAffinityTerms) > 0 {
			if !nodeTopologyMatchesAffinity(state, nodeInfo) {
				return fwk.NewStatus(fwk.UnschedulableAndUnresolvable, ErrReasonAffinityRulesNotMatch)
			}
		}
	} else {
		if !nodeTopologyMatchesAffinity(state, nodeInfo) {
			return fwk.NewStatus(fwk.UnschedulableAndUnresolvable, ErrReasonAffinityRulesNotMatch)
		}
	}

	if state.enableInterPodAffinityHostnameFastPath {
		if nodeTopologyConflictsWithAntiAffinity(state, nodeInfo) || nodePodsConflictWithAntiAffinity(state, nodeInfo) {
			return fwk.NewStatus(fwk.Unschedulable, ErrReasonAntiAffinityRulesNotMatch)
		}
	} else {
		if !satisfyPodAntiAffinity(state, nodeInfo) {
			return fwk.NewStatus(fwk.Unschedulable, ErrReasonAntiAffinityRulesNotMatch)
		}
	}

The self-affinity escape hatch

There is a wrinkle. A pod with affinity to itself — the classic “first pod of a group” case — must be allowed to schedule when no other pod matches yet. The classic algorithm knows this because the global map is empty: len(clusterWideAffinityCounts) == 0 means nothing in the cluster matches, so if the pod matches its own terms, it is allowed.

The fast path throws the map away, so it loses that cluster-wide knowledge. The fix is a single global counter that answers the only question the map was being asked:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:128-131
	// matchingHostScopedAffinityPodsCount is the total number of pods in the cluster that match the incoming pod's host-scoped affinity terms.
	// It is used to optimize checks when all affinity terms in the incoming pod are host-scoped.
	// This will be 0 if the InterPodAffinityHostnameFastPath feature gate is disabled.
	matchingHostScopedAffinityPodsCount int64

and the check that uses it:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:774-793
func satisfiesSelfAffinityCheck(state *preFilterState, nodeInfo fwk.NodeInfo) bool {
	if state.enableInterPodAffinityHostnameFastPath {
		if state.matchingHostScopedAffinityPodsCount <= 0 && podMatchesAllAffinityTerms(state.podInfo.GetRequiredAffinityTerms(), state.podInfo.GetPod()) {
			for _, term := range state.podInfo.GetRequiredAffinityTerms() {
				if _, ok := nodeInfo.Node().Labels[term.TopologyKey]; !ok {
					return false
				}
			}
			return true
		}
		return false
	}

	// When FG is disabled, topologies were fully evaluated in nodeTopologyMatchesAffinity before this fallback.
	// The `len(state.clusterWideAffinityCounts) == 0` check is performed by the caller.
	if podMatchesAllAffinityTerms(state.podInfo.GetRequiredAffinityTerms(), state.podInfo.GetPod()) {
		return true
	}
	return false
}

One counter replaces a whole map. It is populated by a parallel scan of the cluster — the same scan the map would have needed — but it only counts:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:577-589
func (pl *InterPodAffinity) countMatchingHostScopedAffinityPodsGlobally(ctx context.Context, allNodes []fwk.NodeInfo, s *preFilterState) int64 {
	var count int64
	countMatchingPodsOnNode := func(i int) {
		nodeInfo := allNodes[i]
		var localCount int64
		for _, existingPod := range nodeInfo.GetPods() {
			if podMatchesAllAffinityTerms(s.hostScopedAffinityTerms, existingPod.GetPod()) {
				localCount++
			}
		}
		if localCount > 0 {
			atomic.AddInt64(&count, localCount)
		}

So the fast path does not eliminate the cluster-wide scan — it eliminates the map. The scan still happens, but it produces one integer instead of a map with an entry per (topology key, topology value) pair, and the Filter phase does not have to iterate the node’s labels at all.

Preemption keeps the counter honest

Preemption simulates eviction by adding and removing pods from the CycleState, and the counter has to move with it:

go
// pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:187-200
		if len(s.hostScopedAffinityTerms) > 0 {
			// hostScopedAffinityTerms only gets populated if ALL affinity terms of the incoming pod are host-scoped.
			//
			// This plugin keeps a running global counter of all matching pods in the cluster.
			// This counter is populated and updated iff the incoming pod has ONLY host-scoped affinity terms.
			//
			// If this counter is exactly 0, the plugin knows no existing pods satisfy the rules, permitting the first pod in a self-affinity group to pass this affinity check.
			// (If the pod has any non-host scoped affinity terms, this counter remains 0 and the plugin checks 'len(clusterWideAffinityCounts) == 0' instead).
			//
			// The multiplier (+1 or -1) adjusts this counter during "what-if" scheduling simulations like preemption.
			if podMatchesAllAffinityTerms(s.hostScopedAffinityTerms, pInfo.GetPod()) {
				s.matchingHostScopedAffinityPodsCount += multiplier
			}
		}

AddPod calls this with +1 and RemovePod with -1 (pkg/scheduler/framework/plugins/interpodaffinity/filtering.go:601-618). So when the preemption plugin “removes” a pod from a node in its dry run, the counter drops, and when it adds one back, the counter rises. The self-affinity escape hatch therefore behaves correctly inside a preemption simulation — which is exactly when you would not want a bug.

The scoring side

The Filter fast path is only half the story; the scoring side has its own optimisation, and it is a different one. Instead of a per-node computation, PreScore builds one map from topology key to topology value to score, and Score is then a lookup:

go
// pkg/scheduler/framework/plugins/interpodaffinity/scoring.go:190-211
	topoScores := make([]scoreMap, len(allNodes))
	index := int32(-1)
	processNode := func(i int) {
		nodeInfo := allNodes[i]

		// Unless the pod being scheduled has preferred affinity terms, we only
		// need to process pods with affinity in the node.
		podsToProcess := nodeInfo.GetPodsWithAffinity()
		if hasConstraints {
			// We need to process all the pods.
			podsToProcess = nodeInfo.GetPods()
		}

		topoScore := make(scoreMap)
		for _, existingPod := range podsToProcess {
			pl.processExistingPod(state, existingPod, nodeInfo, pod, topoScore)
		}
		if len(topoScore) > 0 {
			topoScores[atomic.AddInt32(&index, 1)] = topoScore
		}
	}
	pl.parallelizer.Until(pCtx, len(allNodes), processNode, pl.Name())

and the Score extension point itself is a single map read per topology key:

go
// pkg/scheduler/framework/plugins/interpodaffinity/scoring.go:242-257
func (pl *InterPodAffinity) Score(ctx context.Context, cycleState fwk.CycleState, pod *v1.Pod, nodeInfo fwk.NodeInfo) (int64, *fwk.Status) {
	node := nodeInfo.Node()

	s, err := getPreScoreState(cycleState)
	if err != nil {
		return 0, fwk.AsStatus(err)
	}
	var score int64
	for tpKey, tpValues := range s.topologyScore {
		if v, exist := node.Labels[tpKey]; exist {
			score += tpValues[v]
		}
	}

	return score, nil
}

scoreMap is map[string]map[string]int64 — topology key, then topology value, then the accumulated weight. Scoring a candidate node is a lookup of node.Labels[tpKey] in the outer map and then tpValues[v] in the inner one. No per-node iteration over the cluster’s pods at all.

Wrapping up

The one thing to remember: the fast path is not “the plugin is faster”, it is “the plugin does not build a cluster-wide map”. The gate is InterPodAffinityHostnameFastPath (alpha, default off, since 1.37), and it only helps when all of the incoming pod’s required affinity terms use kubernetes.io/hostname. Anti-affinity terms are split individually and always benefit.

The part people get wrong: people assume affinity and anti-affinity can both be decomposed per-term. They cannot. Affinity is a conjunction — one pod must satisfy every term — so a single zone-scoped affinity term forces the whole evaluation back onto the global map, no matter how many hostname-scoped terms are alongside it. If your pod has requiredDuringScheduling affinity with both kubernetes.io/hostname and topology.kubernetes.io/zone, the fast path does nothing for you.

What to go do about it: enable the feature gate with --feature-gates=InterPodAffinityHostnameFastPath=true on kube-scheduler and measure scheduler_framework_extension_point_duration_seconds{extension_point="PreFilter"} before and after. If your pods use hostname-scoped affinity, prefer preferredDuringScheduling over requiredDuringScheduling where you can — the scoring path already builds its topology map once in PreScore and is cheap, whereas the required path is the one that can force a cluster-wide scan. And if PreFilter latency is dominated by this plugin, check whether your affinity rules really need to be required: a preferred term with a weight of 100 gets you the same placement preference without the hard filter and the global scan.