失效顺序造成的陈旧值

一句话总结

缓存给出与 DB 不同的值的时间，取决于读写操作以什么顺序交错，而不是“有没有做失效”。同一种策略，也可能因为一个顺序而只错几 ms；而如果没有 TTL，就会一直错到下一次写入到来。

为什么需要它

在 cache-aside 中，读取是“检查缓存 → 没有就读 DB → 放进缓存”三步，写入是“DB 提交 + 缓存处理”两步。每两步之间，都可能插进别的请求的步骤。引用最多的记录是 Facebook 的 Scaling Memcache at Facebook（NSDI 2013）。他们在写入路径上不是更新缓存，而是删除缓存，理由写的是“因为删除是幂等的”。

即便如此，问题依然存在。论文把 stale set 定义为“Web 服务器放进缓存的值不是本应放进去的最新值”，并解释说，它产生于并发更新被重新排序的时候。解决办法是 lease。缓存未命中时，memcached 会给出绑定在该键上的 64 位令牌，客户端放值时一并带上令牌，如果在此期间来了 delete，令牌就会失效，放入被拒绝。

模式本身——cache-aside、失效、惊群（stampede）、TTL 抖动、stale-while-revalidate——由“Redis 与缓存”课程讲。本模块是在它的下一层，确定性地重现交错顺序，并统计陈旧读取的次数。

工作原理

有三种有代表性的交错（R 是读取，W 是写入）。

名称	顺序	留下的东西
迟到的读取的 set	R 未命中 → R 从 DB 读到 v0 …… W 提交（v1）→ W 删除 …… R 把 v0 set 进去	比删除来得更晚的 v0
先删除，后提交	W 删除 …… R 未命中 → 读到 v0 → set v0 …… W 提交（v1）	提交之前被重新填入的 v0
两次写入的逆序 set	W1 提交（v1）…… W2 提交（v2）→ set v2 …… W1 set v1	迟到的 v1

第一行即使“写入后删除”也挡不住。延迟双删（删除 → 提交 → 稍后再删除一次）只有在迟到的 set 先于第二次删除到达时才能挡住。如果等待时间比读取的延迟短，就毫无作用。而读取路径上的最坏延迟（GC 停顿、重试、慢网络），不会体现在平时指标的中位数里，所以这种策略通常好好的，只是偶尔崩溃。第二行就是“先删除再写入”不安全的原因——在删除与提交之间的窗口里，读取会把旧值重新填进去。

版本比较（CAS）。 如果在缓存里把值和 DB 版本一起放进去，并在缓存内部以原子方式检查“只有严格大于缓存中当前版本时才覆盖”，迟到的旧版本就无法覆盖新版本。Redis 事务文档写道，它通过 WATCH 提供 check-and-set。被监视的键如果在 EXEC 之前被改动，整个事务会中止并返回 null。自 8.4 起，对字符串键的 SET 也有 IFEQ 这类比较选项。memcache 的 lease 也是同样的想法，论文把它比作 load-link/store-conditional。如果把比较方向写反，想防止的事情就会原样发生。

TTL 是上限，但不以提交为基准。 TTL 从放进缓存的那一刻开始计算。旧值如果迟到，它会从进来的时刻起存活 TTL 那么久。所以陈旧度的上限不是 TTL，而是“迟到的 set 的延迟 + TTL”。如果没有 TTL，插进来的旧值会一直留到下一次写入到来。Amazon Builders' Library 的缓存文章也写道，TTL 是根据客户端能容忍多陈旧的数据，以及数据有多静态来选择的。

测量什么。 本模块以提交时刻为基准来定义陈旧度：读取结束的时刻 − 取代该读取所返回版本的那次提交的时刻。如果从写入开始的时刻算起，就会混进提交之前的时间，而那段时间 DB 里也是旧值，并不是缓存在撒谎。

在现场相遇的样子

同一篇论文把缓解 thundering herd 列为 lease 的第二种用途，并报告说，在易受这个问题影响的键上，DB 查询峰值从每秒 17K 降到了 1.3K——惊群方面的内容，接着看“Redis 与缓存”课程。把缓存失效作为事件流出去的设计（outbox），由“微服务架构”课程讲；消息到来两次或顺序颠倒的场景，由“订单重复到达，又消失了一次”课程讲。实验中的五个场景，是为了逐一重现上表的顺序而用手选定的时刻和延迟，评分器所使用的隐藏场景，则是按同样的规则随机混合而成的。无论哪一种，在这里要问的问题都一样：在这个顺序下，缓存错了多久，它会自己恢复吗？

下一项实验要做什么

把写入、读取策略作为生成器嵌入确定性模拟器。在五个场景里测出六种策略的陈旧读取数和最大陈旧度，挑出永远不会自行恢复的组合，再用数字选出一种策略。