Two earlier visits covered SGLang’s broad architecture and its newest serving tricks; the first tour at /sglang/ walked the front door to the GPU, and the second at /sglang-2/ chased the recent performance work. This third visit narrows onto the single decision every serving stack lives or dies by: which waiting request gets admitted next, and what that admission costs in KV cache blocks. SGLang answers it with an unusually layered design. A policy layer sorts the queue by how much work the radix cache can save, an adder layer converts each candidate into a token budget that reserves pages the request will need after admission, and the cache layer holds matched prefixes hostage with reference counts so eviction cannot steal a promise the scheduler just made. Each layer is independently readable, and the seams between them are where the interesting comments live.

The tour also catches the project mid-migration on one front. Alongside the classic Python RadixCache, the mem_cache tree now ships an optional Rust core, loaded through a registry that falls back to Python when the native extension cannot be built. The default remains Python; the Rust path is opt-in and explicitly gated by a compatibility check. Watching a codebase move a hot data structure across a language boundary while keeping the old implementation working is a lesson in itself. As always, this is an educational walk through the published code of sgl-project/sglang under the Apache-2.0 license.

SGLang's admission story: HTTP and the Engine feed a tokenizer manager that ships requests over zmq to a single-threaded scheduler, a cache-aware policy sorts the waiting queue by reusable prefix, the PrefillAdder budgets each candidate against page-aligned KV blocks, the radix cache pins matched nodes and frees them on eviction, and the tp worker turns the winning batch into one forward pass.

Reading the overview from left to right:

• The FastAPI entrypoint at python/sglang/srt/entrypoints/http_server.py builds its app and ships it through launch_server; the programmatic Engine path spawns the identical process family.
• The TokenizerManager batches tokenization through AsyncDynamicbatchTokenizer and forwards requests to the scheduler over zmq.
• The Scheduler runs its event_loop_normal or the CPU-GPU overlapping event_loop_overlap variant.
• Each tick calls get_next_batch_to_run, which delegates new work to get_new_batch_prefill and decode to update_running_batch.
• The SchedulePolicy reorders the queue in calc_priority, and the PrefillAdder admits against budgets via add_one_req.
• The RadixCache answers match_prefix and insert, with evict respecting locked nodes.
• A tree core registry can swap in the RustUnifiedTreeCore adapter over a native extension.
• The PagedTokenToKVPoolAllocator owns page-aligned slots, and TpModelWorker runs forward_batch_generation before the DetokenizerManager streams text back.

The detail view: process entry and both event loop flavors, the policy's sort strategies with its queue-size escape hatch, the adder's per-request budget math, the radix cache trio of match, insert, and locked eviction, the registry that can hand the tree to Rust, and the paged allocator writing indices into per-layer KV tensors.

Sorting the queue by what the cache can save

The policy layer starts from a simple observation: if two requests share a prefix, serving the one with the longer shared prefix first turns expensive prefill compute into a cheap cache lookup. calc_priority implements four cache-aware orderings, selected by the CacheAwarePolicy enum at line 168: LPM sorts by longest matched prefix, DFS_WEIGHT walks the radix tree’s subtree weights so whole shared branches surface together, HRRN applies the highest-response-ratio-next rule with prefix awareness, and an experimental SHORTEST_PREFILL_FIRST minimizes immediate work. Each request’s prefix match is computed once, then reused, because the same match that orders the queue is the one the adder will pin.

The escape hatch is the honest part. Prefix matching against a tree costs CPU, and under load that cost competes with the loop it is trying to speed up, so _determine_active_policy downgrades to plain first-come-first-served when the waiting queue exceeds a fixed threshold, with a comment saying exactly that. Cache-aware scheduling is an investment that pays off with a small queue and loses to FCFS with a large one, and the code encodes that trade-off as a constant rather than pretending one policy fits all.

The subtlety inside the sort is worth pausing on. LPM and its cousins need a prefix match for every waiting request, and the policy runs that match through the same tree the scheduler will use for admission, which means the sort itself warms the very state the decision will rely on. A cache-agnostic policy skips matching for ordering but still matches opportunistically so the metrics snapshot can report how many waiting tokens would have hit, and a separate refresh path touches the prefixes of queued requests head-last so an LRU eviction policy retires them in reverse admission order. Scheduling policy, telemetry, and eviction hygiene share one walk of the same tree, which is the kind of economy that only shows up when you read the loops rather than the API docs.

The budget that admission must clear

Sorting only picks a candidate order; admission is arithmetic. The PrefillAdder tracks remaining prefill tokens, remaining total tokens, and page-aligned extend capacity, and add_one_req charges each candidate before allowing it into the batch: extend length plus clipped max_new_tokens, plus a page reserved for allocator alignment overhead, plus Mamba state slots on hybrid models, plus a request slot reserve. Crucially, the candidate’s matched prefix is pinned with a lock around the whole check, so the budget math can safely count those tokens as free until the decision is committed.

The verdict flows through budget_state, whose three-valued answer drives the admission loop: keep adding, stop for other reasons, or stop because there is no token budget left. When the budget says no, the request is deferred rather than dropped, and on hybrid SSM architectures the deferral is staged per pool. The scheduler-side wrapper at get_new_batch_prefill adds gates of its own: a grammar-constrained request cannot enter the batch until its grammar is compiled, allocatable request slots are checked before any prefix math runs, and an adaptive prefill delayer can hold prefills back when pool usage says decode throughput would suffer.

Two more gates reward a close look. A minimum-free-slots delayer can postpone admission outright when the running batch is close to the allocatable ceiling, betting that decode will drain a few requests and prefilling now would only trigger retractions. And when a chunked prefill is already in flight, a dynamic chunk sizer predicts the next slice from the request’s history, so the chunked_prefill_size constant becomes a starting point rather than a straitjacket. Both gates exist because the costliest thing a scheduler can do is admit work that forces the running batch to retract, and both are cheap guards placed before the expensive prefix math ever runs.

The radix cache holds the promise

Every layer above leans on one invariant: a prefix reported as a match must still be resident when the batch launches. The RadixCache enforces it with reference counting. match_prefix walks the tree, splits a node if the match ends mid-segment so the boundary is exact, and returns the matched KV indices along with the terminal node; the adder then inc_lock_refs that node, which removes its blocks from evictable_size until admission completes. Eviction at 552 only ever takes unlocked leaves, which is what makes the lock a real guarantee rather than a suggestion.

The insert side is equally careful. _insert_cache snapshots the request’s kv index row from the ReqToTokenPool at ReqToTokenPool, page-aligns the key, inserts, and then frees the duplicate slots the insertion exposed. Keys carry more than token ids: an extra_key namespace keeps different LoRA adapters or cache salts from sharing nodes even when their token sequences match, a quiet fix for a class of correctness bugs other stacks discover the hard way.

The tree itself is getting a second implementation. The registry at tree_core_registry.py resolves a backend by name or environment, and its fallback check probes whether the Rust toolchain can actually build before honoring a Rust selection, logging the reason and quietly using Python otherwise. The RustUnifiedTreeCore adapter translates the Python interface’s params and result objects into native calls, keeping the tree’s semantics identical so callers cannot tell which core answered. Hierarchical offload remains available either way through the HiCacheController, which prefetches and writes back across host and storage tiers while the scheduler keeps making admission decisions.

From decision to slots to kernel

Once a batch wins admission, the paged layer converts it to memory. The PagedTokenToKVPoolAllocator implements alloc_extend, growing each request’s slot list along page boundaries while respecting the blocks already held by the radix cache, and its indices index straight into the per-layer K and V tensors of MHATokenToKVPool. The scheduler hands the prepared batch to TpModelWorker, whose forward_batch_generation runs one forward pass and returns sampled tokens, and the event loop overlaps the next CPU-side planning round with that GPU work in event_loop_overlap. Finished requests re-enter the tree through cache_finished_req, and chunked requests keep their slot rows across chunks so a partially prefilled prompt survives until the next slice lands.

Three lessons travel well. Sort by savings, not by arrival, but know when to stop sorting. Treat admission as an explicit budget transaction, with the cache pinning assets so the math cannot be invalidated mid-decision. And keep the data structure behind a narrow interface, because a Rust rewrite of a hot tree is only survivable when callers cannot observe the swap. Readers who want the surrounding context can compare the same decisions in vLLM at /vllm/ and /vllm-2/, TGI’s Rust-side scheduler at /text-generation-inference/, LMDeploy’s dual engine at /lmdeploy/, and TensorRT-LLM’s runtime at /tensorrt-llm/; the first two SGLang tours at /sglang/ and /sglang-2/ remain the best map of the wider territory.

Enjoyed this post? Never miss out on future posts by following us