Replicas, Load Balancing, and Batch-Aware Routing

"They told me to balance the load evenly. So I gave every replica exactly one request, and now every GPU is running a batch of one and hating me equally."

A Round-Robin Router With Good Intentions

The single-node work is done. In Chapter 22 we made one model run as fast as one GPU allows: quantized weights, a paged KV cache, fused attention kernels, and continuous batching that keeps the accelerator busy. That gives us a node with a known throughput, a known latency curve, and a known memory budget. It is not enough. A node that answers 300 requests per second cannot serve a product that receives 3,000. The remedy for a throughput ceiling is the one named in Section 1.1: replicate the service across more machines. This section is about doing that replication well for GPU inference specifically, where the naive answer (round-robin across identical replicas) quietly wastes most of the fleet.

The architecture is simple to draw and subtle to operate. A router (sometimes called a gateway or a serving frontend) sits in front of $R$ identical replicas, each a full copy of the optimized model node. Every incoming request is assigned to one replica, joins that replica's queue, and is eventually folded into a batch that the GPU executes. Total fleet throughput is, in the best case, $R$ times one replica's throughput. The router's job is to make the common case the best case, and Figure 23.2.1 shows the two ideas that get it there: batch-aware fill and prefix affinity.

1. Replicate the Node, Multiply the Throughput Beginner

The replicated-service pattern is the oldest move in distributed systems and the one we already named as an axis of distribution. To serve more requests than one server can handle, you run many identical servers and put a load balancer in front. We met this pattern abstractly in Section 2.9, where a stateless replica plus a balancer gives throughput that grows linearly with the replica count and availability that survives any single replica's failure. For ordinary web services, that is essentially the whole story: requests are independent and cheap, so any replica will do, and round-robin or random placement is close to optimal.

GPU inference inherits the pattern and breaks the assumption that makes round-robin optimal. A replica here is not a cheap stateless web worker; it is a full copy of the optimized model node from Chapter 22, holding billions of parameters in GPU memory and most efficient only when it processes many requests together in a batch. Two properties follow, and they are the entire reason this section exists. First, a replica's throughput depends on how it is fed: feed it one request at a time and it runs far below its rated capacity. Second, a replica accumulates state, the KV cache of every active generation, so the replicas are not interchangeable for a request that is mid-conversation. A web balancer assumes replicas are stateless and requests are uniform. Neither holds here, which is why a serving router needs ideas that a web balancer does not have.

2. Why Round-Robin Is the Wrong Default Intermediate

Consider $R$ replicas, each running a GPU step that handles up to $B$ requests and takes time $\tau$ regardless of how many requests are actually in the batch. The fleet's peak throughput is

achieved only when every step runs a full batch of $B$. The cost the hardware bills you, on the other hand, is one GPU-step of $\tau$ per fired batch, full or not. So the quantity that decides whether you are wasting money is the mean batch occupancy $\bar{b}/B$, where $\bar{b}$ is the average number of requests per fired step. A fleet running at 45 percent occupancy is paying for more than twice the hardware its workload needs.

Round-robin maximizes the wrong thing. By spreading each arriving request to the next replica in rotation, it minimizes the number of requests waiting at any one replica, which sounds desirable until you remember that a replica fires a step as soon as it has any backlog at all. Thin, evenly-spread queues mean every replica frequently fires a batch of one or two, the GPU pays the full $\tau$ for a nearly empty batch, and effective throughput collapses toward $R/\tau$ instead of $R \cdot B / \tau$. The fix is batch-aware routing: deliberately let a small queue accumulate at a replica, and let the replica wait a bounded time for its batch to fill before firing. This is the fleet-level generalization of the continuous batching from Section 22.7, where a single node forms batches from its own queue; here the router shapes which requests land in which queue so that batches can fill at all.

For the placement decision itself, the serving world borrows two ideas from classical load balancing and adapts them to batched work. Least-outstanding-requests routes each request to the replica with the shortest current backlog, which keeps queues balanced without the blindness of round-robin. Power-of-two-choices is the cheap approximation: sample two replicas at random and send the request to the less-loaded of the two. This avoids the herd behavior where every request rushes to the single least-loaded replica (a thundering herd that the global least-loaded rule can cause), and it provably keeps the maximum queue length close to balanced with only two probes per request. Both are adapted for GPU work by measuring "load" as queued-plus-in-flight requests against the batch capacity $B$, not raw connection count.

3. Prefix Affinity: Routing to the Cache Advanced

Batch occupancy is only half of the routing problem. The other half comes from statefulness. When a model generates text token by token, it builds a KV cache holding the attention keys and values for every token seen so far, the structure we sized and paged in Section 22.5. That cache lives in the GPU memory of one specific replica. If a follow-up turn in the same conversation, or a new request that shares a long system prompt, is routed to a different replica, that replica has no cache for the shared prefix and must recompute it from scratch, paying the full prefill cost again. Route the request back to the replica that already holds the prefix, and the prefill is nearly free.

This is prefix affinity (also called session affinity or sticky routing). The router keeps a small table mapping each session id or prompt-prefix hash to the replica currently holding its cache, and routes matching requests there. The tension with batch-aware balancing is real: affinity pins a request to a possibly-busy replica, which can hurt load balance, so production routers blend the two, preferring the cache-holding replica unless its backlog exceeds a threshold, in which case they evict and re-route. The payoff is large for workloads with shared prefixes (multi-turn chat, retrieval-augmented prompts with a common context, agent loops that re-send a long tool-description preamble), because the saved prefill is often the dominant cost of the request.

4. Queueing and Admission Control for the Tail Advanced

Filling batches has a cost, and that cost is latency. A request that waits for its batch to fill, or that lands behind a long backlog, experiences a delay that the mean throughput number hides entirely. The metric that matters for a user-facing service is the tail: the p99 latency we made precise in Section 5.3, the time below which 99 percent of requests complete. A serving fleet can have excellent mean latency and a catastrophic tail if a few requests sit behind a saturated replica's queue.

Two mechanisms protect the tail. The first is a bounded fill wait: a replica waits for its batch to fill only up to a deadline, then fires whatever it has, so no request is held hostage to an arrival that never comes. This caps the latency cost of batch-aware routing directly. The second is admission control. When the whole fleet is saturated, queues grow without bound and every request's latency climbs together; it is better to reject or shed a fraction of requests immediately (returning a fast error or a degraded response) than to accept all of them and blow the SLO for everyone. Admission control trades a small drop in completion rate for a bounded tail, and the threshold is usually set on queue depth: if the shortest replica queue already exceeds the point where the SLO is at risk, the router stops accepting new work rather than queueing it. We make the saturation point a control signal for autoscaling in Section 23.4; here it is a control signal for protecting the requests already in flight.

5. Simulating the Three Policies Intermediate

The argument so far is qualitative; the simulation below makes it quantitative. It models a fleet of $R = 4$ replicas, each running GPU steps of fixed cost $\tau$ that process up to $B = 8$ requests. Requests arrive as a Poisson stream, each tagged with a session prefix, and we hold the offered load fixed while swapping the routing-and-batching policy. The three policies are exactly the ones developed above: plain round-robin with greedy firing, batch-aware power-of-two routing with a bounded fill wait, and prefix-affinity on top of batch-aware. We report sustained throughput, mean batch fill (the occupancy that decides GPU efficiency), total GPU busy-seconds (what the hardware actually bills, including the KV-recompute penalty on cache misses), and the p99 queue wait.

import random, statistics

# Discrete-time fleet simulator (1 ms ticks). R replicas each run one GPU "step"
# at a time. A step processes up to B queued requests and costs STEP_MS regardless
# of how full the batch is, so a half-empty batch burns a full GPU slot for half
# the useful work. Offered load is held fixed; the three policies differ only in
# how the ROUTER assigns each arrival and WHEN each replica fires its batch.
#
#   round_robin : even spread; a replica fires the instant it is idle and holds
#                 >=1 request -> many tiny batches -> poor GPU efficiency.
#   batch_aware : route to the shorter of two sampled backlogs (power-of-two) AND
#                 let a replica wait up to FILL_WAIT_MS for the batch to fill.
#   prefix_affinity : batch_aware PLUS pin each session to the replica already
#                 holding its KV cache, avoiding a per-step recompute penalty.

R, B          = 4, 8         # replicas, max batch size per step
STEP_MS       = 40           # one GPU step, fixed cost regardless of fill
HORIZON_MS    = 60000        # simulated wall-clock
ARRIVAL_RATE  = 0.30         # requests per ms (~300 req/s); capacity = R*B/STEP = 800
N_PREFIX      = 50
FILL_WAIT_MS  = 25           # how long a batch-aware replica waits to fill
KV_MISS_MS    = 3            # extra step cost PER uncached prefix in a batch
CACHE_CAP     = 12           # prefixes a replica can keep KV cache for
random.seed(7)

def simulate(policy):
    queues   = [[] for _ in range(R)]     # lists of (arrive_ms, prefix)
    busy_to  = [0] * R                     # tick until which replica is busy
    wait_since = [None] * R                # when current batch-aware wait started
    cached   = [set() for _ in range(R)]
    affinity = {}
    rr = [0]
    fills, waits = [], []
    gpu_ms = 0
    batch_aware  = policy in ("batch_aware", "prefix_affinity")
    use_affinity = policy == "prefix_affinity"

    def route(pfx):
        if policy == "round_robin":
            r = rr[0] % R; rr[0] += 1; return r
        if use_affinity and pfx in affinity:
            return affinity[pfx]                  # session's KV cache lives here
        a, b = random.randrange(R), random.randrange(R)   # power-of-two-choices
        r = a if len(queues[a]) <= len(queues[b]) else b
        if use_affinity:
            affinity[pfx] = r
        return r

    def fire(r, now):
        nonlocal gpu_ms
        q = queues[r]
        batch = q[:B]; del q[:len(batch)]
        pset = {p for (_, p) in batch}
        # KV-cache misses cost extra per uncached prefix (recompute the prefix).
        # Each replica keeps a bounded cache of recently seen prefixes.
        misses = len(pset - cached[r])
        cost = STEP_MS + KV_MISS_MS * misses
        cached[r] |= pset
        if len(cached[r]) > CACHE_CAP:                 # bounded cache, drop overflow
            cached[r] = set(list(cached[r])[-CACHE_CAP:])
        for (arr, _) in batch:
            waits.append(now - arr)
        fills.append(len(batch))
        gpu_ms += cost
        busy_to[r] = now + cost
        wait_since[r] = None

    for now in range(HORIZON_MS):
        # Poisson arrivals: at most one per tick at this rate (rate < 1/ms)
        if random.random() < ARRIVAL_RATE:
            pfx = random.randrange(N_PREFIX)
            queues[route(pfx)].append((now, pfx))
        # each idle replica decides whether to fire
        for r in range(R):
            if busy_to[r] > now or not queues[r]:
                wait_since[r] = None
                continue
            if not batch_aware:
                fire(r, now)                      # greedy: fire on any backlog
            elif len(queues[r]) >= B:
                fire(r, now)                      # batch full
            else:
                if wait_since[r] is None:
                    wait_since[r] = now
                if now - wait_since[r] >= FILL_WAIT_MS:
                    fire(r, now)                  # waited long enough, fire partial

    served = len(waits)
    thr = served / (HORIZON_MS / 1000)
    util = statistics.mean(fills) / B
    waits.sort()
    p99 = waits[int(0.99 * len(waits)) - 1]
    gpu_busy_s = gpu_ms / 1000
    return thr, util, gpu_busy_s, p99

print(f"offered load ~{ARRIVAL_RATE*1000:.0f} req/s, fleet capacity {R*B*1000//STEP_MS} req/s\n")
print(f"{'policy':<18}{'thrupt(req/s)':>14}{'gpu_fill':>10}{'gpu_busy(s)':>12}{'p99_wait(ms)':>14}")
print("-" * 68)
for pol in ("round_robin", "batch_aware", "prefix_affinity"):
    thr, util, steps, p99 = simulate(pol)
    print(f"{pol:<18}{thr:>14.0f}{util*100:>9.0f}%{steps:>12.1f}{p99:>14.0f}")

offered load ~300 req/s, fleet capacity 800 req/s

policy             thrupt(req/s)  gpu_fill gpu_busy(s)  p99_wait(ms)
--------------------------------------------------------------------
round_robin                  303       45%       240.1            49
batch_aware                  299       71%       164.9            80
prefix_affinity              299       61%       150.4            64

Read the table by column. Throughput is the same across all three because the offered load is well inside fleet capacity; what differs is the price paid to serve it. Round-robin has the lowest p99 (49 ms) precisely because it never waits to fill a batch, but it pays for that with 45 percent occupancy and the highest GPU bill (240 seconds), more than half the hardware doing nothing useful. Batch-aware routing trades a slower tail (80 ms, from the fill wait) for a 31 percent cut in GPU-seconds. Prefix-affinity then improves on batch-aware along two axes at once: it cuts the GPU bill further (150 versus 165 seconds) by turning cache misses into hits, and it pulls the tail back down (64 versus 80 ms) because affinity-routed sessions skip the expensive recompute that was inflating their step cost. The lesson is not that one policy dominates; it is that the router's policy is the knob that sets your throughput-per-dollar and your tail at the same time.

# A prefix-aware router fronting several model replicas (SGLang-style).
# The framework tracks each replica's KV-cache contents and routes by longest
# matching prefix, falling back to load balance when no replica holds the prefix.
from sglang import Runtime, Router

replicas = [Runtime(model_path="my-model", base_gpu_id=i) for i in range(4)]
router = Router(
    replicas,
    policy="cache_aware",     # longest-prefix-match affinity, else load balance
    max_wait_ms=20,           # bounded fill wait that caps the tail (Section 4)
    balance_threshold=1.5,    # evict affinity when a replica is 1.5x over the mean
)
router.serve(port=8000)       # one endpoint; clients never see the fleet

6. What the Router Buys You Beginner

Stepping back, the router converts a pile of identical replicas into a single coherent service whose throughput scales with the replica count and whose efficiency depends almost entirely on three decisions: how full it keeps the batches, whether it respects the KV cache, and how aggressively it protects the tail. Round-robin gets the first two wrong by default, which is why a serving fleet is one of the few places where the obvious load-balancing answer is actively harmful. The replicated-service pattern from Section 2.9 still gives you the linear throughput scaling and the failure tolerance; the GPU-specific routing is what keeps that scaling from costing twice what it should.

We have replicated the node, fronted it with a router that fills batches and respects the cache, and protected the tail with bounded waits and admission control. That gives us a fleet that serves a steady stream of low-latency requests efficiently. But not all inference is a steady stream of small requests: some workloads are enormous offline jobs that score billions of records overnight, where latency does not matter and throughput is everything. Serving those well on the same fleet, and knowing when to separate them, is a different optimization with its own routing and batching rules. Section 23.3 takes up online versus batch inference across a fleet.