Taints and tolerations in Kubernetes - Time & Space Complexity

Time Complexity: Taints and tolerations

O(p x n x t)

Understanding Time Complexity

We want to understand how the time to schedule pods changes when using taints and tolerations 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 the following Kubernetes scheduler logic snippet.

apiVersion: v1
kind: Pod
metadata:
  name: example-pod
spec:
  tolerations:
  - key: "key1"
    operator: "Equal"
    value: "value1"
    effect: "NoSchedule"

This pod has a toleration that allows it to be scheduled on nodes with a matching taint.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scheduler checks each pod against all nodes to find a suitable match considering taints and tolerations.
• How many times: For each pod, it loops through all nodes; for each node, it checks all taints and compares with pod tolerations.

How Execution Grows With Input

As the number of pods and nodes grows, the scheduler must do more checks.

Input Size (n)	Approx. Operations
10 pods, 10 nodes	~100 checks
100 pods, 100 nodes	~10,000 checks
1000 pods, 1000 nodes	~1,000,000 checks

Pattern observation: The number of checks grows quickly as both pods and nodes increase, roughly multiplying together.

Final Time Complexity

Time Complexity: O(p x n x t)

This means the scheduler's work grows proportionally with the number of pods (p), nodes (n), and taints per node (t).

Common Mistake

[X] Wrong: "The scheduler only checks each pod once, so time grows linearly with pods."

[OK] Correct: The scheduler must check each pod against every node's taints, so time grows with pods times nodes, not just pods.

Interview Connect

Understanding how scheduling scales helps you explain system behavior and design better cluster setups.

Self-Check

"What if nodes had no taints? How would the time complexity change for scheduling pods?"

Practice

1. What is the main purpose of a taint in Kubernetes?

easy

A. To repel pods from nodes unless they have matching tolerations

B. To allow pods to run on any node without restrictions

C. To label pods for easier identification

D. To increase node resource limits automatically

Solution

1. Step 1: Understand what a taint does

   A taint is applied to a node to repel pods that do not tolerate it.

2. Step 2: Compare with other options

   Options B, C, and D describe unrelated features: pod scheduling without restrictions, pod labeling, and resource limits, which are not taint functions.

3. Final Answer:

   To repel pods from nodes unless they have matching tolerations -> Option A

4. Quick Check:

   Taints repel pods without tolerations = A [OK]

Hint: Taints push pods away; tolerations allow pods to stay [OK]

Common Mistakes:

• Confusing taints with labels
• Thinking taints increase resources
• Assuming taints allow all pods

2. Which of the following is the correct syntax to add a taint to a node named node1 that repels pods without the matching toleration?

easy

A. kubectl taint nodes node1 key=value:NoSchedule

B. kubectl label nodes node1 key=value:NoSchedule

C. kubectl taint pods node1 key=value:NoSchedule

D. kubectl tolerate nodes node1 key=value:NoSchedule

Solution

1. Step 1: Identify the correct command for tainting nodes

   The command to add a taint is kubectl taint nodes followed by node name and taint details.

2. Step 2: Check the options

   kubectl taint nodes node1 key=value:NoSchedule uses the correct syntax. kubectl label nodes node1 key=value:NoSchedule uses label instead of taint. kubectl taint pods node1 key=value:NoSchedule tries to taint pods, which is invalid. kubectl tolerate nodes node1 key=value:NoSchedule uses a non-existent command.

3. Final Answer:

   kubectl taint nodes node1 key=value:NoSchedule -> Option A

4. Quick Check:

   Use kubectl taint nodes for taints = A [OK]

Hint: Use 'kubectl taint nodes' to add taints, not labels or pods [OK]

Common Mistakes:

• Using 'label' instead of 'taint'
• Trying to taint pods instead of nodes
• Using wrong command like 'tolerate'

3. Given the following pod spec snippet, what will happen if the node has the taint key=value:NoSchedule?

tolerations:
- key: "key"
  operator: "Equal"
  value: "value"
  effect: "NoSchedule"

medium

A. The pod will be scheduled but evicted immediately

B. The pod will be scheduled on the tainted node

C. The pod will be rejected and not scheduled

D. The pod will ignore the taint and schedule anywhere

Solution

1. Step 1: Understand the pod toleration

   The pod tolerates the taint with matching key, value, and effect, so it can be scheduled on the node.

2. Step 2: Analyze the taint effect

   The taint effect is NoSchedule, which prevents pods without tolerations from scheduling. Since this pod has the matching toleration, it is allowed.

3. Final Answer:

   The pod will be scheduled on the tainted node -> Option B

4. Quick Check:

   Matching toleration allows scheduling despite taint = C [OK]

Hint: Matching toleration lets pod schedule on tainted node [OK]

Common Mistakes:

• Ignoring the value match in toleration
• Confusing NoSchedule with NoExecute
• Assuming tolerations always allow scheduling

4. You applied the taint key=value:NoSchedule to a node, but pods without tolerations are still scheduling on it. What is the most likely cause?

medium

A. Pods have tolerations matching the taint

B. Taints do not affect scheduling

C. The node is in a NotReady state

D. The taint was applied with a typo in the key or value

Solution

1. Step 1: Check taint correctness

   If pods without tolerations schedule on a tainted node, the taint might have a typo or was not applied correctly.

2. Step 2: Evaluate other options

   Pods have tolerations matching the taint means pods tolerate the taint, which contradicts the question. The node is in a NotReady state is unrelated to taints. Taints do not affect scheduling is false because taints do affect scheduling.

3. Final Answer:

   The taint was applied with a typo in the key or value -> Option D

4. Quick Check:

   Incorrect taint syntax causes scheduling errors = B [OK]

Hint: Check taint spelling carefully if pods ignore it [OK]

Common Mistakes:

• Assuming taints don't affect scheduling
• Ignoring typos in taint keys or values
• Confusing node status with taint issues

5. You want to ensure that only pods with a specific toleration can run on a node, and all other pods are evicted if already running. Which taint effect should you use?

hard

A. NoSchedule

B. PreferNoSchedule

C. NoExecute

D. NoEvict

Solution

1. Step 1: Understand taint effects

   NoSchedule prevents new pods without tolerations from scheduling. PreferNoSchedule tries to avoid scheduling but doesn't guarantee. NoExecute evicts existing pods without tolerations and prevents new ones. NoEvict is not a valid effect.

2. Step 2: Match requirement to effect

   Since you want to evict existing pods without tolerations, NoExecute is the correct effect.

3. Final Answer:

   NoExecute -> Option C

4. Quick Check:

   Evict pods without tolerations = NoExecute = D [OK]

Hint: Use NoExecute to evict pods lacking tolerations [OK]

Common Mistakes:

• Choosing NoSchedule which doesn't evict existing pods
• Confusing PreferNoSchedule with eviction
• Using invalid effect NoEvict