Minimum Rollout Steps Under Surge and Unavailability

hardPROKubernetes Scheduling & RolloutsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

Simulate a rolling update and count how many batch steps it takes to move from all-old to all-new pods, respecting maxSurge and maxUnavailable.

Background

Start with replicas old pods, target replicas new pods. Total pods may range within [replicas - maxUnavailable, replicas + maxSurge]. Each step, the controller: (1) creates as many new pods as surge allows (up to replicas + maxSurge total), then (2) deletes old pods as long as available (non-terminating) pods stay >= replicas - maxUnavailable. Count steps until all pods are new. Model each step as: can_add = (replicas + maxSurge) - (old + new); add that many new; then can_remove = (new + old) - (replicas - maxUnavailable) old pods removed (bounded by old remaining and by new pods created so far able to serve). Return the number of steps. Assume maxSurge + maxUnavailable >= 1 so progress is always possible.

Your Task

def rollout_steps(replicas, max_surge, max_unavailable):

Return the number of steps (int) to fully roll out.

Input Format

replicas (int), max_surge (int), max_unavailable (int).

Output Format

A single int.

Sample

print(rollout_steps(4, 1, 1))

Output:

Example

Input

print(rollout_steps(4, 1, 1))

Output

Reasoning

Initialization: Start with old = 4 (all pods are old) and new = 0. The target is new = 4. The minimum allowed total pods is $4 - 1 = 3$ , and the maximum allowed is $4 + 1 = 5$ .
Step 1:
- Add: We can add up to $5 - (4 + 0) = 1$ new pod. So, new becomes $0 + 1 = 1$ .
- Remove: The current total pods is $4 + 1 = 5$ . We can remove up to $5 - 3 = 2$ old pods, but we are limited by the number of new pods created so far (1) to ensure service availability. Thus, we remove 1 old pod. old becomes $4 - 1 = 3$ .
- State: old = 3, new = 1.
Step 2:
- Add: We can add up to $5 - (3 + 1) = 1$ new pod. So, new becomes $1 + 1 = 2$ .
- Remove: The current total pods is $3 + 2 = 5$ . We can remove up to $5 - 3 = 2$ old pods. We are limited by the number of new pods (2), so we remove 2 old pods. old becomes $3 - 2 = 1$ .
- State: old = 1, new = 2.
Step 3:
- Add: We can add up to $5 - (1 + 2) = 2$ new pods. We need $4 - 2 = 2$ more to reach the target. So, we add 2. new becomes $2 + 2 = 4$ .
- Remove: The current total pods is $1 + 4 = 5$ . We can remove up to $5 - 3 = 2$ old pods. We only have 1 old pod left, so we remove 1. old becomes $1 - 1 = 0$ .
- State: old = 0, new = 4.
The loop terminates because new has reached replicas (4). The total number of steps taken is 3.
The final output is 3

Constraints

Pods count stays within [replicas - maxUnavailable, replicas + maxSurge].
Each step: add new up to surge cap, then remove old down to the availability floor.
Return the step count; maxSurge + maxUnavailable >= 1.

Learn this in

Orchestration & ScalingSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primerPREVIEW

1. Background Knowledge

A rolling update in Kubernetes gradually replaces old-version pods with new-version pods without taking the service offline. The controller is constrained by two knobs: maxSurge (how many extra pods above the desired replicas may exist temporarily) and maxUnavailable (how many fewer than replicas may be running at once). At any moment the total pod count must stay within the window $[\text{replicas} - \text{maxUnavailable},\ \text{replicas} + \text{maxSurge}]$ .

The controller operates in discrete steps (also called batches). Within one step it first adds new pods up to the surge ceiling, then removes old pods down to the unavailability floor. The ordering matters: you cannot delete an old pod before a new one is ready to serve traffic, so the number of deletions in a step is bounded by how many new pods have been created so far (cumulatively) and by the floor constraint.

Think of the state as a pair $(\text{old}, \text{new})$ where $\text{old} + \text{new}$ is the current total. The goal is to reach $(0, \text{replicas})$ . Because the problem guarantees $\text{maxSurge} + \text{maxUnavailable} \ge 1$ , at least one pod can change per step, so termination is assured.

2. Algorithm Approach

This is a simulation problem. There is no closed-form shortcut that is worth deriving; instead you iterate step-by-step, updating old and new according to the two-phase rule until old == 0. The key insight is that each step is deterministic given the current state, so a simple while loop suffices.

The per-step logic:

Compute how many new pods can be added: can_add = (replicas + max_surge) - (old + new).
Add can_add new pods (capped at replicas - new since you never need more than replicas new pods total).
Compute how many old pods can be removed: can_remove = (old + new) - (replicas - max_unavailable).
Cap can_remove by old (can't remove more than exist) and by the number of new pods available to serve (cumulative new).
Decrement old by can_remove.

3. Step-by-Step Strategy

Initialize: old = replicas, new = 0, steps = 0.
Loop while old > 0:
Increment steps.
Phase 1 – Add: can_add = (replicas + max_surge) - (old + new). Clamp to max(0, replicas - new) so you don't overshoot the target. Set new += can_add.
Phase 2 – Remove: can_remove = (old + new) - (replicas - max_unavailable). Clamp to max(0, min(old, new)) — you cannot remove more old pods than exist, nor more than the new pods that can serve them. Set old -= can_remove.
Return steps.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.