Consistent Hash Cache Ring Lab (Interactive)
Hash keys onto a vnode ring and compare keys moved on scale-out vs modulo churn. Place 8,000 hashed keys on a consistent-hash ring with virtual nodes, then measure rebalancing spread and single-flight herd control.
Redis-style Cluster: Consistent Hash Ring + LRU Economics
Hash 8,000 real keys onto the ring, add a node, and count exactly how many keys move compared with modulo hashing.
› Avalanche: synchronized TTLs expire together — jitter every TTL ±10–20% so misses spread over time.
› Penetration: attackers query non-existent keys, all missing to the DB — a Bloom filter of valid keys short-circuits them.
› Stampede: one 50,000-QPS key expires this millisecond — single-flight lets 1 request rebuild while the rest wait on it.
A single node serves keys via O(1) LRU: a HashMap for lookup plus a Doubly Linked List for recency, so get/put/evict never scan. The cluster layer then routes with a consistent-hash ring (client-side Ketama or 16,384 hash slots); each physical host occupies 50 ring positions, which is what keeps per-node key counts near the ideal 2000 instead of wildly uneven slices.
How It Works Under the Hood
A cache cluster fails users in two ways: bad placement and bad miss behavior. Modulo sharding (hash % N) relocates almost every key when N changes; consistent hashing with virtual nodes moves only the K/N fraction whose ring positions fall into the new arc. Sweep nodes and vnodes to watch per-node key spread tighten and keys-moved shrink. On the miss side, a popular key evicted from RAM triggers a thundering herd of identical origin fetches unless single-flight coalesces them. An 80/20 access model on a fixed hot set shows why hit ratio saturates long before the cache fits everything.
Core Architectural Principles
- Consistent hash ring: on scale-out only K/N keys remap, versus (N-1)/N under hash-modulo.
- Virtual nodes smooth per-node key spread from lumpy to near-even.
- Thundering herd: without single-flight, M concurrent misses spawn M origin fetches for one key.
Explain why consistent hashing beats modulo for scale-out, with the K/N remap fraction quantified, and mention vnodes for load balance. Then pivot to miss-path protection — probabilistic expiry, single-flight, and stale-while-revalidate — because a cache's danger is correlated misses. The 80/20 hot-set math, showing a bigger cache is not free, signals sizing maturity.
Consistent hashing minimizes reshuffling on topology changes but adds ring complexity and hot-shard risk without enough virtual nodes.