Distributed Cache Design

A single cache node is limited by its memory, network bandwidth, and availability. A distributed cache spreads entries over multiple nodes so capacity and throughput scale horizontally and one node failure affects only part of the data. Designing one means deciding how keys map to nodes, what happens when nodes fail, how clients find the right node, and how the cache stays consistent with the source of truth.

Partitioning

Each key must map to exactly one owner node (or one owner among replicas).

Modulo hashing is unsuitable when the node count changes, because a resize turns almost every read into a miss and sends a full load to the database. For example, going from 10 to 11 nodes leaves a key on the same node only when hash mod 10 == hash mod 11, which holds for about 1 in 11 keys, so about 91% of keys change owner. With consistent hashing, adding the 11th node moves about 1/11 of the keys, all of them to the new node. Use consistent hashing, with virtual nodes to even out load, or a fixed slot table as Redis Cluster does. See Redis and Memcached.

Replication and availability

If a node fails without replication, its keys are lost from the cache and every request for them reaches the database. Options:

• No replication. Simplest and cheapest. Acceptable when the database can absorb the misses from one node's share, and the cache warms quickly.
• Primary-replica per shard. A replica takes over on failure and can serve reads. Asynchronous replication means the replica may lag, which is acceptable for a cache.
• Replicating hot keys only to spread read load. See cache invalidation, stampede, and hot keys.
• Replica pools across zones, so a zone failure leaves a warm copy.

A cache node failure changes the load on the database. Example with 10 nodes, evenly distributed keys, 100,000 reads/s, and a 95% hit ratio: the database normally receives 5,000 reads/s. If one node fails without replication, its 10,000 reads/s all miss until the keys are reloaded on the nodes that now own them, and the remaining 90,000 reads/s still miss at 5% (4,500/s). The database receives about 14,500 reads/s, roughly 2.9 times the normal load. Plan the database capacity for the miss rate that occurs after losing a node, or protect it with rate limiting and load shedding.

Routing: who finds the node

graph TD
    subgraph client_side["Client-side routing"]
        A1["App + cache client library"] --> N1["Cache node 1"]
        A1 --> N2["Cache node 2"]
        A1 --> N3["Cache node 3"]
    end
    subgraph proxy_side["Proxy routing"]
        A2["App"] --> P["Cache proxy"]
        P --> M1["Cache node 1"]
        P --> M2["Cache node 2"]
        P --> M3["Cache node 3"]
    end

A third form is server-side redirection, where any node accepts a request and answers with a redirect to the owner (Redis Cluster MOVED). Clients cache the topology to avoid the extra hop.

Consistency with the database

A cache is a copy, so it can diverge from the database. Choose a policy based on the tolerated staleness.

• Cache-aside with TTL gives eventual consistency, with staleness bounded by the TTL. See caching fundamentals and strategies.
• Delete on write shortens staleness. A race between a concurrent reader and writer can still leave a stale entry until the TTL.
• Change-data-capture invalidation. The database log is streamed, and a consumer deletes or updates cache keys for each changed row. This removes invalidation logic from application code and is not skipped when a code path forgets it. Delivery is at-least-once, which is safe since deletes are idempotent.
• Versioned values. Store a version (or timestamp) with the value and only overwrite with a newer version, so late writes cannot overwrite newer data.
• Strong consistency through the cache is rarely practical; reads that must be strongly consistent should go to the database (or the leader).

Cross-region caches add replication delay. Typically each region has its own cache, and invalidations are propagated by a message stream or by regional database replication.

Multi-tier caches

graph LR
    R["Request"] --> L1["L1: in-process cache"]
    L1 -->|miss| L2["L2: distributed cache"]
    L2 -->|miss| DB["Database"]
    DB -->|fill| L2
    L2 -->|fill| L1

• L1 is inside each application process: no network, smallest capacity, entries differ per instance, and invalidation must reach all instances.
• L2 is the shared distributed cache: larger, one consistent copy for all instances.
• Multi-tier designs reduce load and latency on the distributed cache, especially for hot keys. The cost is additional staleness: an L1 entry can outlive an L2 invalidation. Use short L1 TTLs (seconds), or broadcast invalidations (for example over pub/sub) to instances.

CDNs and browser caches form further tiers in front of these. See content delivery networks.

Other design considerations

• Serialization. Choose a compact, versioned format (Protobuf, MessagePack). Old and new application versions share the cache during deployments, so a format change must be backward compatible or use versioned keys.
• Key design. Namespaces and versions in keys (app:v3:user:42) allow bulk invalidation by changing the version, and prevent collisions.
• Value size. Large values consume bandwidth and block single-threaded servers. Compress or split them.
• Eviction and memory. Set a memory limit and an eviction policy. See cache eviction policies.
• Warm-up. Preload popular keys before a new node takes traffic.
• Observability. Track hit ratio, evictions, latency percentiles, per-node memory, and hottest keys.
• Failure of the whole cache. Use timeouts and circuit breakers on cache calls so a slow cache does not slow the service, and fall back to the database within its capacity.

Interview questions

• Why is hash(key) mod N a poor partitioning scheme for a cache? Changing N changes the owner of most keys, causing a near-total miss storm on the database. Consistent hashing or fixed slots limit movement to roughly 1/N of the keys.
• When should a proxy be preferred over client-side routing? When many clients in different languages would otherwise each implement routing and hold connections to every node. A proxy centralizes topology and pools connections, at the cost of an extra hop and a component to operate.
• How can a distributed cache be kept consistent with the database? Use TTLs as a bound, delete keys on write, and optionally stream database changes to invalidate keys. Version values so a late write cannot replace a newer one.
• What is the trade-off of adding an in-process L1 cache? It removes network latency and offloads hot keys, but each instance holds separate copies that can be stale longer than the shared L2 cache.