Distributed Cache Design: Part 1

Routing, eviction, and read/write strategy

A distributed cache forces three separate decisions, and it’s easy to blur them together:

1. Which node owns this key? (routing)
2. When the cache is full, what gets thrown out? (eviction)
3. How does the cache stay in sync with the database? (read/write strategy)

Each one has its own failure mode. Get any of them wrong and a routine change — scaling a cluster, a traffic spike, a busy write path — turns into an incident. I’ll work through each with a running example: a package-delivery network routing containers to regional warehouses.

1. Routing: why key % N breaks, and what consistent hashing actually fixes

Say the routing layer assigns each incoming container to a warehouse with the obvious rule:

container_id % number_of_warehouses

It works fine until a warehouse opens or closes. The moment number_of_warehouses changes, container_id % N changes for most container IDs, not just the ones near the new warehouse. Containers that were happily assigned to Warehouse A suddenly hash to Warehouse C. It’s not a small reshuffle, it’s nearly a full one.

Map this onto a cache: number_of_warehouses is your node count, and every container is a cached key. Scale a Redis cluster from four nodes to five with naive modulo hashing, and you invalidate almost the entire cache in one move. That’s not a resize, that’s a self-inflicted stampede.

Put nodes and keys on the same ring instead. Consistent hashing places both on a fixed hash space — say, 0 to 2^32 - 1 — arranged as a ring. Each key belongs to the first node found moving clockwise from the key’s position. When a node joins or leaves, only the keys near that node move. Everyone else keeps their existing assignment.

TreeMap<Long, String> ring = new TreeMap<>();

ring.put(hash("node-A"), "node-A");
ring.put(hash("node-B"), "node-B");

long keyHash = hash(key);

String owner = Optional.ofNullable(ring.ceilingEntry(keyHash))
        .orElse(ring.firstEntry()) // wrap around to the start of the ring
        .getValue();

That’s the gap between opening a new warehouse and rerouting a slice of shipments, versus opening a new warehouse and reassigning nearly everything. One is a normal Tuesday. The other gets its own retro.

Consistent hashing on its own doesn’t fix uneven load, though. With one ring position per physical node, nodes can end up unevenly spaced — one server owns a much bigger arc than its neighbors and takes a disproportionate share of traffic while the rest sit idle. The fix is virtual nodes: give each physical server several positions scattered around the ring instead of just one. That evens out the arcs and, with them, the traffic. This is why basically every production ring implementation you’ll run into — Cassandra, DynamoDB-style designs, most client-side hashing libraries — uses virtual nodes rather than a bare ring.

If your node count changes at runtime — autoscaling, failover, capacity changes — you want consistent hashing. If you’re also seeing one node run hot with only a handful of physical nodes, that’s the signal to add virtual nodes rather than rethink the whole approach.

2. Eviction: what gets thrown out when the cache is full

Routing tells you where a key lives. Eviction tells you what happens when that node runs out of room.

Picture a small regional depot with limited shelf space. When a new container shows up and the shelves are full, something already there has to go. Which one leaves is the eviction policy’s whole job:

• LRU (Least Recently Used) — evict whatever hasn’t been touched in the longest time. Works well when recent access predicts future access.
• LFU (Least Frequently Used) — evict whatever has the lowest access count. Works well when some items stay popular over long stretches, independent of recency.
• TTL (Time to Live) — evict after a fixed duration no matter how often it’s used. Good for data with a natural expiry: session tokens, price quotes, verification codes.

A minimal LRU cache in Java, using LinkedHashMap in access-order mode:

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true); // true enables access-order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

LRU quietly falls apart during a sudden spike or a one-time batch scan. If a big batch of rarely used records all get touched once in a short window, they all count as “recent” and start pushing out entries that are genuinely popular but happened to be idle for a few minutes. That’s cache pollution: a burst of low-value, one-time access displacing high-value, recurring access. If your traffic has any bursty or scan-like shape to it, plain LRU is a liability more than a safety net.

Worth knowing how production systems actually implement this: Redis doesn’t keep a perfectly ordered LRU list — tracking exact recency for every key is expensive at scale. Instead it samples a handful of keys and evicts whichever looks oldest among the sample. Not exact, but close enough at a fraction of the memory and CPU cost. It’s a pattern worth recognizing on its own: approximate the expensive-to-track property instead of computing it precisely.

LRU when recency predicts future demand. LFU when long-term popularity matters more than recency. TTL when there’s a hard expiry regardless of access — and TTL usually isn’t competing with the other two, it’s layered on top of one of them. Flight prices that are only valid for five minutes need TTL; neither LRU nor LFU would evict a stale-but-popular price on its own.

3. Read/write strategy: keeping the cache and the database honest with each other

This is where teams get tripped up most, because “add a cache” sounds like one decision and it’s actually two: how you read, and how you write.

Strategy	Read path	Write path	Main benefit	Main risk
Cache-aside	App checks cache, falls back to DB on miss, populates cache	App writes to DB, invalidates/updates cache	Simple, cache holds only requested data	Stampede on simultaneous misses; stale data if writes don’t invalidate
Read-through	Cache layer loads from DB automatically on miss	Usually paired with another write strategy	Hides loading logic from app code	Needs a cache provider that supports loading
Write-through	Usually reads from cache	Cache and DB updated synchronously	Strong cache consistency	Higher write latency
Write-behind (write-back)	Reads from cache	Cache updated first, DB updated asynchronously	Very fast writes, can batch DB updates	Data loss if cache fails before flush
Write-around	Cache populated only on next read (cache-aside/read-through)	Writes go straight to DB	Avoids polluting cache with rarely-read writes	Read-after-write miss
Refresh-ahead	Cache proactively reloads before TTL expiry	Usually read-driven	Fewer misses on hot data	Wasted refreshes on data nobody re-reads
TTL expiration	N/A — expiration mechanism, not a full strategy	Entries expire after fixed period	Freshness boundary	Expiry storms if many keys expire together

Two examples from the same delivery network are worth sitting with. When a shipment flips from IN_TRANSIT to DELIVERED, both the cache and the primary database get updated before the operation is considered done — that’s write-through. You’re paying the extra latency to guarantee the cache never disagrees with a value people act on immediately. GPS pings are the opposite case: frequent location updates get written to the cache right away and flushed to the database in batches, write-behind style. Losing a few seconds of GPS history if the cache crashes is a fine trade for not hammering the database on every ping.

The trade-off that comes up most in design discussions: for something where a few seconds of staleness is tolerable but losing a write is not — order status updates, say — write-around is usually the right call, not write-through or write-behind. Write-through adds latency you don’t need, since staleness is acceptable here. Write-behind risks losing the write outright if the cache dies before it flushes. Write-around sends the write straight to the database, the actual source of truth, and lets the cache catch up lazily on the next read. You accept a possible cache miss or a brief stale read. You don’t accept a lost write.

One trap worth flagging: write-ahead logging (WAL) is not a caching strategy. It’s a database durability technique — write the change to a log before applying it to the data files. If someone says “WAL” in a caching conversation, they almost certainly mean write-through or write-behind.

Putting it together

Routing, eviction, and read/write strategy are three separate levers, and a real cache design answers all three on their own terms:

• Routing — consistent hashing, with virtual nodes if node count is small and load is uneven, so scaling the cluster doesn’t invalidate the whole cache.
• Eviction — LRU, LFU, or TTL, chosen by whether recency, frequency, or a hard expiry best predicts what should stay.
• Read/write strategy — chosen by which failure you can live with: a stale read, a slow write, or a lost write. You can’t optimize for all three at once.

If you can answer which node, what gets evicted, and what happens on write independently, you have an actual cache design. If the answer is still “we added Redis,” you have a cache-shaped guess.