Cache Aside 的写法很短：读时先查缓存，未命中就读数据库再回填；写时先提交数据库，再删除缓存。这段代码里有一个读者与写者交错的窗口：读者读到旧行之后、回填之前，写者提交了新版本并删掉了缓存，读者随后把旧行写回去。此后缓存里的旧值没有任何人负责清除，只能等 TTL。另一个窗口出现在写者自身：数据库已经提交，删除缓存的那条命令还没发出，进程就退出了。

本篇的验收目标是：数据更新与慢读回填交错之后，旧值可以被拒绝、被检测、被修复；旧值最多存活多久（新鲜度窗口）要写成由哪些量组成的上界，并指出哪些条件下不存在上界。全部数据为合成数据，商品标识形如 sku-lab-05。

需求与范围

服务管理一组商品描述，数据库是唯一真相源，每行有一个单调递增的 version。缓存只是加速副本，允许短暂落后，但不允许“无限期落后”。具体要求：

  • 读路径：命中直接返回；未命中读库并回填。
  • 写路径：只改数据库，然后让缓存失效；不允许写者直接把新值写进缓存（避免写者之间的乱序覆盖成为第二个问题）。
  • 写者在提交后任意时刻崩溃，旧值最终被清除，且不依赖 TTL。
  • 失效命令可能重复、乱序到达，重复和乱序不能把缓存“修回”更旧的版本。

不在范围内：缓存集群、复制与故障切换、淘汰策略、多级缓存、跨地域部署。缓存使用 Java 写的替身，它与 memcached、Redis 的对应关系和差异在“缓存契约”一节单独写出。

教学规模假设

以下数字是教学假设，不是测量值，只用来说明各项开销怎样随参数变化：

参数 假设值
商品条目数 100 000
峰值读 / 写 2 000 次/秒 / 40 次/秒
值条目 TTL 300 秒
墓碑 TTL 60 秒
补删任务轮询间隔 1 秒
巡检周期 600 秒

由此可以估算三项额外成本。同时存在的墓碑数不超过“写入率 × 墓碑 TTL”，即 40 × 60 = 2 400 个（墓碑被回填替换后即不再存在，总数也受键数限制），每个只存版本号。outbox 每秒新增 40 行，已完成行需要按天清理，否则一天累积约 345 万行。巡检若每 600 秒覆盖全部 10 万个键，平均每秒增加约 167 次按主键读库。墓碑 TTL 与巡检周期都是可调的，代价分别落在缓存内存和数据库读负载上。

缓存契约

替身 VersionedCache 的每条命令在同一把锁内执行，相当于单线程服务端逐条处理命令。条目分为值条目（值 + 版本）和墓碑（只有版本）。时间来自注入的时钟，now >= expiresAt 即视为不存在。

表 25-1：缓存替身命令与真实组件的对应

替身命令 语义 memcached 文本协议 Redis
get 返回值条目或墓碑；调用方把墓碑当作未命中 get/gets GET 或读哈希
delete 删除条目并作废该键租约 delete DEL
add 键不存在才写入，墓碑也算存在 add，不满足返回 NOT_STORED SET … NX
cas 唯一值相等才写入；键不存在返回 NOT_FOUND cas，返回 EXISTS/NOT_FOUND SET … IFEQ（8.4.0 起，比较值相等）
putIfNewer 仅当版本更大时写入 基础协议无对应命令 Lua 脚本：读版本、比较、写入
invalidate(v) 写入版本为 v 的墓碑；现有版本不低于 v 时忽略 近似 md <key> I（标记 stale 并递增 CAS） Lua 脚本写墓碑并设过期
getOrLease / fillWithLease 未命中领令牌，持令牌回填 近似 mg <key> N… 返回 W 标志 无内建，需要脚本实现

memcached 的 cas 比较的是“相等”而非“更大”，而且只能用于已存在的键：协议文档写明对不存在的键返回 NOT_FOUND。回填恰好发生在未命中之后，此时没有可比较的唯一值，所以基础协议下回填只能用 add。meta 命令提供了更接近的工具：mg 的 E(token) 可以把外部的行版本作为 CAS 值，N(token) 在未命中时创建空占位并只给一个客户端返回 W（赢得回填权），md 的 I 不删除条目，而是标记 stale 并递增 CAS。按文档描述，持旧 CAS 的 ms … C<旧值> 因不相等而不会写入。这些对应只来自 protocol.txt 的阅读，本章没有运行 memcached。

Redis 文档保证 Lua 脚本原子执行，执行期间其他命令被阻塞，因此“读版本、比较、写入”可以放进一个脚本，与替身在锁内执行的效果相当。差异有三点：脚本访问的键必须作为参数显式传入；脚本缓存是易失的，重启或切换后需要重新加载；Redis 默认异步复制，文档明确说已确认的写在故障切换中仍可能丢失。最后一点意味着墓碑本身可能丢，丢失的后果等同于下文 C7 的“墓碑过期”。

数据模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CREATE TABLE item (
  id      text PRIMARY KEY,
  payload text NOT NULL,
  version bigint NOT NULL CHECK (version > 0)
);
CREATE TABLE cache_invalidation (
  seq        bigserial PRIMARY KEY,
  item_id    text NOT NULL REFERENCES item(id),
  version    bigint NOT NULL,
  created_at timestamptz NOT NULL DEFAULT now(),
  done_at    timestamptz,
  UNIQUE (item_id, version)
);
CREATE INDEX cache_invalidation_pending ON cache_invalidation (seq) WHERE done_at IS NULL;

版本由 UPDATE item SET … version = version + 1 … RETURNING version 在行锁下产生。PostgreSQL 16 的 Read Committed 规则是：并发更新同一行时，后来者等待先到者提交或回滚，然后在新行上继续，因此同一行的版本严格递增且不会重复。这是后面所有“比较版本”的前提：缓存端的比较只有在版本来自同一真相源、同一行时才有意义。cache_invalidation 是失效 outbox，UNIQUE (item_id, version) 保证同一版本只登记一次失效。

一个键在缓存里的状态

图 25-1：单个键的缓存状态与回填、失效的前置条件（版本条件写 + 带版本墓碑策略）

stateDiagram-v2
    [*] --> MISS
    MISS --> VALUE_v: putIfNewer(v)
    MISS --> TOMB_t: invalidate(t)
    VALUE_v --> VALUE_v: putIfNewer(w), 前提 w > v
    VALUE_v --> VALUE_v: putIfNewer(w), w ≤ v 拒绝 REJECTED
    VALUE_v --> TOMB_t: invalidate(t), 前提 t > v
    VALUE_v --> VALUE_v: invalidate(t), t ≤ v 忽略 IGNORED
    TOMB_t --> VALUE_v: putIfNewer(v), 前提 v ≥ t
    TOMB_t --> TOMB_t: putIfNewer(v), v < t 拒绝 REJECTED
    TOMB_t --> TOMB_t: invalidate(u), u > t 升级；u ≤ t 忽略
    VALUE_v --> MISS: TTL 到期
    TOMB_t --> MISS: 墓碑 TTL 到期（保护随之消失）

图里有两条不对称的边。值条目要求新版本严格更大，墓碑接受同版本：墓碑 v2 的含义是“v2 之前的值都过时”，v2 本身恰好是该接受的回填。失效遇到版本不低于自己的值条目时忽略，所以失效重复投递、乱序投递都不会删掉更新的值（重复投递见 C1、C11，乱序见 C6）。

正常路径

读者 read：查缓存，值条目命中即返回；未命中或遇到墓碑时读库，得到 (payload, version)，再按策略回填。写者 write：在一个事务里更新行并取回新版本，提交后用这个版本让缓存失效。C2 记录了这条路径：首次读未命中、读库 v1、回填 STORED；再次读命中；写入后缓存为 TOMB(v2)；下一次读回填 v2，缓存与数据库一致。

写者用自己事务返回的版本做失效，没有再读一次数据库。写者之间的失效顺序与提交顺序可能不同，但每条失效携带的版本由行锁序列决定，缓存端按版本取最大，到达顺序因此无关紧要。

旧值怎样回填进来

基线策略是 add 回填、delete 失效。C3 用闩锁把读者固定在“读库之后、回填之前”，写者在另一个线程、另一条连接上提交：

图 25-2：add 回填与 delete 失效的竞态（C3 的固定交错）

sequenceDiagram
    participant R as 读者线程
    participant C as 缓存
    participant DB as PostgreSQL
    participant W as 写者线程
    R->>C: get → MISS
    R->>DB: SELECT → v1
    Note over R: 闩锁停住（t=0）
    W->>DB: UPDATE … RETURNING version（v2），COMMIT
    W->>C: delete → 键不存在
    Note over R: t=5 放行
    R->>C: add(v1) → STORED
    Note over C: v1 存活到 t=105（5 + TTL 100）

输出中的对应行：

1
2
3
note 事件：t=0 读者未命中 → 读库 v1 → 停住；t=0 写者提交 v2 → delete；t=5 读者 add v1 = STORED
ok   negative control exposes: t=104（回填后 TTL-1）缓存仍返回 v1
ok   t=105 旧值随 TTL 过期 (expected=MISS, actual=MISS)

add 的语义本身没有问题：键确实不存在。问题在于“键不存在”同时可能表示“从未缓存过”和“刚被一次更新删除”，add 无法区分两者。写者的 delete 是在读者回填之前执行的，所以它没有可删的东西，而读者回填时也没有任何证据表明自己的数据已经过时。

修复路线比较

表 25-2：五种策略在同一交错下的结果

策略 回填命令 失效命令 慢读者回填 v1 的结果 用例
基线 add delete 写入，存活到 TTL C3
版本条件写，无墓碑 putIfNewer delete 写入（空键视为更旧） C4
版本条件写 + 带版本墓碑 putIfNewer invalidate(v) 拒绝 C5、C6
租约令牌 fillWithLease delete（作废令牌） 拒绝 C8
延迟双删 add delete，等待，再 delete 取决于回填落在第二次删除之前还是之后 C9

版本条件写为什么需要墓碑

只把回填改成“仅当版本更大”是不够的。写者的 delete 把键清空，读者回填 v1 时与“空”比较，v1 被当作更新写入。C4 的输出是 putIfNewer(v1) = STORED，数据库同时为 v2。比较需要有被比较的对象，所以失效时要留下一个记录了版本的墓碑，回填与墓碑比较才能发现 v1 过时。C5 在完全相同的交错下得到 REJECTED，缓存保持 TOMB(v2)。

C6 检查乱序：读者 A 读到 v1，写者 W2 提交 v2，读者 B 读到 v2，写者 W3 提交 v3；失效 v3 先到，失效 v2 后到。v2 失效被忽略，A 的 v1 回填、B 的 v2 回填都被拒绝，后续读回填 v3。B 的 v2 也被拒绝是正确的：B 读库时 v2 是新的，回填时已被 v3 取代。

这一保证的成立条件是：墓碑在慢读者回填时仍然存在。C7 把墓碑 TTL 设为 30，读者停顿 31，墓碑过期后 v1 重新写入成功。设读者“读库到回填”的最长停顿为 S_max，墓碑 TTL 为 T_tomb，失效到达时刻不早于提交时刻，那么条件 S_max < T_tomb 保证：提交前读到旧行的读者，要么在失效生效前回填、随后被墓碑覆盖，要么在回填时遇到墓碑或版本不低于 v 的值条目而被拒绝。前提是这段时间内保护条目没有被淘汰；墓碑被 v 的回填替换后，保护由值条目 v 承担，它被提前淘汰时同样失去保护。S_max 在 Java 进程里没有天然上界（垃圾回收停顿、线程被挂起都可能拉长它），所以 T_tomb 的取值是在缓存内存与可容忍停顿之间取舍。缓存因内存不足提前淘汰墓碑，效果与过期相同。

租约令牌

租约的概念出处是 NSDI 2013 的论文《Scaling Memcache at Facebook》；本环境无法取得全文，下面的令牌语义是本章自定的契约，不代表论文实现。未命中的读者通过 getOrLease 拿到令牌，回填时必须出示令牌；delete 会作废该键的令牌；令牌有自己的 TTL，过期即失效。已有有效令牌时，其他未命中者读库但不回填。

C8 的事件序列：A 领令牌、读 v1、停住；B 未命中，令牌已被 A 持有，B 读库不回填；写者提交 v2 并 delete，令牌作废；A 持旧令牌回填被拒绝；之后新的未命中者领到新令牌，回填 v2。租约同时限制了回填者的数量，热点键失效后不会有一批读者同时回填。租约与墓碑共享一个失败边界：都依赖失效命令确实送达。写者在提交后崩溃、delete 根本没有发出时，A 的令牌仍然有效，A 会把 v1 写进去。

延迟双删只能降低概率

延迟双删在第一次删除后等待 Δ，再删一次。C9 构造了两种顺序：(a) 读者回填落在两次删除之间，第二次删除把 v1 清掉；(b) 读者停顿超过 Δ，两次删除都在回填之前完成，v1 留到 TTL。Δ 只决定哪些停顿长度会被覆盖，停顿长度没有上界，所以总存在 (b)。它在这张表里的位置是负向对照：Δ 只缩小出错的停顿范围，出错条件本身没有消失。

关键实现

回填与失效的比较都在缓存端的一次原子操作内完成。替身中“仅当版本更大”的回填：

1
2
3
4
5
6
7
8
9
public synchronized Put putIfNewer(String key, String v, long version, long ttl) {
    Entry e = live(key);
    if (e != null) {
        boolean newer = e.tombstone() ? version >= e.version() : version > e.version();
        if (!newer) return Put.REJECTED;
    }
    items.put(key, value(v, version, ttl));
    return Put.STORED;
}

失效写墓碑，并作废该键的租约：

1
2
3
4
5
6
7
public synchronized Put invalidate(String key, long version, long tombTtl) {
    leases.remove(key);
    Entry e = live(key);
    if (e != null && e.version() >= version) return Put.IGNORED;
    items.put(key, new Entry(null, version, true, clock.getAsLong() + tombTtl, ++casCounter));
    return Put.STORED;
}

如果把“读当前版本”和“写入”拆成两次网络往返，两者之间又会出现一个交错窗口，所以真实部署里需要 Redis 脚本或等价的服务端原子命令。读路径中，afterDbRead 是测试注入点，生产代码里为空：

1
2
3
4
5
6
7
8
Store.Row row = Store.read(c, key);
afterDbRead.run();
VersionedCache.Put fill = switch (strategy) {
    case ADD_DELETE, DOUBLE_DELETE -> cache.add(key, row.payload(), row.version(), ttl);
    case VERSION_DELETE, VERSION_TOMBSTONE -> cache.putIfNewer(key, row.payload(), row.version(), ttl);
    case LEASE_DELETE -> token == 0 ? VersionedCache.Put.NOT_STORED
            : cache.fillWithLease(key, row.payload(), row.version(), ttl, token);
};

写路径中，行更新与失效登记在同一个事务里：

1
2
3
4
5
if (withOutbox) {
    Db.update(c, "INSERT INTO cache_invalidation(item_id, version) VALUES (?, ?)", id, v);
}
c.commit();
return v;

写者提交后崩溃

即使缓存端的比较全部正确，失效命令本身也可能没有发出。C11 用独立 JVM 作为写者：子进程在一个事务里更新行并插入 outbox，提交后打印 COMMITTED，然后阻塞在标准输入上等待父进程放行；父进程读到这一行后对子进程执行 kill -9。

图 25-3：写者提交后被 SIGKILL，outbox 补删修复（C11）

sequenceDiagram
    participant P as 父进程（缓存 + 补删任务）
    participant W as 写者 JVM
    participant DB as PostgreSQL
    W->>DB: BEGIN，UPDATE → v2，INSERT outbox(v2)，COMMIT
    W-->>P: stdout: COMMITTED 2
    P->>W: kill -9（退出码 137）
    Note over P: 缓存仍是 VALUE(v1)
    P->>DB: pg.sh restart-immediate
    P->>DB: 补删第 1 次：SELECT … FOR UPDATE SKIP LOCKED
    P->>P: invalidate(v2) → TOMB(v2)
    Note over P: 标记 done_at 之前注入失败，事务回滚
    P->>P: 读者回填 v2
    P->>DB: 补删第 2 次：重发 invalidate(v2) → IGNORED，标记 done_at，COMMIT

输出中的关键行：

1
2
3
4
5
note (b) 子进程 pid=1743303 输出 "COMMITTED 2" 后收到 kill -9，退出码 137
ok   (b) 缓存仍是 v1：失效没有发出 (expected=VALUE(v1,p1), actual=VALUE(v1,p1))
ok   (b) immediate 重启后 outbox 待处理行仍在 (expected=1, actual=1)
note (b) 补删第 1 次：claimed=1 marked=0 error=crashed after send, before mark
ok   (b) 重发的失效 v2 没有删掉已回填的 v2 (expected=VALUE(v2,p2), actual=VALUE(v2,p2))

这里的保证来自两步检查，而不是“用了事务”这件事本身。第一步是 outbox 行与数据更新同事务提交：只要 v2 可见，v2 的失效登记就一定存在；immediate 停机后两者一起由 WAL 恢复（C11 断言了重启后数据库仍为 v2、待处理行仍为 1）。第二步是补删任务“先发送、后标记”，并且失效命令对重复投递幂等：发送后、标记前失败只会导致重发，重发遇到已回填的 v2 时被忽略。如果顺序反过来（先标记完成再发送），发送前崩溃就会丢掉这次失效。

C12 是对照：写者不写 outbox，同样在提交后被 kill -9。补删任务找不到任何行，t=TTL-1 时缓存仍返回 v1，而数据库为 v2。

C13 与 C14 覆盖补删任务自身的故障。缓存端口不可达时，发送抛出连接异常，事务回滚，行保持待处理，缓存中的旧值继续存在；换到可达端口后补删完成。两个领取者各用一条连接、以 FOR UPDATE SKIP LOCKED 处理 20 行，结束时失效命令共发送 20 次。本用例没有断言两者的领取事务确实重叠，也没有去掉 SKIP LOCKED 的对照，因此只说明并发运行下没有出现重复发送。SKIP LOCKED 只负责“同一时刻一行只被一个领取者持有”；领取者崩溃后锁随事务释放，行会被再次领取，这时的重复发送仍由失效的幂等性兜住；领取者崩溃这一步本章没有单独实验，C11 的“发送后、标记前失败”是它在单个领取者上的等价情形。

巡检

outbox 覆盖写者崩溃，覆盖不了“缓存里已经存在一个旧值”的情况，例如基线策略留下的旧回填、墓碑过期后的回填，或者绕过写路径直接改库。巡检遍历缓存中的值条目，按主键读数据库版本，缓存版本更低时用数据库版本写墓碑。

C15 先用基线竞态制造一个旧值，再加一个正常键，第 1 轮 checked=2 stale=1 repaired=1，第 2 轮无旧值，之后读者回填 v2。第二部分检查巡检自身的竞态：巡检读到数据库 v2 之后、修复之前，写者提交 v3 并写下墓碑 v3；巡检的 v2 修复被忽略，缓存保持 TOMB(v3)。巡检的修复命令同样带版本，所以它的数据库读即使过时，也只会被缓存端拒绝，不会回退缓存。

巡检的失败边界是覆盖范围：它只检查自己枚举到的键。按缓存快照枚举时，键的数量受缓存规模限制；真实缓存一般不提供廉价的全量枚举，需要换成按数据库变更时间或按热点键抽样，代价与覆盖率要另行估算。

新鲜度窗口

定义：键在时刻 t_c 提交版本 v，旧值窗口 W 是从 t_c 起，到任何读路径都不再返回低于 v 的版本为止的时长。时间都以缓存服务端的时钟计。

1
2
3
4
5
6
7
8
9
D_sync  = 写者提交到失效命令在缓存端生效的时延
D_relay = P_relay + E_relay + R_cache      （轮询间隔 + 一轮领取与发送 + 缓存不可达期间的重试时长）
D_scan  = I_scan + E_scan                  （巡检周期 + 一轮巡检耗时）

带版本墓碑，且 S_max < T_tomb：
    写者正常：          W ≤ min(D_sync, S_max + T_ttl)
    写者提交后崩溃：    W ≤ min(D_relay, S_max + D_scan, S_max + T_ttl)
基线 add + delete、墓碑失效（S > T_tomb）、延迟双删未覆盖（S > Δ）：
    W ≤ S + min(T_ttl, D_scan)

提交之后、失效生效之前，慢读者可能把旧值回填进空键，这类条目的 TTL 与巡检覆盖都从回填时刻起算，所以公式中的 T_ttl、D_scan 项都要加上停顿 S。提交前就已缓存的旧值条目最迟在 T_ttl 内过期，被 S_max + T_ttl 覆盖。C3 是第二类的一次实例：S = 5、T_ttl = 100，没有巡检，旧值可见区间为 [0, 105)。

以下情况没有上界。T_ttl 为无穷（键不过期）、没有巡检、失效又丢失：C12 的情形如果键不设 TTL，旧值会一直保留，这是由 C12 推出的结论，没有单独运行。缓存长期不可达：R_cache 不受控，outbox 行只能一直待处理。基线策略下读者停顿 S 本身无界，回填可以晚到任意时刻。墓碑能否在真实组件中存活，还受淘汰和复制丢失影响，这两项都会让条件 S_max < T_tomb 失效。

并发压力

C10 不用闩锁：8 个线程、4 个键，每线程 300 次操作，约 20% 是写，读者在读库与回填之间随机停 0–2ms。只断言一个不变量：所有线程结束、缓存静止之后，每个值条目的版本等于数据库版本。本用例的墓碑 TTL 远大于运行时长（时钟不推进），墓碑在运行期间不会过期。

1
2
3
note VERSION_TOMBSTONE：写=452 回填成功=257 回填被拒=444 静止后旧值条目=0
ok   静止后每个值条目的版本都等于数据库版本 (expected=0, actual=0)
note ADD_DELETE（同种子，交错不可重复）：写=452 回填成功=312 未写入=265 静止后旧值条目=1（本次计数，不作断言）

“回填被拒”既包括过时回填，也包括两个读者读到同一版本时后到者的重复回填，计数只对应这一次运行。同种子的基线策略在本次证据中留下 1 个旧值条目。这个计数由调度决定，不作断言：随机调度不一定撞上窗口，某次运行为 0 也不能说明基线正确，可重复的证据只能来自 C3 那种固定交错。

证据与限制

表 25-3：本章保证、观察位置与失败边界

保证 成立条件 观察位置 失败边界
旧回填被拒绝 版本来自同一行的行锁序列；比较在缓存端原子执行；墓碑存活 ≥ S_max C5、C6 的 fill 结果与 TOMB(vN) 墓碑过期或被淘汰（C7）；版本不单调
失效幂等 失效携带版本，缓存取最大 C1、C6 的 IGNORED；C11 中重复失效被忽略，缓存仍为 v2 失效不带版本（普通 delete）时，重复投递会删掉已回填的新值，多一次未命中
写者崩溃后失效不丢 outbox 与数据更新同事务；补删先发送后标记 C11 的待处理行计数与重启后断言 缓存长期不可达（C13）；outbox 被清理而未处理
补删不并发重复 FOR UPDATE SKIP LOCKED 领取，事务持锁 C14 的发送次数 20（未观测事务重叠） 领取者崩溃后重领导致重复，依赖失效幂等
旧值可被发现 巡检能枚举到该键 C15 的 stale/repaired 未枚举的键

实验类别：C1 是带手动时钟的模型回放；C2–C10、C13–C15 是真实线程加真实 PostgreSQL 16 事务；C11、C12 是多进程集成，包含 kill -9 与 pg.sh restart-immediate。缓存是进程内替身，未运行 memcached 或 Redis，它们的对应关系只来自官方文档。TTL 用手动时钟推进，没有测量任何真实耗时，本章不报告吞吐或延迟数字。完整说明见证据目录中的 LIMITS.md。

本批导航

  • 上一篇：24 在线变更的数据兼容
  • 下一篇：26 租约互斥与资源端栅栏
  • 本批索引：仓库 batch-3/INDEX.md（阅读顺序与运行入口），batch-3/STATUS.md、batch-3/SOURCES.md
  • 运行入口：batch-3/examples/cache-consistency/run.sh
  • 证据目录：batch-3/evidence/25/
  • 本篇工程与证据快照：backend-systems-25.tar.gz（SHA-256 见同目录 backend-systems-25.tar.gz.sha256）。正文中的 examples/、evidence/、SOURCES.md 路径都相对仓库的 batch-3/ 目录，与快照包内布局一致。