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

Time Complexity: Node affinity and anti-affinity

O(n * m)

Understanding Time Complexity

We want to understand how the time to schedule pods changes when using node affinity and anti-affinity rules in Kubernetes.

Specifically, how does the scheduler's work grow as the number of nodes and pods increases?

Scenario Under Consideration

Analyze the time complexity of this node affinity and anti-affinity snippet.

apiVersion: v1
kind: Pod
metadata:
  name: example-pod
spec:
  affinity:
    nodeAffinity:
      requiredDuringSchedulingIgnoredDuringExecution:
        nodeSelectorTerms:
        - matchExpressions:
          - key: disktype
            operator: In
            values:
            - ssd
    podAntiAffinity:
      requiredDuringSchedulingIgnoredDuringExecution:
      - labelSelector:
          matchExpressions:
          - key: app
            operator: In
            values:
            - frontend
        topologyKey: kubernetes.io/hostname

This pod requires nodes labeled with "disktype=ssd" and avoids nodes with pods labeled "app=frontend" on the same host.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scheduler checks each node's labels and running pods to match affinity and anti-affinity rules.
• How many times: It repeats this check for every node and for pods on those nodes.

How Execution Grows With Input

As the number of nodes (n) and pods per node (m) grow, the scheduler must check more labels and pods.

Input Size (n nodes, m pods/node)	Approx. Operations
10 nodes, 5 pods/node	~50 checks
100 nodes, 10 pods/node	~1000 checks
1000 nodes, 20 pods/node	~20,000 checks

Pattern observation: The checks grow roughly with the number of nodes times the pods per node.

Final Time Complexity

Time Complexity: O(n * m)

This means the scheduler's work grows proportionally with the number of nodes and pods it must evaluate.

Common Mistake

[X] Wrong: "The scheduler only checks node labels once, so time stays the same no matter how many pods or nodes there are."

[OK] Correct: The scheduler must check each node and the pods on it to apply affinity and anti-affinity rules, so more nodes and pods mean more checks.

Interview Connect

Understanding how scheduling time grows helps you explain how Kubernetes handles workloads efficiently and what might slow it down as clusters grow.

Self-Check

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

Practice

1. What does nodeAffinity in Kubernetes primarily control?

easy

A. Which nodes a pod can be scheduled on based on node labels

B. The order in which pods start in a deployment

C. The network policies applied to pods

D. The resource limits of a pod

Solution

1. Step 1: Understand nodeAffinity purpose

   Node affinity is used to specify rules about which nodes a pod can run on, based on labels assigned to nodes.

2. Step 2: Compare options to nodeAffinity function

   Options B, C, and D relate to pod startup order, network policies, and resource limits, which are unrelated to node affinity.

3. Final Answer:

   Which nodes a pod can be scheduled on based on node labels -> Option A

4. Quick Check:

   nodeAffinity controls pod placement on nodes [OK]

Hint: Node affinity = pod placement by node labels [OK]

Common Mistakes:

• Confusing node affinity with pod resource limits
• Thinking node affinity controls pod startup order
• Mixing node affinity with network policies

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

easy

A. "nodeAffinity": {"preferredDuringSchedulingIgnoredDuringExecution": [{"weight": 1, "preference": {"matchExpressions": [{"key": "disktype", "operator": "In", "values": ["ssd"]}]}}]}

B. "podAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": {"labelSelector": {"matchLabels": {"disktype": "ssd"}}}}

C. "nodeSelector": {"disktype": "ssd"}

D. "nodeAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": {"nodeSelectorTerms": [{"matchExpressions": [{"key": "disktype", "operator": "In", "values": ["ssd"]}]}]}}

Solution

1. Step 1: Identify required node affinity syntax

   Required node affinity uses the key requiredDuringSchedulingIgnoredDuringExecution with nodeSelectorTerms and matchExpressions to specify node labels.

2. Step 2: Check options for correct structure

   "nodeAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": {"nodeSelectorTerms": [{"matchExpressions": [{"key": "disktype", "operator": "In", "values": ["ssd"]}]}]}} matches the required node affinity syntax. "nodeAffinity": {"preferredDuringSchedulingIgnoredDuringExecution": [{"weight": 1, "preference": {"matchExpressions": [{"key": "disktype", "operator": "In", "values": ["ssd"]}]}}]} is preferred affinity, C is nodeSelector (different syntax), and D is pod affinity, not node affinity.

3. Final Answer:

   "nodeAffinity": {"requiredDuringSchedulingIgnoredDuringExecution": {"nodeSelectorTerms": [{"matchExpressions": [{"key": "disktype", "operator": "In", "values": ["ssd"]}]}]}} -> Option D

4. Quick Check:

   Required node affinity uses requiredDuringSchedulingIgnoredDuringExecution [OK]

Hint: Required node affinity uses requiredDuringSchedulingIgnoredDuringExecution [OK]

Common Mistakes:

• Confusing preferred and required affinity syntax
• Using podAffinity instead of nodeAffinity
• Mixing nodeSelector with nodeAffinity syntax

3. Given this pod spec snippet, what will happen if a node has label zone: us-east-1a but no label disk: ssd?

{
  "affinity": {
    "nodeAffinity": {
      "requiredDuringSchedulingIgnoredDuringExecution": {
        "nodeSelectorTerms": [
          {
            "matchExpressions": [
              {"key": "zone", "operator": "In", "values": ["us-east-1a"]},
              {"key": "disk", "operator": "In", "values": ["ssd"]}
            ]
          }
        ]
      }
    }
  }
}

medium

A. The pod will be scheduled only if preferredDuringScheduling is set

B. The pod will not be scheduled on the node because it lacks the required disk label

C. The pod will be scheduled but with a warning

D. The pod will be scheduled because the zone label matches

Solution

1. Step 1: Analyze required node affinity conditions

   Required node affinity means all match expressions must be true for scheduling. The node must have both zone: us-east-1a and disk: ssd labels.

2. Step 2: Check node labels against requirements

   The node has zone: us-east-1a but lacks disk: ssd. This fails the required condition, so the pod cannot be scheduled there.

3. Final Answer:

   The pod will not be scheduled on the node because it lacks the required disk label -> Option B

4. Quick Check:

   Required affinity needs all labels matched [OK]

Hint: Required affinity means all labels must match [OK]

Common Mistakes:

• Assuming partial label match is enough
• Confusing required with preferred affinity
• Thinking pod schedules with warnings on missing labels

4. You wrote this pod spec with pod anti-affinity but pods are still scheduled on the same node. What is the likely error?

affinity:
  podAntiAffinity:
    preferredDuringSchedulingIgnoredDuringExecution:
    - weight: 100
      podAffinityTerm:
        labelSelector:
          matchLabels:
            app: myapp
        topologyKey: "kubernetes.io/hostname"

medium

A. Incorrect labelSelector syntax causes failure

B. Missing nodeSelector in the pod spec

C. Using preferred instead of required anti-affinity allows scheduling on same node

D. topologyKey should be set to "zone" instead of hostname

Solution

1. Step 1: Understand pod anti-affinity types

   Preferred anti-affinity suggests avoiding co-location but does not enforce it strictly. Required anti-affinity enforces pods not to be scheduled together.

2. Step 2: Analyze the pod spec anti-affinity type

   The spec uses preferredDuringSchedulingIgnoredDuringExecution, which is a soft rule. This allows pods to be scheduled on the same node if needed.

3. Final Answer:

   Using preferred instead of required anti-affinity allows scheduling on same node -> Option C

4. Quick Check:

   Preferred anti-affinity is a soft rule [OK]

Hint: Preferred anti-affinity is soft; use required to enforce [OK]

Common Mistakes:

• Confusing preferred and required anti-affinity
• Assuming labelSelector syntax is wrong without checking
• Thinking topologyKey must be zone for anti-affinity

5. You want to ensure pods with label app=frontend never run on the same node as pods with label app=backend. Which affinity configuration achieves this?

hard

A. Use podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution and labelSelector matching app=backend

B. Use nodeAffinity with requiredDuringSchedulingIgnoredDuringExecution and labelSelector matching app=backend

C. Use podAffinity with preferredDuringSchedulingIgnoredDuringExecution and labelSelector matching app=backend

D. Use nodeSelector with label app=backend

Solution

1. Step 1: Identify requirement to prevent co-location of pods

   Pod anti-affinity prevents pods from running on the same node as other pods matching certain labels.

2. Step 2: Choose required anti-affinity for strict enforcement

   Using requiredDuringSchedulingIgnoredDuringExecution enforces pods never co-locate on the same node.

3. Step 3: Match labelSelector to pods to avoid

   The labelSelector should match pods with app=backend to prevent frontend pods from scheduling on same node.

4. Final Answer:

   Use podAntiAffinity with requiredDuringSchedulingIgnoredDuringExecution and labelSelector matching app=backend -> Option A

5. Quick Check:

   Pod anti-affinity + required = strict pod separation [OK]

Hint: Use required podAntiAffinity to strictly separate pods [OK]

Common Mistakes:

• Using nodeAffinity instead of podAntiAffinity for pod separation
• Using preferred instead of required anti-affinity for strict rules
• Confusing podAffinity with podAntiAffinity