Case Study: Distributed Cache¶

Step 1: Requirements¶

Functional: GET/SET/DELETE on a key-value pair, with an optional TTL per key (a Memcached/Redis-cluster-shaped system).

Non-functional: sub-millisecond latency per operation; the total dataset is larger than any single machine's RAM, so it must be distributed across many machines; adding or removing a cache node should disrupt as little of the existing cached data as possible.

Step 2: Capacity estimation¶

The number that determines everything here is dataset size vs. a single machine's RAM. If the working set to cache is 500GB and each cache node has 64GB of usable RAM, at least 8 nodes are needed just to hold the data once (before any replication) — this single division is what turns "design a cache" into "design a distributed cache" in the first place, rather than pointing at a single large Redis instance.

Step 3: High-level design¶

graph LR client["Client"] --> router["Client-side routing<br/>(consistent hash)"] router --> n1["Cache node 1"] router --> n2["Cache node 2"] router --> n3["Cache node 3"]

Unlike a database, a distributed cache commonly does its request routing client-side (the client library knows the hash ring and which node a key belongs to) rather than through a load balancer — an extra network hop to a router just to look up which cache node to hit would erase much of the latency benefit caching exists to provide.

Step 4: Deep dive — consistent hashing¶

Plain hash(key) % N breaks catastrophically when N changes: adding or removing one node changes the modulus for nearly every key, remapping almost the entire dataset at once — a near-total cache wipe at the exact moment (a node change) the cache should be most resilient.

graph TD subgraph ring["Hash ring (0-359 degrees)"] n1["Node A: position 0"] n2["Node B: position 120"] n3["Node C: position 240"] end k1["key 'user:42' hashes to position 50"] -.->|"assigned to next node clockwise"| n2 k2["key 'user:99' hashes to position 200"] -.->|"assigned to next node clockwise"| n3

Each node is placed at one or more positions on a hash ring; each key is assigned to whichever node sits at the next position clockwise from the key's own hash. Removing Node B only remaps the keys that were between Node A and Node B on the ring (they now map to Node C) — every other key's "next node clockwise" is unaffected, so only the fraction of keyspace actually owned by the removed node gets redistributed, not the whole dataset. This is the same technique already covered for consistent hashing in load balancing, applied here to cache-node selection instead of backend-server selection — same underlying mechanism, different layer.

In practice, each physical node is placed at many positions on the ring (virtual nodes), not just one — a single position per node means node removal dumps its entire keyspace onto exactly one neighbor, unevenly loading it; many virtual nodes per physical node spread a removed node's keyspace across many neighbors roughly evenly instead.

Step 4 (continued): the hot key problem¶

Consistent hashing distributes keyspace evenly, but not necessarily traffic — one extremely popular key (a viral post's like-count, a trending product) can direct a disproportionate share of all requests at the single node that owns it, overwhelming that node even though the overall keyspace is balanced.

graph TD hot["Hot key: 'trending_post:123'"] --> node["Single node owning it<br/>via consistent hashing"] node --> overload["Overwhelmed — even though\nkeyspace distribution is even"]

Mitigation: replicate exceptionally hot keys onto multiple nodes (clients pick one at random per request, spreading the load), or cache the hottest keys in each application server's own local memory as a short-TTL first layer in front of the distributed cache entirely — an extra cache layer specifically for the small number of keys hot enough to justify it.

Step 5: Bottlenecks and trade-offs¶

Replication for availability (each key stored on 2+ nodes, so one node's failure doesn't lose that data) trades memory capacity for resilience — the same trade every database replication decision makes, just applied to cache nodes instead of a primary database. Eviction policy (commonly LRU) determines what gets dropped under memory pressure — a policy mismatched to the actual access pattern (e.g. LRU when access is closer to random) evicts data that was about to be reused, quietly degrading hit rate without any error or obvious signal pointing at the eviction policy as the cause.

Common pitfall¶

Treating a distributed cache as a durable store because it's spread across multiple replicated nodes is a category error — even with replication, a cache is explicitly allowed to evict or lose data (that's what TTLs and eviction policies are for), and an application that would break on a cache miss for data it never wrote anywhere else has quietly turned an optional performance layer into an unacknowledged single point of data loss. Anything that must survive a cache-wide outage belongs in the actual database underneath, with the cache treated as strictly optional acceleration on top of it.