Distributed Caching: Architecture and Invalidation Across Nodes

Part 1 (caching in system design) treated the simplest useful shape: one cache in front of one database, with the application making every decision. That shape stops working for the same reason a single application server does: the working set outgrows one machine’s memory, or one machine’s failure takes the entire cache layer with it. The answer is the same answer every layer eventually gives, make it a fleet. But a fleet of caches is not one cache split into pieces. It is a coordination problem wearing a cache’s clothes, and most of this article is about the three decisions that define it: where each key lives, how copies across tiers stay honest, and what happens when a node disappears.

Distributed caching is the architecture in which a cache is spread across multiple cooperating nodes (each holding a share of the keys, routed to by consistent hashing) so the fleet serves as one logical cache with more memory and more availability than any single node could offer. The win is capacity; the price, paid throughout this article, is that nothing is single-copy anymore, not the data, not the placement, and not the failure behavior.

Routing: who decides where a key lives

With one cache, the question “which cache?” had one answer. With a fleet, every read and write must first be routed to the owning node, and there are three places the decision can live:

• Client-side routing. The application’s cache client computes the placement itself; the standard approach with Memcached, where the client keeps the consistent-hash ring and talks directly to the node that owns the key. No middleman, one network hop, and the client library owns the cluster view.
• Proxy routing. A routing layer in front of the fleet takes each request and forwards it to the owning node. The application stays unaware of the topology, at the cost of an extra hop on every operation and one more component to run.
• Coordinator routing. A node in the fleet itself acts as coordinator: the model of Redis Cluster, where any node redirects the client to the right one. Routing state lives with the cluster, at the cost of a redirect round trip the first time a key is touched.

All three agree on one thing: the placement must be consistent hashing or something like it, so membership changes move only a small share of keys rather than the whole keyspace. What differs is who holds the membership view, and therefore what breaks first when nodes come and go. Client-side routing fails first at library versions: a stale client with a stale ring view disagrees about placement, which quietly becomes the same data in two places. And every extra hop is paid for out of the budget explained in latency vs throughput: a cache that adds a network hop per read spends its budget on coordination before it serves a single key.

Cache tiers: one copy close, one copy shared

Fleet scale brings a second architectural decision: copies. A remote cache node is one network hop away; process memory is one pointer away. Most large systems end up with both, as a two-tier cache:

• Tier 1, in-process. A small local cache inside each application instance, holding the hottest keys in the same memory as the request handling. Hits cost nothing network-shaped; misses fall through to Tier 2.
• Tier 2, the shared fleet. The distributed cache proper: every instance shares one view of the keyspace, capacity measured in the fleet’s total memory, one hop away.

The tier pattern trades memory for latency, and its price is paid in consistency. Two tiers mean every key hot enough for Tier 1 exists in at least two copies, on machines that cannot see each other, precisely the territory of the CAP theorem and consistency models. A stale local copy is not a bug in the cache tier; it is the price of the hop you did not make. Whether that price is acceptable is a decision made per data type, and it turns urgent the moment writes exist: as soon as a key is written, every copy in every tier is wrong until updated.

Hot keys: the shard that will not spread

Consistent hashing balances the count of keys per node, and the count is the wrong thing to balance. Traffic is skewed; part 1’s observation that a small hot set serves most requests cuts across the fleet now: one celebrity’s profile, one product page, one trending key can account for more requests than the rest of the keyspace together. Placement dutifully assigns that single key to one node, and that node becomes the busiest machine in the fleet while its neighbors idle.

Hot keys are an architecture problem before they are a hardware one, and the counters come in three families:

• Split the key. Replicate one hot key into a handful of siblings (product:42:v1 through v8, with readers choosing a suffix) so the load spreads across nodes. Cheap, and the reason hot-key schemes tend to look like versioned keys.
• Replicate the key. Allow the same key on several nodes and let clients pick among them, spreading reads of known-hot keys across a small replica set.
• Absorb it locally. Put the hottest keys into Tier 1 in-process memory, so the request never reaches the fleet. The strongest counter, and the one that reintroduces the tier pattern’s consistency price.

The measurement matters more than the fix: a hot key can only be found by watching per-key traffic, and only a fleet forces you to look. Adding cache nodes to fix a hot key is the most common wrong move; the placement sends the hot key to one of the new nodes, and the problem moves without shrinking.

Distributed cache invalidation

Everything above is read traffic. Writes are where a single cache was easy and a fleet is not. In part 1, invalidating a key meant deleting it from the one cache. In a fleet, a write handled by application instance A must invalidate (or update) every copy: the owning node’s copy, the Tier 1 copies on every instance that touched the key recently, and any replica of the owning node. The invalidation crosses the same network the reads cross, and inherits every one of that network’s failure modes.

Three architectures exist for getting an invalidation across a fleet, trading immediacy against machinery:

• Broadcast, publish the delete everywhere. The application, or the owning node, publishes an invalidation event that every instance and cache node applies. Immediacy, at the cost of a delivery mechanism; a pub/sub channel, a broadcast protocol, a fan-out service, and of defining what happens when a subscriber misses a message while restarting.
• Gossip, let the fleet converge. Nodes exchange invalidations periodically and copies age out without a central publisher. No fan-out machinery, but the window in which some nodes still hold the stale key is longer and less predictable.
• TTL, give up on immediacy. Cap the divergence with expiry and accept bounded staleness in exchange for zero coordination. The pragmatic default at fleet scale, usually combined with a fast path for the few keys that genuinely cannot wait.

The choice is not one architecture but a per-key decision, and it is the reason distributed cache invalidation has its reputation for difficulty: the cost of immediacy is a second distributed system (a message layer with its own failure modes) on which correctness now depends. The deliberate techniques (purges, versioned keys, write-through) are catalogued in cache invalidation strategies, part 6 of this series; the architectural point to carry from here is that at fleet scale, invalidation is message delivery, and every message-delivery question in a distributed system asks what happens when the message is lost.

Redis vs Memcached

Two cache servers dominate the choice, and the choice is less about benchmarks than about how much machinery belongs in a cache layer. Both are in-memory, both are fast enough that the network hop usually costs more than the lookup, and both are placed and routed by the consistent-hash patterns this article has described. What differs is scope:

Reading the table bottom-up is the useful exercise. Memcached is deliberately a cache (no persistence, no replication, nothing to operate) and Redis is a cache that can also be much more, which is both its appeal and its risk. The Redis-specific patterns live in redis caching, part 4 of this series, and the internals underneath (data structures, persistence, Sentinel vs Cluster) in redis architecture, part 5. One warning belongs here regardless of tool: the more a cache server can do, the more it gets asked to do things a cache must not; becoming load-bearing state that cannot be flushed. The disposable-copy principle from part 1 survives distribution only by design.

When a node disappears

The last fleet decision is the one most teams defer until an outage forces it: what happens when cache nodes die? Part 1’s answer for a single cache (fall back to direct database reads) still works, with one difference in kind: fleet routing means only the dead node’s share of keys goes cold, so the fallback load is the traffic that node was absorbing, concentrated on the database in the moments after the failure. That concentration is the cache avalanche scenario, and part 3 covers it in full; this article’s concern is the design decision underneath it:

• Fail-open. Miss on the dead node’s keys and serve from the database. The system stays up and slow, and the database absorbs the burst.
• Fail-closed. Treat the cache as required and refuse work it cannot serve quickly. Failures are faster, but the cache is now a dependency whose loss reduces availability, a single point of failure with extra steps.

The honest default is fail-open with headroom: the cache exists to save load, so its failure should cost load, not correctness. But that default is only honest if the source can absorb the burst: a capacity question to answer before the incident, not during it.

When not to distribute

The fleet is the right answer when one cache demonstrably cannot hold the working set, when availability requires surviving a cache node’s death, or when the request rate exceeds one machine’s serve capacity. None of those is a guess; each is measurable: working set size, hit ratio at current memory, per-node request rates. A cache missing on half its lookups at 90 percent memory is out of working-set room. A cache at 20 percent memory with a 98 percent hit ratio has headroom and does not need a fleet today.

The reason to hesitate is that every property this article described (routing, tiers, hot keys, cross-node invalidation, fail-open headroom) is a cost that arrives with the fleet. Distribution is a scale answer; at the wrong scale it is pure overhead. The sequence that works: measure the single cache first, distribute when the measurements say to, and keep treating the fleet as the disposable copy part 1 demanded: bigger, but never load-bearing.

Common mistakes

• Distributing before measuring. A fleet hides hit-ratio problems that a single cache makes obvious, and adds new ones.
• Stale client ring views. Mixed client versions with different membership views disagree about placement, the same value served from two nodes. Roll client and membership changes together.
• Unjittered TTLs across the fleet. The fleet turns identical TTLs into synchronized expiry; part 3 covers the avalanche that follows.
• Replicating the cache to feel safe. Cache replication is load-spreading, not durability. Treating a replica as a source of truth converts a disposable copy into state, the one thing part 1 forbade.
• Solving hot keys with more nodes. Placement sends the hot key to exactly one of the new nodes. Measure per-key traffic first, then split, replicate, or absorb locally.

FAQ

What is distributed caching?

A cache spread across multiple cooperating nodes (each holding a share of the keys, routed to by consistent hashing) serving as one logical cache. The fleet adds memory and survives node failure; in exchange, routing, tiers, and invalidation become cross-node coordination problems.

How does invalidation work across a distributed cache?

Three ways, trading immediacy for machinery: broadcast the delete to every node and client (immediate, needs a delivery mechanism), gossip invalidations until the fleet converges (no fan-out, longer stale windows), or cap divergence with TTLs (zero machinery, bounded staleness). Most fleets use TTLs as the default and reserve fast paths for keys that cannot wait; the deliberate techniques (purges, versioned keys, write-through) are part 6 of this series.

What is a hot key in a distributed cache?

A single key receiving a disproportionate share of requests (a celebrity profile, a trending product) which placement assigns to one node no matter how large the fleet is. The counters: split the key into suffixed variants, replicate it across several nodes, or absorb it in an in-process tier. Adding nodes does not help: the key still lands on exactly one of them.

Redis or Memcached for a distributed cache?

Memcached for a pure cache with minimal operations: multi-threaded, flat string keys, no persistence or replication to manage. Redis when the cache wants data structures, pub/sub for invalidation, or managed replication and failover, with the discipline that a cache must stay flushable. The Redis-specific depth is parts 4 and 5 of this series.

What happens when a cache node dies?

Only that node’s share of keys goes cold; the requests it would have served become database reads; a burst concentrated in the moments after the failure, and an avalanche risk if a whole fleet goes cold at once. The design decision underneath is fail-open (serve from the database, slower but alive) versus fail-closed (refuse work), covered with its failure modes in part 3.

Related articles

• Next read: cache stampede and failure modes; part 3: what happens when caches expire together or go down, and how to survive it.
• caching in system design; part 1: single-cache patterns, eviction, and the hit-ratio math this fleet scales up.
• redis caching, part 4: implementing the distributed patterns with the standard tool.
• redis architecture, part 5: the data structures, persistence, Sentinel vs Cluster underneath the fleet.
• cache invalidation strategies, part 6: the deliberate techniques; purges, versioned keys; that broadcast invalidation delivers.
• consistent hashing; the placement scheme that routes every key in the fleet.