Caching & Storage — latency physics and the art of lying fast

1The memory hierarchy — latency numbers every programmer should know

Hardware is a pyramid: each level down is ~10–100× bigger and ~10–100× slower.

            ┌──────────────┐   ~0.3–1 ns      registers
            │   L1 cache   │   ~1 ns          64 KB-ish
           ┌┴──────────────┴┐  ~3–4 ns        L2, ~1 MB
          ┌┴────────────────┴┐ ~10–20 ns      L3, tens of MB (shared)
         ┌┴──────────────────┴┐ ~60–100 ns    RAM
        ┌┴────────────────────┴┐ ~10–100 µs   NVMe SSD read
       ┌┴──────────────────────┴┐ ~1–10 ms    spinning disk seek
      └──────────────────────────┘

The numbers that actually run your day — with the intuition anchor: pretend an L1 hit takes 1 second (multiply everything by 10⁹) and feel how absurd the spread is.

Three conclusions to actually say in interviews:

2Caching patterns

Cache-aside (lazy loading) — the default, probably what you run

 read:  app ──GET key──► Redis ── hit ──► return          (fast path)
                           │ miss
                           ▼
                    app ──query──► Postgres ──► app SETs Redis (with TTL) ──► return

 write: app ──write──► Postgres, then DEL (invalidate) the Redis key

• App owns the logic; cache is a dumb sidecar. Only requested data gets cached; cache failure degrades to "slow," not "down."
• Costs: first request per key eats a miss; invalidate-on-write is on you (the hard part, §4); brief staleness windows exist.
• Prefer delete-on-write over update-on-write: deleting is idempotent and avoids racing two writers into a stale overwrite; the next read repopulates.

Write-through

Writes go through the cache layer, which synchronously writes the store and the cache. Reads are always warm and consistent-with-store; writes pay double latency; you may cache things never read. Often paired with cache-aside reads.

Write-back (write-behind)

Write to the cache only; flush to the store later, in batches:

 app ──write──► cache (ack immediately!) ──async batch──► store

Blazing write latency + write coalescing, at the price of losing acked data if the cache dies before flush. You've met this pattern everywhere respectable: CPU caches, the OS page cache (write() returns before disk; fsync forces it), and Postgres itself (shared_buffers dirty pages, WAL fsync at commit for the durable part + background checkpoints for data pages). Use in apps only for tolerable-loss data (view counters, analytics buffers).

3Eviction — the cache is full, who dies?

TTL (time-based)

Every entry gets a lifespan (SET key val EX 300). Not really an eviction policy — it's a staleness bound: "I can tolerate 5 minutes of lie." TTL is also the safety net that makes imperfect invalidation survivable — even a missed invalidation self-heals in one TTL. Almost everything you cache should have one.

LRU — Least Recently Used (+ the implementation sketch interviewers want)

Evict what's gone longest unused. The classic O(1) implementation = hash map + doubly linked list:

        hash map                 doubly-linked list (recency order)
   key ──► node ptr          MRU ◄─► [k3] ◄─► [k1] ◄─► [k7] ◄─► LRU
                                                    evict from here ──►

 get(k):  map lookup → unlink node → move to MRU end → return value      O(1)
 put(k,v): if present: update + move-to-front.
           else: if full → evict LRU tail (and its map entry); insert at MRU.  O(1)

# In real Python: functools.lru_cache, or OrderedDict:
from collections import OrderedDict

class LRU:
    def __init__(self, cap): self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k)              # mark most-recently used
        return self.d[k]
    def put(self, k, v):
        if k in self.d: self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap: self.d.popitem(last=False)  # evict LRU

LFU — Least Frequently Used

Evict the least often used. Resists scan pollution (one touch ≠ hot) but needs aging/decay so yesterday's celebrity keys eventually die, and costs more bookkeeping.

What Redis really does

maxmemory + maxmemory-policy: allkeys-lru, volatile-lru (only TTL'd keys), allkeys-lfu, volatile-ttl, noeviction (errors on write — the default!). And Redis's "LRU" is approximate — it samples N random keys and evicts the stalest, because a true global linked list across millions of keys costs memory and coherence. Knowing "Redis LRU is sampled, and the default policy is noeviction" is a strong flex.

4Cache invalidation & stampede protection

Invalidation strategies, in order of increasing effort

1. TTL only — accept bounded staleness. Right answer surprisingly often (config, feature flags, rarely-changing lookups).
2. Delete-on-write (cache-aside) — write DB, DEL key. Gaps: multi-key dependencies (an entity cached under user:42, user:email:x, and inside three list caches), and the write-DB-then-crash-before-DEL window.
3. Versioned/namespaced keys — never mutate, change the key: user:42:v{updated_at} or a namespace counter you bump to mass-invalidate. Old entries die by TTL/eviction. Sidesteps races entirely.
4. Event-driven — publish change events (you have Kafka!) or CDC (Debezium) and let a consumer invalidate/update caches. Decoupled and reliable; eventual by nature.

Cache stampede (thundering herd)

A hot key expires → 1,000 concurrent requests all miss → 1,000 identical DB queries → DB tips over → the outage caused by the cache:

        TTL expiry
 ───────────┬──────────────► time
   hits...  │ ██████████ 1000 misses hammer Postgres simultaneously

Protections (know several):

5Redis — core structures and what each is for

Redis = single-threaded (command execution) in-memory data-structure server. Single-threaded is a feature: every command is atomic — no locks needed — and one core over RAM still does ~100k+ ops/s. (I/O threads exist for socket work; command logic stays serial.)

6CDNs — the same idea, planet-sized

A CDN is cache-aside at the edge of the internet: hundreds of PoPs holding copies close to users, because you cannot cache away the speed of light (~200 ms India↔US) but you can move the copy.

 user (Pune) ──5ms──► edge PoP (Mumbai) ── hit ──► done
                          │ miss
                          └──────► origin (your LB/Kong/S3) → cache per headers → serve

• Controlled by HTTP headers: Cache-Control: public, max-age=86400, stale-while-revalidate=60, ETag/If-None-Match (304s), Vary. TTL + SWR + purge APIs = the same invalidation toolkit as §4, over HTTP.
• Static assets: fingerprinted filenames (app.9f3ab2.js, immutable, cache ~forever) = versioned keys, again — deploys change the URL, never invalidate.
• CDNs also cache APIs (public GETs), terminate TLS near users (cutting handshake RTTs), absorb DDoS, and run edge compute.

7OpenSearch / Elasticsearch — the inverted index vs the B-tree

Why Postgres is the wrong shape for search

WHERE title LIKE '%database%' can't use a B-tree (not a prefix) → full scan; no relevance ranking, fuzziness, or language handling. A B-tree maps key → row. Search needs the reverse: word → documents.

The inverted index

At index time, each document is analyzed — tokenized, lowercased, stemmed ("Running" → "run"), stopwords dropped — then each term posts into a dictionary:

 doc1: "Postgres indexes B-trees"      TERM DICTIONARY → POSTINGS LISTS
 doc2: "Redis cache eviction"          ─────────────────────────────────
 doc3: "Postgres caching with Redis"   "postgres" → [1, 3]
                                       "index"    → [1]
                                       "redis"    → [2, 3]
                                       "cache"    → [2, 3]   (cache/caching → same stem)
                                       "b-tree"   → [1]

 query "postgres cache" → lookup two postings lists → union/intersect
                        → score each doc (BM25: rare terms & term frequency
                          weigh more, long docs normalized) → ranked results

That's it — search over millions of docs = a few sorted-list lookups + merge + scoring. Wildly cheap compared to scanning.

Structural differences from a B-tree database — the part interviewers probe

QInterview questions you should be able to answer

✓Self-test before moving on