Pod affinity and anti-affinity in Kubernetes - Time & Space Complexity

Time Complexity: Pod affinity and anti-affinity

O(n)

Understanding Time Complexity

When Kubernetes schedules pods, it checks rules like pod affinity and anti-affinity to decide where pods should run.

We want to understand how the time to make these decisions grows as the number of pods and nodes increases.

Scenario Under Consideration

Analyze the time complexity of this pod scheduling snippet with affinity rules.

apiVersion: v1
kind: Pod
metadata:
  name: example-pod
spec:
  affinity:
    podAffinity:
      requiredDuringSchedulingIgnoredDuringExecution:
      - labelSelector:
          matchExpressions:
          - key: security
            operator: In
            values:
            - S1
        topologyKey: kubernetes.io/hostname
  containers:
  - name: nginx
    image: nginx

This pod requests to be scheduled on a node where pods with label "security: S1" already run on the same hostname.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking all existing pods on all nodes to find matches for affinity rules.
• How many times: For each node, the scheduler scans pods running there to verify label matches.

How Execution Grows With Input

As the number of nodes and pods grows, the scheduler must check more pods per node to satisfy affinity rules.

Input Size (n)	Approx. Operations
10 nodes, 50 pods	Checks pods on each node, about 50 checks total
100 nodes, 500 pods	Checks increase roughly 10 times, about 500 checks
1000 nodes, 5000 pods	Checks increase roughly 100 times, about 5000 checks

Pattern observation: The number of checks grows roughly linearly with the total number of pods across nodes.

Final Time Complexity

Time Complexity: O(n)

This means the scheduling time grows roughly in direct proportion to the number of pods the scheduler must check for affinity.

Common Mistake

[X] Wrong: "The scheduler only checks one node or a fixed small number of pods regardless of cluster size."

[OK] Correct: The scheduler must evaluate all nodes and pods to find a suitable place, so the work grows with cluster size.

Interview Connect

Understanding how pod affinity affects scheduling time helps you explain real cluster behavior and scalability in interviews.

Self-Check

What if we changed requiredDuringSchedulingIgnoredDuringExecution to preferredDuringSchedulingIgnoredDuringExecution? How would the time complexity change?

Practice

1. What is the main purpose of podAffinity in Kubernetes?

easy

A. To automatically restart pods on failure

B. To prevent pods from running on the same node

C. To limit the number of pods per node

D. To schedule pods close to other pods with matching labels

Solution

1. Step 1: Understand podAffinity concept

   Pod affinity is used to place pods close to other pods that have specific labels, improving communication or resource sharing.

2. Step 2: Compare options with podAffinity purpose

   Only To schedule pods close to other pods with matching labels describes placing pods close to others with matching labels, which matches podAffinity's goal.

3. Final Answer:

   To schedule pods close to other pods with matching labels -> Option D

4. Quick Check:

   podAffinity = place pods close [OK]

Hint: Affinity means placing pods near each other [OK]

Common Mistakes:

• Confusing affinity with anti-affinity
• Thinking affinity limits pods per node
• Mixing affinity with pod restart policies

2. Which of the following is the correct syntax to specify a required pod anti-affinity rule in a pod spec?

easy

A. "podAntiAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": [{"labelSelector": {"matchLabels": {"app": "web"}}, "topologyKey": "kubernetes.io/hostname"}]}

B. "podAntiAffinity": {"preferredDuringSchedulingIgnoredDuringExecution": [{"weight": 100, "podAffinityTerm": {"labelSelector": {"matchLabels": {"app": "web"}}, "topologyKey": "kubernetes.io/hostname"}}]}

C. "podAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": [{"labelSelector": {"matchLabels": {"app": "web"}}, "topologyKey": "kubernetes.io/hostname"}]}

D. "podAffinity": {"preferredDuringSchedulingIgnoredDuringExecution": [{"weight": 50, "podAffinityTerm": {"labelSelector": {"matchLabels": {"app": "web"}}, "topologyKey": "kubernetes.io/zone"}}]}

Solution

1. Step 1: Identify required pod anti-affinity syntax

   Required pod anti-affinity uses podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution and a label selector plus topology key.

2. Step 2: Match syntax with options

   "podAntiAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": [{"labelSelector": {"matchLabels": {"app": "web"}}, "topologyKey": "kubernetes.io/hostname"}]} correctly uses podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution and proper labelSelector and topologyKey.

3. Final Answer:

   Correct required pod anti-affinity syntax -> Option A

4. Quick Check:

   Required anti-affinity uses podAntiAffinity + requiredDuringScheduling [OK]

Hint: Required anti-affinity uses podAntiAffinity + requiredDuringScheduling [OK]

Common Mistakes:

• Using podAffinity instead of podAntiAffinity
• Confusing required and preferred rules
• Wrong topologyKey values

3. Given this pod spec snippet, what will happen if a pod with label app: frontend is scheduled?

affinity:
  podAffinity:
    requiredDuringSchedulingIgnoredDuringExecution:
    - labelSelector:
        matchLabels:
          app: backend
      topologyKey: kubernetes.io/hostname

medium

A. The pod will be scheduled only if no pod with label app=backend exists

B. The pod will be scheduled on any node regardless of other pods

C. The pod will be scheduled on a node that already runs a pod with label app=backend

D. The pod scheduling will fail due to syntax error

Solution

1. Step 1: Understand required podAffinity behavior

   Required podAffinity means the pod must be placed on a node where pods with matching labels already run, here app=backend.

2. Step 2: Apply to given pod spec

   The pod with label app=frontend requires a node with pods labeled app=backend, so it will schedule only on such nodes.

3. Final Answer:

   The pod will be scheduled on a node that already runs a pod with label app=backend -> Option C

4. Quick Check:

   Required podAffinity = schedule near matching pods [OK]

Hint: Required podAffinity means schedule near matching pods [OK]

Common Mistakes:

• Thinking podAffinity prevents scheduling near pods
• Confusing required and preferred affinity
• Assuming scheduling fails without matching pods

4. You wrote this anti-affinity rule but pods are still scheduled on the same node:

podAntiAffinity:
  requiredDuringSchedulingIgnoredDuringExecution:
  - labelSelector:
      matchLabels:
        app: database
    topologyKey: ""

What is the likely cause?

medium

A. Empty topologyKey causes the rule to be ignored

B. Label selector is incorrect syntax

C. Required rules are always ignored by scheduler

D. podAntiAffinity must be under preferredDuringSchedulingIgnoredDuringExecution

Solution

1. Step 1: Check topologyKey usage

   The topologyKey must be a valid node label key like kubernetes.io/hostname. Empty string disables the rule.

2. Step 2: Understand scheduler behavior

   With empty topologyKey, the scheduler ignores the anti-affinity rule, allowing pods on same node.

3. Final Answer:

   Empty topologyKey causes the rule to be ignored -> Option A

4. Quick Check:

   Valid topologyKey needed for anti-affinity [OK]

Hint: topologyKey cannot be empty for anti-affinity rules [OK]

Common Mistakes:

• Leaving topologyKey empty
• Misplacing anti-affinity under preferred instead of required
• Assuming required rules are ignored

5. You want to deploy multiple replicas of a pod with label app: cache so that no two pods run on the same node, but you want the scheduler to try to keep pods in the same zone if possible. Which affinity configuration achieves this?

hard

A. Use podAffinity with requiredDuringSchedulingIgnoredDuringExecution on app: cache and topologyKey: kubernetes.io/hostname only

B. Use podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution on app: cache and topologyKey: kubernetes.io/hostname, plus podAffinity with preferredDuringSchedulingIgnoredDuringExecution on topologyKey: failure-domain.beta.kubernetes.io/zone

C. Use podAntiAffinity with preferredDuringSchedulingIgnoredDuringExecution on app: cache and topologyKey: kubernetes.io/hostname only

D. Use podAffinity with preferredDuringSchedulingIgnoredDuringExecution on app: cache and topologyKey: failure-domain.beta.kubernetes.io/zone only

Solution

1. Step 1: Prevent pods on same node strictly

   Use podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution and topologyKey: kubernetes.io/hostname to ensure no two pods run on the same node.

2. Step 2: Prefer pods in same zone

   Add podAffinity with preferredDuringSchedulingIgnoredDuringExecution and topologyKey: failure-domain.beta.kubernetes.io/zone to encourage scheduling pods in the same zone but not strictly.

3. Step 3: Combine both rules

   Use podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution on app: cache and topologyKey: kubernetes.io/hostname, plus podAffinity with preferredDuringSchedulingIgnoredDuringExecution on topologyKey: failure-domain.beta.kubernetes.io/zone combines strict anti-affinity on node and preferred affinity on zone, matching the requirement.

4. Final Answer:

   Use required podAntiAffinity on hostname and preferred podAffinity on zone -> Option B

5. Quick Check:

   Strict anti-affinity + preferred affinity = Use podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution on app: cache and topologyKey: kubernetes.io/hostname, plus podAffinity with preferredDuringSchedulingIgnoredDuringExecution on topologyKey: failure-domain.beta.kubernetes.io/zone [OK]

Hint: Use required anti-affinity on node + preferred affinity on zone [OK]

Common Mistakes:

• Using affinity instead of anti-affinity to separate pods
• Using preferred instead of required for strict separation
• Ignoring zone preference