Cruxly › System design › Scaling Building Blocks

Cache Eviction and Topology

which key to evict, and which machine owns it

The previous lesson covered when to cache and how fresh it should be. This one covers the two questions that come right after: when the cache is full, what gets thrown away — and once the cache is bigger than one machine, which machine holds which key.

Eviction is a bet on the next request

A cache is finite, so something has to leave when it fills. Every eviction policy is a bet on which key you're least likely to need next.

Policy	Evicts	How it fails
LRU (least recently used), the default: traffic clusters in time	The key untouched longest	Can't tell "read a minute ago, likely again" from "read once, never again". A one-time scan makes every scanned key most recently used and evicts the whole hot working set
LFU (least frequently used)	The key with the fewest accesses ever	Scan-proof: a one-time read gets a count of 1, never enough to displace a key read thousands of times. But a key hot last week keeps its count and never leaves, unless counts decay
ARC / window-TinyLFU	Weighs recency and frequency, shifting to whichever predicted hits better recently	More bookkeeping. What Caffeine and some Redis-adjacent designs actually run

LRU's implementation (hash map + doubly linked list) is in the LRU cache exercise in this track. In an interview, "adaptive between LRU and LFU, weighted by recent hit-rate evidence" beats defending one side as permanent.

:::warn "I'd use LRU" alone is not a complete answer Name the access pattern, then the policy, then the failure you accept: "Recency-clustered traffic with occasional batch scans, so plain LRU risks the scan problem. I'd use window-TinyLFU, or send scan traffic to a separate, smaller cache so it can't evict the real working set." :::

If asked "what about FIFO?", place each in one sentence. Ruling one out correctly is itself a signal.

Policy	Evicts	Verdict
FIFO	The oldest insert	Arrival order, not access order: drops hot data as readily as cold. A queue policy, not a cache policy
LIFO / FILO	The newest insert	Worse: evicts what you were most likely to read next
MRU (most recently used)	Whatever was just touched	Correct only for a known one-pass scan (a database reading a large table once through a small buffer), where "just touched" means "cold forever". A narrow exception
Random	A random key	No bet, so no access pattern can be crafted to defeat it. Cheap: Redis's approximated LRU samples a few keys instead of tracking exact recency

One machine is not enough: partitioning the cache itself

Once the working set outgrows one machine's memory, or the request rate outgrows its throughput, the cache itself must be partitioned across nodes.

:::key Same mechanism as database sharding, different stakes Both use consistent hashing. But a cache miss is cheap (fall through to the database); a database read on the wrong shard is a correctness bug. :::

Two separate decisions, not alternatives:

The mapping (key → node): plain % N (avoid), a consistent-hashing ring, rendezvous hashing, or fixed hash slots (Redis Cluster: 16,384 slots, each owned by one node; rebalancing moves whole slots).
Where the mapping runs:

Where it runs	Latency	The cost
Smart client (e.g., Redis Cluster clients)	No extra hop: the client caches the slot map and talks straight to the owner	Every client library must get it right; during resharding the server replies `MOVED`/`ASK` and the client updates its map
Proxy layer (Twemproxy, Envoy)	One more hop	No service reimplements the mapping, but the proxy is another tier to scale and operate

:::warn Plain % N remap on node-count change is a full cache flush Changing N changes key % N for nearly every key. Add the cold-cache problem from the previous lesson and "add a cache node" can briefly take your database down. Consistent hashing remaps only about 1/N of keys. :::

Replicate the cache tier? The data is disposable (the database holds the real copy), so no durability story is needed. Availability is the question: if the database was sized assuming the cache absorbs most reads, losing one node sends its share, often the hottest keys, straight to the database.

Your case	Do this
The database can absorb one cache node's miss traffic	Skip replication; accept losing a node
It can't (the cache is load-bearing)	Cache replicas, or a gutter pool (Facebook): a few spare cache servers take over a failed node's keys with short TTLs, so its traffic doesn't land on the database

Redis or Memcached: choosing the shared tier

Everything above assumes a shared tier exists. Two engines fill it, and "which one" is a question about what you will ask of the tier besides GET and SET. (The partitioning mechanics are in Distributed Cache Cluster; this section is about the engines underneath.)

Dimension	Memcached	Redis
Model	Strings under a key, nothing else	Strings plus lists, sets, sorted sets, hashes, bitmaps and more, with server-side commands on each
Threads	Multithreaded: each worker thread runs its own event loop, so one big node uses many cores	Commands run mostly on one thread. Optional I/O threads (`io-threads`, off by default, reworked in Redis 8) take over socket reads and writes, but the docs still advise several instances to use several cores
Durability	None by default. A restart is an empty cache	Optional RDB snapshots and an append-only file
Replication	None built in; servers do not talk to each other	Asynchronous primary-replica copies
Sharding	Client-side hashing across independent servers	Redis Cluster, or client-side as well
Memory	Slab classes: fixed-size chunks per class, one LRU per class	Per-key overhead grows with richer types; eviction is sampled

What the data structures buy. A sorted set holds a leaderboard that is updated and ranked inside the server; with a plain key/value tier you would read the whole blob, change it and write it back, racing every other writer. That is the real argument for Redis: logic that must be atomic and server-side. If every value is an opaque serialized object that you fetch and replace whole, the richer types buy nothing.

What durability and replication change. A cache tier is disposable, so for pure caching their main use is a smaller stampede after a restart: a Redis node that reloads its snapshot comes back warm; a Memcached node comes back empty and sends its whole share to the database. Do not over-read them. Redis replication is asynchronous, and WAIT makes a write more likely to survive but does not make Redis a strongly consistent store. Redis Cluster can lose acknowledged writes in a partition. A tier you treat as a source of truth needs a design for that, not a flag.

Eviction in practice. Memcached evicts by LRU inside each slab class, so a workload whose item sizes shift can starve one class while another sits idle; Facebook wrote an adaptive allocator that moves slabs to the class that is evicting recently used items. Redis lets you pick the policy and approximates LRU by sampling a few keys. With noeviction it refuses writes when full: correct for a datastore, wrong for a cache. Policies, slots and hash tags (multi-key operations need keys in one slot, and a hot tag is a hot node) are covered in Redis in depth: cluster slots, eviction, persistence and the lock debate.

A choice rule.

Why teams still pick Memcached at scale. Facebook's Memcache deployment is the reference: a demand-filled look-aside cache where writers delete the key rather than update it, with the engine kept simple and the intelligence moved into a client library and a proxy (mcrouter). Their leases are the engine-level answer to stale sets and herds: a miss hands one client a token to refill the key, issued at most once per 10 seconds per key, and the others wait briefly. For one set of herd-prone keys, peak database load fell from 17K to 1.3K queries per second. That design is possible because the engine is simple; it is not an argument that the simple engine is always right.

:::key Verified November 2026

Redis eviction: allkeys-lru, allkeys-lfu (LFU since 4.0), allkeys-random, volatile-ttl, noeviction; maxmemory-samples is 5 in the documented example. A least-recently-modified policy (allkeys-lrm) arrived in Redis 8.6.
Redis threading: the Redis docs call it "mostly" single-threaded for command execution, with modern versions using threads for other work; Redis 8 reworked I/O threading (io-threads, default 1, so off) while commands still run on the main thread. ElastiCache's comparison page likewise credits Memcached, not Redis, with using multiple cores.
Redis persistence: the default AOF fsync is every second, so a crash loses up to one second of writes; an RDB-only setup should expect to lose minutes.
Redis Cluster: 16,384 hash slots; replication between nodes is asynchronous.
Memcached: an LRU cache by default, with a per-slab-class LRU and 1 MB pages; servers do not replicate or coordinate.
Version numbers move; check the current docs before quoting a feature in a design review.

:::

Worked arithmetic. A 10-node Memcached tier with consistent hashing loses 10% of the cached keys when a node dies. If the tier absorbs 95% of 100,000 reads per second, the database normally sees 5,000; during the loss it sees about 5,000 + 0.10 x 95,000 = 14,500, nearly three times its usual load, until the keys refill. A replica ready to promote would largely remove that spike. Whether it is worth paying for depends on whether the database can take 14,500.

Further reading: Nishtala et al., Scaling Memcache at Facebook (NSDI 2013), and the Redis and Memcached documentation.

Proxies: the layer that sits in front and does more than route

A proxy (Twemproxy or similar) sits between client and origin. Beyond picking a cache node, it can act on every request and response without either side knowing.

Job	Examples
Filter	Access checks; reject malformed requests before they reach the origin
Log	Record every request centrally, without instrumenting each origin
Transform	Add or strip headers; TLS termination (the most common case); compress responses for slow clients

Collapsed forwarding is the technique worth naming: several requests for data that sits close together (nearby map tiles, adjacent rows of an uncached range) become one origin request, and that response answers every caller. It's request coalescing (from the thundering-herd material) generalized from "the exact same key" to "keys cheap to fetch together". The proxy is the place for it because it's the one component that sees all the requests.

Coherence across a fleet, and the two-hop invalidation bug

The previous lesson assumed one cache tier. Many systems cache the hottest keys twice: in the shared tier, and in a small in-memory layer per app instance so the hottest reads never leave the process. Invalidating the shared tier doesn't reach those local copies.

A two-tier cache has two invalidation problems, not one. Three fixes, none free:

Fix	Freshness	The cost
Very short local TTLs (seconds)	Stale for at most the local TTL	A small staleness window everywhere, always
Publish invalidation events (Redis pub/sub or a queue topic); each instance evicts the key on arrival	Near-immediate	An instance that misses the event (network blip, slow consumer) stays silently stale. Keep a backstop TTL underneath
No local tier	Only the shared tier's	A network hop on every read. A legitimate answer when the local tier's correctness risk outweighs the latency it saves

Every extra tier is one more place staleness can hide, and one more invalidation path to exercise in practice, not just draw on a whiteboard.

How to say it in the interview

"Eviction policy is a bet about what the next request looks like — LRU bets on recency, LFU bets on frequency, and the wrong bet for this workload is a real performance bug. Topology is a separate question: once one machine cannot hold the working set, I need a way to find a key without asking every node."

Checklist

Named the workload's access pattern before picking an eviction policy
Identified the one-time-scan failure specific to plain LRU
Named LFU's own failure — a stale but historically popular key that never gets evicted
Offered an adaptive policy (ARC / window-TinyLFU) as what production systems actually use
Could place FIFO, LIFO, MRU, and random replacement in one sentence each if asked
Chose between Redis and Memcached from what the tier must do, not from habit
Used consistent hashing for the cache tier itself, not just the database
Decided cache replication by whether the cache is load-bearing
Distinguished invalidating the shared cache from invalidating per-instance local copies
Named at least one concrete fix for local-tier staleness and its own cost
Named what a proxy layer actually does beyond routing — filter, log, transform
Named collapsed forwarding for spatially-close requests specifically

Practice this interactively