DEV Community: Yathiskumar

vLLM reinvented the operating system, and nobody told you

Yathiskumar — Tue, 11 Aug 2026 17:49:32 +0000

A few weeks ago I was reading the vLLM scheduler source, and I got the specific kind of déjà vu you get when you walk into a stranger's house and their kitchen is laid out exactly like your grandmother's.

There was a block table. There was a free list. There was a preemption path that could either swap a victim out to host memory or throw its work away and recompute it later. There was a fallback for when memory ran out mid-flight.

I had read this code before. In 2009. It was called an operating systems textbook.

This is not a criticism — it's the highest possible compliment, and it's also the most useful thing I can tell you if you're an engineer who feels like the ground moved under you in the last eighteen months. "AI infrastructure" sounds like a field you have to start over in. It mostly isn't. The dominant problems in LLM serving are memory fragmentation, cache affinity, queue scheduling, and rate limiting — and if you have ever tuned a JVM, sized a Redis cluster, or debugged a p99 that only spiked at 4pm, you already own the concepts.

You just have to see the translation table. So here it is.

Why this suddenly matters

The reason I'm writing this now rather than a year ago is that the interview loop changed.

For years, "design a system that serves an ML model" was a question you got if you applied for an ML infrastructure role. In 2026 it turns up in general backend loops — "design a customer support chatbot on top of a third-party LLM," "design safeguards for an agent that can take actions for a user," "walk me through serving a 70B model to 10,000 concurrent users." The guides tracking these loops describe the same shift: AI scenarios have moved out of specialist interviews and into standard ones, and cost-efficiency is now graded alongside latency and throughput rather than treated as a bonus.

That last one is the tell. Cost-and-operations grading is what happens when a technology stops being a research demo and becomes a line item. And when something becomes a line item, the questions asked about it stop being novel and start being the questions we have always asked about expensive machines.

Which is good news for you. Let's go through the four big ones.

1. PagedAttention is virtual memory. Actually, literally.

Start with the problem, because the problem is the fun part.

When an LLM generates text, it keeps a running scratchpad for every request called the KV cache — the key and value tensors for every token processed so far. It grows by one entry per token, on every single step, for the entire life of the request. It is large: for a big model with a long context, we're talking gigabytes per request, living on a GPU that has maybe 80 of them.

Here's the trap. Early serving systems stored each request's KV cache in one contiguous slab. Contiguous allocation needs a size up front. But you don't know the size up front — you have no idea whether the model will produce 12 tokens or 4,000. So the only safe move was to allocate for the maximum: reserve 2,048 tokens' worth of GPU memory for a request that might write 30.

If you have ever sized a buffer for the worst case, you already know how this ends. The vLLM paper measured it: existing systems were using only about 20–38% of their KV cache memory for actual token state. The other 60–80% was fragmentation and over-reservation. Two thirds of the most expensive RAM on earth, sitting empty, reserved for tokens that were never generated.

You have seen this bug. It is the allocator bug. Fixed-size slots waste the tail of every allocation (internal fragmentation); variable-size slots leave unusable gaps between live objects (external fragmentation); and the classic escape hatch is to stop demanding that a logical object be physically contiguous at all.

Which is exactly what PagedAttention does. Chop the KV cache into fixed-size blocks — say 16 tokens each. Scatter those blocks anywhere in GPU memory. Keep a block table mapping each sequence's logical block i to whatever physical block actually holds it. The attention kernel gets taught to gather across that table.

Figure omitted — see the diagram in the original post

If you swap four nouns, that paragraph is from a 1970s paper on demand paging. Logical blocks are pages. The block table is a page table. The GPU allocator is the frame allocator. And the payoff is the payoff paging always gives you: internal fragmentation is bounded to at most one partial block per sequence instead of one giant wasted reservation, and external fragmentation disappears entirely because every block is interchangeable. Waste drops to a few percent. More requests fit in memory. More requests in memory means bigger batches, and bigger batches on a GPU means throughput — the paper reports 2–4× against the state of the art at the time, at equal latency.

Then it gets better, in a way that will make you grin if you've ever implemented copy-on-write. Two requests that share a system prompt have identical KV state for that prefix. Identical state, block table indirection, refcounts... so of course vLLM shares the physical blocks between them and only copies when one diverges. fork() for transformers.

And when GPU memory runs out mid-generation — because a batch of requests all decided to be chatty at once — the engine preempts. It picks victims and either swaps their blocks out to CPU memory or discards them and recomputes from the prompt later. Swap or recompute. That is a page-replacement policy with an unusually honest cost model.

If you want to feel rather than read this: the memory allocation playground lets you watch first-fit, best-fit, and buddy allocators shred a heap into unusable holes, and the page replacement simulator lets you run FIFO, LRU, Clock, and OPT against the same reference string and watch FIFO commit Bélády's anomaly in public. Same mechanics, smaller numbers.

2. Prefix-aware routing is consistent hashing, rediscovered under pressure

Now scale it out. One GPU becomes a fleet.

Your instinct — a good instinct, earned honestly — is round-robin or least-connections in front of N identical replicas. Stateless workers, uniform work, spread it evenly. This is correct for essentially every web service you have ever operated.

It is quietly terrible here, and the reason is that your replicas are not stateless. Each one has a warm KV cache full of prefixes it has already computed.

Picture a support-bot deployment. Every request carries the same 6,000-token system prompt — policies, tone, tool definitions, few-shot examples. Processing those 6,000 tokens is the prefill phase, and it is real compute. If a request lands on a replica that already has that prefix cached, prefill is a table lookup and the user sees a first token almost immediately. If it lands on a cold replica, the GPU grinds through 6,000 tokens of attention before emitting a single character.

Round-robin guarantees that every replica ends up caching every prefix, which means your effective cache size is the size of one replica no matter how many you buy. You have built an N-node cluster with 1 node's worth of cache. Meanwhile the requests bounce between them, evicting each other's work.

Figure omitted — see the diagram in the original post

The fix is the thing you already know: route by content, not by counter. Hash the prefix, send matching prefixes to the same replica, let each node specialize. Cache affinity. That is consistent hashing wearing a name badge that says "prefix-aware routing," and the ecosystem converged on it from three directions at once:

SGLang's router tracks approximate prefix locality with a radix tree and falls back to shortest-queue routing when nodes get imbalanced.
GKE's Inference Gateway hashes the incoming token prefix and picks the replica most likely to hold it.
llm-d goes exact: every vLLM pod publishes KV-cache events, the router maintains an index keyed by block hash, filters candidates down to pods that actually hold the prefix, and picks the least token-loaded pod within that set.

Read that last one again, because the two-stage structure is the whole lesson. Filter by cache locality, then balance load inside the filtered set. Pure locality routing creates hotspots — one viral prefix melts one pod. Pure load balancing throws away the cache. You need both, and "both" means locality as a filter and load as a tiebreaker.

Their published benchmark is eye-watering and I want to be precise about it rather than let you take home a number that doesn't survive contact with your workload: on 8 vLLM pods across 16 H100s, simulating 150 tenants with 6,000-token contexts, precise prefix-aware scheduling hit a P90 time-to-first-token of 0.54 seconds versus 31 seconds for approximate routing and 92 seconds for random. That's the 57× headline. Throughput roughly doubled against cache-blind configs.

The caveat is doing a lot of work: total KV demand was 73% of cluster capacity — deliberate, heavy cache pressure, six times what any single pod could hold. Under light load with a tiny shared prefix, the gap shrinks toward nothing. Which is itself the familiar lesson: cache-aware routing wins exactly when the cache is scarce and the workload is skewed, and if you've ever argued about whether to shard by user ID, you have had this exact argument before.

The consistent hashing simulator is the fastest way to internalize the failure mode — add and remove nodes, watch how much of the keyspace remaps, and see why virtual nodes exist. The load balancing playground runs round-robin, least-connections, EWMA, and power-of-two-choices against one shared request stream so you can watch a skewed workload wreck a naive policy in real time.

3. Continuous batching is a scheduler fighting head-of-line blocking

Third problem, and this one is pure queueing theory.

GPUs want big batches — that's how you amortize weight loading against arithmetic. So batch the requests. The naive version, static batching, collects N requests, runs them together until every one has finished generating, then starts the next batch.

You have already spotted it. Request A wants 20 tokens, request B wants 2,000. A finishes at step 20 and its slot sits there, occupied and idle, burning GPU for 1,980 steps while B rambles. And every request that arrived at step 21 waits in line behind B for no reason at all.

That is head-of-line blocking. Same phenomenon as one slow query pinning a connection pool, one fat HTTP/1.1 response stalling a pipelined connection, one giant job hogging a thread pool. Long job in front, short jobs starving behind it, utilization on the floor.

Figure omitted — see the diagram in the original post

Continuous batching — the design shared by vLLM, TGI, and SGLang — fixes it by making the batch composition mutable every single decoding step. A request finishes, it leaves immediately. A slot opens, a queued request joins mid-flight. The batch is a living set, not a cohort. Iteration-level scheduling rather than request-level.

This has a prerequisite, and the prerequisite is section 1. You can only admit new work every step if you can hand out memory in small increments to a request whose final size you don't know — which is precisely what paged KV blocks give you. And you need preemption for the moment where you've admitted more work than will fit and something has to be evicted mid-generation. Paging and scheduling are co-dependent here, exactly as they are in an OS.

From there the research goes exactly where an OS person would guess. Chunked prefill splits a huge prompt into pieces and interleaves them with ongoing decodes, so one 100k-token prompt doesn't stall everyone else — that's time-slicing a long-running job. FastServe assigns priority by prompt length using a skip-join multi-level feedback queue, which is MLFQ, unmodified, from the same textbook. Others are chasing predictive shortest-job-first by guessing output length, which is SJF with the classic asterisk: SJF is provably optimal for mean waiting time and requires knowing job length, which you never do.

The entire arc — FCFS is bad, preemption helps, priority needs aging or it starves, SJF needs an oracle — is the scheduling chapter. It's just running on hardware that costs $30,000 a card, which is why people are suddenly willing to fund the research.

4. Token-per-minute limits are a token bucket that can't price the job

Last one, and this is where the analogy earns its keep by breaking in an interesting place.

LLM providers meter on two axes: requests per minute and tokens per minute. RPM is the limiter you know. TPM is the one that actually binds, because a single 200k-context call can eat as much quota as fifty 4k-token calls — which is how you end up at 5% of your RPM, eating 429s all day.

The algorithm underneath is the same token bucket that has been guarding APIs since forever. (The naming collision between "bucket tokens" and "LLM tokens" is the funniest accident in modern infrastructure and I refuse to stop enjoying it.) But a token bucket assumes cost is known at admission time: a request arrives, it costs one token, you check, you decide. With an LLM call you know the input size and nothing else — the output length is decided by the model, one token at a time, over the next several seconds. You are being asked to admit a job to a fixed-capacity system without knowing what it will cost.

Every strategy from there is a bet. Reserve pessimistically and you throttle yourself for capacity nobody used; debit as you stream and the limit becomes advisory, discovered only after you have blown it.

I went down this exact rabbit hole in Why your LLM app gets 429s even when you're under the rate limit — how each vendor accounts for it, the reserve-then-reconcile pattern, why your retry logic is making it worse, and what breaks once more than one worker shares the budget. For our purposes here the point is narrower, and it is the one thing on this list that your operating systems course genuinely did not prepare you for: admission control without a price tag.

Where the map actually tears

I've spent 2,000 words arguing that this is all familiar, so let me be honest about the four places it genuinely isn't. These are the parts worth thinking hard about — and, not coincidentally, the parts that separate a good interview answer from a great one.

Allocations grow after they're made. A malloc gives you a size and that size is a fact. A KV cache allocation grows by one block every few steps for the entire life of the request, and it stops growing at a moment nobody can predict. Your allocator is servicing a workload where every live object is slowly inflating. There's no classic analogue to "the heap is fine right now but will be full in eleven seconds because of objects that already exist."

Eviction cost isn't uniform. LRU assumes a miss costs about the same regardless of which item you dropped. Evict a KV block and the cost of getting it back is proportional to how much prefix has to be recomputed — dropping a block from a 100k-token conversation is enormously more expensive than dropping one from a 500-token chat. The right policy has to weigh recompute cost, not just recency. (Weighted eviction exists in the classic literature, but it's the exception there and the default here.)

One machine runs two opposite workloads. Prefill is compute-bound: a big parallel matrix crunch over the whole prompt. Decode is memory-bandwidth-bound: one token at a time, dragging the entire weight matrix across the bus for each. They want different batch sizes, have different SLOs (time-to-first-token versus time-per-output-token), and they're contending for the same silicon. It's as if your database ran OLAP and OLTP on the same box with no isolation — which is why the newer designs disaggregate them onto separate pools entirely.

Cost is a first-class design constraint, not an afterthought. The reason interviewers grade cost explicitly now is that the arithmetic is brutal and unavoidable. Cache hit rates aren't a latency nicety here; a bad routing policy doesn't just make things slower, it multiplies your GPU bill. This is the part where "just add replicas" — the reflex that solves most web-tier problems — is the wrong answer, and being able to say why is the answer they're looking for.

The actual takeaway

The pattern I keep landing on is this: new hardware constraints don't invent new algorithms, they re-run the old tournament with different scoring.

Paging won on 1970s minicomputers because RAM was scarce and expensive. GPU memory is scarce and expensive, so paging won again. Cache affinity beats naive load balancing whenever recomputation is costly. Preemptive scheduling beats run-to-completion whenever job lengths vary wildly. These aren't facts about operating systems. They're facts about resources under contention, and transformers didn't repeal them.

Which means the way to get good at AI infrastructure is not to memorize this year's serving frameworks — those will churn, and half the specific numbers in this post will be stale within eighteen months. It's to get so fluent in the underlying dynamics that you recognize them on sight when they show up wearing a new name. Fragmentation looks like fragmentation. Head-of-line blocking looks like head-of-line blocking. A cache with the wrong routing policy looks like a cache with the wrong routing policy, whether it's holding rows or attention keys.

That fluency is the thing I've been trying to build at Subroute — every algorithm is a live simulation you can run, tune, and break in the browser, because watching a policy fall over is worth more than reading about the failure mode. Right now it covers allocators, page replacement, cache eviction, rate limiting, load balancing, consistent hashing, and consensus, among others. Free, no signup.

And if you've operated any of this at scale and something above doesn't match what you've seen in production, I want to hear it. The gap between the paper and the pager is where the interesting stuff lives.

Originally published at subroute.dev.

I Got Tired of Watching YouTube Videos to Understand Graph Algorithms. So I Built This Instead.

Yathiskumar — Wed, 10 Jun 2026 14:00:44 +0000

Let me be honest with you.

Graph algorithms always felt odd to me.

Every time I sat down to learn BFS or Dijkstra, the same thing happened. I'd read an article. Get confused. Open YouTube. Watch one video. Then another. Then a third one at 1.5x speed. Two hours later, I'd close my laptop thinking "okay, I kind of get it"... and forget everything by next week.

Sound familiar?

The problem was never the videos. Some of them are great. The problem was that I was always watching someone else's understanding. I was never touching the algorithm myself.

So I did something about it

A while back, I started building Subroute — an interactive playground for technical concepts. I started this journey with topics like rate limiting and caching.

The idea is simple: learn by touching the system, not just reading about it.

And now, the topic that troubled me the most is finally live — Graph Algorithms.

👉 Check it out here: subroute.dev/topics/graph-algorithms

What's inside

Ten algorithms. Each one with its own page, its own live prototype you can play with, and a small quiz to check yourself.

Breadth-First Search (BFS) — visit a graph in expanding rings
Depth-First Search (DFS) — go deep first, then back up
Topological Sort — the build-order and task-scheduling trick
Dijkstra — the classic shortest path
Bellman-Ford — shortest path that survives negative edges
Floyd-Warshall — every distance, between every pair
Union-Find (DSU) — connectivity in near-constant time
Kruskal's MST — cheapest network, sorted edges first
Prim's MST — cheapest network, grown from one node
A* — the pathfinder behind games, GPS, and robots

The whole track takes about 100 minutes. Not 100 minutes of watching. 100 minutes of doing.

The one thing that changed everything for me

While building this, I realized something that no video ever told me clearly:

You don't need to memorize ten algorithms. You only need to know which question each one answers.

"What can I reach from here?" → BFS / DFS
"What's the cheapest route?" → Dijkstra (or Bellman-Ford if weights can be negative)
"How do I connect everything for the least cost?" → Kruskal / Prim
"What's the fastest path to that goal?" → A*

Once that clicked, the code became easy. Most of these are barely twenty lines. The hard part was never the code — it was knowing when to use what. So I added a side-by-side comparison table and a decision guide right on the page, because that's the cheat sheet I always wished I had.

Why this is not "just another tutorial site"

Because every concept here has a live prototype. You don't read about how Dijkstra grows its frontier — you watch it happen, you poke it, you break it, you run it again.

That's the whole point of Subroute. Reading gives you familiarity. Touching gives you intuition.

I need your help

I'm building this in public, and I genuinely want feedback. Brutal honesty welcome.

Did the explanations make sense?
Was any prototype confusing?
Which topic should I build next?

Go play with it: subroute.dev/topics/graph-algorithms

If even one person stops their endless YouTube loop and finally gets graph algorithms because of this — building it was worth it.

Drop your thoughts in the comments. I read every single one. 🙌

Three problems I had to solve to teach algorithms in a browser

Yathiskumar — Mon, 25 May 2026 08:09:53 +0000

A few months ago, I noticed I was rereading the same ByteByteGo article on rate limiting for the fourth time.

I could recite the token bucket definition. I could draw the diagram. I could explain it in an interview. But if you'd asked me "what happens when the refill rate is half the request rate and the bucket is small?" — I'd have stared into the middle distance, run the math in my head, and given a noncommittal answer.

The diagram wasn't the problem. The diagram was actually pretty good. The problem was that the diagram was static, and the algorithm wasn't.

Token buckets, sliding windows, leaky buckets, LRU caches, garbage collectors, load balancers — these are all systems that do something over time. They have dynamics. Their interesting behavior is what happens at the edges: when load spikes, when memory fills, when one server dies. None of that lives in a diagram. It lives in what happens next.

So I built Subroute — a playground where every algorithm is a live simulation in the browser. You adjust the parameters, you watch it run, you break it. The goal is to skip the "stare at the diagram and imagine" step entirely.

Building it taught me three things I didn't expect.

Problem 1: Time is a liar in the browser

The first thing I learned is that you cannot trust the clock.

A rate limiter is fundamentally about time. Tokens refill at N per second. Windows tick over every X milliseconds. Requests arrive at some rate distribution. The whole concept depends on a consistent forward-marching clock.

My first naive implementation used setInterval(tick, 100). Tick the simulation every 100ms, advance the algorithm, render the new state. It worked beautifully — until I tabbed away to check Slack.

When you background a browser tab, most browsers throttle timers aggressively. setInterval(tick, 100) becomes setInterval(tick, 1000) or worse. Then I'd tab back, and the simulation would either freeze, lurch forward in a giant jump, or quietly desync — the visible state ahead of the algorithm's internal state by minutes of simulated time.

Date.now() had the opposite problem. Real wall-clock time kept ticking, so if I used it as the source of truth, the bucket would silently "refill" 30 seconds worth of tokens the instant the tab regained focus. The simulation would jump, not freeze. Worse for teaching, because you couldn't see what had happened — you just saw the aftermath.

The fix took two changes:

A virtual clock. Every algorithm reads from simulationTime, not Date.now(). The simulation owns the concept of "now."
A requestAnimationFrame driver. Instead of setInterval, I increment simulationTime by a controlled delta inside rAF. When the tab backgrounds, rAF pauses cleanly. When it foregrounds, it resumes from where it stopped. No drift, no surprise jumps.

The bonus, which I didn't see coming, is that once time is virtual it becomes adjustable. I can give readers a speed slider — 0.25x to play through a slow burst in detail, 10x to fast-forward through a hundred refills in seconds. The same slider that solved a bug became one of the most useful teaching tools in the whole thing.

That pattern kept showing up: the right primitive solves a bug and unlocks a feature you didn't plan for.

Problem 2: Randomness is the enemy of learning

Once the clock was solid, I plugged in a random workload generator — Poisson arrivals, exponential intervals, the standard textbook stuff — and pointed it at five rate-limiting algorithms in parallel.

They all looked identical.

Token bucket, leaky bucket, fixed window, sliding window log, sliding window counter — five legitimately different algorithms with five different trade-offs. Under a uniformly random workload they were indistinguishable on the chart.

Which makes sense in hindsight: averaged over enough randomness, every rate limiter accepts the same fraction of requests. The differences only show up under patterns — bursts, sustained pressure, mixed traffic.

This is the gap between academic descriptions of algorithms and what they actually do in production. Real traffic isn't uniform random. Real traffic is Zipfian (a few keys dominate everything), bursty (most of the day is quiet, then 10x in a 30-second window), or scan-heavy (a backup job sweeps the entire keyspace once, blowing past every cache).

I rewrote the workload generator with two changes:

Named presets instead of free parameters. "Bursty," "scan," "Zipfian," "diurnal" — each one carefully constructed to make the differences between algorithms visible. The scan preset, for instance, is the single best demonstration of why ARC and LIRS exist and why vanilla LRU doesn't survive contact with production.
Seeded RNG. Every preset uses a fixed seed by default, which means everyone who clicks "scan workload" sees the exact same request stream. Reproducible. When someone tells me "the LRU panel looks broken at second 47," I can load the same seed and look at the same second.

The seeded-RNG decision turned out to matter for a reason I didn't foresee: it made the simulations shareable. A reader can screenshot a moment and another reader can reproduce it. The simulation becomes a thing two people can have an argument about, which is what learning resources should be.

Problem 3: Side-by-side is a feature, not a layout

The third decision was the one that changed the whole product.

My early prototype showed one algorithm at a time. Pick "token bucket" from a dropdown, watch it run, switch to "leaky bucket," watch that one run separately. This is how every existing resource handles it — one algorithm per page, you flip between them.

It doesn't work. By the time you've switched from "token bucket" to "leaky bucket" and watched it for ten seconds, you've already forgotten what the token bucket looked like. Comparison becomes a memory exercise.

The change that fixed it sounds trivial: render all five algorithms simultaneously, side by side, on the same canvas. But the implementation matters — they had to share one workload stream, not five independent ones. Otherwise you're back to comparing averages of randomness.

The architecture became:

One workload generator, producing a single stream of requests per simulation tick.
Five algorithm panels, each subscribing to the same stream as a consumer.
Each panel computes its own decision (accept/reject, hit/miss, route/queue) and renders its own state.

The result is the most "aha" moment I've shipped. Hit the scan preset on the cache eviction page and watch four of the policies degrade in real time while ARC and LIRS hold their hit rate. You don't have to explain scan resistance after that. The reader has seen it.

This is the heuristic I now use to evaluate every new simulation: can a reader feel the difference between two algorithms in 30 seconds of playing? If not, it's not done.

What this taught me about teaching

The pattern across all three problems was the same. Each one started as "how do I make this work technically" and ended as "this is what makes the algorithm legible."

A virtual clock fixed a bug, then became the speed slider — and the speed slider is how readers see slow-motion bursts in detail.

Seeded workloads fixed a reproducibility issue, then became the named presets — and the named presets are what reveal the algorithms' actual differences.

Side-by-side rendering fixed a comparison problem, then became the core layout — and the core layout is what turns five separate articles into one playground.

Reading about algorithms tells you what they are. Diagrams tell you what they look like. But intuition — the kind you need to make architecture decisions, debug latency spikes, or answer an interview follow-up — only comes from watching them behave. The simulation is the teacher. The words around it are labels.

What's next

Subroute today covers six topics: rate limiting, cache eviction, cache write policies, garbage collection, memory allocation, load balancing. The next batch is on the runway: queues, consistent hashing, replication strategies, and the hard one — consensus.

Raft and Paxos are where this approach has the most to prove. Most explanations of consensus are very good at describing the happy path and very bad at conveying what happens during a network partition. That's exactly where a simulation should win: slice the cluster in half, watch the leader election, scrub time backward, see exactly which node thought what when.

If you want to poke the current set, subroute.dev is free and there's no signup. If you've built or operated any of these in production and something in a simulation feels off, I want to hear about it — that's the feedback that makes the next version better than the last.

This post originally appeared on subroute.dev/blog.