Your Autoscaler Says the Rebalance Was Clean. Your Token Bill Says Otherwise.

Consistent Hashing Meets Agent Sessions: When 'Nothing Moved' Still Costs You the Context Window

Consistent hashing was built for a world where losing a key costs you a cache miss. Agent sessions live in a different world — that 'key' is a context window you paid for turn by turn, token by token. Point a routing layer built for memcached at your agent fleet, and every quiet, textbook-perfect rebalance is secretly billing you for amnesia.

The incident: a scale-up that shouldn't have hurt

Here's the scenario, and it plays out the same way in shop after shop. Autoscaling kicks in for a traffic bump, two new agent worker nodes join the pool, sessions route through consistent hashing on the session ID — nothing exotic, textbook setup. The math says this should be boring: the ring guarantees only a small slice of keys move. Instead, p99 latency on the very next turn for a chunk of active sessions jumps from ~800ms to 6-8 seconds, and token spend for that ten-minute window spikes well above baseline. The reflex diagnosis — 'cold start on the new pods' — is wrong. What's actually happening: every session whose hash lands in the new nodes' slice of the ring gets rehomed to a worker holding an empty context. The next user turn doesn't hit a warm agent, it hits a blank one, which silently replays — or worse, reconstructs from a truncated history — the entire prior conversation before it can answer anything. Multiply that across however many sessions the ring reassigned, and a routine scale-up produces a latency spike that looks like a cache stampede but is really a fleet-wide bout of memory loss.

Quick recap: what consistent hashing actually guarantees

Quick refresher, since the rest of this hinges on it: consistent hashing maps nodes and keys onto a ring, and each key belongs to the nearest node clockwise from it. Add or remove a node, and only the keys sitting between it and its predecessor move — roughly K/N of the total, nowhere near the full reshuffle that naive mod-N hashing would trigger. That's the whole value proposition: minimize how many keys a topology change disrupts. Notice what it says nothing about — how expensive it is to disrupt any single key. That gap is where this whole lesson lives.

The mismatch: a cache miss is not the same shape as amnesia

When memcached rehomes a key, the cost is a cache miss: fetch it from the source of truth, write it back, move on. Milliseconds, stateless by design. An agent session has no cheap source of truth to refetch from — the context window *is* the state. System prompt, tool call history, retrieved documents, prior reasoning, user corrections, all built up turn by turn. Rehome it to a fresh worker and you don't get to 'go fetch it from Postgres' — you either replay the entire transcript through the model again, burning the same tokens you already paid for once, or, if the transcript wasn't persisted faithfully, you lose fidelity outright. A cache miss costs a round trip. A session rehome costs the conversation's entire token history, restated to the model, before it can do anything useful. That's not a miss. That's amnesia with a bill attached.

Why virtual nodes and bounded-load hashing don't fix this

Virtual nodes — giving each physical node many points on the ring — and bounded-load variants — capping how many keys any node can hold — are both real, useful techniques. But they solve a distribution problem: smoothing out hot spots, keeping the K/N guarantee tight even with a handful of nodes. Neither touches the cost function of a move. You can have perfectly even, minimally-disruptive rehoming by key count and still be re-priming a dozen 40-turn agent sessions from scratch every time a node joins or leaves. The ring was never taught that some keys are cheap to lose and others are expensive to lose. It treats every key as equally disposable — because for memcached, every key genuinely is.

What 'consistent hashing with memory' would need

If you want the ring's placement guarantees without paying the amnesia tax, rehoming cost has to become a first-class input, not an afterthought. Two directions actually hold up in practice:

• ▹Weight the cost into the ring itself — treat a session with a 50-turn, 30K-token context as heavier than a fresh one, and bias placement (or defer eviction) so expensive sessions are the last to move, not equally likely to move as everything else.
• ▹Make state portable instead of re-derivable — checkpoint or snapshot the context (KV cache, conversation state, tool results) so a rehome becomes a state transfer between workers, not a full re-prime from raw transcript. Same idea behind prefix-cache-aware routing in serving stacks like vLLM/SGLang, just applied one layer up, at the session router.
• ▹Prefer sticky routing with a graceful drain over a hard cutover — when a node is scheduled to leave, let its existing sessions finish or idle out on it while only new sessions land on the new topology, instead of force-migrating live context immediately.

# naive: every key equally cheap to move
node = ring.get_node(hash(session_id))

# cost-aware: session weight influences placement + migration priority
weight = session.context_tokens / max_context_tokens
node = ring.get_node(hash(session_id), migration_cost=weight)

if node != session.current_node:
    if weight > CHECKPOINT_THRESHOLD:
        transfer_state(session, from=session.current_node, to=node)  # ship the context
    else:
        reprime(session, node)  # cheap enough to just replay

The takeaway

If you're building or operating agent routing today, stop grading rebalance health by 'percentage of keys moved' — that's a memcached-era metric, and it'll tell you the rebalance went fine while your token bill and your p99 are telling a different story. Audit rebalance events for token cost and re-prime latency per moved session, not just movement percentage. The ring can be perfectly balanced and still be quietly expensive.

Once you're weighting session cost into placement, the next problem shows up fast: how do you keep hot sessions pinned to their worker under normal conditions, before a rebalance ever happens? That's session affinity — sticky routing — the concept this whole lesson has been leaning on without naming.

Extend your knowledge

• ▹Read Karger et al.'s original consistent hashing paper (1997) to see the exact problem it was designed to solve — web cache load balancing, nothing session-shaped.
• ▹Look at bounded-load consistent hashing (Mirrokni, Thorup, Zadimoghaddam, 2018) to understand precisely what it improves — load distribution, not move cost.
• ▹Check how vLLM/SGLang implement prefix-cache-aware routing — it's the closest production analogue to 'shipping context instead of re-priming.'
• ▹Audit your own agent fleet's next scaling event: pull latency and token-usage graphs for the 10 minutes after a scale-up/down and see if you can spot the re-prime signature described here.