Cache Hit Rate Drops After Adding a Node: Consistent Hashing

Caching · Intermediate · 7 min read · published 2026-10-23

This article was written by Claude (Anthropic) and published automatically. Published by Osama Fayyaz.

What this solves: You add one cache server and hit rate collapses while the database melts. See why hash(key) % N remaps most keys, and how a hash ring moves only a small slice.

The Forces at Play

You add one cache node to handle growth and your cache hit rate drops from 95% to near zero. Database CPU spikes and p99 latency explodes. This happens precisely because you added capacity.

The culprit is almost always the innocent-looking routing line node = nodes[hash(key) % len(nodes)].

Modulo routing is perfect while N is fixed. Change N and the mapping of nearly every key changes with it. Going from 4 to 5 nodes, a key stays put only when h % 4 == h % 5. That holds for 4 out of every 20 hash values, so 80% of keys move. Going from 10 to 11 nodes moves about 91%.

A moved key is a cold miss. Every one of those misses becomes a database read at the same moment.

So you are caught between competing pressures:

• Elasticity. You want to add and remove nodes freely, for autoscaling, failures, and maintenance.
• Locality. Every client must independently compute the same node for the same key, with no lookup hop.
• Stability. A membership change should disturb as few keys as possible.
• Balance. Each node should carry roughly equal load.

Consistent hashing gives you all four with a cheap, client-side calculation.

The Shape

The pattern works like this:

• Hash both nodes and keys onto the same circular space, for example 0 to 2^64.
• A key belongs to the first node token found clockwise from the key's position.
• Each physical node owns many virtual node tokens scattered around the ring, rather than a single point.

flowchart LR
    subgraph Client["App process (every instance runs the same code)"]
        K["key: user:42"] --> H["stable hash<br/>xxhash64 -> 0x7A1F..."]
        H --> L["binary search sorted token list<br/>first token >= 0x7A1F"]
        M["membership source<br/>config / service discovery"] --> R["ring builder<br/>150 vnode tokens per node"]
        R --> T["sorted token table<br/>0x11..->A#7, 0x3C..->C#2,<br/>0x7B..->B#91, 0xA0..->A#33 ..."]
        T --> L
    end
    L -->|"token 0x7B.. = B#91"| B[("Cache node B")]
    L -.-> A[("Cache node A")]
    L -.-> C[("Cache node C")]
    D[("New node D")] -. "joins: inserts 150 tokens,<br/>each steals a thin arc from a neighbour" .-> T

The important point is that all intelligence lives in the client. Cache nodes are ordinary Redis or memcached servers with no idea a ring exists.

The ring is just a sorted array of (token, node) pairs. Every app instance can rebuild it independently, as long as each one sees the same membership list and uses the same hash function.

How Data Flows Through It

Here is one read of user:42, followed by a scale-up.

1. Startup. Service discovery returns nodes [A, B, C]. The ring builder hashes "A#0" through "A#149", and the same for B and C. It then sorts all 450 tokens.
2. Lookup. xxhash64("user:42") returns 0x7A1F.... A binary search finds the next token, 0x7B02..., which is labelled B#91. The client sends GET user:42 to node B. This costs O(log V) and needs no network hop.
3. Miss path. On a miss, the client reads from the database and writes the value back to B.
4. Scale-up. Node D appears in discovery, and every client rebuilds its ring with 600 tokens. D's 150 tokens land in random spots. Each token claims only the thin arc between itself and the previous token.
5. Effect. Roughly 1/4 of keys now resolve to D, taken evenly from A, B and C. The other ~75% resolve exactly where they did before. user:42 most likely still maps to B and stays a hit.

Compare that with modulo routing, where the same change would have moved about 75% of keys onto different nodes.

A minimal ring:

import bisect, hashlib

def h(s: str) -> int:  # stable across processes and languages
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

class Ring:
    def __init__(self, nodes, vnodes=150):
        pairs = sorted((h(f"{n}#{i}"), n) for n in sorted(nodes) for i in range(vnodes))
        self.tokens = [t for t, _ in pairs]
        self.owners = [n for _, n in pairs]

    def node_for(self, key: str) -> str:
        i = bisect.bisect_left(self.tokens, h(key)) % len(self.tokens)  # wrap around
        return self.owners[i]

What Each Piece Owns

• Hash function. Owns deterministic placement. It must give identical output in every process, language and restart. It does not own security or randomness; never use a salted hash like Python's hash().
• Membership source (static config, Consul, Kubernetes endpoints). Owns who is in the ring. It does not own routing decisions or health judgements made per request.
• Ring builder / token table. Owns mapping hash space to nodes and smoothing balance through virtual nodes. It does not own replication, data migration or hot-key handling.
• Client lookup. Owns picking a node per key. It does not own retries against a different node. Silently falling back to "any node" scatters copies of the same key across the cluster.
• Cache nodes. Own storing bytes and evicting. They deliberately know nothing about the ring, which is exactly why they stay simple and interchangeable.

The design also leaves some things out on purpose. Nobody moves data when membership changes. Moved keys simply miss once and refill. That is fine for a cache, and it is precisely why a cache is the ideal fit for this pattern.

Where It Breaks Down

Too few virtual nodes.

• With one token per node, arc sizes vary wildly. One node can own 2–3x its fair share.
• Worse, a dead node's whole arc falls on its single clockwise neighbour. That neighbour's load doubles and it dies next: a cascade.
• With 100–200 vnodes, both the imbalance and the failover load are spread across every survivor.

Clients that disagree about membership.

• During a rollout, half your pods may see [A,B,C,D] while the other half see [A,B,C]. The same key now lives on two nodes.
• Writes and invalidations go to only one copy, so stale data survives deletes.
• Mitigations:
  • Log a ring fingerprint and alert when instances differ.
  • Version the membership config.
  • Keep TTLs short enough to bound how long the damage lasts.

Flapping nodes.

• A health checker that ejects a slow node, re-adds it, then ejects it again churns 1/N of keys on every flip.
• Use hysteresis instead of instant ejection.
• Consider leaving a down node in the ring and treating its keys as misses.

Hot keys.

• Consistent hashing balances key counts, not traffic. One celebrity key still pins one node.
• Fix this separately, with a local in-process cache or by replicating the hot key across N nodes under suffixed names.

Operational burden.

• The ring code itself is tiny.
• The real cost is keeping membership consistent across every client, in every language that talks to the cache.

When This Is Overkill

A single cache node. If one node with a replica fits your working set, skip sharding entirely. Most apps with a few GB of hot data live happily here.

Redis Cluster or a managed equivalent. These already solve the problem server-side with 16,384 fixed hash slots. Resharding moves slots, and smart clients follow MOVED redirects. Don't layer your own ring on top.

Fixed fleets. If the node count never changes, plain modulo is fine. Its only weakness is resizing.

Simpler alternatives. If you do need client-side sharding, rendezvous (HRW) hashing gives the same minimal disruption with no token table: score each node with hash(key, node) and pick the highest. It is ideal for under ~50 nodes. Jump consistent hash is even leaner, but it only supports adding or removing nodes at the end of the list.

The signal you've outgrown modulo. Hit rate craters and database load spikes every time you scale, deploy a node change or lose a server. Add the ring at that point, before autoscaling makes resizes routine.

Key takeaway: If clients pick a cache node with hash(key) % N, every resize remaps almost every key. Use a ring with 100–200 virtual nodes per server and a stable, process-independent hash, so a resize moves only about 1/N of keys.

import hashlib

def stable_hash(s: str) -> int:
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")