The four architectures

How does each scheduler architecture protect cluster state, and why do two random probes go so far?

Architecture	Concurrency-control analogue	What it gives up
Monolithic (one scheduler, global view)	single lock	scheduler throughput; extensibility
Two-level offers (a resource manager offers resources to per-framework schedulers)	pessimistic locking	a global view: frameworks see only a subset, so cross-framework preemption and packing are impossible, and gangs must hoard offers
Shared-state optimistic (many schedulers work on a copy of the cluster state, commit with CAS)	MVCC + CAS retry	wasted work under conflict. The conflict rate rises with gang size and with resource scarcity
Distributed sampling (each scheduler probes a few random machines)	no coordination	global constraints, fairness and gangs. It buys near-optimal placement from the power of two choices

The surprise: sampling needs only two probes

Sampling works for a counterintuitive reason: probing two random nodes and taking the one with the shorter queue gives an exponentially better tail than probing one, and probing all of them barely improves on two (the power of two choices). So most of the value of a global view can be obtained from a sample of size 2. That is why a scheduler can skip coordination entirely and still place well: it gives up only what needs the global view (constraints, fairness, gangs).

Contested, honestly: does the monolithic scheduler really not scale?

The "monolithic schedulers do not scale" claim is more cited than demonstrated. Google's monolithic Borg scheduler ran production clusters at scale for years. The shared-state work was motivated as much by extensibility (letting different teams add scheduling policies without editing one codebase) as by throughput.

Treat "centralized schedulers do not scale" as organizational reality more than physical law. Lena should measure her own decisions-per-second need before she redesigns anything.

The cluster state is a shared object. Pick pessimistic, optimistic or sampled, and pay the same prices you would pay in a database.

Case, resolvedConstructed case · Lena at Brightlane

The scheduler at 100% CPU, the machines idle

Interactive analytics split each query into thousands of 100 ms tasks, and the central scheduler could not place them fast enough. Where it started: Scheduler architecture →

Lena measures: her scheduler can do about 5,000 placements per second, and the new 100 ms tasks need far more. She has three options. (1) Make tasks bigger by batching many 100 ms tasks into one scheduled unit of about 5 seconds (the fixed cost of a scheduling decision is spread over more work). (2) Add a sampling-based fast path for tiny tasks (probe 2 machines, take the less busy one) and keep the careful scheduler for gangs and quota. (3) Move to optimistic shared-state schedulers, accepting retries. She picks (1) and (2): batching cuts demand 50×, and the sampling path handles the rest. The careful scheduler still owns fairness, gangs and quotas. She notes that (3) would add a conflict rate that rises as the cluster fills up.