Performance cost — large topology domains and broad selectors

Pod affinity and anti-affinity walk the cluster’s Pod list at scheduling time. The cost is proportional to the topology domain size and the selector’s breadth. This lesson covers the cost model, the worst-case scenarios, and the patterns that keep the scheduler fast.

The cost model

flowchart LR
    A[Scheduler receives Pod] --> B[Filter phase]
    B --> C[Affinity filter]
    C --> D{For each candidate node}
    D --> E{For each Pod on node}
    E --> F{Selector matches?}
    F --> G{Constraint satisfied?}
    D --> H["O(N x P)<br/>N nodes, P Pods"]
    H --> I[Cost grows with N and P]

The cost is O(N × P) where N is the number of nodes considered and P is the average Pod count per node. The scheduler caches Pods; the cost is amortised across scheduling decisions, but the first scheduling of a Pod with broad affinity can be slow.

Large topology domains

flowchart TB
    A[Topology key] -->|kubernetes.io/hostname| B["Same node<br/>~tens of Pods"]
    A -->|topology.kubernetes.io/zone| C["Same zone<br/>hundreds to thousands of Pods"]
    A -->|topology.kubernetes.io/region| D["Same region<br/>tens of thousands of Pods"]

A selector with topologyKey: kubernetes.io/hostname walks one node’s Pods. A selector with topologyKey: topology.kubernetes.io/zone walks every node in the zone. A region-level selector walks every node in the region.

For a cluster with 1000 nodes and 1000 zones:

• Hostname: ~10 Pods per node → ~10 evaluations per scheduling decision.
• Zone: ~1000 nodes per zone × ~10 Pods → ~10,000 evaluations per scheduling decision.
• Region: ~1,000,000 evaluations per scheduling decision.

The region-level topology is impractical for large clusters.

Broad selectors

labelSelector:
  matchLabels:
    app: web

A selector that matches many Pods (e.g., all web Pods in a 1000-replica Deployment) requires walking 1000 Pods per node.

flowchart TB
    A[Selector breadth] -->|narrow<br/>1-10 Pods| B[Fast]
    A -->|medium<br/>10-100 Pods| C[Moderate]
    A -->|broad<br/>100-1000+ Pods| D[Slow]
    D --> E[Cost dominates scheduler latency]

The worst-case scenario

A selector matching all Pods (no labels) on every node in a region:

labelSelector:
  matchExpressions:
  - key: app
    operator: Exists

This selector matches every Pod with any app label. With 100,000 Pods cluster-wide, the scheduler walks all 100,000 at every scheduling decision.

flowchart LR
    A["Selector: Exists"] --> B[Matches all Pods with app label]
    B --> C[Scheduler walks all Pods]
    C --> D[10,000+ Pods per node]
    D --> E[100,000+ Pods cluster-wide]
    E --> F[Seconds per scheduling decision]

The mitigation patterns

Pattern 1: tight selectors

labelSelector:
  matchLabels:
    app: cache
    cache-type: redis

A selector that matches only Redis cache Pods, not all Pod’s with app: cache. Tight selectors are fast.

Pattern 2: narrow topology

topologyKey: kubernetes.io/hostname

Hostname topology walks fewer Pods. Zone topology is acceptable for many use cases; region is usually too broad.

Pattern 3: caching

The scheduler caches Pods and their selectors. The cache is updated by watch events. For a Pod’s first scheduling, the cache may not be fully populated, leading to slower scheduling. Subsequent schedulings are faster.

Pattern 4: topology spread over anti-affinity

flowchart LR
    A{Spread requirement}
    A -->|Balanced distribution| B["Topology spread<br/>cheaper"]
    A -->|Strict separation| C["Anti-affinity<br/>more expensive"]
    B --> D["Counting Pods per domain<br/>not walking selectors"]
    C --> E[Walking selectors per node]

Topology spread uses a counter (Pod count per domain) rather than a selector walk. The cost is O(N) where N is the number of domains, not O(N × P) like anti-affinity.

For most “spread replicas” use cases, topology spread is the cheaper and better choice.

Pattern 5: scheduler tuning

The kube-scheduler’s flags control behaviour:

kube-scheduler \
  --scheduler-name=default \
  --config=/etc/kubernetes/scheduler-config.yaml \
  --percentage-of-nodes-to-score=50 \
  --bind-timeout=100s

--percentage-of-nodes-to-score (default 100, may be tuned) limits how many nodes the score phase considers. Lower values trade accuracy for speed.

Monitoring scheduling latency

# Prometheus metrics from kube-scheduler
scheduler_e2e_scheduling_duration_seconds
scheduler_scheduling_algorithm_duration_seconds
scheduler_cache_size

A dashboard that surfaces these metrics catches performance degradation. The scheduler_e2e_scheduling_duration_seconds histogram shows the time from Pod creation to bind; the scheduler_cache_size gauge shows the cache memory.

flowchart TB
    A[Metrics] --> B[scheduler_e2e_scheduling_duration_seconds]
    A --> C[scheduler_cache_size]
    A --> D[scheduler_pending_pods]
    B --> E{P99 > 100ms?}
    C --> F{Cache > 10MB?}
    D --> G{Pending > 100?}
    E -->|yes| H[Investigate broad affinity]
    F -->|yes| H
    G -->|yes| H

Failure modes

Failure 1: scheduler is slow

flowchart TB
    A[Scheduler latency p99 > 1s] --> B{Affinity usage?}
    B -->|broad selectors| C[Tighten selectors]
    B -->|zone/region topology| D[Narrow to hostname]
    B -->|many Pods per node| E[Topology spread instead]
    C --> F[Verify latency]
    D --> F
    E --> F

The fix: tighten selectors, narrow topology, or switch to topology spread.

Failure 2: scheduler OOM

The scheduler’s cache grows with cluster size. With 100,000 Pods, the cache can be hundreds of MB. The scheduler’s memory limit must accommodate this.

# kube-scheduler memory limit
--scheduler-name=default \
--config=/etc/kubernetes/scheduler-config.yaml

The scheduler’s leader-elect lease and metrics add to memory usage. Tune the memory limit accordingly.

Failure 3: scheduling hangs

A selector with a typo (e.g., app: webb) matches no Pods. The filter passes trivially; the score phase adds no bonus. The Pod schedules, but the operator expected the preference to apply.

The fix: verify the selector matches the intended Pods.

Quiz

Production discipline

• Tight selectors. A selector matching 1-10 Pods is fast; a selector matching 100+ is slow.
• Narrow topology. Hostname is the narrowest; zone is acceptable; region is too broad for most clusters.
• Use topology spread for replica distribution. It’s cheaper than anti-affinity for the “spread evenly” use case.
• Monitor scheduling latency. A dashboard that surfaces p99 scheduling time catches performance regressions.
• Audit affinity usage. A query for Pods with broad selectors (e.g., app: web with 100+ replicas) flags candidates for tightening.

Pod affinity is a powerful tool, but its cost is real. Operators who use it deliberately have schedulers that stay fast.