maxmemory-policy · 近似 LRU · 8 位对数计数器

Redis：宁可采样也不要全局链表

前五页比的是命中率与元数据写入量，Redis 的取舍还多一个维度：内存。一个 SET k v 存下来的对象可能只有几十字节，为它挂一条双向链表就要多花两个指针。

1 · `maxmemory-policy` 的八个取值

内存达到 maxmemory 时的行为由 maxmemory-policy 决定，取值有八个，由两个正交的维度组合而成：候选集合是全体 key 还是只有带 TTL 的 key，以及在候选里按什么规则挑：

	全体 key	只在带 TTL 的 key 里挑
近似 LRU	`allkeys-lru`	`volatile-lru`
近似 LFU	`allkeys-lfu`	`volatile-lfu`
随机	`allkeys-random`	`volatile-random`
剩余 TTL 最短	无	`volatile-ttl`

第八个是 noeviction：不淘汰，写命令直接返回错误。它是默认值，因为把 Redis 当数据库用与当缓存用是两件事，静默丢数据比报错更糟。

volatile-* 这一族有个容易踩的坑：候选集合为空时（没有任何 key 带 TTL），它们的行为退化成 noeviction。

2 · 精确 LRU 的账

精确 LRU 要维护一条覆盖全部 key 的双向链表。这笔开销有三项：

第一项是内存。每个对象加两个指针，64 位机上是 16 字节。Redis 的 key 常常很短，值也可能只是一个计数器；对一个平均 60 字节的对象，16 字节是 27% 的额外开销。

第二项是写放大。每次读命令都要把对应结点摘下来挂到表头，六次指针写落在几条不同的 cache line 上。本系列的统一口径下这是每次命中 6 次元数据写。

第三项是共享结构。链表是全局的，任何一次访问都要改它。Redis 主流程是单线程的，这一项不构成锁竞争，但它仍然是一次随机访存，而且让 COW 场景（BGSAVE fork 之后）的页面被无谓地弄脏。

Redis 的选择是把这三项一起去掉：对象头 robj 里本来就有一个 24 位字段，allkeys-lru 模式下它存一个精度为秒的全局时钟采样值。命中路径上只写这一个字段，不多占任何内存，也没有链表可动。

代价是没有全局顺序，淘汰时无从知道谁最旧。

3 · 采样与淘汰池

allkeys-lru 的淘汰过程是：从 hash 表里随机取 maxmemory-samples 个 key（默认 5），比较它们的时钟字段，踢掉最旧的那个。

Redis 3.0 起加了一层淘汰池：一个容量 16 的数组，按空闲时间排序，长期保留历次采样里最好的候选。每次淘汰把新采到的 key 与池内已有的合并，从中取最旧的踢掉，剩下的留在池里供下次使用。池的作用是让不同轮次的采样结果累积，等效于放大了采样数。

图 3-1 · 采样数从 1 到 100 时三项度量的变化：与精确 LRU 的决策一致率、被淘汰者在「由旧到新」排序里的平均名次、以及最终命中率。可开关淘汰池并切换 workload。

4 · 三种度量给出三种结论

近似得好不好，度量方式不同结论差很多。容量 200、20000 次访问的 Zipf workload 实测：

`maxmemory-samples`	决策一致率	平均名次（共 200）	命中率
1	0.45%	100.4	56.1%
3	1.56%	50.0	60.0%
5（默认）	2.58%	32.2	60.6%
10	4.81%	17.8	61.1%
20	10.06%	9.0	61.1%
50	22.51%	3.5	61.2%
100	39.50%	1.5	61.2%
精确 LRU	100%	0.0	61.2%

第一列是原先打算用的主度量：淘汰的那个 key 是不是恰好等于精确 LRU 会淘汰的那个。跑出来它几乎没有信息量——从 $N$ 个候选里抽中「唯一正确答案」的概率本来就约等于 $N / c$ ， $N = 5$ 、 $c = 200$ 时理论值 2.5%，实测 2.58%。这个度量量的是采样比例，不是近似质量。

第二列才有意义：被淘汰者在「由旧到新」的排序里排第几。 $N = 5$ 时平均排在第 32 名，也就是落在最旧的 16% 里； $N = 10$ 时是 8.9%， $N = 50$ 时是 1.8%。它随 $N$ 的下降接近 $c / (N + 1)$ 。

第三列是最终真正在乎的东西，而它对 $N$ 极不敏感：默认的 5 已经拿到精确 LRU 的 60.6/61.2 = 99.0%，加到 10 就只差 0.1 个百分点。Redis 文档建议大多数场景不必调它，实测支持这个建议。

淘汰池的效果落在第二列上：同样 $N = 10$ ，不开池平均名次 17.8，开池 4.0——相当于把采样数放大到 50 上下，而每次淘汰的采样成本不变。

5 · 8 位对数计数器

allkeys-lfu 模式下那 24 位字段被切成两半：高 16 位存上次衰减的时刻（单位是分钟），低 8 位是访问计数器。

8 位只能数到 255，而一个热 key 一天可能被访问上百万次。Redis 的办法是让计数器按对数增长：

P(\text{计数器加一}) = \frac{1}{(\text{counter} - \text{LFU\_INIT\_VAL}) \cdot \text{lfu-log-factor} + 1}

新对象的计数器从 LFU_INIT_VAL = 5 起步（不从 0 起步，否则新对象立刻被淘汰）。lfu-log-factor 默认 10 时，各档的期望访问次数是：涨到 6 只要 1 次，涨到 10 要 105 次，涨到 15 要 460 次，涨到 255 约 $3.1 \times 10^5$ 次。8 个 bit 覆盖了从个位数到几十万的访问量级。单次实测会在期望值上下大幅波动，因为每一格都是一个几何分布。

这个设计还顺带把命中路径的写入量压得更低：计数器越高，加一的概率越小，也就越少真的写那个字段。实测 Zipf workload 上 lfu-log-factor 取 10 时每次访问只写 0.081 个字段，是近似 LRU 的 1/7.5、是精确 LRU 的 1/45。代价是分辨率：factor 越大，两个热度相近的 key 越难区分，实测命中率从 factor 0 的 65.8% 降到 factor 100 的 63.8%。

图 5-1 · 8 位对数计数器随访问次数的爬升，以及 lfu-log-factor 对命中率与写入量的影响。可调参数并切换到衰减视图。

6 · `lfu-decay-time` 与老化

计数器只增不减就会重演淘汰策略是在猜未来 §4 的 cache pollution。Redis 的老化机制是 LFUDecrAndReturn：读取计数器时先看距上次衰减过了几分钟，除以 lfu-decay-time 得到周期数，按周期数把计数器减下来。

lfu-decay-time 取 0 有一个不直观的含义：它不是「立刻衰减」，而是完全不衰减。源码里那一行是 num_periods = server.lfu_decay_time ? elapsed / server.lfu_decay_time : 0，0 走的是三目运算的另一支。文档里这条写得含糊，读代码才踏实。

老化的效果在热点迁移的 workload 上最明显。实测突发热点、容量 200：lfu-decay-time 取 0（不衰减）命中率 86.7%，取 1 分钟 88.7%，取 5 分钟与 60 分钟又都回到 86.7%——衰减周期长到覆盖不了热点的迁移周期，就等于没有衰减。这两个时间尺度必须匹配，而 Redis 只能给出默认值 1，真实的匹配点取决于流量。

7 · 参考文献

Redis. Key eviction. Redis 文档 develop/reference/eviction 一节，含 maxmemory-policy 全部取值与 maxmemory-samples 的取值建议。
Redis. redis/src/evict.c. evictionPoolPopulate、performEvictions、LFULogIncr、LFUDecrAndReturn 的实现。
Sanfilippo, S. (2016). Random notes on improving the Redis LRU algorithm. Redis 官方博客，介绍淘汰池的动机与效果对比图。
Einziger, G., Friedman, R., & Manes, B. (2017). TinyLFU: a highly efficient cache admission policy. ACM Transactions on Storage, 13(4), Article 35.