Efficient Microsecond-scale Blind Scheduling with Tiny Quanta

Zhihong Luo, Sam Son, Dev Bali, Emmanuel Amaro, Amy Ousterhout, Sylvia Ratnasamy and 1 other

Datacenter requests fan out into thousands of tiny jobs, some lasting under a microsecond and some hundreds, and to keep the short ones from stalling behind the long ones a scheduler must interrupt and reshuffle jobs constantly — but doing that every microsecond costs more than it saves; this work from UC Berkeley builds Tiny Quanta, which makes each switch almost free by yielding through lightweight coroutines that a compiler sprinkles with cheap physical-clock checkpoints, and splits the scheduler into a thin global load-balancer plus fast per-core schedulers, letting it slice time into one-microsecond pieces and sustain 1.2 to 6.8 times the throughput of prior systems at low tail latency.

The argument in one glance

Problem

Tiny jobs of wildly different lengths stall behind each other

A single client request to a datacenter often fans out into thousands of internal jobs, many lasting only a few microseconds. But the mix is broad: alongside the half-microsecond jobs are occasional ones that run for hundreds of microseconds. When a short job arrives and the cores are busy with a long one, it waits — head-of-line blocking — and a job that needed half a microsecond suffers a delay hundreds of times its own length, wrecking tail latency.
What people did

Preempt running jobs in small time slices, blindly

The cure is to preempt: give each job a small quantum of service, then switch to the next so short jobs are not trapped behind long ones. Done blindly — without assuming anything about how long any job will run, which keeps the system general across workloads — this means time-sharing every job in fixed quanta. The smaller the quantum, the sooner a short job gets its turn, and the less blocking.
Why it fell short

At microsecond quanta, the switching overhead eats the benefit

Every switch costs something, and the standard preemption mechanism — hardware interrupts driven by a central scheduler — costs about a microsecond each. At quanta of a microsecond or two, that overhead rivals the work itself, so throughput collapses and the central scheduler, triggering an interrupt for every quantum on every core, becomes the bottleneck. Finer interleaving also threatens to thrash the CPU caches. So the very small quanta that would cut tail latency are not affordable.
This paper's idea

Make each switch nearly free, and spread the scheduling across cores

Tiny Quanta makes preemption cheap enough to do every microsecond. Instead of interrupts, jobs run as lightweight coroutines and yield voluntarily at checkpoints a compiler inserts automatically — checkpoints that read the hardware clock, so they can be placed sparsely yet fire on time. And instead of one central scheduler, a thin global dispatcher merely load-balances jobs onto cores while each core schedules its own quanta. Together these let it slice time into one-microsecond pieces and sustain 1.2 to 6.8 times the throughput of prior systems.

Why this problem is worth solving

The core difficulty is a tension between two things that both scale with how finely you slice time, so it is worth being precise about it.

When jobs of very different lengths share a set of cores, a short job that arrives while a long job is running will, under run-to-completion scheduling, have to wait for the long job to finish — head-of-line blocking. The remedy is preemptive processor sharing: give each job a small slice of time, a quantum, then pause it and let another job run, cycling through so no job monopolizes a core. The size of the quantum sets a tradeoff. A small quantum means a newly-arrived short job waits at most one quantum before running, so tail latency stays low; but every preemption costs overhead — saving one job’s state, loading another’s — and the smaller the quantum, the more often you pay it, dragging down throughput. There is thus a sweet spot, and it moves: the cheaper each switch is, the smaller a quantum you can afford, and the lower you can push tail latency without losing throughput. The whole game is to make the switch cheap enough that microsecond-scale quanta become practical.

The choice to schedule without any knowledge of job durations is deliberate, and it shapes everything.

Some schedulers peek at each request to estimate its service time, or assume the overall distribution of durations is known, and use that to prioritize — running the likely-short jobs first. This can work beautifully, but it ties the system to a particular workload: a new request type or a shifting distribution breaks the assumptions and forces a redesign. Blind scheduling refuses this knowledge. It assumes nothing about how long any individual job will take, or even about the shape of the distribution, and so stays general across arbitrary and evolving workloads. The price is that a blind scheduler cannot simply run the short jobs first, because it does not know which they are; it must instead preempt everything in small quanta and let processor sharing sort it out. That is provably the right policy for broad, heavy-tailed distributions — but it only pays off if preemption is cheap, which is exactly what makes microsecond-scale blind scheduling hard, and worth solving, since it delivers low tail latency without brittle assumptions.

What people did before, and where it broke

Run jobs to completion, first come first served (Caladan-style). Steer each request to a core and let it finish, work-stealing to balance load. Where it broke. With no preemption, a short job stuck behind a long one suffers severe head-of-line blocking — good throughput for long jobs, terrible tail latency for short ones.
Preempt with hardware interrupts (Shinjuku-style). Use special virtualization features to interrupt cores and time-share jobs. Where it broke. Even optimized, an interrupt costs about a microsecond, so at quanta below five microseconds the overhead crushes throughput; the system becomes unstable when forced to preempt very often.
Assume knowledge of service times or their distribution. Peek at request types or model the distribution to prioritize short jobs. Where it broke. It sacrifices generality — a new workload or a shifting distribution breaks the assumptions and forces the system to be re-tuned or redesigned.
Insert yield points by hand. Have developers manually place cooperative yields in their code so jobs relinquish the core. Where it broke. Microsecond jobs have few natural yield points, and placing them by hand to hit an accurate interval is cumbersome and error-prone.
Instrument yields by counting instructions. Have a compiler add a probe to each basic block that increments an instruction counter, and yield when it crosses a threshold. Where it broke. The count-to-time translation is inaccurate because instructions vary in duration, and keeping the counter correct needs a probe in nearly every block — over a thousand for one small job, adding 60 percent overhead.
The gap. Every path either did not preempt (blocking short jobs), preempted too expensively (interrupts), gave up generality (assuming job knowledge), or instrumented too heavily (instruction counting). What was missing was a way to preempt blindly, at microsecond quanta, cheaply enough that the overhead does not swamp the work — which is exactly what fine-grained datacenter scheduling needs.

How Tiny Quanta works

Cheap preemption plus two-level scheduling for microsecond quanta

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Yield on the real clock, checked sparsely, instead of counting instructions everywhere. The heart of cheap preemption is a compiler that inserts checkpoints where a job can yield, but the prior way — counting instructions, with a probe in nearly every block and a shaky translation from counts to time — was both inaccurate and heavy, adding a thousand probes and sixty percent overhead to a single small job. Tiny Quanta instead has each probe read the hardware cycle counter directly and yield only if enough real time has passed. A clock reading costs more per probe than an increment, but because it is correct wherever it sits, probes can be spread far apart — thirty times fewer — and their timing is exact rather than estimated. Reading an accurate physical signal at a few carefully-placed points, rather than maintaining an inaccurate proxy densely throughout, is the same discipline the binary-disassembly work covered elsewhere on this site follows, grounding its decisions in real measured statistics placed where they count instead of a convenient but wrong assumption applied everywhere.

Split the scheduler into a cheap global level and fast local ones. A single central scheduler that preempts and steers every quantum across all the cores does more and more work as quanta shrink, until it saturates and becomes the bottleneck — the reason prior systems could not go below a few microseconds. Tiny Quanta breaks the scheduler in two: a thin global dispatcher that only balances whole jobs across cores as they arrive, and a per-core scheduler that handles the fine-grained quantum switching locally. Because the dispatcher’s work is per-job, not per-quantum, its load stays flat as the quanta get tinier, so it never chokes. Relieving a central coordinator by pushing the frequent, fine-grained decisions down to independent per-unit schedulers, while it keeps only the coarse global choices, is the same two-level structure the serverless GPU-scaling work covered elsewhere on this site adopts, pairing one global scaler with fast local schedulers on each node so the center never becomes the limit.

Stay blind, and let processor sharing sort the jobs out. The tempting shortcut is to peek at each job, guess its length, and run the short ones first — but that binds the system to a workload and shatters when the workload shifts. Tiny Quanta refuses to guess: it assumes nothing about durations and simply time-shares every job in tiny quanta, which lets a short job preempt a long one within a quantum without anyone ever knowing which was which, a policy provably right for broad, unpredictable distributions. Declining to predict a quantity it cannot reliably know, and instead reacting to what jobs actually do, is the same instinct the serverless orchestration work covered elsewhere on this site acts on, refusing to forecast a duration that varies too much and letting the system respond to real behavior rather than a fragile estimate.

Following a short job through Tiny Quanta

A half-microsecond job arriving behind a long one

Tracing one short job shows the mechanisms cooperating.

Step 1 of 5

A short job arrives into a busy system

A 500-microsecond job is already running on the cores when a 0.5-microsecond job arrives. Under run-to-completion, the short job could wait hundreds of microseconds — a delay a thousand times its own length, the head-of-line blocking that ruins tail latency.

The mix of a thousand-to-one duration ratio is exactly the "extreme bimodal" workload the paper stresses.

Why it works

Cheap coroutine yields replace expensive interrupts. Preempting with a hardware interrupt through a central scheduler costs about a microsecond, unaffordable at microsecond quanta → but yielding through a user-space coroutine takes only tens of nanoseconds, needing no system call or page-table change → so a job can be switched constantly without the overhead swamping the work.
Physical-clock checkpoints placed sparsely are cheap and accurate. Prior compilers counted instructions, needing a probe in nearly every block and translating counts to time inaccurately → but a probe that reads the hardware cycle counter works correctly anywhere, so it can be placed thirty times more sparsely with exact timing → so the instrumentation adds little overhead while still yielding on schedule.
Splitting the scheduler in two removes the central bottleneck. A single scheduler that preempts and steers every quantum across all cores saturates as quanta shrink → but a thin global dispatcher that only load-balances per job, with each core scheduling its own quanta, keeps the dispatcher’s work constant → so the scheduler scales down to sub-microsecond quanta without becoming the limit.
Keeping each job on one core preserves cache locality. Steering a job’s quanta to whichever core is free scatters its data and forces cache misses on resume → but with per-core scheduling a job lives on one core throughout, so its lines stay in that core’s private caches → so fine-grained interleaving does not pay the cache-pollution tax it otherwise would.
Processor sharing keeps short jobs from waiting on long ones, blindly. Running jobs to completion makes a half-microsecond job wait behind a five-hundred-microsecond one → but time-sharing every job in tiny quanta lets the short one preempt within a quantum, needing no service-time estimate → so tail latency stays low across broad, unpredictable distributions.

What it costs (trade-offs and scope)

It needs the application’s source code and a recompile. The compiler pass instruments the app to insert probes, so unmodifiable binaries and closed external libraries get only a fixed-cost approximation and cannot be preempted inside.
Preemption is cooperative, not guaranteed. A job yields only when it reaches a probe, so a long uninstrumented region — a system call, an external library call, or an explicit critical section — can overrun its quantum; unlike a hardware interrupt, there is no hard cutoff.
Being blind gives up the gains of knowing job sizes. Tiny Quanta deliberately assumes nothing about durations, so systems that do know job types can sometimes beat it — a run-to-completion policy, for instance, gives long jobs lower latency at medium load.
The tail-latency guarantee is empirical. The load-balancing-plus-sharing combination is proven near-optimal only for the mean sojourn time; its tail behavior, the real target, is established by simulation and experiment, and the tie-break rule is a heuristic.
The clock-reading probes still cost cycles. Each probe reads the cycle counter, which takes tens of cycles; the win depends on the compiler bounding path lengths to keep probes rare, which is harder for very complex control flow.
It depends on a software-readable cycle counter and is architecture-specific. The mechanism needs a hardware timestamp instruction, available on common architectures (x86, ARM, RISC-V) but tied to each one.
The comparison and cache study have caveats. The prior systems ran on different hardware and operating systems, and the cache conclusion comes from a synthetic pointer-chasing microbenchmark measuring only within-job locality.

The evaluation

Microsecond-scale blind scheduling approaches

Property	Caladan (run to completion)	Shinjuku (interrupts)	Tiny Quanta
Preemption mechanism	None, runs to completion
Scheduler architecture	Distributed, work-stealing
Smallest practical quantum		About 5 microseconds	About 1 microsecond
Short-job head-of-line blocking		Low, but throughput capped
Relative throughput		TQ 1.2 to 6.8 times higher

Blind schedulers for microsecond-scale datacenter jobs, evaluated on a 16-worker server across bimodal, TPC-C, exponential, and RocksDB workloads against Caladan (run-to-completion) and Shinjuku (interrupt-based preemption). Tiny Quanta schedules blindly at roughly 1-microsecond quanta and sustains 1.2 to 6.8 times the throughput of prior systems at low tail latency — for example 6.85 times Shinjuku on an exponential workload and about 2 times on RocksDB GETs.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Tiny Quanta is a sharp systems result: it makes microsecond-scale blind preemption practical by attacking overhead on two fronts — replacing hardware interrupts with lightweight coroutine yields triggered at sparse, physical-clock compiler checkpoints, and splitting the central scheduler into a thin per-job dispatcher plus fast per-core schedulers that also keep jobs cache-resident — sustaining 1.2 to 6.8 times prior throughput at low tail latency down to roughly one-microsecond quanta. Read the result with its assumptions. It needs the application’s source and a recompile, and its preemption is cooperative, so a long uninstrumented region or critical section can overrun a quantum with no hard interrupt to stop it. Being deliberately blind, it forgoes gains a workload-aware scheduler could capture, and its tail-latency behavior is shown empirically rather than proven. The clock probes still cost cycles, the mechanism is tied to architectures with a readable cycle counter, and the head-to-head ran the baselines on different hardware. The durable idea is that the sweet-spot quantum is set by the cost of a switch, so if you drive that cost to almost nothing — cheap yields, sparse accurate checkpoints, a scheduler that does not bottleneck — you can slice time far finer than before and cut tail latency without paying in throughput.

Background

Why microseconds are the hard regime

It helps to see why so much recent systems work circles the microsecond. For decades, the units that mattered in computing were either nanoseconds (a cache hit, a single instruction) or milliseconds (a disk seek, a network round trip across the internet), and the software techniques for each were mature: spin for nanoseconds, context-switch and block for milliseconds. But modern datacenters created a new regime in between — internal services that answer in a few microseconds, fast enough that the old millisecond machinery (interrupts, blocking, the kernel scheduler) is far too heavy, yet slow enough that you cannot just spin and wait. This “killer microsecond” regime breaks the assumptions of both worlds, and scheduling is where it bites hardest, because an operation that costs a microsecond is negligible against a millisecond job but ruinous against a microsecond one. The key-value store concurrency work covered elsewhere on this site wrestles with the same regime from the data side, where a lock acquisition or a cache-line bounce that no one would notice in a slower system becomes the dominant cost. Tiny Quanta matters because it shows that even the expensive act of preemption can be made microsecond-cheap, extending fine-grained control into a regime that used to forbid it.

If you remember only three things

1. Datacenter requests fan out into thousands of tiny jobs whose durations vary enormously (a half-microsecond to hundreds), so short jobs suffer head-of-line blocking behind long ones unless the scheduler preempts constantly; doing this blindly — assuming nothing about job durations, which keeps the system general — requires small time quanta, but the smaller the quantum the more often you pay the switching overhead, and at microsecond quanta the standard mechanism of hardware interrupts through a central scheduler costs about a microsecond per switch, erasing the benefit and bottlenecking on the central core.
2. Tiny Quanta makes preemption microsecond-cheap with two mechanisms. Forced multitasking runs jobs as lightweight coroutines (yielding in tens of nanoseconds, no interrupt or kernel) and has an LLVM compiler pass insert checkpoints that read the hardware cycle counter — placed sparsely (thirty times fewer than the prior instruction-counting approach) because a clock reading is correct anywhere and its timing is exact, not estimated. Two-level scheduling splits the scheduler into a thin global dispatcher that only load-balances whole jobs (its work constant as quanta shrink) and per-core schedulers that time-share quanta by processor sharing, with a Join-the-Shortest-Queue policy and a Maximum-Serviced-Quanta tie-break; keeping each job on one core also preserves private-cache locality.
3. Evaluated on a 16-worker server across bimodal, TPC-C, exponential, and RocksDB workloads against Caladan (run-to-completion) and Shinjuku (interrupt preemption), Tiny Quanta schedules blindly at roughly 1-microsecond quanta and sustains 1.2 to 6.8 times prior throughput at low tail latency — but it requires the application's source and a recompile, its cooperative preemption can overrun on uninstrumented regions or critical sections, being blind it forgoes gains a workload-aware scheduler could capture, its tail-latency behavior is empirical rather than proven, and its clock probes and cycle-counter dependency carry their own costs.

Check yourself

Check your understanding

1. Why is scheduling microsecond-scale jobs with a broad range of durations so hard?
2. How does Tiny Quanta make each preemption cheap?
3. What does two-level scheduling accomplish?
4. Which statement best reflects the limits of Tiny Quanta?

Sources

The paper is “Efficient Microsecond-scale Blind Scheduling with Tiny Quanta” by Zhihong Luo, Sam Son, Dev Bali, Emmanuel Amaro, Amy Ousterhout, Sylvia Ratnasamy, and Scott Shenker, published at ASPLOS 2024, DOI 10.1145/3620665.3640381. The authors are at UC Berkeley, VMware Research, UC San Diego, and ICSI; the system is open-sourced.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the introduction and motivation establishing blind scheduling of microsecond jobs with broad service-time distributions, the head-of-line-blocking problem, and the quantitative case that smaller quanta help only if preemption overhead is small enough (with the extreme-bimodal simulation showing benefits vanish at 100-nanosecond and 1-microsecond overheads); the three challenges of sub-5-microsecond quanta (preemption overhead, scheduler scalability, cache pollution); the design of forced multitasking with coroutine yields and the compiler pass that places physical-clock probe points sparsely (bounding the instructions between probes) rather than the inaccurate, dense instruction-counter approach (which added over a thousand probes and 60 percent overhead to a RocksDB GET versus Tiny Quanta’s 40 probes); the two-level scheduling with a load-balancing dispatcher and per-core processor-sharing schedulers, the Join-the-Shortest-Queue policy with the Maximum-Serviced-Quanta tie-break, and its cache-locality benefit; and the evaluation on a 16-worker Xeon server against Caladan and Shinjuku across extreme and high bimodal, TPC-C, exponential, and RocksDB workloads, reporting 1.2 to 6.8 times the throughput of prior systems (for example 6.85 times Shinjuku on the exponential workload and around 2 times on RocksDB GETs), plus the ablations isolating the contributions of the instruction-counter alternative, slow yields, inaccurate timings, and the load-balancing and scheduling policies.