StaffInfrastructureScheduling

Design a Distributed Task Scheduler

A full Staff-level walkthrough of a Borg/Kubernetes-style cluster scheduler that places millions of containers across 100K+ machines — trading scheduling latency against bin-packing optimality, with priority preemption, autoscaling, and multi-tenant quotas. Follow it top to bottom, or jump to any step.

Level: Staff
Category: Scheduling · Infrastructure
Interview time: 45 min

100% free · No login required

WHAT THIS QUESTION TESTS

·Two-phase scheduling: filtering then scoring

·Priority preemption with anti-starvation

·Autoscaling: HPA + cluster autoscaler

·Failure recovery and reschedule on machine loss

★ STAFF-LEVEL SIGNALS

★Partitioned shared-state schedulers (Omega-style) over a single scheduler

★Quantifies tradeoffs across four scheduler architectures

★Shards etcd by namespace; in-memory aggregated machine view

★Multi-tenant quotas with burst, reclamation, and per-team preemption budgets

Scope & ambiguity

Framing statement

“A distributed task scheduler at hyperscale manages millions of containers across hundreds of thousands of machines. The key challenge is scheduling latency vs optimality — finding the best machine for each task quickly enough to not bottleneck deployment velocity. I’ll focus on the scheduling algorithm, resource management, and multi-tenancy isolation.”

Phased delivery

Phase

Timeline

Scope

Phase 1

0–4 months

Single-cluster scheduler, bin-packing, priority preemption

Phase 2

4–10 months

Multi-cluster federation, autoscaling, placement constraints

Phase 3

10–18 months

ML-based scheduling optimization, gang scheduling, spot/preemptible support

Requirements

Functional requirements

FR1 — Schedule containers/tasks onto a fleet of machines based on resource requirements
FR2 — Support priority levels with preemption (high-priority evicts low-priority)
FR3 — Placement constraints (zone, GPU, SSD requirements)
FR4 — Automatic failure recovery (reschedule on machine failure)
FR5 — Autoscaling (scale tasks based on CPU/memory/custom metrics)
FR6 — Multi-tenancy with resource quotas per team

Non-functional requirements

Requirement

Target

Scheduling latency

p50 < 100ms, p99 < 5s for a single task

Cluster size

100,000+ machines per cluster

Tasks managed

10M+ running tasks

Availability

99.99% for scheduler control plane

Machine utilization

> 80% (bin-packing efficiency)

Back-of-envelope estimation

Capacity estimates

Metric

Value

Machines per cluster

100,000

Tasks per machine

~100 average (mix of sizes)

Total running tasks

10M

Task scheduling rate

~10K tasks/sec (starts + reschedules)

Machine state updates

100K machines × 1 heartbeat/10s = 10K/sec

Resource dimensions

CPU (millicores), memory (MB), GPU, disk, network

API design

Service definition (gRPC)

scheduler.proto

// Task submission

rpc SubmitTask(TaskSpec) returns (TaskStatus);

rpc SubmitTaskGroup(TaskGroupSpec) returns (TaskGroupStatus); // batch/gang

message TaskSpec {

string name = 1;

ResourceRequirements resources = 2; // cpu: 500m, memory: 1Gi, gpu: 1

ContainerSpec container = 3; // image, command, env

Priority priority = 4; // CRITICAL, HIGH, NORMAL, LOW, PREEMPTIBLE

PlacementConstraints constraints = 5; // zone, node_labels, anti-affinity

string namespace = 6; // team/tenant

AutoscalePolicy autoscale = 7; // min/max replicas, metric target

}

// Machine registration

rpc RegisterMachine(MachineSpec) returns (MachineStatus);

rpc Heartbeat(HeartbeatRequest) returns (HeartbeatResponse);

Data model

Storage choices

Data

Storage

Rationale

Task state (desired + actual)

etcd (Raft consensus)

Strongly consistent, watch-based updates

Machine state (capacity, allocated)

In-memory (scheduler) + etcd (durable)

Fast access for scheduling decisions

Task logs and metrics

Bigtable (time-series)

High volume, time-range queries

Configuration/quotas

etcd

Consistent, versioned

etcd scaling concern: etcd has a practical limit of ~100K keys for good performance. For 10M tasks, we need sharding.

Solution: Shard etcd by namespace/team. Each shard manages ~100K tasks. Scheduler maintains an in-memory aggregated view.

High-level architecture

Architecture diagram

Control plane → scheduler → node agents

[Users / CI-CD Pipelines]

[API Server] -- Control Plane Team

(validates, persists to etcd)

[Scheduler] -- Scheduling Team

(watches for unscheduled tasks, assigns to machines)

| |

[Machine DB] [Queue (priority)]

(in-memory (pending tasks

machine state) sorted by priority)

[Node Agent] -- Node Team

(runs on every machine, manages containers)

| | |

[Container] [Container] [Container]

[Monitoring / Autoscaler] -- Platform Team

Deep dives

WHERE STAFF IS WON

Scheduling algorithm

Two-phase scheduling:

Filtering → scoring

Phase 1: FILTERING (eliminate infeasible machines)

For each pending task, filter machines that:

✓ Have sufficient free resources (CPU, memory, GPU)

✓ Meet placement constraints (zone, labels, anti-affinity)

✓ Are healthy (recent heartbeat)

✓ Not cordoned/draining

Result: list of feasible machines (typically 10-50% of cluster)

Phase 2: SCORING (rank feasible machines)

Score each feasible machine on:

- Bin-packing score: prefer machines that leave the LEAST wasted resources

(e.g., if task needs 2 CPU, prefer machine with 2.5 free vs 10 free)

- Spread score: spread tasks of same service across zones/racks

- Affinity score: co-locate with dependent services

- Load score: prefer less-loaded machines (for latency-sensitive tasks)

Final score = weighted sum of all scoring functions

Select machine with highest score

Alternatives considered:

Approach

Description

Pros

Cons

Single scheduler

One process makes all decisions

Global optimal decisions

Bottleneck at scale (single-threaded)

Parallel scoring

Single scheduler, parallel scoring across machines

Better throughput

Still single decision point

Multi-level (Mesos-style)

Resource offers to frameworks, frameworks decide

Decoupled, multi-framework

Suboptimal: each framework sees partial view

Shared-state (Omega-style)

Multiple schedulers with shared state, optimistic concurrency

High throughput, no bottleneck

Conflict resolution needed

My choice — shared-state with partitioning (Omega-style):

Multiple scheduler instances, each responsible for a partition of namespaces
Shared machine state (eventually consistent, ~1s lag)
Optimistic concurrency: two schedulers may try to use the same resources → one fails and retries
At 10K tasks/sec with 10 partitions = 1K tasks/sec per scheduler (manageable)

Priority preemption

Priority levels & preemption

Priority levels:

CRITICAL (0): Infrastructure services (scheduler itself, monitoring)

HIGH (100): Production serving (search, ads)

NORMAL (200): Production batch (daily pipelines)

LOW (300): Development/testing

PREEMPTIBLE (400): Can be evicted any time (batch ML training)

Preemption algorithm:

1. High-priority task arrives, no resources available

2. Find lowest-priority tasks on feasible machines

3. Preempt enough low-priority tasks to free required resources

4. Evicted tasks: get 30-second graceful shutdown signal

5. Evicted tasks: re-queued at their priority level (may land on different machine)

Anti-starvation:

- Preemptible tasks guaranteed at least 10 minutes of run time

- Low-priority tasks get priority boost after waiting >1 hour

- Per-team preemption budget: can't preempt more than 20% of another team's tasks

Autoscaling

HPA + cluster autoscaler

Horizontal Pod Autoscaler (HPA):

1. Collect metrics per task (CPU, memory, custom metrics)

2. Compute: desired_replicas = current_replicas × (current_metric / target_metric)

3. Example: current CPU = 80%, target = 50%, current replicas = 10

→ desired = 10 × (80/50) = 16 replicas

4. Scale up: immediately schedule additional tasks

5. Scale down: wait 5 minutes (stabilization window), then remove tasks

6. Bounds: min_replicas ≤ desired ≤ max_replicas

Cluster Autoscaler:

1. Detect pending tasks that can't be scheduled (no feasible machines)

2. Determine how many new machines are needed

3. Provision new machines (cloud API or internal provisioning)

4. Wait for machines to join cluster (~2-5 min)

5. Schedule pending tasks on new machines

Scale down: detect machines with utilization < 50% for 10+ minutes

→ drain tasks to other machines → decommission machine

Multi-tenancy and resource quotas

Per-team quotas & reclamation

Per-team quotas:

Team: Search

CPU quota: 50,000 cores

Memory quota: 100TB

GPU quota: 500

Priority: can use CRITICAL and HIGH

Team: ML Research

CPU quota: 10,000 cores

GPU quota: 1,000

Priority: NORMAL and PREEMPTIBLE only

Quota enforcement:

- Hard quotas: cannot exceed (request rejected)

- Soft quotas: can exceed if cluster has spare capacity (burst)

- Guaranteed vs burstable: guaranteed resources always available, burstable = best-effort

Resource reclamation:

- If team A is under-using quota, team B can burst into unused capacity

- When team A needs resources back: preempt team B's burst usage

Multi-team rollout

1. Core scheduler (Weeks 1–8): Single-scheduler, bin-packing, basic priority.

2. Scale (Weeks 9–16): Shared-state multi-scheduler, autoscaling, quotas.

3. Production (Weeks 17–24): Migration from the existing scheduler — parallel run, compare placement decisions, measure utilization improvement.

4. Optimization (Months 7+): ML-based scheduling, gang scheduling for distributed training.

Bottlenecks & evolution

Bottleneck analysis

Bottleneck

Mitigation

Scheduling latency at 10K tasks/sec

Partitioned shared-state schedulers, parallel scoring

etcd for 10M tasks

Sharded etcd by namespace, in-memory caching

Heartbeat storm (100K machines)

Batched heartbeats, hierarchical reporting (rack → cluster)

Autoscaler oscillation

Stabilization windows, rate limiting scale events

2–3 year evolution

Year 1: Reliable scheduling for 100K machines, priority preemption, autoscaling, multi-tenancy.

Year 2: ML-based scheduling (predict resource usage, improve bin-packing by 10–15%), gang scheduling (for ML training jobs that need N GPUs simultaneously), spot/preemptible market (internal pricing for spare capacity).

Year 3: Multi-cluster federation (schedule across data centers), edge scheduling (IoT/edge devices), serverless integration (auto-scale to zero), FinOps integration (cost visibility per task/team).

★

Rubric — Senior vs Staff

Dimension

Senior signal

Staff signal

Scheduling algorithm

Bin-packing with a filtering + scoring pass; picks a reasonable heuristic.

Compares single / parallel / Mesos-offer / Omega shared-state; justifies partitioned shared-state with explicit concurrency tradeoffs.

Priority & preemption

Higher priority evicts lower; graceful shutdown signal before eviction.

Adds anti-starvation — minimum run-time guarantees, priority boost on age, per-team preemption budgets.

State & consistency

Uses etcd/Raft for task state; watch-based updates.

Identifies etcd key-count limit, shards by namespace, keeps an in-memory aggregated view for fast scheduling.

Multi-tenancy

Per-team quotas with hard limits.

Hard vs soft quotas, burst into spare capacity, reclamation via preemption when the owner needs it back.

Scale & operations

Reschedules on machine failure; heartbeat-based health.

Tames heartbeat storms (batched/hierarchical), autoscaler oscillation (stabilization windows), and plans migration off the existing scheduler.

★ MORE WALKTHROUGHS

Want more breakdowns like this?

Join free early access for upcoming RAG, LLM eval, agents, and AI infrastructure walkthroughs.

Join Free Early Access →