Distributed Cache

Intermediate

Overview

A distributed cache is an in-memory key-value store spread across multiple nodes, designed to serve hot data with sub-millisecond latency and shield backend databases from read load. Think Redis or Memcached deployed as a cluster. The design challenge is keeping data distributed evenly, handling node failures gracefully, and managing cache consistency at scale.

High-level architecture for Distributed Cache

Functional Requirements

Store and retrieve key-value pairs with sub-millisecond latency.
Support TTL (time-to-live) per key for automatic expiration.
Distribute data across multiple nodes for capacity and throughput beyond a single machine.
Support cache eviction when memory is full (LRU, LFU, or configurable policy).
Provide atomic operations (get, set, delete, increment).

Non-Functional Requirements

Low latency: p99 read/write under 1 ms within the same datacenter.
High throughput: hundreds of thousands to millions of operations per second across the cluster.
High availability: the cache should survive individual node failures without full data loss.
Scalability: add nodes to grow capacity and throughput linearly.
Consistency: eventual consistency is acceptable - the source of truth is the backing database.

Capacity Estimation

Assume 500K QPS across the cluster, 1 KB average value size, and 50 GB total hot dataset.

Cluster size: if each node holds ~8 GB in memory and serves ~100K QPS, you need ~7 nodes for capacity and ~5 nodes for throughput -> provision 7 nodes (capacity is the bottleneck).
Bandwidth: 500K/s x 1 KB = 500 MB/s of cache traffic, split across nodes.
Memory per node: 50 GB / 7 ~ ~8 GB per node, leaving headroom for overhead.
Network: at 500 MB/s total, each node handles ~70 MB/s — well within a 1 Gbps NIC.

High-Level Architecture

The system consists of a cluster of memory-optimized cache nodes and a central configuration service (like ZooKeeper or etcd) that maintains the cluster topology. Application clients embed a smart library that hashes keys to determine which physical node owns the data, routing requests directly to the correct node without an intermediate proxy hop.

Data Model

Entity	Fields / Schema	Storage Choice
cache_entry	key (hash), value (bytes), ttl, created_at, last_accessed	In-memory hash table per node
node_metadata	node_id, hash_range, status, last_heartbeat	Configuration store / service registry

Detailed Design

Data Distribution: Consistent Hashing

The cache client library uses consistent hashing with virtual nodes to map each key to a cache node. Each physical node is placed at multiple points on the hash ring (virtual nodes) to ensure even distribution. When a node is added or removed, only a small fraction of keys are remapped.

Client-Side Routing

The cache client maintains the ring topology and routes each request directly to the correct node — no central proxy on the data path. This eliminates a network hop and a single point of failure. The topology is fetched from a configuration service and updated on node membership changes.

Eviction Policy

When a node's memory is full, it evicts entries based on the configured policy. LRU (Least Recently Used) is the default. Redis uses an approximated LRU (sampling a subset of keys) to avoid the overhead of maintaining a full access-ordered list.

Handling Node Failures

Accept the miss (Memcached approach): When a node dies, its keys are temporarily unavailable. Requests miss the cache and fall through to the database. Simple, but causes a burst of database load.
Replicate hot data (Redis Cluster approach): Each key is stored on the primary node and replica nodes. If the primary fails, the client reads from the replica, avoiding stampedes.

Cache Stampede Mitigation

When a popular key expires, hundreds of requests simultaneously hit the database. Mitigations include Locking/Request Coalescing (the first miss acquires a lock while others wait), and Probabilistic Early Expiration (clients randomly refresh the key slightly before its TTL expires).

Bottlenecks & Solutions

The primary bottleneck is hot keys (e.g., a celebrity's profile). Consistent hashing maps a single key to a single node, so if that key gets 100,000 QPS, that specific node will melt down while the rest of the cluster sits idle. To fix this, you must identify hot keys and cache them locally in the application memory (L1 cache), or salt the key to spread copies of it across multiple cache nodes.

Interview Follow-up Questions

Q: How do you keep the cache consistent with the database?

The Cache-Aside pattern is standard: the application writes to the DB, then deletes the cache key. A TTL acts as a fallback to clear stale data eventually. Write-Through guarantees consistency but adds latency. For strict consistency, CDC (Change Data Capture) tools like Debezium can tail the DB transaction log and update the cache asynchronously.

Q: What happens during a network partition if you use replication?

A distributed cache usually favors Availability over Consistency (AP in CAP theorem). During a partition, split-brain might occur where clients write to old masters. We tolerate this because the cache is not the source of truth; stale reads are acceptable and will be overwritten or expired.