Caching Strategies

What You Should Understand

• 能畫出一個 request 從 browser 到 database 沿路經過的每一層 cache
• 能比較 cache-aside、read-through、write-through、write-behind、write-around 的一致性與延遲 tradeoff
• 知道 LRU / LFU / FIFO / TTL 各自的行為，以及為什麼 LRU 是預設選擇
• 能診斷並解決 cache stampede、penetration、avalanche、hot key、big key 五大故障模式
• 理解 Redis 為什麼快、六種核心資料結構的典型用途、RDB 與 AOF 的差異
• 知道 CDN 的 request flow、push vs pull、以及 Cache-Control headers 怎麼控制快取行為

Where We Cache

Caching happens at every layer between the user and the database. A single page load may hit half a dozen caches before any query reaches disk:

直覺：越靠近 user 的 cache 越快、但越難失效（invalidate）；越靠近 database 的 cache 越一致、但省下的延遲越少。設計時的問題永遠是「這份資料可以容忍多舊（staleness budget），以及誰共享它」。

The value of a cache is captured by the expected latency:

Hit rate $p_{\text{hit}}$ 是 cache 最重要的健康指標 — hit rate 太低時，cache 不但沒幫助，還多付一次 lookup 的成本。

Caching Patterns

How the cache interacts with the database on reads and writes defines the pattern. 面試最常考的比較題：

Cache-Aside (Lazy Loading)

The application owns all the logic:

1. Read: check cache → hit: return → miss: read DB → write result to cache with TTL → return
2. Write: update DB → delete the cache key (not update — see Cache Consistency)

直覺：cache-aside 是「lazy」的 — 只有真的被讀到的資料才會進 cache，所以 cache 裡永遠是 working set。缺點是第一次讀（cold read）比較慢，而且 DB 更新和 cache 刪除之間有短暫的 stale window。

Write-Through vs Write-Behind

直覺：write-through 像「同步記帳」— 每筆寫入同時落到 cache 和 DB，讀永遠新鮮，但每次寫都付兩次成本。Write-behind 像「先記在便條紙、晚點再抄進帳本」— 寫入超快、還能 batch 合併（同一個 key 改一百次只要 flush 一次），但 cache 節點掛掉時便條紙上的資料就沒了。所以 write-behind 適合掉了也能接受的資料：view counts、like counters、metrics。

Eviction & Expiration

Cache memory is finite. Two mechanisms bound it: expiration（時間到就失效, TTL）and eviction（空間滿了就淘汰）。

Why LRU is the default：真實流量幾乎都有 temporal locality — 剛被讀過的東西短時間內再被讀的機率遠高於隨機。LRU 用 hash map + doubly linked list 就能做到 $O(1)$ 的 get/put，實作成本低、對大多數 workload 表現穩定。Redis 的 allkeys-lru 實際上是 approximate LRU（隨機取樣 N 個 keys 淘汰最舊的），用少量精確度換掉維護全域 linked list 的成本。

Hot key considerations：eviction policy 保護不了你對付 hot key — 一個 key 被每秒十萬次讀取時，問題不是它會不會被 evict（不會），而是所有流量集中打在存這個 key 的單一 Redis node 上。解法在 How Caches Go Wrong。

How Caches Go Wrong

面試的高分區。四種經典故障模式 + 對策：

Cache Stampede in Detail

直覺：想像演唱會門票頁的 cache 剛好在開賣瞬間過期 — 十萬個 requests 同時 miss，全部衝去打 database 重算同一份資料。DB 瞬間過載，回應變慢，更多 requests 堆積，雪球越滾越大。

Three complementary defenses:

1. Mutex lock：miss 時先搶一把分散式鎖（Redis SET key_lock 1 NX EX 10）。搶到的那個 request 去重算並回填 cache，其他人短暫等待後重讀 cache。DB 只被打一次。
2. Request coalescing：在 application 層把同一個 key 的併發 misses 合併成一次 origin 請求（Go 的 singleflight 模式）。
3. Jittered TTL：ttl = base + random(0, jitter)，讓同一批寫入的 keys 不會同一秒集體過期 — 同時也是 avalanche 的解法。

Cache Penetration in Detail

直覺：攻擊者一直查 user_id = -1 — cache 裡沒有、DB 裡也沒有，所以每次都直穿到 DB。Cache 完全失效，形同虛設。

• Negative caching：查無此人也 cache 起來（value 存個 null 標記，TTL 給短一點如 60 秒），下次同樣的爛 key 直接被 cache 擋掉。
• Bloom filter：把所有存在的 key 預先放進 bloom filter。查詢先問 filter — 回答 "definitely not present" 就直接拒絕，不碰 cache 也不碰 DB。Bloom filter 有 false positive（說「可能存在」但其實沒有）但沒有 false negative，所以擋掉的一定是真的不存在。

Stale Data: The Two Hard Problems

"There are only two hard things in Computer Science: cache invalidation and naming things."

這句老話會紅不是沒原因：cache 的本質就是允許一份資料有兩個版本存在。所有 invalidation 策略都在回答同一個問題 — 舊版本最多能活多久、誰負責殺掉它。下一節深入。

Cache Consistency

Write 進 DB 之後，cache 裡的舊值怎麼辦？三個層次的答案：

Invalidate vs Update on Write

直覺：為什麼業界預設是 delete 而不是 update？兩個 writes A、B 先後更新 DB（B 較新），但寫 cache 的順序可能顛倒（B 先到、A 後到）— cache 裡就永久留著舊值 A，直到 TTL 才救回來。Delete 沒有這個問題：不管誰先刪，cache 都是空的，下一次 read 從 DB 讀到的一定是最新值。另外「先更新 DB 再刪 cache」的順序也比「先刪 cache 再更新 DB」安全 — 後者在刪除與 DB commit 之間，任何 read 都會把舊值重新填回 cache。

TTL as Safety Net

無論 invalidation 邏輯多完美，都要設 TTL。直覺：invalidation 是主動治療，TTL 是保險 — 當 delete 訊息丟失、event 沒送到、或有你沒想到的 write path 時，TTL 保證錯誤狀態的存活時間有上限（bounded staleness）。TTL 長短就是你的 staleness budget：使用者名稱可以 stale 一小時，但庫存數量可能只能 stale 五秒。

Event-Driven Invalidation

當寫入方很多（多個 services 都會改同一張表）或需要跨 datacenter 失效時，靠每個 writer 自覺刪 cache 不可靠。改用事件驅動：

• CDC (Change Data Capture)：用 Debezium 之類的工具訂閱 DB 的 binlog / WAL，每個 row change 產生一個 event，consumer 收到後刪對應 cache key。好處：不管誰用什麼方式寫 DB，invalidation 都不會漏。
• Pub/Sub：writer 更新 DB 後發 message（Kafka / Redis pub-sub），所有持有 local cache 的 app instances 訂閱並清掉自己那份 — 這是解決「application in-memory cache 跨 instance 不一致」的標準做法。

Redis in Practice

Life of a Redis Query

1. Client 透過 TCP 送出 RESP protocol 編碼的 command（例如 GET user:42）
2. Redis 的 event loop（epoll/kqueue 多路複用）偵測到 socket 可讀，讀入並解析 command
3. 單一 main thread 在 hash table 中查 key — 純記憶體操作，通常 $O(1)$
4. 結果寫回 output buffer，event loop 在 socket 可寫時送出

整趟 server 端處理常在 100 microseconds 之內；你量到的 1ms 左右延遲大多是網路 round trip。

Why Single-Threaded Is Fast

直覺：Redis 的瓶頸通常是網路和記憶體頻寬，不是 CPU — 所以多執行緒對單一 instance 幫助有限，反而引入鎖的成本。（Redis 6.0 之後把 network I/O 的讀寫交給 I/O threads，但 command execution 仍是單執行緒。）副作用是一個慢 command（KEYS *、對 big key 的 HGETALL）會 block 所有人 — 這就是 big key 危險的原因。

Core Data Structures and Use Cases

Rate limiter 兩種經典 Redis 實作：fixed window 用 String 的 INCR + EXPIRE（每分鐘一個 key，超過閾值就拒絕）；sliding window 用 zset — score 存 timestamp，ZREMRANGEBYSCORE 移除視窗外的舊記錄、ZCARD 數視窗內的請求數，精確但成本較高。

Persistence: RDB vs AOF

實務上常兩者並用（Redis 4.0 之後的 mixed persistence：RDB 打底 + AOF 補尾巴）。但記住：如果你的設計需要 Redis「絕對不能掉資料」，通常代表你把 cache 當 database 用了 — 該重新想一下 source of truth 在哪。

CDN

How a CDN Request Flows

1. User 請求 img.example.com/logo.png — DNS 解析（CNAME 指向 CDN）把 user 導到地理上最近的 edge server（透過 GeoDNS 或 anycast）
2. Edge server 檢查本地 cache — hit: 直接回傳，延遲可能只有 10-30ms
3. Miss: edge 向 origin server（或中間層 regional cache / origin shield）拉取，回傳給 user 並存入 edge cache
4. 之後同區域的所有 users 都吃到這份 edge copy，直到 TTL 過期或被主動 purge

直覺：CDN 就是「部署在全世界的 read-through cache」— 它把 origin 的內容搬到離 user 最近的地方，省掉跨洲的 network round trip（一趟跨太平洋約 150ms）。

Push vs Pull

Cache Keys and Cache-Control Headers

CDN 用 cache key 決定兩個 requests 算不算「同一份內容」— 預設是 URL（含 query string），可加入特定 headers（如 Accept-Encoding）或 cookies。Cache key 設計太細（把所有 query params 都算進 key）會讓 hit rate 崩掉；太粗則會把 A 使用者的內容回給 B — personalized response 絕對不能進 shared cache。

Versioned URLs（app.a1b2c3.js）是 static assets 的最佳解：內容變了就換檔名，於是 TTL 可以設一年、永遠不需要 invalidate — 用 naming 徹底繞過 invalidation 這個難題。

Real-World Use Cases

Case 1: 模型推論結果快取（Prediction Cache）

你的 fraud detection model 每次推論要 80ms（feature fetching 50ms + inference 30ms），但 latency budget 只有 100ms 且 QPS 在促銷時暴衝 10 倍。分析後發現同一個 user 在 5 分鐘內的 risk score 幾乎不變 — 於是加一層 prediction cache：key 是 fraud:user_id:context_hash，value 是 score，TTL 5 分鐘。Hit rate 到 70%，平均延遲從 80ms 降到 30ms，model server 的量少了三分之二。

這裡的核心 tradeoff 是 staleness vs cost：cache 的 5 分鐘內如果 user 行為突變（盜刷開始），你會用舊的低風險分數放行交易。所以高風險訊號（如換裝置、異地登入）要能 bypass cache 或主動 invalidate。Feature cache 也是同一邏輯 — batch features（7-day spend）可以 cache 很久，real-time features（本次交易金額）永遠不 cache。

Interview follow-ups：

• Cache key 該包含哪些東西？如果 model version 更新了，舊 cache 怎麼辦？（答：key 裡放 model version，或 deploy 時整批 invalidate / 換 key prefix）
• 什麼樣的模型輸出不適合 cache？（答：高度依賴 real-time context、或 label 變化極快的場景；以及 exploration 流量 — cache 會讓 bandit 學不到東西）
• 促銷開始的瞬間大量 cold users 同時 miss，怎麼防止 model server 被打爆？（答：request coalescing + 對 model server 設 rate limit，超出就 fallback 到規則分數）

Case 2: 推薦系統熱門榜單 — Redis Sorted Set

你負責電商首頁的「即時熱銷榜」：全站商品依過去一小時的購買數排序取 top 100，每秒被讀幾萬次。用 SQL GROUP BY + ORDER BY 每次現算會殺死 database。標準解法是 Redis zset：每筆訂單事件 ZINCRBY hot:2026070314 1 item_42（key 帶小時做 rolling window），讀取用 ZREVRANGE hot:current 0 99 WITHSCORES — $O(\log n + k)$，單次不到 1ms。

榜單本身又是一個 hot key：所有前端 instance 都在讀同一個 zset。進一步優化：每個 app instance 用 local in-memory cache 存 top 100，TTL 1 秒 — 對 Redis 的讀量從每秒數萬降到每秒每 instance 一次，榜單最多舊 1 秒，完全可接受。這是「distributed cache 前面再放一層 local cache」的經典兩層架構。

Interview follow-ups：

• 要做「過去 24 小時」的 sliding window 榜單怎麼辦？（答：每小時一個 zset，讀取時 ZUNIONSTORE 合併 24 個，或後台定期 merge 好存成一個 result key）
• Redis 掛了榜單就沒了，可以接受嗎？（答：可以 — 榜單是 derived data，可從訂單流重建；用 RDB snapshot 加速恢復，掛掉期間 fallback 到昨日榜單）
• 為什麼不用 database 的 materialized view？（答：refresh 頻率和讀取 QPS 都差好幾個數量級；但如果榜單只要每小時更新一次，materialized view + CDN 反而更簡單）

Case 3: A/B 實驗設定檔快取 — 一次 Stale Config 事故

你的實驗平台把 experiment config（分流比例、feature flags）存在 DB，每個 app instance 啟動時載入並放在 in-memory cache，TTL 30 分鐘。某天 PM 發現實驗 B 版有嚴重 bug，緊急在後台把實驗關掉 — 但接下來的 30 分鐘內，各 instance 的 local cache 陸續過期，有的 instance 已經停掉 B 版、有的還在出 B 版。結果：（1）bug 多影響了半小時的 users；（2）這半小時的實驗數據「同一個 user 可能先看到 B 再看到 A」，SUTVA 被破壞，整段數據只能丟棄。

事後改進：保留 TTL 當 safety net，但加上 event-driven invalidation — config 更新時透過 Redis pub-sub 廣播 config_changed 事件，所有 instances 立刻重新載入；另外加一個 version key（config:version 的整數），instances 每 10 秒輕量地檢查 version 有沒有變，作為 pub-sub 訊息掉了的第二道防線。Kill switch 這種「必須秒級生效」的路徑則完全不走 cache。

Interview follow-ups：

• 為什麼不乾脆把 TTL 設成 5 秒？（答：可以，但每 5 秒全部 instances 打一次 DB，config 表變成新的瓶頸；event-driven + 長 TTL 是更好的 cost/freshness 平衡）
• 這件事對實驗分析有什麼影響？怎麼在數據裡偵測？（答：檢查 assignment log 裡同一 user 短時間內出現兩種 variant；分析時排除 rollout/rollback 的過渡時段）
• 如果是幾千台 instances 的規模，pub-sub 掉訊息怎麼辦？（答：version polling 兜底 + 監控各 instance 回報的 config version 分布，發現分歧就告警）

Hands-on: Caching in Python

LRU Cache with OrderedDict

from collections import OrderedDict

class LRUCache:
    """O(1) get/put LRU cache — the classic interview implementation."""

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()  # key -> value, ordered by recency

    def get(self, key):
        if key not in self.cache:
            return None
        self.cache.move_to_end(key)  # mark as most recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict least recently used

# Built-in alternative for pure functions: functools.lru_cache
from functools import lru_cache

@lru_cache(maxsize=1024)
def expensive_feature(user_id: int) -> float:
    ...  # computed once per user_id, then served from memory

Cache-Aside with Redis: Jittered TTL + Stampede Lock

import json
import random
import time
import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

BASE_TTL = 300      # 5 minutes
TTL_JITTER = 60     # spread expiry over +/- 1 minute window
LOCK_TTL = 10       # recompute lock auto-expires (holder crash safety)
NULL_TTL = 60       # negative cache for nonexistent keys

def jittered_ttl() -> int:
    # keys written together should NOT expire together (avalanche defense)
    return BASE_TTL + random.randint(0, TTL_JITTER)

def get_user(user_id: int) -> dict | None:
    key = "user:" + str(user_id)
    cached = r.get(key)

    if cached == "__NULL__":
        return None                    # negative cache hit (penetration defense)
    if cached is not None:
        return json.loads(cached)      # normal cache hit

    # Cache miss: only ONE request recomputes (stampede defense)
    lock_key = key + ":lock"
    got_lock = r.set(lock_key, "1", nx=True, ex=LOCK_TTL)

    if got_lock:
        try:
            row = db_fetch_user(user_id)          # the expensive DB query
            if row is None:
                r.set(key, "__NULL__", ex=NULL_TTL)
                return None
            r.set(key, json.dumps(row), ex=jittered_ttl())
            return row
        finally:
            r.delete(lock_key)
    else:
        # Someone else is recomputing — wait briefly, then re-read cache
        for _ in range(20):
            time.sleep(0.05)
            cached = r.get(key)
            if cached is not None:
                return None if cached == "__NULL__" else json.loads(cached)
        return db_fetch_user(user_id)  # fallback: lock holder likely died

def update_user(user_id: int, fields: dict):
    db_update_user(user_id, fields)        # 1) write source of truth first
    r.delete("user:" + str(user_id))       # 2) then DELETE (not update) cache

Redis Sorted Set: Leaderboard and Rate Limiter

# Leaderboard: increment on each purchase event, read top-K
r.zincrby("hot_items", 1, "item_42")                 # O(log n) update
top10 = r.zrevrange("hot_items", 0, 9, withscores=True)  # top 10 with counts

# Sliding-window rate limiter: allow 100 requests per 60 seconds
def allow_request(user_id: str, limit: int = 100, window: int = 60) -> bool:
    key = "rate:" + user_id
    now = time.time()
    pipe = r.pipeline()
    pipe.zremrangebyscore(key, 0, now - window)  # drop events outside window
    pipe.zadd(key, {str(now): now})              # record this request
    pipe.zcard(key)                              # count requests in window
    pipe.expire(key, window)                     # garbage-collect idle users
    count = pipe.execute()[2]
    return count <= limit

Interview Signals

What interviewers listen for:

• 你會先問 read/write ratio 和 staleness budget，再決定 pattern，而不是反射性地說 "add Redis"
• 你主動提到 cache 失效後的世界：stampede、avalanche、cache 掛掉時 DB 扛不扛得住
• 你知道 invalidation 用 delete 而非 update、順序是先寫 DB 再刪 cache，並能解釋 race condition
• 你把 TTL 定位成 safety net 而不是唯一的一致性機制，並能講出 event-driven invalidation
• 你能把 caching 連回 ML 系統：feature/prediction cache 的 staleness 會直接影響模型決策品質

Practice

Flashcards

Quiz