Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops

The guide already covers cache stampede, replacement policies, and write strategies at the mechanism level. This page goes one layer deeper on the four things a senior interviewer actually probes: the math behind probabilistic early expiration (XFetch), why textbook exact-LRU quietly serializes a read-heavy cache, the operational reality of Redis vs Memcached, and how to reconcile the "is a Redis hit 0.2 ms or 1 ms?" numbers that drift across sources.

1. Probabilistic early expiration (XFetch), derived

A stampede happens because a key expires at a single instant T, and every concurrent reader simultaneously misses and hammers the origin. A per-key mutex (single-flight) fixes correctness but blocks every reader behind the one recomputing. XFetch fixes it without blocking anyone: each reader independently decides to refresh a little early, with a probability that rises as T approaches, so on average exactly one reader refreshes just before expiry and the herd never forms.

On each read you store, alongside the value, its recompute cost delta (how long the last regeneration took) and its absolute expiry T. A reader triggers an early recompute when:

now - delta * beta * ln(rand()) >= T

Here rand() is uniform on (0,1], so ln(rand()) is negative and -ln(rand()) is exponentially distributed with mean 1. The term delta * beta * (-ln rand) is a random "pretend expiry earlier" offset whose expected size is delta * beta. So a reader tends to volunteer to refresh in a window of roughly delta * beta before the real expiry — exactly long enough to recompute (which takes delta) before anyone truly misses.

Worked trace. Say a key is expensive to build: delta = 50 ms, beta = 1, TTL of 60 s. With 200 ms left before T, a reader refreshes only if -ln(rand) >= 200/50 = 4, i.e. probability e^-4 ≈ 1.8% — almost everyone just serves the cached value. With 20 ms left, the bar is -ln(rand) >= 0.4, probability e^-0.4 ≈ 67% — now it is very likely someone among the concurrent readers has already kicked off the refresh. Because that refresh takes ~50 ms and started ~50 ms early, the fresh value is in place at T and no thundering herd occurs. Turn beta up (>1) to refresh more eagerly for very hot keys; down (<1) to hug the TTL for cheap keys.

2. XFetch vs the alternatives

• Per-key mutex / single-flight: simplest and exact — one recompute, others wait or serve stale. But it blocks readers (latency spike for the herd) and needs a distributed lock if the cache is shared. Best when recompute is cheap-ish and you want zero redundant work.
• stale-while-revalidate: serve the expired value immediately and refresh in the background. Zero latency hit, but every reader may briefly see stale data and you still need one-flight to avoid N background refreshes. Best when brief staleness is acceptable (feeds, counts).
• XFetch: no blocking, no explicit lock, and it refreshes before expiry so readers rarely see a miss at all. The cost is a little redundant early work and carrying delta per key. Best for expensive-to-compute hot keys where both blocking and staleness are unacceptable.

3. Exact-LRU quietly serializes a read-heavy cache

Textbook LRU is a hashmap plus a doubly-linked list: on a hit you move the touched node to the most-recently-used end. The trap: that move mutates shared structure, so even a read (GET) must take a write lock. Under a read-heavy workload — which is the entire point of a cache — every reader now contends on one lock, and your beautifully O(1) cache serializes all reads on a single mutex. Throughput collapses under concurrency for a reason that never shows up in a single-threaded benchmark.

Fixes, and what they cost:

• Striped / sharded locks: partition the keyspace into N segments each with its own lock. Cuts contention ~N×, cheap to build, but LRU is now per-shard (approximate globally) and hot keys can still collide within a shard.
• Sampled eviction (Redis): don't maintain a global order at all — on eviction, sample a handful of keys and drop the oldest. Reads only update a cheap per-key access timestamp/counter (no list surgery), so reads don't need a write lock. Approximate LRU/LFU, but effectively lock-free on the read path.
• CLOCK / second-chance: a ring with a reference bit; a read just sets a bit (an atomic write, no relinking). Approximates LRU with near-zero read-side coordination. This is why OS page caches use CLOCK, not exact LRU.

4. Redis & Memcached: the operational reality

Persistence (Redis). Two mechanisms with different failure windows:

• RDB — periodic point-in-time snapshots via a fork(). Compact, fast restart, but a crash loses everything since the last snapshot. The fork can also spike memory (copy-on-write) on write-heavy datasets.
• AOF — append every write to a log; replay on restart. appendfsync everysec loses at most ~1 s; always is near-zero-loss but fsync-per-write throttles throughput. AOF files grow and need periodic rewrite/compaction.

The design point: if Redis is a pure cache, you often want no persistence (a cold restart just re-fills from the origin) — persistence only buys you a warm cache and costs you fork/fsync overhead. If Redis is a store, you need AOF (and usually replication).

maxmemory eviction. When memory is capped, the policy decides behaviour under pressure: allkeys-lru / allkeys-lfu (evict across all keys — the usual cache setting), volatile-lru/ttl (only evict keys with a TTL — dangerous if some keys have none), and noeviction (reject writes with an error once full — safe for a store, a self-inflicted outage for a cache). Redis's LRU/LFU here are the sampled approximations from §3.

Memcached contrast. Multithreaded (scales across cores on one node), slab allocator (fixed-size classes → simple, but internal fragmentation for odd value sizes), no persistence, no replication, no data structures — just bytes. Redis is single-threaded for the command path (no read-side locks needed, predictable latency) with rich types and optional persistence/replication. Pick Memcached for a dumb, multi-core, pure LRU byte cache; Redis when you want structures, persistence, or replication.

5. Reconciling the "0.2 ms vs 1 ms" Redis latency

Different pages quote a Redis hit as ~0.2 ms and others as ~1 ms. Both are right — a cache hit is not a constant, it is a network round-trip plus serialization, so the number moves with percentile and payload:

• Same-LAN p50 for a small value: typically ~0.1–0.3 ms (the RTT dominates; Redis itself serves in microseconds).
• p99, or a large/serialized value, or a busy server: ~1 ms and up (tail queuing, TCP, serializing a big object, a cross-AZ hop).

The mental model to carry into an interview: a remote cache hit costs one network RTT + serialization, not a fixed figure — quote a range and name the percentile. (An in-process/local cache hit is sub-microsecond and in a different universe; that is the real reason L1/near caches exist in front of Redis.)

Pitfalls

• Single-flight without a stale fallback still spikes latency for the whole herd while one thread recomputes — pair it with serve-stale or XFetch.
• Exact LRU in a concurrent cache looks O(1) but serializes reads on the move-to-MRU write lock; benchmark under concurrency, not single-threaded.
• Leaving Redis persistence on for a pure cache pays fork/fsync cost for a warm restart you may not need; and noeviction on a cache turns a full instance into write failures.
• Quoting a single Redis latency number hides the tail — the miss/fill path and p99, not the average hit, dominate user-visible latency.

Judgment layer — when each is right

• Stampede control: cheap recompute + exactness matters → single-flight. Brief staleness OK, latency critical → stale-while-revalidate. Expensive hot key, no blocking and no staleness → XFetch.
• Eviction structure: single-threaded or low concurrency → exact LRU is fine and precise. High-concurrency read-heavy → sampled-LRU (Redis) or CLOCK; reach for striped locks only if you truly need a global order.
• Engine: pure multi-core byte cache → Memcached. Need structures / persistence / replication / predictable single-threaded latency → Redis.
• Persistence: cache → none or RDB; store → AOF everysec (durability/throughput balance) or always only when loss is unacceptable.

Takeaways

• XFetch beats the herd with math, not locks: refresh early with probability e^(-(T-now)/(delta·beta)), so one reader refreshes ~delta·beta before expiry and no one misses.
• Exact LRU's move-to-MRU is a hidden write on every read — it serializes read-heavy caches; real systems approximate with sampled-LRU or CLOCK.
• Redis persistence and eviction policy are the operational knobs that decide cache-vs-store behaviour under failure and memory pressure.
• A remote cache hit is an RTT + serialization, not a constant — quote a range with a percentile.

---

Re-authored/Deepened for this guide.

I just read a lesson on **Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops (Deep Dive)** (System Design) and want to truly understand it. Explain Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.