Investigation 014 · The Scheduling Problem
The desired state is complete.
Yet nothing is running.
A workload knows what it should be — how many copies, what resources, what configuration. It does not know where. Before anything can execute, a distributed system must decide, among every capable machine, exactly one destination.
Begin the investigation ↓Prologue
Ten distribution centers, and every order needs exactly one
A growing company opens its tenth distribution center. With only one building, every order went to the same place — no discussion, no coordination. As the company expands, the decision stops being obvious: some centers are larger, some have refrigerated storage, some are already near capacity, some are closer to the customer.
Sending too many orders to one location creates delays while other facilities sit idle. Sending refrigerated goods to a warehouse without cold storage guarantees failure. Even choosing randomly produces unpredictable results — some warehouses overloaded by chance, others underutilized.
Assigning work eventually becomes an independent responsibility, separate from fulfilling the work itself. Distributed systems encounter the very same problem: long before a machine can execute a workload, someone — or something — must first decide where it should run.
First Principles
A workload without a destination is a description, not an instruction
Every execution begins with a location — a program on a processor, a query on a server, a container on a machine. A workload's desired state can describe what application should run, how many instances, its resources, its configuration. Everything except one thing: its destination. It says what should happen. It does not yet say where.
With only one machine, this is invisible — every workload goes to the only available destination, and placement and execution look like the same activity. Add a second machine, and a choice must suddenly be made. Add a third, a fourth, a thousandth, and the number of possible destinations keeps growing while the workload still needs exactly one.
This lets us separate two activities that previously looked identical: deciding where a workload belongs, and actually running it. A workload must move from “I should exist” to “I should exist here” before execution can even begin.
A workload must move from “I should exist” to “I should exist here” before execution can even begin.
Naive Architecture
Someone must decide. But who?
Without introducing any specialized component, several candidates emerge naturally. Perhaps the workload decides for itself. Perhaps every machine volunteers. Perhaps the first available machine simply accepts it. Perhaps the choice is random. Perhaps a central decision-maker assigns every workload. Each idea removes the immediate uncertainty. Each can be implemented. Architectures should never be chosen because they sound elegant — they should survive contact with reality.
Notice what still hasn’t happened: nothing is running. No process has been created, no resources consumed, no machine has begun execution. The only question on the table is where the workload should go. Placement is not execution — it is the decision that makes execution possible.
Placement is not execution — it is the decision that makes execution possible.
The Architecture That Almost Worked
First Come, First Served — beautifully simple, quietly broken
Instead of analyzing resources or comparing machines, adopt a single rule: always assign the workload to the first machine. No calculations, no coordination, no decision-making. Every new workload receives a destination immediately, and every workload is placed exactly once. For a small system, it appears to solve the problem completely.
Lab — First Come, First Served at Scale
Three machines, each comfortably able to run ten workloads. Send new workloads and watch where the rule sends them.
No workloads sent yet. Every one will go to Machine A.
This should feel familiar. Polling appeared sufficient until scale exposed its cost. Ownership appeared to define lifecycle until deletion proved otherwise. Now placement appears trivial — reduced to a single instruction. Perhaps it is also beautifully incomplete.
Perhaps it is also beautifully incomplete.
Breaking Our Design
Six realities, six missing responsibilities
Machines have different capabilities. Resources are finite. Demand changes continuously. Failures occur without warning. Clusters grow, shrink, and evolve while workloads are still arriving. Six increasingly hostile experiments attack six different assumptions.
Episode 1 — First Come, First Served
Twenty-five workloads arrive at a three-machine cluster. Every one is assigned to Machine A. It exhausts its CPU and memory while Machines B and C sit almost idle.
The architecture did exactly what was asked. The failure is in the rule: it asks “which machine comes first?” instead of “which machine has enough capacity?” Placement decisions must consider available capacity.
Episode 2 — Random Placement
Stop favoring any machine — choose one at random instead. Machine A is almost full, Machine C is idle, and random selection still gives each an equal chance of receiving the next workload.
Fair is not the same as correct. Removing bias is not enough — placement decisions must be informed by the current condition of the available machines.
Episode 3 — The Resource Problem
A workload requiring a GPU is assigned to a machine with no GPU. Execution fails immediately — not because anything was broken, but because the placement was never possible in the first place.
Execution cannot invent missing resources. A scheduler must match workload requirements with machine capabilities before making a placement decision.
Episode 4 — The Global Knowledge Problem
Each machine examines only itself and honestly concludes “I can run this workload.” Three machines reach the same reasonable local conclusion — but the workload can only be placed once.
Correct local observations do not produce a correct global decision. A scheduler requires global knowledge to make local placement decisions.
Episode 5 — The Changing Cluster Problem
Waiting for a perfectly stable cluster view before deciding sounds safe — except the cluster is never still. Every time the view nears stability, something else moves, and an unscheduled workload waits forever.
Perfection is not achievable. A scheduler must decide in a continuously changing environment, accepting occasional misplacement in exchange for progress.
Episode 6 — The Concurrent Placement Problem
Two scheduler replicas, added for availability, both observe the same unscheduled workload, both evaluate Machine B as suitable, and both record a placement. The workload is assigned twice.
This is the lost update problem from INV·009, arriving from a new direction. Placement decisions must be persisted as conditional writes, protected by the same versioned-truth guarantee as any other write to shared state.
Placement decisions must be persisted as conditional writes, protected by the same versioned-truth guarantee as any other write to shared state.
Lab — Test Every Placement Strategy
Try each universal placement strategy against a realistic scenario. Watch each one collapse.
Click a strategy to test it against reality.
Turning Point
We now have enough evidence
Always choosing the first machine ignored capacity. Choosing randomly ignored information. Matching resources required understanding both workloads and machines. Good decisions required visibility across the cluster. Even complete knowledge became outdated as the cluster kept changing. Running more than one scheduler exposed the same shared-write race every other controller has to guard against.
Placement was never about choosing a machine. It has always been about which responsibilities a distributed system cannot skip.
Placement was never about choosing a machine. It has always been about which responsibilities a distributed system cannot skip.
The Scheduling Contract
Seven responsibilities every scheduler must satisfy
Identify workloads with a complete desired state that are missing exactly one thing: a destination.
Know each machine's resources, capabilities, health, and constraints — without this, placement is guesswork.
A correctness constraint. Machines that cannot satisfy a workload's requirements must be removed before any selection is made.
A policy constraint. Among capable machines, choose the best under current conditions — tunable without affecting correctness.
Not zero, not many — exactly one. This is the moment unplaced desired state becomes placed desired state.
Record the destination as part of desired state so every other component can independently observe the same truth.
Creating the execution environment, starting the process, and monitoring health belong to a separate contract entirely.
Desired State
Decision
Desired State
Lab — Filter First, Then Rank
A workload needs 8 CPU, 16 GB memory, and a GPU. Filter out infeasible machines — a correctness step — then rank the survivors — a policy step.
Four candidate machines, unfiltered. Requirement: 8 CPU, 16 GB memory, GPU.
Engineering Reflection
Placement is the boundary between intent and location
The scheduler never possesses perfect information. While it evaluates one workload, new workloads arrive, existing ones finish, machines fail and recover, resources are consumed and released. This is not a flaw — it is a fundamental property of distributed systems. A scheduler also cannot guarantee that a workload will execute successfully; it can only choose a destination that appears suitable at decision time. Execution may still fail because the world changed afterward.
Filtering can never be skipped. Ranking can be simplified or replaced. Confusing correctness with policy is one of the most common architectural mistakes in placement systems — and one of the most consequential.
Costs Accepted
Imperfect information. The scheduler cannot pause the cluster while it thinks — perfect placement is impossible, timely placement is achievable.
Not guaranteed optimal. Searching for the mathematically best destination doesn't scale — schedulers aim for sufficiently good, predictable, scalable decisions.
Centralized responsibility. One decision-maker simplifies placement but becomes a critical component whose availability and correctness matter to the whole system.
No guarantee of execution. The scheduler's work ends at the placement record — whether the workload actually starts belongs to an entirely different layer.
Investigation Exercise
Exercise 1 — No central scheduler. Four machines with different resources, three workloads with different requirements. Ask each machine to independently decide whether it should run a workload. Record every decision.
Exercise 2 — Beyond local knowledge. Which decisions required knowledge beyond a single machine's own perspective? What information was each machine missing?
Exercise 3 — Could execution fix it? Could the execution layer have corrected a poor placement decision after the fact, or was the mistake already unrecoverable?
Exercise 4 — Whose responsibility? Which responsibilities clearly belonged to placement rather than execution — and which were you tempted to blur together?
Bridge to INV·015
The workload has a destination. Nothing is running yet.
Good placement required understanding workload requirements, machine capabilities, cluster-wide state, a system that never stops changing, and protection against concurrent writers. From these failures we derived the Scheduling Contract: a scheduler exists to make exactly one informed placement decision, and its responsibility ends the moment that decision is recorded.
Imagine you are Machine B, and the scheduler has just assigned a workload to you. How do you discover that assignment? Who creates the execution environment? Who starts the application? Who observes whether it succeeds or fails, and reports the result back?
The next investigation begins exactly where this one ends — the destination has been chosen, and the workload has not yet started.
Deliberate Simplifications Ledger
| We deliberately postponed | Owned by |
|---|---|
| How two scheduler instances avoid placing the same unscheduled workload on different machines simultaneously — the binding step's relationship to optimistic concurrency | INV·015 — The Execution Problem |
| Scoring strategies, bin-packing heuristics, affinity rules, taints, preemption, and topology-aware placement — all placement policy, not architectural contract | Implementation detail — deferred as a group |
| How a scheduler keeps its view of node resources current as the cluster changes — its relationship to the Informer and the cost of stale cluster pictures | INV·015 — The Execution Problem |
| Multiple independent schedulers sharing one cluster without conflicting placements | Deferred to a later investigation — extensibility section |
Sources
Official Documentation: Kubernetes Documentation — Scheduling, Preemption and Eviction.
Source Code: k8s.io/kubernetes/pkg/scheduler — the scheduler framework, the two-phase filter/score pipeline, and the binding step.
Design Proposal: KEP-624 — Scheduling Framework, the design that formalized the filter and score phases as a plugin-based architecture with explicit extension points.
Papers: Schwarzkopf et al., Omega: flexible, scalable schedulers for large compute clusters (EuroSys 2013) — optimistic concurrency for scheduler binding and decentralized multi-scheduler architectures. Verma et al., Large-scale cluster management at Google with Borg (EuroSys 2015) — the two-level feasibility-then-scoring architecture that directly informed kube-scheduler's design.
Books: The Datacenter as a Computer, Barroso, Clidaras & Hölzle — cluster-level resource management and the economics of placement at scale. Kubernetes: Up and Running, Burns, Beda & Hightower — practical scheduler behavior in production clusters.
Next: INV·015 — The Execution Problem