CockroachDB admission control: stealing the queue back from the scheduler

CockroachDB’s pkg/util/admission is the production counterpoint to this topic’s papers: where DAGOR sheds across services and redis rejects on one thread, cockroach builds a user-space scheduler inside each node — work is intercepted before it becomes a runnable goroutine and queued where it can be reordered by tenant and priority. The repo is cloned at ~/repos/cockroach (pinned at cockroach@a7e11788); this is a code-read, ~1.5 h, focused on two interfaces, one queue, and two overload signals. Before opening files, this chapter builds the ideas in order; the anchor table below maps each step to an exact file:line.

The problem in one sentence

When a node saturates, queueing happens somewhere — and the Go scheduler’s runnable queue is FIFO with no notion of priority or tenant, so a backup can starve user reads unless the database moves the queue into its own code. Admission control doesn’t eliminate the wait; it relocates it to a place that can reorder it while keeping the CPU and disks busy.

Terms of art used below:

• Runnable goroutine — a goroutine ready to run but not currently on a CPU: work already waiting in the Go scheduler’s queue. Cockroach samples runnable-per-CPU as its CPU overload signal (Step 3).
• Slot — a unit of concurrency, held while work runs and returned when it finishes (Step 2).
• Token — a unit of rate, consumed at admission and never returned, used where the true cost lands later (Step 2).
• L0 files / sub-levels — Pebble’s LSM write-stall signals (topic 4): the depth of unpaid compaction debt, cockroach’s IO overload signal (Step 4).

The concepts, step by step

Step 1 — the reframe: overload control as a user-space scheduler

In: nothing yet — this step establishes the central design move every later step implements. Out: the reframe (move the queue out of the Go scheduler into code you can reorder) and its deliberately node-local scope.

The package doc comment states the two goals — limit node overload (admission.go:11-13) and provide performance isolation between priorities and tenants (admission.go:14-19) — and the central move (admission.go:21-24): “shift queueing from system-provided resource allocation abstractions that we do not control, like the goroutine scheduler, to queueing in admission control, where we can reorder.” Scope is deliberately node-local, not cluster-level (admission.go:26-33): in a system with strong work affinity, only the node itself can protect itself in time — cluster-level admission “can complement node level admission control” but not replace it.

 without admission control:            with admission control:

 reqs ──▶ goroutines ──▶ Go runqueue   reqs ──▶ WorkQueue ──▶ few goroutines
                         (FIFO, blind          (ordered by tenant,
                          to priority           priority, arrival)
                          and tenant)                 │
                                               grant when a slot/token frees

Why it matters: as with topic 34’s coordinated omission, latency lives in the queue you aren’t looking at. Cockroach makes the queue visible, owned, and reorderable.

Step 2 — slots vs tokens: concurrency vs rate

In: the reorderable queue from Step 1 needs a currency for “is a resource free?” Out: the two currencies — slots (returnable, for CPU) and tokens (non-returnable, for IO) — and why the choice encodes closed- vs open-loop control.

The package doc (admission.go:54, “Tokens and slots are the two ways admission is granted”) splits resources by whether work completion is observable. A slot models concurrency: occupied while the work runs, returned when it finishes — right for CPU-bound KV work, where “done” is well-defined. A token models rate: consumed at admission and never returned — right for IO, because a write’s true cost lands later, when compactions rewrite those bytes; there is nothing to hand back.

graph LR
    W[work arrives] --> Q{resource kind}
    Q -->|CPU-bound KV| S[take a slot]
    S --> R[run] --> D[done: slot returned]
    Q -->|IO / bytes written| T[consume byte tokens]
    T --> P[write lands in L0]
    P --> C[compactions pay later - no return]

Why it matters: the slot/token split is the type system of overload — it encodes whether backpressure can be closed-loop (slots: measure occupancy) or must be open-loop (tokens: refill on a capacity model).

Step 3 — the CPU signal: runnable goroutines per CPU, additive slots

In: the slot currency from Step 2, which needs a target count. Out: the CPU overload signal (runnable-per-CPU, not utilization) and the additive-increase/additive-decrease loop that hunts the slot count the machine can sustain.

The overload signal for CPU is not utilization — it is runnable goroutines per CPU, sampled every 1 ms (kv_slot_adjuster.go:16, KVSlotAdjusterOverloadThreshold, default 32). A runnable-but-not-running goroutine is work that is already waiting; this is queuing-time detection in scheduler clothing — the same instinct as DAGOR’s average queuing time, and for the same reason both are local signals and neither is CPU utilization: 100% busy with an empty queue is healthy, 100% busy with a deep queue is overload.

kvSlotAdjuster.CPULoad(runnable, procs, samplePeriod) (kv_slot_adjuster.go:29 for the type, :46 for the method) turns the signal into an adaptive concurrency limit. The adjustment is additive both ways — the code’s own comments say so — one slot per 1 ms tick:

// kv_slot_adjuster.go — CPULoad: additive adjust (71–72, 84, 91), triggers (99, 103)
71      if usedSlots > 0 && total > kvsa.minCPUSlots && usedSlots <= total {
72          total--        // comment :65/:81: "additive decrease", 1 slot per 1 ms tick
84      if usedSlots >= total && total < kvsa.maxCPUSlots {
91          total++        // comment :81/:90: "additive increase", 1 slot per 1 ms tick
99      if runnable >= threshold*procs {                              // overloaded → decrease
103     } else if float64(runnable) <= float64((threshold*procs)/2) { // underloaded → increase

So at runnable >= threshold*procs it decreases total slots by one (:72); at or below half that (:103) it increases them by one (:91) — additive-increase/additive-decrease (AIAD), every millisecond, hunting the concurrency the machine can actually sustain. (This is not AIMD: the decrease is total--, not a multiplicative total *= (1-α); the comment at :65 calls it “additive decrease” explicitly. DAGOR’s admission controller is the AIMD one — do not conflate them.)

 runnable/CPU
   ▲
   │ ≥ threshold        → slots-- (overloaded: shrink concurrency)
   │
   │  (dead band)         hold
   │
   │ ≤ threshold/2      → slots++ (underloaded: probe upward)
   └────────────────────────────▶ sampled every 1 ms

The dead band between threshold/2 and threshold is what keeps the controller from oscillating on every tick: it only acts at the extremes.

Step 4 — the IO signal: L0 debt, tokens as compaction budget

In: the token currency from Step 2, which is open-loop and needs a feedback signal to size refills. Out: the LSM-derived IO overload signal (L0 file and sub-level counts) and how it turns token refill into a compaction budget spent by priority.

For stores, overload is read straight off the LSM: L0 file count and L0 sub-level count (io_load_listener.go:69 and :77). You know these numbers from topic 4 — they are Pebble’s write-stall signals, the shape of unpaid compaction debt. Cockroach promotes them from a per-store reflex (stall everyone identically when L0 is deep) to a node-wide admission policy: when L0 crosses the thresholds, byte tokens for incoming writes are limited — sized so compactions can pay the debt down — and the WorkQueue spends that budget on the highest-priority work first, instead of stalling all writers blindly.

graph TD
    L[L0 files and sub-levels grow] --> S{over threshold?}
    S -->|no| U[unlimited byte tokens]
    S -->|yes| B[compute limited byte tokens per interval]
    B --> WQ[WorkQueue spends tokens by priority and tenant]
    WQ --> PD[incoming writes slow, compactions catch up]
    PD --> L

Why it matters: this closes the loop the token model opened in Step 2 — tokens can’t be returned, but the L0 signal measures the accumulated consequence of past grants and throttles future ones.

Step 5 — the priority ladder: below zero means “yield to users”

In: the WorkQueue that spends slots (Step 3) and tokens (Step 4). Out: the concrete int8 priority ladder that decides which work waits under overload, and how priority and tenancy compose.

WorkPriority is an int8 (admissionpb/admissionpb.go:23) and the ladder is deliberate: LowPri = MinInt8 (−128), BulkLowPri = −100, UserLowPri = −50, BulkNormalPri = −30, NormalPri = 0, LockingNormalPri = 10, UserHighPri = 50 (admissionpb/admissionpb.go:29-48). Everything below zero is bulk/background — backups, rebalancing, changefeed catch-up — so under overload it is precisely the elastic work that waits while user foreground traffic keeps its latency. Within one priority, the WorkQueue enforces fairness across tenants: priority orders classes of work, tenancy divides capacity inside a class.

Step 6 — the grant loop: requester and granter

In: the signals (Steps 3–4) and the priority policy (Step 5). Out: the two interfaces that turn “who wants to run” and “what is free” into grants, so adding a resource is writing a granter, not a scheduler.

Two small interfaces decouple “who wants to run” from “what resource is free”: requester (admission.go:178) answers hasWaitingRequests and accepts granted, while granter (admission.go:198) offers tryGet (the uncontended fast path) and returnGrant. The concrete requester is WorkQueue (work_queue.go:303), whose doc comment (work_queue.go:277) spells out the ordering: a group heap orders tenants by used slots/tokens (fairness), and within each tenant, work is ordered by priority and create time — i.e. (tenant fairness, WorkPriority, FIFO arrival). A request enters at WorkQueue.Admit (work_queue.go:813) — try the fast path, else queue and block — and CPU-bound KV work reports completion via AdmittedWorkDone (work_queue.go:1196, which panics if called for non-KV work), returning its slot and closing the loop of Step 2. Because signal (Steps 3-4), policy (Step 5), and mechanism (this loop) are separate interfaces, adding a resource means writing a granter, not a scheduler.

Step 7 — contrast: redis rejects, DAGOR spans services, cockroach reorders

In: the full cockroach mechanism from Steps 1–6. Out: where cockroach sits against this topic’s other two code-reads on the reject-vs-reorder and intra-node-vs-cross-service axes.

Hold this topic’s three code-reads side by side. Redis (reading-redis-backpressure.md) is single-threaded: it cannot reorder admitted work, so its only move is a fast error at the door (OOM gate, output-buffer kills). DAGOR (reading-dagor.md) works between services: priorities travel in RPC headers, upstream throttles for downstream. Cockroach sits in the middle: intra-node like redis, but multi-core and priority-aware like DAGOR — it neither rejects (work waits, it doesn’t fail) nor coordinates across nodes (the doc comment leaves distributed admission as a complement, not a replacement).

Where each step lives in the code

All paths relative to ~/repos/cockroach/pkg/util/admission.

Read order: the package doc top to bottom (it is the design document) → requester/granter → WorkQueue.Admit → kvSlotAdjuster.CPULoad → the two L0 thresholds and the io_load_listener.go comment block. Resist reading the rest of work_queue.go; these anchors are the skeleton.

Questions to answer in notes.md

1. Why is runnable-goroutines-per-CPU a better overload signal than CPU utilization? Relate it to DAGOR’s finding that queuing-time (DAGOR_q) beats response-time (DAGOR_r) shedding — what does each pair of signals say about where waiting lives?
2. Why can a slot be returned but a token cannot? Trace one KV read and one write: at what moment is each resource’s true cost fully known, and what does that imply for closed- vs open-loop control?
3. The AIAD slot adjuster decreases at threshold*procs but only increases at or below half that. What failure mode does the dead band prevent, and what would equal thresholds do?
4. Topic 4’s Pebble stalls writes when L0 gets deep — every writer, equally. What can cockroach’s token-based version do that the stall cannot, and what risk does granting any writes during L0 debt introduce?
5. For the M35 capstone gate: FalkorDB executes queries on a fixed thread pool over GraphBLAS kernels. Which of cockroach’s pieces map (WorkQueue in front of the pool? slots = pool threads?), and which signal replaces runnable-goroutines-per-CPU when you don’t own the scheduler?

Done when

Answer each before unfolding it.

• You can narrate one KV request end to end — Admit fast path vs queue, grant by (tenant, priority, arrival), run, AdmittedWorkDone slot return — naming each hop’s interface.

  Answer

  A KV request calls WorkQueue.Admit (work_queue.go:813). Admit asks the granter (admission.go:198) for tryGet — the uncontended fast path; if a slot is free it runs immediately. Otherwise it enqueues in the WorkQueue (the concrete requester, work_queue.go:303), which orders waiting work by tenant fairness (group heap on used slots/tokens), then WorkPriority, then create time (work_queue.go:277). When a slot frees, the granter calls granted on the requester, which dequeues the next winner. The work runs, then reports completion via AdmittedWorkDone (work_queue.go:1196), returning its slot — closing the concurrency loop of Step 2. AdmittedWorkDone panics if called for non-KV work, because only slots (not tokens) are returnable.

• You can state both overload signals (runnable per CPU; L0 files/sub-levels) and say why neither is utilization.

  Answer

  CPU overload is runnable goroutines per CPU, sampled every 1 ms against KVSlotAdjusterOverloadThreshold (default 32, kv_slot_adjuster.go:16). IO overload is L0 file count and L0 sub-level count (io_load_listener.go:69, :77) — Pebble’s write-stall signals from topic 4, the depth of unpaid compaction debt. Neither is utilization because utilization cannot tell a healthy busy server from an overloaded one: 100% CPU with an empty runnable queue is fine, 100% CPU with a deep runnable queue is overload. Both signals measure waiting — runnable-but-not-running work, and accumulated write debt — which is exactly DAGOR’s queuing-time instinct in a different vocabulary.

• You can explain, in two sentences, why writes get tokens and CPU work gets slots — and why the two are not interchangeable.

  Answer

  CPU-bound KV work has an observable completion — the goroutine finishes — so a slot (held while running, returned on completion, AdmittedWorkDone) models it as concurrency and closes the loop. A write’s true cost lands later, when compactions rewrite its bytes out of L0, so there is nothing to return at admission time; a token (consumed once, never returned, refilled on a capacity model driven by the L0 signal) models it as a rate. They are not interchangeable because a returnable slot assumes you know when the cost is paid, and for IO you do not until compaction happens.

• You can place cockroach, redis, and DAGOR on the axes reject-vs-reorder and intra-node-vs-cross-service unaided.

  Answer

  Reject vs reorder: redis rejects (fast -OOM/-BUSY/disconnect at the door — one thread, nothing to reorder); cockroach reorders (work waits in a WorkQueue and is granted by priority/tenant, it does not fail); DAGOR sheds by priority (drops low-priority whole tasks). Intra-node vs cross-service: redis and cockroach are both intra-node (one process/one node), while DAGOR is cross-service (priorities ride RPC headers, upstreams throttle for downstreams). Cockroach is the multi-core, priority-aware midpoint: intra-node like redis, priority-aware like DAGOR, and it explicitly leaves cluster-level admission as a complement, not a replacement (admission.go:26-33).

References

Code

• CockroachDB — pkg/util/admission, cloned at ~/repos/cockroach, pinned at cockroach@a7e11788

Related guides

• README.md — topic 35 overview and the capstone gate
• reading-redis-backpressure.md — the reject-don’t-reorder pole
• reading-dagor.md — the cross-service pole
• ../04-lsm-deep-dive/README.md — where L0 files and sub-levels were first met as write-stall signals