A fast C++20 simulator for evaluating scoring functions for cluster job scheduling — the multi-dimensional bin-packing problem at the heart of warehouse-scale schedulers like Google Borg. It replays the public Google 2011 cluster trace (12,583 machines, ~24.4M tasks over 29 days) through 21 placement policies and measures packing quality, queueing behavior, and preemption cost.
📊 Interactive report (all policies, mathematical definitions, four experimental regimes, insights): https://claude.ai/code/artifact/f510ba98-a4eb-43dc-96f1-b18503de9182
Built on the methodology of:
- A. Verma, L. Pedrosa, M. Korupolu, D. Oppenheimer, E. Tune, J. Wilkes. Large-scale cluster management at Google with Borg. EuroSys 2015.
- A. Verma, M. Korupolu, J. Wilkes. Evaluating job packing in warehouse-scale computing. IEEE Cluster 2014.
- Novikov et al. AlphaEvolve: a coding agent for scientific and algorithmic
discovery. 2025 (§3.3.1 and Fig. 6 — the deployed Borg scheduling
heuristic, implemented here as
alpha_evolve).
make # builds bin/cluster-sim, bin/evolve, bin/test_basic (clang++/g++, zlib)
make test
A CMakeLists.txt is provided as an alternative to the Makefile.
# Synthetic workload, full snapshot metric suite, all policies
./bin/cluster-sim --mode snapshot --machines 2000 --rho 0.75 --trials 5
# Fetch a slice of the Google 2011 trace (N of 500 task_events parts);
# the full table is ~1.5 GB compressed
./scripts/download_trace.sh data 10
# Replay day 1 through selected policies (64-machine sampling, Borg-style)
./bin/cluster-sim --mode event --trace-dir data --days 1 \
--policy best_fit,alpha_evolve,evo_search --sample-k 64
# Borg-style priority scheduling: production (priority >= 9) evicts batch
./bin/cluster-sim --mode event --trace-dir data --days 1 --preempt --sample-k 64
# Production band only, whale outliers removed, horizontal inflation
./bin/cluster-sim --mode snapshot --trace-dir data --min-priority 9 \
--max-task-dim 0.9 --inflate-mode clone --sample-k 64
./bin/cluster-sim --help lists every flag. --json out.json writes
machine-readable results; --util-csv prefix (event mode) writes a
utilization time series per policy.
Each policy scores every feasible machine for the task being placed and picks
the argmax (ties to the lowest index). Notation: d = task demand,
f = machine free, c = capacity; a = d_cpu/f_cpu, b = d_mem/f_mem;
r = f − d the post-placement residual with normalized components
ρ_x = r_x/c_x; u_x = 1 − ρ_x the post-placement utilization
(u⁰ pre-placement); s the standard slot (default 0.05/0.05).
| family | policy | score (maximized) | intuition |
|---|---|---|---|
| baseline | first_fit |
first feasible by index | the classic 1-D baseline |
random |
uniform over feasible | control: what does scoring buy at all? | |
| tight pack | best_fit |
u_c + u_m | pack tightest; shape-blind in 2-D |
norm2 |
−(ρ_c² + ρ_m²) | L² best fit | |
cheby |
−max(ρ_c, ρ_m) | L∞ (worst-dimension) best fit | |
| alignment | dot |
(d_c f_c)/c_c² + (d_m f_m)/c_m² | demand where free points the same way |
cosine |
cos(d/c, f/c) | scale-free shape match | |
tetris |
d_c f_c + d_m f_m | unnormalized; favors big machines | |
align_fill |
cos(d/c, f/c) + ½(u_c + u_m) | shape match, consolidation tiebreak | |
| spread | worst_fit |
−(u_c + u_m) | maximum headroom everywhere |
epvm |
−Σ_x (10^{u_x} − 10^{u⁰_x}) | E-PVM marginal cost (Borg's hybrid family) | |
convex_spread |
−Σ_x 1/(1.05 − u_x) | harmonic headroom | |
| dim-aware | balance |
−|ρ_c − ρ_m| | keep the leftover square |
min_strand |
−(ρ_c·[r_m<s_m] + ρ_m·[r_c<s_c]) + ε·fit | don't create stranded leftovers | |
imbalance_wt |
−|ρ_c − ρ_m|(ρ_c + ρ_m) | imbalance weighted by residual size | |
slot_loss |
−(⌊slots(f)⌋ − ⌊slots(r)⌋) + ε·fit | minimize schedulable slots destroyed | |
| evolved | alpha_evolve |
−(a + b + b/a + a/b) | AlphaEvolve Fig. 6, deployed on Borg |
ae_tight |
(a + b) − (b/a + a/b) | roominess inverted | |
ae_shape |
−(b/a + a/b) | shape term alone | |
ae_pow |
−(a + b + (b/a)² + (a/b)²) | quadratic shape penalty | |
| searched | evo_search |
see src/policy.cc |
champion of bin/evolve (below) |
--sample-k K scores only K randomly sampled machines per placement
(power-of-k-choices, §3.4 of the Borg paper), with a full-scan fallback in
feasibility experiments.
Snapshot mode packs the tasks alive at the workload's busiest instant
(or --at T) onto an empty cluster and reports, per policy over --trials
shuffled orders:
- placed% — fraction of snapshot tasks placed.
- utilization — allocated / capacity per dimension.
- holes% — leftover free space still usable, in standard slots.
- stranding — fraction of free CPU (mem) on machines that fit no slot: capacity wasted because the other dimension ran out.
- compaction — smallest fraction of machines (random subsets, binary search, median) onto which the whole workload still packs. Lower = better; requires 100% placement, so 1.000 also flags policies that can't fully place the base workload.
- inflation — largest multiplier λ that still fully packs.
--inflate-mode scalegrows every task's demand by λ (capped by the largest task vs the largest machine — see the whale caveat below);--inflate-mode clonepacks ⌊λN⌋ tasks instead, leaving shapes intact.
Event mode replays the arrival stream through a discrete-event scheduler
with a pending queue, reporting time-weighted utilization over a steady-state
window, first-placement latency percentiles, and queue statistics. With
--preempt, pending tasks drain highest-priority-band first and a
production/monitoring task (trace priority ≥ 9) that fits nowhere may evict
batch tasks (lowest-priority, largest-first, on the machine needing the least
eviction); victims re-queue and resume their remaining duration; production
is never evicted. The report then splits latency by band and counts
evictions.
Workload filters compose: --days N (arrivals in the first N days, true
durations kept), --min-priority N (e.g. 9 = production + monitoring),
--max-task-dim X (drop whale tasks with any request > X).
bin/evolve runs a (μ+λ) evolutionary search over a parameterized scoring
family that contains alpha_evolve as one point:
score = −(w₀·a^p1 + w₁·b^p1 + w₂·(b/a)^p2 + w₃·(a/b)^p2
+ w₄·(u_c+u_m) + w₅·|ρ_c−ρ_m|)
Fitness is the demand-weighted placed fraction on the workload's peak
snapshot (common random numbers across genomes); a held-out snapshot from the
second half of the window is reported but never selected on. The shipped
evo_search policy is the generation-20 champion of
./bin/evolve --trace-dir data --days 1 --seed 1; it beat alpha_evolve by
+1.6pp on its training objective and +1.9pp on the held-out snapshot (but not
on FIFO tail latency — fitness choice matters; see the report).
With the full trace in data/ (./scripts/download_trace.sh data 500):
./bin/cluster-sim --mode snapshot --trace-dir data --max-tasks 40000000 --days 1 \
--sample-k 64 --trials 5 --seed 1 --json results/snapshot.json
./bin/cluster-sim --mode event --trace-dir data --max-tasks 40000000 --days 1 \
--sample-k 64 --seed 1 --json results/event.json --util-csv results/util --util-dt 300
./bin/cluster-sim --mode event --trace-dir data --max-tasks 40000000 --days 1 \
--preempt --sample-k 64 --seed 1 --json results/event_preempt.json
./bin/cluster-sim --mode snapshot --trace-dir data --max-tasks 40000000 --min-priority 9 \
--max-task-dim 0.9 --inflate-mode clone --sample-k 64 --trials 5 --seed 1 \
--json results/snapshot_prod_clone.json
./bin/cluster-sim --mode snapshot --trace-dir data --max-tasks 40000000 --min-priority 9 \
--max-task-dim 0.9 --sample-k 64 --trials 5 --seed 1 --no-compaction \
--json results/snapshot_prod_scale_nowhale.json
python3 site/build_page.py # -> site/compare.html
The committed results/*.json are the exact outputs behind the published
report. Everything is deterministic in --seed regardless of thread count.
- Machines are struct-of-arrays; each policy's scan is a templated tight loop
(no virtual dispatch). ~1–2M placements/s with
--sample-k 64. - Everything parallelizes across policies: event mode runs one policy per
worker; snapshot mode fans every (policy × trial × experiment) job onto a
shared pool (
--threads, default = cores). Results don't depend on thread count. - The event engine keeps overload from going quadratic: pending-queue retries skip the full-scan fallback under sampling, and the drain prefilter uses an incrementally maintained max-free upper bound (O(1) per finish) instead of rescanning all machines.
- Trace loader gotchas handled: events beyond the observation window carry a 2⁶³−1 sentinel timestamp (ignored — otherwise unfinished tasks get ~292,000-year durations); tasks without an observed end run to trace end; utilization CSV output is hard-capped as a disk-filler backstop.
- Known metric ceilings: overloaded snapshots pin compaction/stranding for
every policy, and two mem-0.955 whale tasks cap scale-mode inflation at
1.047× unless
--max-task-dimexcludes them. The report's "metrics fail silently at their ceilings" insight came from exactly these.
src/core.h Res / Task / Cluster (SoA) primitives
src/policy.* the 21 scoring functions + machine picker (sampling, ties)
src/metrics.* utilization / hole-filling / stranding on a cluster state
src/workload.* synthetic generator + Google 2011 v2 trace loader (gz CSV)
src/sim.* FIFO + preemptive event engines; pack / compaction / inflation
src/evolve.cc (mu+lambda) evolutionary search over scoring functions
src/pool.h minimal parallel-for used by all experiment fan-out
src/main.cc CLI, tables, JSON output
tests/ deterministic sanity tests (make test)
scripts/ trace download helper
site/ interactive report generator (template + build_page.py)
results/ committed experiment outputs behind the published report