Scheduler Performance at Large Scale

Scheduler as Bottleneck

Kubernetes scheduler watches unscheduled Pods, matches Pods to nodes, assigns Pods. Single-threaded event loop processes one Pod at a time. At 1000 nodes:

• Node evaluations per Pod: O(n) = 1000 predicates
• Affinity/anti-affinity checks: additional O(m) where m = Pods on node
• Pending queue: 1000s Pods if churn high
• Scheduling latency: 100ms → 10 seconds as queue grows

Impact: Pods sit Pending longer → app startup delayed → SLO miss.

Internal Model: Scheduling Algorithm

High-Level Flow

1. Watch unscheduled Pod (PodScheduled=false)
2. EnqueuePod() → add to scheduling queue

3. Main loop:
   pod := queue.Pop()  // dequeue Pod
   
   // Find feasible nodes (predicates)
   feasible := []
   for node := range nodes {
     if predicate(pod, node) {  // resource fit, affinity, taint/toleration
       feasible.append(node)
     }
   }
   
   // Score feasible nodes (priorities)
   scores := {}
   for node := range feasible {
     score := 0
     score += imageLoaclity(pod, node)  // prefer nodes with image
     score += spreadPriority(pod, node) // spread across nodes
     score += leastRequestedPriority(pod, node)  // favor less loaded
     scores[node] = score
   }
   
   // Bind to best node
   bestNode := max(scores)
   bind(pod, bestNode)

Predicate Evaluation (Filtering)

Predicates are boolean checks. Pod scheduled only if all predicates pass.

Common predicates:

• PodFitsResources: allocatable >= requested
• NodeMemoryPressure: node not under memory pressure
• PodFitsHostPorts: port conflict check
• NoDiskConflict: volume claim check
• MatchNodeSelector: node label selector
• PodToleratesNodeTaints: taint/toleration match
• PodAffinityPredicate: pod affinity (complex, O(m) where m = Pods on node)

Complexity:

• Simple predicates (resource check): O(1)
• Affinity predicates: O(m) where m = Pods on candidate node
• For 1000 nodes × average O(m) = O(1000 * m) per Pod

At scale: If Pod has complex affinity (topologySpreadConstraints), evaluating all 1000 nodes can take 50-100ms per Pod. With 10,000 pending Pods, scheduling 1000 Pods/second = impossible, latency increases.

Priority Scoring (Ranking)

After filtering (only feasible nodes), scheduler scores feasible nodes.

Scoring priorities:

• Least Requested: nodes with least resource usage (spreading)
• Most Requested: nodes with most usage (bin packing)
• Image Locality: nodes that already have Pod image cached
• Balancing Resource: balance CPU/memory usage across nodes
• Zone Spreading: spread Pods across zones (high availability)

Complexity: O(feasible_nodes) per priority × number of priorities = O(feasible × priorities) total.

At scale: Feasible nodes might be 500 (out of 1000). 5 priorities × 500 nodes = 2500 score evaluations per Pod. With 10 Pods queued, = 25,000 evaluations sequentially.

Caching for Speed

Scheduler maintains node cache to avoid fetching fresh node data from API server every time.

nodeCache = {
  "node-1": {
    allocatable: {cpu: 7600m, memory: 29GB},
    allocatedResources: {cpu: 2000m, memory: 5GB},
    podList: [pod1, pod2, ...],
    taints: [...],
    labels: {...}
  },
  ...
}

Cache invalidated on node update (label change, taint addition). If cache stale, scheduling decisions wrong (e.g., schedule Pod to node with no IP available).

Cache consistency: GKE uses informer cache, which watches API server. Latency ~100ms, so cache might be slightly stale but eventually consistent.

Scheduling Latency Curve

As cluster approaches limits:

Pods pending | Scheduling latency (ms)
0-100       | 10-20
100-500     | 20-50
500-1000    | 50-100
1000-5000   | 100-500
5000+       | 500-2000+

Beyond 5000 pending Pods, latency becomes unacceptable (>1 second per Pod).

GKE Optimization: Topology Aware Scheduling (TAS)

Problem: Default Scheduler Spreads Pods

Default scheduler uses SelectorSpreadPriority — spreads replicas across nodes/zones for resilience. BUT for ML training (distributed jobs), spreading = network hops = latency.

TAS Solution

TAS (Google-specific extension) places worker Pods close together (same ToR switch) when training job specified:

apiVersion: batch/v1
kind: Job
metadata:
  name: train
spec:
  completions: 100
  parallelism: 100
  template:
    spec:
      topologySpreadConstraints:
      - maxSkew: 1
        topologyKey: topology.kubernetes.io/zone  # spread across zones
        whenUnsatisfiable: DoNotSchedule
      - maxSkew: 10  # allow up to 10 skew on hostname
        topologyKey: kubernetes.io/hostname
        whenUnsatisfiable: ScheduleAnyway
      affinity:
        podAntiAffinity:
          preferredDuringSchedulingIgnoredDuringExecution:
          - weight: 100
            podAffinityTerm:
              topologyKey: cloud.google.com/gke-nodepool

Result: Workers packed on same node pool, low latency inter-worker communication.

Predicate Optimization at Scale

Predicate Short-Circuiting

If first predicate fails, stop evaluating (don't check remaining predicates).

Example:

Pod requests 4 CPU, node allocatable 1 CPU → PodFitsResources fails
→ Don't check affinity, taint, port predicates (waste)

Scheduler should prioritize cheap predicates first (resource check), expensive last (affinity).

Pre-filtering Cache

Some predicates have pre-computed state. Example: PodAffinityPredicate needs to know "which Pods running on this node". Instead of fetching every time, cache per node.

nodeCache[node].podsByLabel[label] = [pod1, pod2, ...]

Lookup O(1) instead of O(m).

Real-World Scenario: Rolling Update Cascading Delay

Case: 1000-node cluster, rolling update of Deployment (100 replicas → new image).

Timeline:

1. Kubernetes kills 25% old Pods (surge=25%)
2. Deployment controller spawns 25% new Pods
3. Scheduler dequeues new Pods
4. Predicate: old Pods still have node bindings (not fully removed yet)
5. Affinity check: new Pods might have antiAffinity to old Pods → more nodes to check
6. Scheduling latency: 100-200ms per Pod × 25 Pods = 2-5 seconds to schedule wave
7. Meanwhile, old Pods still terminating
8. Cascade: each wave delayed, rolling update takes minutes instead of 10 seconds

Resolution:

• Set terminationGracePeriodSeconds low (5-10s, default 30s)
• Increase surge% (more parallel wave)
• Disable/simplify anti-affinity during rolling
• Use Deployment.strategy.maxSurge/maxUnavailable tuning

References

• Kubernetes Scheduler
• GKE Topology Aware Scheduling
• Scheduler Performance Tuning