Caching

Why Cache?

A cache is a fast, usually in-memory store that keeps copies of expensive-to-produce data close to where it is consumed. The goal is to trade a small amount of memory and staleness for large gains in latency and throughput, and to shed load from an origin (a database, a downstream service, or an object store).

Caching works because real workloads are skewed: a minority of keys serve a majority of requests (the 80/20 or Zipf pattern). If the hot set fits in RAM, most reads never touch the origin.

Hit Ratio — the Number That Matters

The cache hit ratio is hits / (hits + misses). Effective average latency is a weighted blend of cache and origin latency:

avg_latency = hit_ratio * cache_latency + (1 - hit_ratio) * origin_latency

Example: cache = 1 ms, origin = 40 ms
  hit_ratio 0.50 -> 0.50*1 + 0.50*40 = 20.5 ms
  hit_ratio 0.90 -> 0.90*1 + 0.10*40 =  4.9 ms
  hit_ratio 0.99 -> 0.99*1 + 0.01*40 =  1.4 ms

Notice the curve is non-linear: moving from 90% to 99% cuts latency roughly 3.5x, and it cuts origin load by 10x (from 10% of traffic to 1%). The last few percent of hit ratio protect the origin more than they speed up any single request.

Where to Cache

  Browser        CDN / Edge      App server      Shared cache      Database
 (private)      (POP, global)   (local heap)   (Redis cluster)    (buffer pool)
     |               |               |                |                |
 [==cache==] -> [==cache==] -> [==cache==] ->    [==cache==]   -> [==cache==]
  fastest,        near user,     per-instance,    shared &         page/query
  per-user        static assets  low latency,     coherent,        cache,
                                 not coherent      network hop      transparent

Caching Patterns

Cache-aside (lazy loading)

The application manages the cache. On read: check cache; on miss, read origin, populate cache, return. This is the most common pattern — only requested data is cached, and the cache can be down without breaking correctness (only latency suffers).

value = cache.get(key)
if value is None:            # cache miss
    value = db.read(key)
    cache.set(key, value, ttl=300)
return value

Read-through is the same logic, but the cache library (not your code) loads from the origin on a miss. Write-through writes to cache and origin synchronously, keeping them consistent at the cost of write latency. Write-behind (write-back) writes to cache first and flushes to the origin asynchronously — fast writes, but a crash can lose un-flushed data. Refresh-ahead proactively reloads popular keys before they expire, hiding miss latency for hot data.

Eviction Policies

A cache has finite memory, so it must decide what to evict when full. TTL controls staleness; the eviction policy controls capacity.

Redis maxmemory-policy options combine these (e.g. allkeys-lru, volatile-lfu). Modern caches often use TinyLFU/W-TinyLFU (as in Caffeine) which approximates LFU with a small frequency sketch and beats plain LRU on most workloads.

Cache Invalidation — the Hard Problem

"There are only two hard things in computer science: cache invalidation and naming things." The challenge: when the underlying data changes, cached copies become stale. Strategies:

Stampede, Penetration, and Hot Keys

Thundering herd / cache stampede

When a popular key expires, thousands of concurrent requests miss simultaneously and all hit the origin at once, which can topple it. Mitigations:

1. Request coalescing / single-flight
   Only ONE request recomputes; others wait for the result.

2. Locking (mutex per key)
   First miss acquires lock, recomputes, sets; others retry-read.

3. Jittered TTL
   ttl = base + random(0, spread)   # spread expiry over time

4. Early / probabilistic refresh (XFetch)
   Refresh a bit BEFORE expiry with probability rising as TTL nears 0.

Cache penetration

Requests for keys that do not exist always miss the cache and always hit the origin (common in credential-stuffing or scraping). Defenses: cache the negative result (a short-TTL "null" sentinel) and use a Bloom filter in front of the cache — a probabilistic set that answers "definitely not present" cheaply, short-circuiting lookups for keys that cannot exist.

Hot key

One key (a celebrity profile, a flash-sale item) receives so much traffic it saturates a single cache node. Fixes: replicate the key across nodes with a random suffix (key#1..key#N), pin it to a local in-process cache, or add a small client-side cache tier.

Distributed Caching

A single cache node has bounded memory and throughput. Distributed caches spread keys across many nodes. The routing question — "which node owns this key?" — is answered with consistent hashing, which minimizes the fraction of keys that move when a node is added or removed.

Naive: node = hash(key) % N
  Add one node (N -> N+1): almost ALL keys remap -> mass miss storm.

Consistent hashing: place nodes and keys on a ring [0, 2^32).
  A key belongs to the next node clockwise.
  Adding/removing a node only moves keys in ONE arc (~1/N of keys).
  Virtual nodes (many points per physical node) smooth the load.

        0/2^32
          *  nodeA
      key3 |    \
   nodeC * |     * nodeB
          \|    /
       key1 *  key2

Redis Cluster instead uses 16,384 hash slots assigned to nodes; a key maps to CRC16(key) % 16384. Client-side sharding, twemproxy, or Redis Cluster all solve the same routing problem.

Redis vs Memcached

Consistency & Coherence

A cache is a second copy of the truth, so it can disagree with the origin. Write-through keeps them in lock-step (strong-ish consistency) but pays on every write. Write-back lets them diverge until the flush, so reads through the cache are consistent but the origin lags. Across multiple app instances holding local caches, you get a coherence problem: node A updates, node B still serves the old value. Solutions include a shared distributed cache (single source), pub/sub invalidation messages that tell every node to drop a key, or short TTLs to bound divergence.