Scheduling & Workload Management
Which work runs now, which work waits, and who pays for the waiting?
Who this mechanism is for: a developer who writes code, runs jobs on shared machines (a batch cluster, a database, a Kubernetes cluster, a data warehouse) and has noticed that "the cluster is busy" is a different problem from "the code is slow." You do not need to know queueing theory or how cluster managers work inside. Every technical term is explained the first time it appears, and again in the glossary at the end. A few small formulas appear; each one comes with a worked example.
The story we will follow
Lena is a platform engineer at Brightlane, a logistics-analytics company. Brightlane runs one shared compute cluster of 200 machines, called Hub. Four kinds of work share it: dashboard queries that analysts run all day, nightly data pipelines, machine-learning training jobs that need many machines at once, and a few small web services. Omar leads the data-science team and is the loudest user of Hub.
Hub grows every month. During one busy quarter, Lena meets six problems, one at the start of each article below. Each problem looks like a bug in the scheduler. Each one is actually a consequence of how shared resources, waiting and missing information work. At the end of each article we go back and solve her problem with the mechanisms of that part.
This is the main idea of this whole mechanism:
A second sentence we will keep repeating:
Scheduling is the management of a rivalrous resource under unknown job durations. It conserves work and only relocates delay, so admission (deciding what to let in), not ordering, is the real control.
How this mechanism is organized
- 1
What scheduling is
What changes when many jobs compete for one resource, and why is "information" the hard part?
CaseEvery job marked high priority
- 2
Deciding when
In what order should jobs run, and what does each ordering cost? FIFO, priority, fairness, deadlines, gangs, preemption, locality, packing, DAGs, backfill.
CaseA 2-second query that waits 40 minutes
- 3
Deciding where
Which machine should a task run on, when machines differ in data, failure risk, price and shape?
CaseThree replicas on three machines, down together
- 4
Scheduler architecture
The scheduler is a shared data structure too. How do we protect it?
CaseThe scheduler at 100% CPU, the machines idle
- 5
Workload management
How do we decide what to let in? Admission, limits, isolation, lanes, killers, quotas, autoscaling, routing.
CaseMonday 09:00: reloads, abandoned queries, late machines
- 6
What scheduling forbids
What does this whole area forbid, what are the escapes, and who really pays?
CaseOne page for the CFO
After that: a summary, hands-on labs, interview questions and a glossary.
One request: do not skip the small numbers. Most ideas here are simple arithmetic on two or three numbers. The arithmetic is the content.
What do I do, and what does each option cost?
Can I see it myself?
FIFO versus SRPT, on heavy-tailed and on steady job sizes
One server at 90% load, FIFO against preemptive SRPT, with heavy-tailed and with steady job sizes: mean, p99 and the largest jobs.
SimulatePythonHead-of-line blocking: one queue versus two
Four workers, one queue: four 5-second jobs in front of 200 tiny ones, then a separate pool, then the big jobs cut into chunks.
MeasurePythonStranded resources and DRF
How many (1 CPU, 16 GB) tasks fit a (32 CPU, 256 GB) machine; then dominant resource fairness for two tenants on 9 CPU and 18 GB.
SimulatePythonThe power of two choices
100,000 tasks onto 100,000 machines: one random choice, the lesser loaded of two, and of three. The maximum load over five seeds.
SimulatePythonThroughput versus goodput past the knee
A service of 100/s receives 150/s and clients give up after 2 s: unbounded queue, bounded queue, and bounded queue with a deadline check.
SimulatePythonThe multiplexing dividend and its collapse under correlation
16 tenants with partly correlated demand: the 99th percentile of the summed demand against the sum of 99th percentiles, for ρ from 0 to 1.
SimulatePython with NumPyAn autoscaler that arrives too late
A reactive autoscaler with a 240-second delay against two 90-second bursts: unserved demand and idle capacity for 0% to 200% headroom.
SimulatePython
Can I reason about it under questioning?
Interview questions
Short questions on scheduling, such as ordering policies, fairness, gangs and deadlines, placement and locality, scheduler architectures and workload management, each with an answer you could give aloud and a link to the full explanation.
Scenarios
Longer problems on scheduling and workload management, of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.
The tensions this mechanism takes a position on. Each recurs across mechanisms.
Isolation vs. utilization
For example: multi-tenancy, resource pools, spot capacity.
Latency vs. throughput
For example: batching, group commit, micro-batch.
Coupling vs. coordination cost
For example: 2PC vs. sagas, schema contracts vs. schema-on-read.
Early binding vs. late binding
When structure is committed; determines where the failure surfaces, at write time or read time.
Generality vs. specialization
For example: general engines vs. purpose-built structures.
Show all 9 trade-offsShow fewer
Simplicity vs. adaptivity
For example: static plans vs. adaptive execution.
Ordering vs. parallelism
Global order costs serialization; parallelism costs order.
Fail-fast vs. fail-degraded
Reject or continue when something is wrong.
Cost as a substitutable resource
Money buys position on every other axis; the only axis denominated in a different unit.
Ideas this mechanism meets that keep coming back, mechanism after mechanism.
Independence is assumed
Independence is assumed everywhere and is true almost nowhere.
Costs are conserved
Costs are conserved, never removed.
Fixed cost per operation
Fixed cost per operation implies a natural batch size.
Guarantees have scope
Atomicity is bounded by the shared commit substrate.
Variance costs more than volume
Variance costs more than volume.
Show all 12 principlesShow fewer
Granularity mismatch
Granularity mismatch creates amplification.
Which way the error points
Queues explode near full load
Response time explodes as utilization nears 100%.
Designate one write
Atomicity over n items is atomicity over one designated item.
Randomization replaces coordination
Randomization can replace coordination.
Undeclared dependencies
An optimization that succeeds becomes an undeclared dependency, with leverage 1/(1 − h).
A cap replaces an estimate
Where a value cannot be predicted, systems substitute a cap.