Design a Distributed Cache (like Redis) - System Design

Everyone thinks a cache is a hash map with a size cap. “Store key-value pairs in RAM, evict when it fills up, done.” Then the interviewer makes it distributed: the data no longer fits on one machine, you have twenty cache nodes, and now the hard questions arrive. Which node owns a given key, and what happens to every other key when you add node twenty-one? How do you decide what to throw out when memory is full, and does that decision cost you a lock on the hot path? When the source-of-truth database changes, how does the stale copy in the cache get corrected without a thundering herd? And when one celebrity key gets ten million reads a second, how do you stop a single node from melting?

A distributed cache is deceptive because the single-node version is genuinely easy and the distributed version is genuinely hard, and the interview is entirely about the gap. The whole design comes down to four decisions: how you place keys across nodes (consistent hashing), how you evict within a node (LRU/LFU), how you stay available when a node dies (replication), and how you keep entries fresh (invalidation) - all while a handful of hot keys try to concentrate load on single nodes.

Let me do it properly.

Functional Requirements (FR)

In scope:

• GET / SET / DELETE by key. The core key-value operations. SET key value [TTL], GET key, DELETE key. Values are opaque blobs (strings, serialized objects) up to a few MB.
• TTL / expiry. Entries can carry a time-to-live and expire automatically. This is the most common invalidation mechanism.
• Eviction under memory pressure. When a node’s memory budget is full, it must evict entries by a policy (LRU, LFU, or similar) rather than crash or reject writes.
• Horizontal scale. Data spread across N nodes so total capacity is N times one node. Adding/removing nodes rebalances a minimal fraction of keys.
• High availability. A node dying must not lose the whole keyspace it owned, and reads should keep working. Replication per shard.
• Atomic operations (bonus). INCR, SETNX (set-if-not-exists), compare-and-set - single-key atomic ops for counters, locks, and dedup.

Explicitly out of scope (say this out loud so you control the scope):

• Durability as a primary goal. A cache is not a database. We may snapshot for fast warm-up, but the source of truth lives elsewhere. Losing cache data means a cold cache and a slower backend, not lost user data.
• Rich queries. No secondary indexes, no range scans over values, no SQL. Access is by exact key. (Redis has extras like sorted sets; we treat those as an add-on, not the core.)
• Strong cross-key transactions. Multi-key ACID transactions across shards are a distributed-database problem. We offer single-key atomicity and leave cross-shard consistency to the application.
• Global multi-region strong consistency. We design a single-region cluster with async cross-region replication as an extension, not synchronous global consensus.

The one decision that drives everything: the cache sits on the read hot path of every service that uses it. A cache exists to be fast (sub-millisecond) and to absorb read load off a slower backend. So the design is dominated by “keep lookups O(1) and near-instant, spread the keyspace evenly with minimal reshuffling, and never let a single hot key or a single node failure take the whole thing down.”

Non-Functional Requirements (NFR)

• Scale: ~100M keys, ~10 TB of cached data total, spread across a cluster. Read-heavy: on the order of 1M+ ops/sec at peak, with reads outnumbering writes ~10:1 (that ratio is the entire reason a cache exists).
• Latency: p99 GET under ~1ms server-side (in-datacenter round trip a bit more). A cache that is not fast is pointless - the backend it fronts is already the slow path.
• Availability: 99.99%+. A single node failure must not lose its shard’s data outright and must not cause read errors for the keys it owned. Failover in seconds.
• Consistency: eventual and best-effort. A cache is allowed to be briefly stale or to miss - a miss just means “go ask the source of truth.” The correctness contract is weak on purpose; we optimize for speed and availability, and treat staleness as a bounded, tunable problem via TTL and invalidation.
• Durability: near zero required. The backing database is the durable store. We may keep an optional snapshot/AOF for fast restart, but we never promise the cache will not lose data on a crash. Losing the cache is survivable (cold-start, higher backend load), losing the database is not.

Back-of-the-Envelope Estimation (BoE)

Let me ground the design in numbers.

Data volume and node count:

Total cached dataset:      10 TB
Usable RAM per cache node:  64 GB (leave headroom; say ~50 GB usable for data)

Nodes just to hold the data:
  10 TB / 50 GB  = ~200 nodes

Add replication (1 replica each) -> ~400 nodes total.
Round up for headroom and hot spots -> ~500 nodes.

Object math:

Total keys:        100,000,000  (100M)
Avg value size:    10 TB / 100M = ~100 KB average
  (in reality a bimodal mix: many tiny keys + some large blobs;
   100 KB is the blended average for sizing)
Per-entry overhead: key string + metadata (TTL, LRU ptrs, freq counter)
  ≈ 60-100 bytes fixed overhead per entry regardless of value size.
100M entries * ~80 bytes overhead = ~8 GB of pure bookkeeping.

That 8 GB of metadata is not free - it is why eviction metadata design matters. A naive per-entry doubly-linked-list LRU adds two pointers (16 bytes) per key on top; at 100M keys that is another 1.6 GB just for LRU ordering. This is why production caches use approximate LRU instead of exact.

Throughput:

Peak ops:           1,000,000 ops/sec
Read:write ratio:   ~10:1
  Reads:  ~900K/sec
  Writes: ~100K/sec

Per node (500 nodes, evenly spread):
  1M / 500 = 2,000 ops/sec/node average.

Two thousand ops/sec/node is trivial - a single Redis node does 100K-200K simple ops/sec. So average load is a non-problem. The entire difficulty is in the tails: the hot key that concentrates 10M reads/sec onto the one node that owns it, and the rebalancing storm when a node joins or leaves. Averages are comfortable; skew is what breaks you.

Hot key blast radius:

One celebrity key (e.g. a viral post's cached render):
  10,000,000 reads/sec on ONE key -> ONE node.
A single node caps out around ~200K ops/sec.
10M / 200K = 50x over a single node's capacity.

That 50x overload of one node from one key is the scenario the hot-key section exists to solve. No amount of even sharding helps, because a single key lives on a single node by definition.

Bandwidth:

Reads: 900K/sec * 100 KB avg = 90 GB/sec aggregate read bandwidth.
Spread over 500 nodes = ~180 MB/sec/node. Fine on 10GbE+ NICs.
But a single hot 100 KB key at 10M reads/sec = 1 TB/sec from one node.
That alone forces replication/local-caching of hot keys.

The bandwidth math confirms the same story: aggregate is easy, the hot key is catastrophic. Size the design for skew, not for the average.

High-Level Design (HLD)

A distributed cache is a fleet of in-memory shards plus a routing layer that decides which shard owns each key. The routing can live in a smart client, in a proxy, or in the cluster itself (gossip). Here is the end-to-end picture: application clients route by consistent hashing to a ring of cache nodes, each node is a primary with one or more replicas, and a config/membership service tracks who is in the ring.

                 ┌──────────────────────────────────────┐
                 │        Application Services            │
                 │  (each embeds a smart cache client)    │
                 └───────────────────┬────────────────────┘
                                     │ key -> hash -> ring position
                                     │ pick owning node (+ replicas)
                 ┌───────────────────┼────────────────────┐
                 │                   │                    │
        ┌────────▼────────┐ ┌────────▼────────┐ ┌────────▼────────┐
        │  Cache Node A   │ │  Cache Node B   │ │  Cache Node N   │
        │  (primary)      │ │  (primary)      │ │  (primary)      │
        │  hashmap + LRU  │ │  hashmap + LRU  │ │  hashmap + LRU  │
        │  eviction meta  │ │  eviction meta  │ │  eviction meta  │
        └───┬─────────────┘ └───┬─────────────┘ └───┬─────────────┘
            │ async repl        │ async repl        │ async repl
        ┌───▼─────────────┐ ┌───▼─────────────┐ ┌───▼─────────────┐
        │ Replica A'      │ │ Replica B'      │ │ Replica N'      │
        └─────────────────┘ └─────────────────┘ └─────────────────┘

        Membership / config plane (who is in the ring):
        ┌────────────────────────────────────────────────────┐
        │  Cluster Manager (gossip OR etcd/ZooKeeper)         │
        │  - node join/leave, health, failover promotion      │
        │  - authoritative ring / slot map pushed to clients   │
        └────────────────────────────────────────────────────┘

        On a MISS, the application falls back to source of truth:
        ┌────────────────────────────────────────────────────┐
        │  Backend Database (durable source of truth)          │
        └────────────────────────────────────────────────────┘

Request flow - a GET (the read hot path):

1. The application calls cache.get(key). The smart client hashes the key and consults its local copy of the ring/slot map to find the owning node (and its replicas).
2. The client sends GET key to the owning primary. The node looks up its in-memory hash map: O(1).
3. Hit: the node bumps the key’s recency/frequency metadata (for eviction) and returns the value. Sub-millisecond, done.
4. Miss: the node returns “not found.” The application reads from the backend database, then does cache.set(key, value, ttl) to populate the cache for next time (cache-aside pattern). This is the common read-through fill.
5. If the primary is unreachable, the client fails over to a replica for reads (and the cluster manager promotes a replica to primary for writes).

Request flow - a SET (the write path):

1. The application calls cache.set(key, value, ttl). Same hashing -> owning primary.
2. The primary writes the entry into its hash map, sets expiry metadata, and (if over the memory budget) evicts one or more victims by policy.
3. The primary asynchronously replicates the write to its replica(s). For a cache we usually accept async replication (fast, eventually consistent) rather than blocking the write on replica acks.
4. Invalidation of the underlying data (when the DB row changes) is a separate flow covered in the deep dive - typically the app deletes/updates the cache key on write to the DB.

The key architectural insight: the placement function (which node owns a key) is the spine of the whole system. Get it wrong and every node addition reshuffles the entire keyspace (mass cache misses -> backend meltdown). That is why consistent hashing is the first deep dive.

Component Deep Dive

Four hard parts: (1) key placement across nodes, (2) eviction within a node, (3) replication and failover, and (4) invalidation under hot keys. I will walk each from naive to scalable.

1. Key Placement: Modulo Hashing -> Consistent Hashing -> Virtual Nodes

Approach A: Modulo hashing (the naive instinct)

Pick the node for a key with node_index = hash(key) % N, where N is the number of nodes.

def node_for(key, nodes):
    return nodes[hash(key) % len(nodes)]

Dead simple and it spreads keys evenly across nodes. Where it breaks: adding or removing a node reshuffles almost everything. The moment N changes from 20 to 21, hash(key) % 21 produces a different index than hash(key) % 20 for nearly every key. Concretely, only about 1/N of keys keep their home; roughly (N-1)/N of all keys - ~95% at N=20 - now map to a different node.

Before: hash(key)=12345, 12345 % 20 = 5   -> node 5
Add one node (N=21):
After:  12345 % 21 = 6                     -> node 6  (moved!)

For a cache, “moved” means “the new node has a miss for that key,” so ~95% of the cache is effectively cold the instant you scale out or lose a node. Every one of those misses hits the backend database at once. This is a cache-stampede-by-design: the exact moment you add capacity (often because you are overloaded) you trigger a mass miss that hammers the DB. Modulo hashing is disqualified for anything that changes membership.

Approach B: Consistent hashing (the fix)

Map both nodes and keys onto the same fixed circular hash space (say 0 to 2^32 - 1). A key is owned by the first node encountered walking clockwise from the key’s position on the ring.

Hash ring (0 .. 2^32-1), positions from hash(node_id) and hash(key):

        Node A (hash=10)
       /                \
  Node D (hash=95)     key K1 (hash=15) -> walk clockwise -> Node B
      |                     \
       \                Node B (hash=40)
        Node C (hash=70) /
              key K2 (hash=80) -> clockwise -> Node D

To find a key’s node: hash the key, then find the next node clockwise (a binary search over the sorted node positions - O(log N)). The magic is what happens on membership change: adding or removing a node only affects the keys in the arc between that node and its predecessor. Add node E between A and B, and only keys that fell in (A, E] move from B to E. Every other key stays put.

Add Node E (hash=25) between A(10) and B(40):
Only keys with hash in (10, 25] move (from B to E).
Everything else is untouched. ~1/N of keys move, not (N-1)/N.

So scaling from 20 to 21 nodes moves ~1/21 (~5%) of keys instead of ~95%. That single property - minimal reshuffling - is why consistent hashing is the standard placement scheme for distributed caches. The blast radius of a node change is one arc, not the whole ring.

Approach C: Virtual nodes (the production refinement)

Plain consistent hashing has two problems. First, uneven load: with only 20 points on the ring, the arcs between them are wildly unequal by luck, so some nodes own huge arcs (and lots of keys) while others own slivers. Second, uneven failure redistribution: when a node dies, its entire arc dumps onto the single next node clockwise, doubling that one node’s load instead of spreading the pain.

The fix is virtual nodes (vnodes): each physical node is placed on the ring many times (say 100-200 positions) using hash(node_id + ":" + i) for i in 0..V.

Physical Node A -> A#0, A#1, ..., A#150  (150 points on the ring)
Physical Node B -> B#0, B#1, ..., B#150
... each physical node scattered across ~150 ring positions.

Now each physical node owns 150 small arcs scattered around the ring instead of one big arc. Two wins:

• Even load. With 150 points per node, the law of large numbers smooths arc sizes - every physical node ends up owning roughly the same total fraction of the keyspace. Variance drops sharply as V grows.
• Even failure spreading. When physical node A dies, each of its 150 arcs is inherited by whatever different physical node is next clockwise from that arc. A’s load is redistributed across ~150 other nodes, not dumped on one. No single node doubles.

You can also weight nodes by giving beefier machines more vnodes, so heterogeneous hardware gets proportional load. The cost is a larger ring structure (150 * num_nodes entries) and slightly more memory in the client/router, which is negligible. Virtual nodes are the answer: consistent hashing for minimal reshuffling, vnodes for even distribution and even failure recovery.

Where does the ring live? Three options: (a) client-side - every smart client holds the ring and routes directly (one network hop, but every client must learn membership changes; this is the Memcached/Redis-cluster-client model); (b) proxy - a routing tier (like twemproxy) holds the ring and clients are dumb (extra hop, simpler clients); (c) server-side gossip - nodes know the full map and redirect misrouted requests (Redis Cluster’s MOVED/ASK redirection). The membership itself is tracked by a coordination service (etcd/ZooKeeper) or gossip so all parties converge on the same ring.

2. Eviction: When Memory Fills, What Do You Throw Out?

A cache node has a hard memory budget. When a write would exceed it, the node must evict existing entries. The policy decides hit rate, and the implementation decides whether eviction costs you latency on the hot path.

Approach A: Exact LRU with a doubly-linked list (the textbook answer)

Least Recently Used: evict the entry that has not been accessed for the longest time. The classic implementation is a hash map (key -> node) plus a doubly-linked list ordered by recency. On every access you unlink the node and move it to the head; the tail is the eviction victim.

HashMap: key -> list_node
List (MRU) head <-> n1 <-> n2 <-> ... <-> nK <-> tail (LRU, evict here)

GET key:  O(1) map lookup, then unlink node + move to head.
SET key:  insert at head; if over budget, drop the tail node.

O(1) per operation, exact recency ordering. Where it breaks at scale: memory overhead and lock contention. Two pointers per entry (prev/next) is 16 bytes on top of every key - at 100M keys that is 1.6 GB of pure pointers (the BoE flagged this). Worse, every read is now a write to the linked list (you mutate the list to move the node to the head), so a read-heavy cache is constantly rewriting its ordering structure. In a multi-threaded node that list is shared mutable state, so it needs a lock, and now your 900K reads/sec are all contending on one eviction lock. Exact LRU turns a lock-free read path into a serialized one.

Approach B: Approximate LRU (sampling - what Redis actually does)

You do not need a perfectly-ordered list to evict a reasonable victim - you need to evict something old, not necessarily the single oldest. So drop the linked list. Store just a last-access timestamp (a few bytes) in each entry’s metadata. When you need to evict, sample K random keys (Redis default is ~5), and evict the one with the oldest timestamp among the sample.

On eviction:
  sample = pick_random(keys, K=5)
  victim = min(sample, key=lambda e: e.last_access_ts)
  evict(victim)

Why this is better in practice:

• No per-entry pointers. Just a timestamp field, so far less metadata memory.
• Reads stay cheap. A GET only updates a timestamp field in place - no shared list to relink, so no eviction lock on the read path.
• Good enough accuracy. Sampling 5 keys reliably picks a near-oldest victim; bumping K to 10 gets you very close to exact LRU. You trade a tiny bit of eviction precision for a huge drop in memory and contention. Redis maintains a small pool of best candidates across samples to improve quality further.

Approach C: LFU when recency lies (frequency, with decay)

LRU has a known failure mode: a one-time bulk scan (a batch job reading millions of keys once) parades fresh-but-useless keys to the front and evicts your genuinely hot working set. Recency is fooled by a scan. LFU (Least Frequently Used) evicts by access count instead: a key read 10,000 times survives; a key read once during a scan is evicted first.

The naive LFU counter has two problems: (1) an exact per-key counter is more metadata, and (2) it never forgets - a key that was wildly popular last week but is now dead keeps its high count and refuses to be evicted (cache pollution by stale-popular keys). The fix is what Redis LFU does:

• Probabilistic counter (a small ~8-bit counter that increments with decreasing probability as it grows, so it approximates a logarithmic access count in one byte).
• Time decay: the counter is halved/decremented over time so that old popularity fades and a once-hot-now-cold key becomes evictable again.

Access count stored as ~8-bit log-ish counter (Morris counter style).
Increment probability shrinks as counter rises (saturates ~ log scale).
Decay: periodically reduce counters so stale-popular keys age out.
Evict: sample K keys, drop the lowest (frequency, then recency) victim.

Decision summary:

The answer: approximate (sampling) LRU as the general default because it is cheap and lock-light, and LFU with decay when the workload has scan traffic or a stable hot set that recency would wrongly evict. Offer both as a per-key or per-node policy (Redis exposes exactly this via maxmemory-policy: allkeys-lru, allkeys-lfu, volatile-* variants that only evict keys with a TTL, etc.).

Expiry vs eviction are different mechanisms and both exist: expiry removes keys whose TTL has passed (via lazy checks on access plus a background sampling sweep), while eviction removes live keys because you are out of memory. A volatile-lru policy only evicts keys that have a TTL, protecting keys you marked as must-keep.

3. Replication and Failover: Surviving a Dead Node

A single node owning a shard is a single point of failure - lose it and every key in its arcs is gone (cold misses that stampede the DB) and its writes error out. Replication fixes availability.

Naive: no replication, rely on the ring

“If a node dies, consistent hashing just routes its keys to the next node clockwise, which will refill from the DB.” Where it breaks: the next node has none of the dead node’s keys, so every request for those keys is a miss that goes to the backend - simultaneously, for the whole failed shard. That is a correlated cache-miss flood exactly when you are already down a node. You need the data to survive the node, not just the routing.

Better: primary-replica per shard, async replication

Each primary has one or more replicas that hold a copy of its data. The primary streams writes to replicas.

Write to Primary A:
  1. apply to A's memory
  2. stream the op (or the value) to Replica A' asynchronously
  3. ack the client immediately (do NOT wait for A')

If A dies: promote A' to primary; clients re-route to A'.
Reads can be served from replicas to spread read load.

The core trade-off is sync vs async replication:

• Async (default for caches). The primary acks the client before the replica confirms. Fast (no extra round trip on the write path), but a primary can die after acking a write and before the replica received it - that write is lost. For a cache this is usually acceptable: the source of truth is the DB, so a lost cached write just becomes a future miss. This is the Redis default (asynchronous replication).
• Sync / semi-sync. The primary waits for at least one replica to ack before acking the client. No acknowledged write is lost on single-node failure, at the cost of a round trip of latency on every write. Use only when the cache holds data you cannot cheaply recompute.

Consistency consequence: async replication means a read served by a replica can be stale (it has not yet received the latest write to the primary). This is the classic read-your-writes hazard: write to primary, immediately read from a replica, see old data. Mitigations: route reads that need freshness to the primary, or accept bounded staleness (fine for most cache use). This is a direct instance of the CAP trade-off - during a partition we choose availability (serve possibly-stale reads) over consistency, which is the right call for a cache.

Failover mechanics. A cluster manager (Redis Sentinel, or a Raft/ZAB-based coordinator like etcd/ZooKeeper, or gossip-based cluster consensus) health-checks nodes. On a primary failure it: (1) detects via missed heartbeats with a quorum agreeing (to avoid one flaky observer triggering failover), (2) promotes the most up-to-date replica to primary, (3) updates the ring/slot map, (4) pushes the new map to clients (or clients discover it via MOVED redirects). The dangerous case is split-brain: a network partition where the old primary is alive but isolated and a replica gets promoted, giving two primaries accepting writes. Guard with quorum-based promotion (a majority must agree the old primary is dead) and fencing (the demoted old primary must stop accepting writes when it rejoins).

4. Cache Invalidation Under Hot Keys (the core hard part)

“There are only two hard things in computer science: cache invalidation and naming things.” Invalidation is keeping the cached copy consistent with the source of truth when the source changes, and hot keys make every invalidation strategy dangerous.

The write strategies (how the cache and DB stay in sync)

• Cache-aside is the default and most common. On read, check cache; on miss, load from DB and populate. On write, write the DB and then invalidate (delete) the cache key so the next read reloads fresh. Deleting rather than updating avoids caching a value that a concurrent write is about to change.
• Write-through keeps the cache always consistent by writing both stores on every write, but pays two writes inline and caches data that may never be read.
• Write-back is fastest for write-heavy workloads (batch and coalesce writes to the DB) but risks losing writes if the node dies before flushing - only acceptable when some loss is tolerable.

The cache-aside race worth naming in an interview: reader A gets a miss and reads value v1 from the DB; meanwhile writer B updates the DB to v2 and deletes the (empty) cache key; then reader A writes its now-stale v1 into the cache. The cache is left holding v1 forever (until TTL). Fixes: put a short TTL on entries so any stale value self-heals within the TTL window; or use versioning / CAS on the fill (only populate if the version matches); or delete-after-write with a small delay (delayed double delete). TTL is the cheap, robust backstop: even if invalidation logic has a bug, staleness is bounded by the TTL.

The hot key problem and why it breaks invalidation

Now overlay a hot key (one viral post, one trending product) taking millions of reads/sec. Two failure modes:

(a) Hot-key node overload. All those reads hit the single node owning that key (BoE: 50x a node’s capacity). Consistent hashing cannot help - one key, one node. Fixes:

• Client-side / local caching of hot keys. Each application server keeps a tiny in-process cache (with a short TTL, a few seconds) for the hottest keys, so the vast majority of reads never leave the app server. This is the single most effective hot-key fix: it turns 10M reads/sec at one cache node into a handful of reads per app server per TTL window. The cost is a bit more staleness (bounded by the local TTL) and the need to invalidate local copies (or just let the short TTL expire them).
• Read replicas for the hot shard. Add replicas of the node owning the hot key and fan reads across them. Multiplies read capacity by the replica count.
• Key splitting (hot key sharding). Store the hot value under K suffixed keys hotkey#0..hotkey#K-1, each landing on a different node via the ring; readers pick a random suffix. One logical key becomes K physical copies spread across K nodes, so its read load divides by K. Cost: K copies to invalidate on write, and K times the memory for that value.

(b) Thundering herd / cache stampede on invalidation or expiry. The instant a hot key is invalidated or its TTL expires, thousands of concurrent readers all miss simultaneously and all stampede the backend to recompute the same value at once - potentially knocking over the DB. This is the most dangerous hot-key scenario because it converts a routine expiry into a backend outage. Fixes:

• Request coalescing (single-flight). When many readers miss the same key at once, let exactly one of them fetch from the DB and recompute; the rest wait for that single result. This caps backend load for a hot key at one concurrent recompute regardless of read volume.
• Lock / lease on recompute. The first misser acquires a short lock (SETNX a mutex key) and recomputes; others briefly serve the stale value or wait-and-retry. Only one DB read happens.
• Probabilistic early recompute. Recompute a hot key before it expires, with a probability that rises as expiry approaches (XFetch algorithm), so one lucky reader refreshes it early and the herd never all misses at the same instant.
• Never-expire + async refresh for the hottest keys. Do not TTL the hottest keys at all; instead refresh them in the background on a schedule so a read never triggers a synchronous recompute. Reads always hit; freshness comes from the background job.
• Cache the miss (negative caching). For keys that legitimately do not exist (to stop repeated backend lookups for absent data - a cache-penetration attack), cache a short-lived “not found” marker so a flood of requests for a nonexistent key does not all fall through to the DB.

The honest interview framing: invalidation is a consistency-vs-load trade, and hot keys sharpen it. TTL bounds staleness cheaply but creates synchronized expiry; delete-on-write is fresher but races; and any expiry on a hot key must be paired with coalescing or early-refresh or it becomes a stampede. State the layered answer: short TTL as the backstop, delete-on-write for freshness, local hot-key caching to shed read load, and single-flight recompute to cap backend load on a miss.

API Design & Data Schema

Client API (the data plane)

The cache exposes a small, exact-key command set, not REST. Over a binary protocol (RESP for Redis) for speed:

GET   key                         -> value | NIL
SET   key value [EX seconds]      -> OK            # optional TTL
SETNX key value [EX seconds]      -> 1 if set, 0 if key existed   # set-if-absent
DEL   key                         -> 1 if deleted, 0 if absent
EXPIRE key seconds                -> 1 | 0
TTL   key                         -> remaining seconds | -1 (no ttl) | -2 (absent)
INCR  key                         -> new integer value            # atomic counter
CAS   key old_value new_value     -> OK | MISMATCH                # compare-and-set
MGET  key1 key2 ...               -> [values]      # batch (careful: cross-shard)

Notes: MGET across shards must be scattered by the client to each owning node and gathered - the client library handles the fan-out. INCR, SETNX, and CAS are single-key atomic ops (the node is single-threaded per key, or uses a per-key lock), which is what makes the cache usable for counters, distributed locks, and dedup.

Admin / control-plane API (managing the cluster)

POST   /admin/v1/nodes            # add a node -> triggers ring rebalance of ~1/N keys
       { "node_id": "cache-207", "addr": "10.0.4.7:6379", "vnodes": 150, "weight": 1 }

DELETE /admin/v1/nodes/{node_id}  # drain + remove; its arcs reassigned clockwise

GET    /admin/v1/ring             # current ring / slot map (nodes, vnode positions)

PUT    /admin/v1/policy/{node}    # eviction & memory config
       { "maxmemory_bytes": 53687091200, "policy": "allkeys-lfu", "sample_k": 10 }

The ring/membership is the authoritative cluster state, stored in the coordination service and versioned so clients can detect staleness and refetch.

Data model: in-memory KV, not SQL

The stored unit is key -> value + metadata. Access is always by exact key at extreme rate with no joins, no range scans, and no durability requirement. That is the textbook profile for an in-memory key-value store, not a relational database. SQL is the wrong tool here: disk-backed durable transactions add exactly the latency a cache exists to avoid, and a relational engine cannot serve O(1) keyed lookups at a million ops/sec from RAM the way a hash table can. We deliberately keep it in memory and non-durable.

Per-entry structure (in RAM, per node):

Entry {
  key            string        # the lookup key (also hashed for placement)
  value          bytes         # opaque blob, up to a few MB
  expire_at      int64|null    # absolute expiry epoch ms; null = no TTL
  last_access    int32         # for approx-LRU (seconds resolution ok)
  freq_counter   uint8         # for LFU (log-ish, decayed)
  flags/size     small ints    # type flags, encoded size
}

Primary index:  open-addressing / chained hash table  key -> Entry   (O(1))
Eviction meta:  the last_access / freq_counter fields, sampled on evict
Expiry:         lazy check on access + background sampling sweep

Cluster metadata (in the coordination service, e.g. etcd/ZooKeeper):

node_id        STRING PK
addr           STRING        # host:port
vnode_count    INT           # ring points for this node
weight         FLOAT         # load weight (more vnodes for bigger boxes)
role           ENUM          # primary | replica
replica_of     STRING|null   # primary node_id if this is a replica
state          ENUM          # joining | active | draining | down
ring_version   INT           # bumped on every membership change

This metadata is tiny, read-heavy, and must be strongly consistent (every client must agree on the ring, or two clients route the same key to different nodes). So the cluster map lives in a strongly-consistent coordination store even though the cached data is eventually-consistent. Two different consistency needs, two different stores - a deliberate split.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Hot key overloading a single node (breaks first). One celebrity key concentrates millions of reads/sec on the one node that owns it (BoE: 50x a node’s capacity). Even sharding cannot help - one key lives on one node. Fix: local (client-side) caching of hot keys with a short TTL is the biggest lever (most reads never leave the app server), plus read replicas for the hot shard and key splitting (hotkey#0..K across K nodes) for the extreme cases. This is the single most important scaling move for a cache because skew, not average load, is what melts it.

2. Cache stampede on hot-key expiry/invalidation. When a hot key expires or is invalidated, thousands of readers miss at once and stampede the backend to recompute the same value, potentially taking down the DB. Fix: single-flight / request coalescing (one recompute per key regardless of read volume), probabilistic early recompute (refresh before expiry so the herd never synchronizes), and background refresh / never-expire for the very hottest keys. Add negative caching to stop floods for nonexistent keys.

3. Rebalancing storm on node join/leave. With modulo hashing this reshuffles ~95% of keys (mass miss -> DB meltdown). Fix: consistent hashing with virtual nodes so a membership change moves only ~1/N of keys and spreads the moved load across many nodes. Warm new nodes gradually (rate-limit backfill) so the small set of moved keys does not stampede the DB either.

4. Uneven load / hot shard. Some nodes own bigger arcs or hotter key ranges than others. Fix: vnodes (150+ per node) smooth arc sizes via the law of large numbers, and weighting gives bigger machines proportionally more vnodes. Monitor per-node op rate and re-weight or split hot arcs.

5. Single node failure losing a shard. A dead primary erases its keyspace (correlated misses) and blocks its writes. Fix: primary + replica per shard with async replication and quorum-based failover (Sentinel/etcd/gossip) that promotes the most up-to-date replica in seconds. Guard split-brain with quorum promotion and fencing of the demoted primary.

6. Eviction lock contention on the read path. Exact LRU makes every read mutate a shared linked list under a lock, serializing a read-heavy workload. Fix: approximate (sampling) LRU - store a timestamp per entry and sample K keys at eviction time, so reads only update a field in place with no shared-list lock. Use LFU with decay when scans or stable hot sets fool recency.

7. Metadata memory overhead. At 100M keys, per-entry pointers/counters add gigabytes (LRU pointers alone ~1.6 GB). Fix: drop linked-list pointers (approx LRU needs only a timestamp), use a 1-byte probabilistic LFU counter, and set TTLs so idle keys self-evict. Encode small values inline to cut per-object allocator overhead.

8. Replica staleness / read-your-writes. Async replication means a replica read can return a value older than a just-committed write to the primary. Fix: route freshness-critical reads to the primary, accept bounded staleness elsewhere (correct for a cache), and keep replication lag monitored. This is the CAP choice made explicit: availability over strict consistency, with TTL bounding how wrong a stale entry can be.

Wrap-Up

The trade-offs that define this design:

• Consistent hashing with virtual nodes over modulo hashing. We give up the trivial simplicity of hash % N because it reshuffles ~95% of keys on any membership change (a built-in cache stampede). Consistent hashing moves only ~1/N of keys, and vnodes make the distribution even and spread failover load across the whole cluster instead of dumping it on one neighbor.
• Approximate LRU / LFU-with-decay over exact LRU. We give up perfect recency ordering to kill the two costs that matter at 100M keys: the per-entry pointer memory and the shared-list lock that would serialize a read-heavy workload. Sampling picks a near-oldest victim cheaply; LFU with decay wins when scans or stable hot sets would fool recency.
• Async replication over synchronous. We accept that a just-acked write can be lost on a primary crash and that replica reads can be briefly stale, in exchange for fast writes and available reads. This is safe precisely because a cache is not the source of truth - a lost or stale cache entry becomes a future miss, not lost data. TTL bounds the staleness.
• Layered invalidation over any single strategy. Short TTL as the always-on backstop (bounds staleness even if logic is buggy), delete-on-write for freshness, local hot-key caching to shed read load, and single-flight recompute to cap backend load on a miss. No one mechanism is enough; hot keys force all four.
• Two consistency models, two stores. The cached data is eventually consistent and in-memory (optimized for speed); the cluster ring/membership is strongly consistent in a coordination service (every client must agree on placement). Mixing these up is a classic design error.

One-line summary: a fleet of in-memory shards placed by consistent hashing with virtual nodes, each a primary with async replicas and approximate-LRU/LFU eviction, kept fresh by TTL plus delete-on-write, and defended against hot keys with client-side caching, read replicas, key splitting, and single-flight recompute - trading strict consistency and durability for sub-millisecond reads that survive node failures and traffic skew.