Design Walkthrough 01 — A Multi-Tenant Cluster Scheduler (YARN-Style)

Problem statement: Design the scheduler for a 5,000-node cluster shared by ~40 teams running a mix of batch ETL (hours), interactive SQL (seconds–minutes), and long-running services. Teams have budget-derived entitlements. The cluster must run hot (>80% utilization) without letting any team starve.

Table of Contents

Step 1: Characterize the workload

Before any boxes: the three workload classes have conflicting scheduling needs.

ClassContainer lifetimeLatency sensitivityFailure cost
Batch ETLminutes–hoursnone (throughput)re-run a task
Interactive SQLsecondshigh (human waiting)query retry, user anger
Servicesdays–monthsSLO-boundoutage

A single queue with one policy cannot serve all three — this observation drives the whole design and is the first thing to say out loud in an interview.

Step 2: Constraints and non-goals

  • Scale: 5,000 nodes × ~50 containers ⇒ ~250K concurrent containers; scheduling decisions must be O(ms) — the scheduler is a single logical chokepoint.
  • Multi-tenancy: entitlements are organizational facts (budgets), so the queue structure should be hierarchical, mirroring the org.
  • Run hot: guaranteed capacity must be borrowable when idle, which forces preemption into the design (you cannot have all three of: guarantees, borrowing, no preemption).
  • Non-goals: gang scheduling and global optimality. State them — choosing heuristic per-heartbeat scheduling over an optimal solver is a decision.

Step 3: Architecture

YARN's split is the reference answer and worth defending from first principles:

  • ResourceManager (RM): the arbiter. Holds queue state and node state; makes allocation decisions. Keep it application-logic-free so its failure domain is small.
  • NodeManager (NM) per node: enforcement (cgroups), health, container lifecycle. Heartbeats carry node status in and allocation decisions out — the heartbeat is the scheduling clock, which bounds decision latency and gives natural batching.
  • ApplicationMaster (AM) per application: all app-specific logic (task graphs, retries, speculation) is pushed out of the RM. This is the architecturally load-bearing decision: it caps RM complexity and lets frameworks (Spark, Tez, services) innovate independently.

State & HA: RM state (app registry, delegation tokens) to a replicated store; leader election for active/standby; NMs and AMs re-register on failover (work-preserving restart — running containers keep running, the new RM rebuilds the picture from re-registration).

Step 4: The scheduling policy

Hierarchical queues with capacity + elasticity:

  • Each queue has guaranteed (sums to 100% per level) and max (elastic ceiling).
  • Idle capacity is borrowable; accounting tracks each queue's steady-state fair share vs current usage — the delta drives both allocation priority and preemption targeting.
  • Within a queue: FIFO with size-based weighting for batch; fair-share for interactive (or a dedicated low-latency queue with small max container size and strict limits); services get a queue with no preemption-out and placement constraints.
  • Locality via delay scheduling: skip up to N heartbeats waiting for a node-local slot before relaxing node → rack → any. Cheap and effective for HDFS-resident inputs.
  • Dominant Resource Fairness for multi-resource (CPU/mem/GPU) fairness — per-resource fairness is gameable; DRF compares each tenant's dominant share.

Step 5: Preemption

The part most candidates hand-wave; be concrete:

  1. Compute over-capacity queues vs starved queues from guaranteed/usage deltas.
  2. Select victims newest-first within over-capacity queues (minimize lost work), respecting per-app disruption budgets and never-preempt flags (services, AMs themselves).
  3. Warn before kill: send the AM a preemption message with a grace period (e.g. 30 s) so frameworks can checkpoint or drain; kill only on expiry.
  4. Rate-limit global preemption (e.g. ≤2% of cluster per minute) to prevent oscillation — preemption + elastic borrowing forms a feedback loop that will thrash without damping.

Step 6: Failure modes

  • RM failover: covered by work-preserving restart; the subtle bug class is double accounting during re-registration (container reported by both NM re-registration and the recovered state store) — dedupe by container id, version the epoch.
  • Heartbeat storms: 5,000 NMs × 1 s heartbeats is fine; 50K is not — move to event batching / longer intervals with async node updates.
  • Rogue AM: an AM requesting pathological container shapes (1 GB × 100K) — per-queue and per-app caps on outstanding requests; admission control at submission.
  • Skewed node attrition: rack failure shifts load; scheduler must re-spread without violating constraints — this is where placement constraints earn their complexity.

Step 7: Evolution pressures

What changed in the real world since YARN's design, and how the design absorbs it:

  • GPUs: indivisible, topology-sensitive resources break "resources are fungible scalars" — resource types + placement constraints, and bin-packing rather than spreading.
  • Long-running services: pushed YARN toward container reuse, rolling restart of NMs, and eventually lost ground to Kubernetes — be ready to compare (K8s: declarative reconciliation, richer pod model; YARN: locality-aware throughput scheduling at lower per-decision cost).
  • Federation: past ~10K nodes, shard the RM (sub-clusters + router) rather than scaling one scheduler loop.

Interviewer follow-ups

  1. Why per-application masters instead of a smarter central scheduler? — failure isolation, framework extensibility, RM simplicity; cost: per-app overhead, AM scheduling becomes two-level (and two-level schedulers suffer information hiding — concede it).
  2. How would you add SLA-based scheduling? — admission control with deadline feasibility check, reserved capacity windows (resource reservations), backfill around reservations.
  3. Capacity vs fair scheduler — when is each wrong? — capacity wrong for ad-hoc shared research clusters (idle guarantees waste); fair wrong when org-level isolation is a contractual requirement.
  4. What metric tells you the scheduler itself is the bottleneck? — allocation latency percentiles vs heartbeat interval, pending-request queue age, and scheduler-loop utilization; not cluster utilization, which confounds demand.

References