Day 2 Medium Caching LRU/LFU/ARC Invalidation

缓存 — 从浏览器到 DB 的多层穿透艺术Caching: Layers, Eviction Policies, Write Strategies, Invalidation

问题场景

用户访问首页 200ms 内必须返回，DB 查询一次需要 80ms，单查首页要 7 个查询——不缓存就是死。但缓存不是『加个 Redis』那么简单：Facebook 2010 年因为一次 Memcached 失效风暴丢了 2.5 小时全站可用性；Discord 2017 年发现消息列表的 LRU 在热点频道下表现糟糕，换 LFU 后命中率从 78% 提到 96%；GitHub 2020 年 PR 页面用 Russian Doll caching，命中率 99.3%。

本期讲三件事：缓存放在哪一层、怎么淘汰、怎么写。最关键的是『缓存失效』，被 Phil Karlton 称为计算机科学两大难题之一（另一个是命名）。

需求与约束（面试必问）

高层架构（多层缓存）

graph LR
    B["Browser cache
localStorage / SW"]
    CDN["CDN Edge
Cloudflare / Akamai"]
    RP["Reverse Proxy
Varnish / Nginx"]
    APP["App + L1
in-proc · Caffeine"]
    L2["Redis / Memcached
跨进程共享 L2"]
    DB[("DB + buffer pool")]

    B -->|①| CDN -->|②| RP -->|③| APP -->|④| DB
    APP <-.->|miss → 回填| L2
    L2 -.miss.-> DB

    classDef client fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    classDef edge fill:#0e2030,stroke:#5eead4,color:#e8eef5
    classDef cache fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef origin fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class B client
    class CDN,RP edge
    class APP,L2 cache
    class DB origin

命中率从左到右递增；返回时反向回填每一层，下一次请求短路

关键技术点

1. 缓存层次：Browser / CDN / App / DB Buffer Pool

原理：每一层缓存解决不同的延迟问题。Browser cache 省网络（0ms vs 50ms）；CDN 把静态资产放到用户 50 公里以内的 PoP，p50 延迟 10ms；app 进程内 cache（Guava / Caffeine / Python functools.lru_cache）省 Redis 一次 RTT（0.1ms vs 1ms）；Redis 跨进程共享，命中后省 DB 查询（1ms vs 50ms）；DB buffer pool（Postgres shared_buffers, InnoDB buffer pool）省磁盘 IO。

Trade-off：
现实案例：

2. 淘汰策略：LRU vs LFU vs ARC vs TinyLFU

原理：缓存容量有限，必须选一个『谁先死』规则。

策略淘汰对象适合场景命中率
LRU最久未访问的时间局部性强（最近访问 = 即将再访问）中
LFU访问次数最少的频率局部性强、热点稳定高（稳态）
ARC自适应 LRU+LFU访问模式变化、不想调参高
W-TinyLFU带准入控制的 LFU有突发流量、扫描型访问极高
FIFO/Random先进/随机O(1) 极简、纯 streaming低
Trade-off： 
# Python LRU 极简实现 (用 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)        # 最近访问 → 末尾
        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)  # 淘汰头部（最久未访问）

# Redis 实际用『近似 LRU』：每次淘汰从 5 个随机 key 中挑最久的
# maxmemory-policy allkeys-lru / allkeys-lfu / volatile-ttl
现实案例：

3. 写策略：Cache-aside vs Write-through vs Write-back

原理：写数据时缓存和 DB 谁先谁后、谁负责，决定了一致性和复杂度。

Cache-aside (lazy)Write-throughWrite-back
读miss → DB → 回填 cachecache hit（永远）cache hit
写写 DB → 删 cache写 cache → 同步写 DB只写 cache → 异步刷 DB
一致性有窗口（最终一致）强（cache = DB）弱（宕机丢未刷数据）
写延迟低（只写 DB）高（两次写）极低（只写内存）
适用Redis + DB 最常见金融、强一致读CPU cache、SSD FTL
# Cache-aside 标准写法 (Python)
def get_user(uid):
    user = redis.get(f"u:{uid}")
    if user: return json.loads(user)
    user = db.query("SELECT * FROM users WHERE id=%s", uid)
    redis.setex(f"u:{uid}", 3600, json.dumps(user))  # TTL 兜底
    return user

def update_user(uid, data):
    db.update("UPDATE users SET ... WHERE id=%s", uid, data)
    redis.delete(f"u:{uid}")   # ⚠️ 删而不是更新，避免并发写错乱
    # ⚠️ 还要小心: 删之后立刻有人读, 可能再次回填旧值 → 双删 / 延迟双删
Trade-off：
现实案例：

4. 失效难题：TTL、惊群、雪崩、穿透

原理：四个经典坑，每个都在生产环境炸过。

# Single-flight 防击穿 (Go)
var g singleflight.Group
func GetHot(key string) (any, error) {
    v, err, _ := g.Do(key, func() (any, error) {
        if v := redis.Get(key); v != nil { return v, nil }
        v := db.Query(key)
        redis.SetEX(key, v, ttlWithJitter(3600))
        return v, nil
    })
    return v, err
}
现实案例：

扩展与优化（增长后怎么办）

常见陷阱（资深工程师也常翻车）

1. 更新缓存还是删除缓存？ 答案永远是删除。更新会让两个并发写产生乱序（A 写值 v1 → B 写值 v2 → B 更新 cache → A 更新 cache，cache 永远停在 v1）。
2. 先写 DB 还是先删 cache？ 标准是『先 DB 后删 cache』。先删 cache 的话，删完到 DB 写完之间有窗口，别人读会回填旧值。极端情况用『延迟双删』：删 → 写 DB → sleep 500ms → 再删一次。
3. 缓存 vs 数据库的最终一致窗口：永远不可能 0。承认这一点，给业务定『stale 容忍度』。
4. 把 Redis 当 DB 用：Redis 持久化（RDB / AOF）不是设计目标，宕机 RPO 至少几秒。账户余额这种数据，Redis 是 cache 不是 source of truth。
5. 忽略冷启动：服务重启或 cache cluster 替换瞬间，命中率 0%，DB 直接被打爆。要预热或慢启动放量。

面试问题示例

  1. 设计 Instagram 首页 feed 缓存，用户量 10 亿，p99 < 200ms。
  2. Redis 一个 hot key（如顶流明星的粉丝列表）QPS 100w，怎么扛？
  3. 缓存一致性怎么做？说说『先写 DB 还是先删 cache』各自的失败场景。
  4. LRU 和 LFU 的实现细节，时间复杂度，分别什么场景下选哪个？
  5. Cache penetration（恶意查不存在的 key）怎么防？Bloom Filter 的误判率怎么算？

关键资源

English Summary

Caching is a multi-layer art spanning browser, CDN, reverse proxy, in-process, distributed (Redis/Memcached), and DB buffer pools. Choose eviction policy by access pattern: LRU for recency, LFU for frequency, W-TinyLFU (Caffeine) when in doubt. Write strategies trade consistency for performance: cache-aside is the default, write-through ensures correctness, write-back maximizes throughput at the cost of durability. The hardest part is invalidation — beware thundering herd, avalanche (use TTL jitter), penetration (bloom filter), and the eternal question of delete vs update cache (always delete).

深入思考（点击展开答案）

1. 命中率从 95% 降到 90%，DB 负载会变成几倍？为什么不是简单的 2 倍？

表面算法：miss rate 5% → 10%，回源 QPS 翻倍 = DB 2 倍负载。

实际更严重，至少 3 个放大效应：

  • 缓存被打穿时往往伴随写入：miss 后要回填 cache，多一次 Redis SET；高并发下还会 thundering herd——同一 key 1000 个并发请求同时回源，DB 收到的是 1000 次而不是 1 次。
  • DB 自身的 cache 也连锁失效：Postgres shared_buffers / MySQL buffer pool 命中率会跟着掉，磁盘 IO 飙升，p99 不止 2 倍。
  • 连接池争抢：DB connection pool 通常按 95% 命中设计的容量，突然 2 倍 QPS 直接打满，新请求排队，p99 雪崩。

真实数字：90% 命中率下 DB 实际负载通常是 3-5 倍。所以监控里看到命中率掉 5 个百分点就要警觉。

2. cache-aside『先写 DB → 再删 cache』，生产仍偶尔读到旧值。至少列 3 种可能原因及对应修法。
  • 并发写读交错：A 读 cache miss → A 读 DB（拿到旧值 v1）→ B 写 DB（v2）→ B 删 cache → A 回填 cache(v1)。cache 永远是旧值。修法：延迟双删（B 删 → sleep 500ms → 再删一次）；或用 single-flight 限制并发回填。
  • 主从复制延迟：写主库后删 cache，但有人立刻读，路由到 replica（还没复制完），拿到旧值回填 cache。修法：删 cache 后强制读主一段时间；或者『先写主 → wait for replica → 再删 cache』。
  • 删除失败：DB 写成功但 Redis 网络抖动删除失败，没有重试。修法：用 outbox / CDC 模式，把 invalidation 事件落地（Debezium 监听 binlog → 发到 Kafka → consumer 删 cache），保证 at-least-once。
  • 多区缓存不同步：US-East 删了 cache，US-West 没删。修法：跨区广播 invalidation（Facebook 用 mcsqueal）。
  • 客户端本地缓存：app 进程内 Caffeine 还在用旧值，远端 Redis 删了也没用。修法：本地 cache TTL 短一点，或订阅 Redis pub/sub 主动失效。
3. Redis Cluster 不支持跨 slot 的 MULTI / 事务。这个限制怎么影响 key 设计？hash tag（{user:123}）解决了什么、引入了什么新问题？

影响：你不能在一个事务里同时操作 user:123:profile 和 user:123:posts——它们 hash 到不同 slot 在不同节点上，MULTI 会被拒绝（CROSSSLOT 错误）。同理 MGET、MSET 跨 slot 也不行。

Hash tag 怎么用：把要放一起的 key 写成 {user:123}:profile 和 {user:123}:posts，{} 里的部分作为 hash 输入，保证两个 key 落同一 slot。

引入的新问题：

  • 数据倾斜：一个 user 所有 key 都在同一节点，顶流用户那个 slot 变 hot spot，单节点 CPU 飙红。
  • 大 key 风险：把多个 collection 绑到一起，单个用户数据膨胀就是单节点内存爆炸。
  • resharding 痛苦：cluster 扩容时 slot 迁移要把整组 key 一起搬，迁移期间这组 key 的写操作要排队。
  • 反模式诱惑：开发者会把『可能一起读』的所有 key 都打 tag，最后退化成单节点 Redis。

实战建议：hash tag 只用在真正必须原子的场景（购物车 + 库存）；展示型多 key 拼装，让 app 端做并发 GET 而不是依赖事务。

4. Hot key 单点 QPS 100w，单 Redis 实例顶不住。至少列 3 种解法（不同方向），各自代价？
  • ① Key 分片（写时拆、读时合并）：把 celebrity:123:followers_count 拆成 celebrity:123:followers_count:{0..15}，写时随机选一个 +1，读时 16 个 SUM。代价：读放大 16 倍、强一致性丢失（瞬时 sum 可能短暂偏小）、只适合可累加数据。
  • ② 多副本读（local replica）：把 hot key 复制到多个 Redis 节点，client 随机选一个读。代价：写要 fanout 到 N 个副本、副本一致性（用 master-replica 异步同步会有 lag）。Redis Cluster 的 READONLY 模式就是这个思路。
  • ③ 多级缓存：app 进程内 L1 cache：每个 app 实例本地 Caffeine 缓存这个 hot key，TTL 1s。100 台 app × 每秒 1 次回源 = 100 QPS，Redis 压力立刻消失。代价：最长 1s stale、内存浪费（100 份副本）、invalidation 困难。
  • ④ CDN / edge cache：如果是公开数据（明星粉丝数），直接放 CDN，边缘节点扛 100w QPS。代价：只适合可公开缓存的内容、失效慢（30s+）。
  • ⑤ Pre-compute + 推送：根本不让用户实时查，把数据预生成在每个用户的 timeline cache 里（Twitter fanout-on-write）。代价：写放大极大，对 1 亿粉丝的明星不适用。

实战组合：通常 ① + ③ 一起上——分片承担写、本地 L1 承担读。

5. 服务重启时命中率瞬间 0%，DB 直接被打爆。预热怎么做？预热过程本身如何不把 DB 打挂？

预热时机：

  • 新版本上线前（蓝绿部署的 green 环境预热好再切流量）；
  • Redis cluster 替换时（旧集群导出 → 新集群导入）；
  • 大促前夜（提前把可预测的热数据灌进去）。

怎么预热：

  • 离线分析 + 批量灌入：从过去 7 天访问日志算 top 10w key，离线 dump 出 KV，用 RESTORE 或 pipeline 批量写 Redis（避免一条条 SET）。
  • 线上慢启动放量：新实例上线时 LB 只给 1% 流量，cache 慢慢填，5 分钟后线性放到 100%。Envoy 的 slow_start_config 直接支持。
  • 双 cache 切换：旧 Redis 还在服务，新 Redis 后台 mirror 一份流量预热，切流时 hit rate 已经高了。

预热本身不打挂 DB：

  • 限速：预热脚本用 token bucket，比如 5k QPS 上限，避免把 DB connection 打满。
  • 读 replica：预热从 replica 读，不挤占主库的事务能力。
  • 错峰：在低谷时段（凌晨 3-5 点）预热；或者用线上自然流量『顺路』预热（first user 触发回源，后面的人受益）。
  • Single-flight：预热过程也要防 thundering herd，同一 key 只让一个 worker 回源。

真实故事：Pinterest 2014 年因 Memcached 整集群替换没预热，DB 被打挂 30 分钟，事后改成『新旧集群并行运行 1 小时』。

← 回到 index