【Redis / 缓存内核】maxmemory 策略：近似 LRU/LFU 与 MEMORY DOCTOR

第 7 篇 讲的是已过期 key 如何被清扫；本篇讲仍有效 key 在内存触顶时如何被踢出。maxmemory 与 maxmemory-policy 是缓存角色 Redis 的核心旋钮，但源码实现的不是操作系统课本里的真 LRU，而是用固定内存的采样 + 淘汰池近似——理解这一层，才能解释「明明开了 LRU 却淘汰了热 key」类故障。

与相邻系列的分工：

本文锚定 Redis OSS 7.4.x evict.c、object.c（MEMORY DOCTOR），并对照站内 页面置换算法 与 Buffer Pool 中的 LRU/CLOCK 讨论。

本文是「Redis / 缓存内核」系列第 8 篇（共 16 篇）。→ 系列目录

版本锚定：Redis OSS 7.4 / 8.x；默认 maxmemory-samples 为 5，LFU_INIT_VAL 为 5。

一、问题：内存上限下的在线驱逐

当 zmalloc_used_memory() 超过 maxmemory（且非 noeviction），写路径在 processCommand 里调用 performEvictions() 尝试腾出 mem_tofree。这是典型的 demand paging 式在线决策：只见过去访问，不见未来——与 Bélády OPT 不可实现性同一抽象（详见 页面置换 第一节）。

Redis 与 OS 页置换的关键差异：

二、策略矩阵：volatile × allkeys

config.c 注册 8 种 policy（MAXMEMORY_*）：

volatile-* 只从 db->expires 采样——无 TTL 的 key 永不作为淘汰候选，内存触顶时可能直接 OOM 拒绝写入。纯缓存场景若忘记给 key 设 TTL，volatile-lru 等于「只删有过期时间的 subset」，常踩坑。

allkeys-* 从 db->keys 采样，把 Redis 当整个数据集的上限容器；与 Buffer Pool 驱逐脏页不同，Redis 驱逐的是应用可见的 key，且会发 evicted 通知并写 AOF/复制。

三、近似 LRU：24 位时钟与淘汰池

3.1 LRU 时钟

真 LRU 需维护全序访问链表。Redis 在 redisObject 里用 24 位 lru 字段存上次访问的压缩时钟：

#define LRU_CLOCK_RESOLUTION 1000  /* 毫秒；1000 表示秒级粒度 */

unsigned int getLRUClock(void) {
    return (mstime() / LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

读/写命中时 LRU_CLOCK() 写入 o->lru。estimateObjectIdleTime() 用当前时钟减 o->lru 得 idle 毫秒——这是 CLOCK 族思路：不移动链表，只打时间戳（对照 页面置换 CLOCK 节）。

当 1000/hz <= LRU_CLOCK_RESOLUTION 时，主循环在 serverCron 预计算 server.lruclock，避免每次访问调 mstime()——精度与 hz 绑定，高 hz 提高时钟分辨率。

3.2 采样与 eviction pool

performEvictions() 在 LRU/LFU/TTL 类策略下调用 evictionPoolPopulate()：每次从候选 dict 随机抽 maxmemory-samples 个 key（默认 5，可配 1–64），把 idle 最大的若干名填入固定大小 淘汰池 EvictionPoolLRU[EVPOOL_SIZE]（16 槽）。

/* evict.c 文件头注释（节选） */
/* Every time there is a key to expire, we sample N keys (usually ~5)
 * to populate a pool of M keys (EVPOOL_SIZE = 16).
 * After the pool is populated, the best key in the pool is expired. */

然后从池尾（idle 最大）取候选，若 key 仍存在则 dbGenericDelete()。池内可能残留已删 key 的「幽灵」条目，下次再填充。

与真 LRU 的差距：一次驱逐决策只看 \(N\) 个随机样本中的最优，全局热 key 若不在样本中就可能被误踢——扫描型 workload（全表遍历）下近似 LRU 表现差，与 Megiddo & Modha 在 ARC 论文（IBM, 2003）中指出的「纯 LRU 对频率与最近性失衡」是不同维度的问题，但现象类似：单次顺序扫描可冲掉整个淘汰池视角下的「冷」数据。

3.3 LFU 编码

volatile-lfu / allkeys-lfu 复用 lru 字段，高 16 位为衰减时间，低 8 位为对数计数器（LFU_INIT_VAL = 5 起步）。LFUDecrAndReturn() 做时间衰减，LFULogIncr() 在访问时亚线性增频——用 8 位近似 Morris 计数思想，避免 per-key 高频计数器内存。

运维可调 lfu-log-factor、lfu-decay-time（OBJECT FREQ 读当前计数）。LFU 对周期性热点（如每分钟刷新的报表 key）通常优于秒级 LRU 时钟，但参数敏感，无 universal 最优（与 ARC 自适应论点形成对照，Redis 未实现 ARC）。

3.4 volatile-ttl 与 random

volatile-ttl 从 expires 采样后选 剩余 TTL 最短 的 key（evictionTimeProc），适合「优先保留长 TTL 会话」的业务，但不保证保留访问频率高的 key。

random 策略一次随机选一个候选 dict 槽中的 key，无池；实现最便宜，行为最难预测，仅适合均匀访问或调试。

flowchart TD
  ov["memory > maxmemory"]
  pe["performEvictions()"]
  sample["evictionPoolPopulate<br/>N = maxmemory-samples"]
  pool["EvictionPool[16]<br/>max idle / min freq"]
  del["dbGenericDelete + lazyfree?"]
  ov --> pe --> sample --> pool --> del

四、performEvictions 与延迟

performEvictions() 循环驱逐直到 mem_freed >= mem_tofree 或无法继续。每次删除走 dbGenericDelete(..., server.lazyfree_lazy_eviction, DB_FLAG_KEY_EVICTED)，大对象可异步释放（第 7 篇）。

注意：

• 驱逐在写命令路径上同步发生，连续驱逐多个 key 会拉长延迟；latency 监控里有 eviction-del 事件。
• 有从节点时，每 16 个 key 可能 flushSlavesOutputBuffers()，避免复制缓冲堆积。
• maxmemory-eviction-tenacity（7.x）控制单次驱逐循环的时间上限，防止极端情况下饥饿。

noeviction 下 performEvictions 返回 EVICT_FAIL，写命令得到 OOM 类错误，读命令仍可服务——这是「缓存」与「存储」角色分界：宁可拒写也不默默丢有效数据（除非业务接受）。与 architecture/17 的 缓存穿透/击穿 不同：那些是 应用未命中后的 DB 压力；本篇是 Redis 进程内内存已满 时的 key 驱逐。

4.1 单线程边界：驱逐占主线程

performEvictions() 由写路径 processCommand 调用（第 2 篇），与 IO threads 无关：

IO threads 再快，高 maxmemory 触顶 + 大 value 删除 仍会在主线程形成尾延迟——排障时勿只调 io-threads（第 15 篇）。

五、MEMORY DOCTOR：概念化信号

MEMORY DOCTOR 调用 getMemoryDoctorReport()（object.c），基于 getMemoryOverheadData() 做规则化启发诊断，不是 AI 分析。核心判定阈值（概念摘要）：

与淘汰的关系：high_frag / big_peak 不直接说明 LRU 选错，但可区分「policy 误踢热 key」与「内存碎片/lazyfree 未归还」。驱逐本身会制造大量释放块，加剧碎片——长期高驱逐率应同时看 MEMORY PURGE、activedefrag 与 key 设计（大 key、无 TTL）。

本站不粘贴本机 MEMORY DOCTOR 输出；读者可在实例上执行 MEMORY DOCTOR 对照上表理解字段。

七、学术谱系与研究讨论

7.1 谱系

谱系：Bélády OPT（1966）→ LRU 链表（教科书）→ CLOCK 近似（Corbató 等）→ Redis 采样池（evict.c 注释自 2014 起演进）→ LFU 对数计数（Redis 4.0+）→ ARC/2Q（Megiddo & Modha, FAST 2003；Redis 未实现）。算法层对照见 storage/66 缓存工程 淘汰算法节；本篇钉 Redis 源码取舍。

7.2 争论

1. 近似 LRU 是否「够好」：Redis 官方文档明确写的是 approximated LRU。对 heavy-tailed 热点，LFU 或业务侧 TTL 常更稳；对扫描，应靠 allkeys-lfu 或客户端避免冷数据大面积进入。
2. volatile vs allkeys 语义：volatile-* 隐含「无 TTL 数据更宝贵」；若业务相反，应 allkeys-* 并给常驻 key 显式长 TTL 或 PERSIST——与 architecture/17 Cache-Aside「删缓存 vs 设 TTL」是 不同层 的决策。
3. 采样数 N 的权衡：maxmemory-samples 增大提高近似质量，但单次 performEvictions CPU 上升——与 PostgreSQL Buffer Pool 的 clock sweep 扫全表不同，Redis 刻意限制为常数级采样（Buffer Pool 对照）。

7.3 开放问题

1. Redis 是否会引入 ARC 类自适应策略——主线至今无承诺；Megiddo & Modha (FAST 2003) 的 WA/RA 权衡在 Redis 里由 policy + samples 手工近似。
2. Cluster 下 slot 倾斜：淘汰池按 kvstore 分片，极端倾斜 slot 的 跨 slot 公平性 需结合 第 13 篇；无 peer-reviewed 统一结论。
3. 驱逐 vs 应用击穿：architecture/17 的 singleflight / 布隆 防 DB 被打穿；本篇 误踢热 key 导致 miss 上升——现象类似但根因与修复 不在同一层。

八、常见误解

8.1 「开了 LRU 就等于操作系统 LRU」

不对。Redis 是 N 随机样本 + 16 槽池 + 秒级时钟，不维护全局 LRU 序。热 key 不在样本中仍可能被踢。

8.2 「淘汰和过期是一回事」

不对。过期看 expires 时间戳；淘汰看 maxmemory-policy 与访问元数据。过期 key 应先被 第 7 篇 路径删除；若仍超内存，才驱逐未过期 key。

8.3 「volatile-lru 会删所有 key」

只删设了 TTL 的 key。无 TTL 的 key 在 volatile-* 下受保护，可能导致 write OOM。

8.4 「LFU 不需要预热」

新 key 以 LFU_INIT_VAL 起步，需若干次访问才能积累频率；极短生命周期的 key 可能被 LFU 误判为冷数据。

九、小结

三句话小结

1. 八种 policy 先分 volatile/allkeys 候选集，再在 LRU/LFU/TTL/random 间选 victim。
2. 近似 LRU/LFU 靠 redisObject.lru 时钟/计数 + 每次约 5 个随机样本填入 16 槽淘汰池，不是全局链表。
3. MEMORY DOCTOR 用碎片、峰值、客户端/复制缓冲等启发规则指路，不替代对 maxmemory-policy 与 workload 的分析。

上一篇：TTL 与过期

下一篇：RDB 快照

参考资料

源码（Redis OSS 7.4.x，A 级）

1. src/evict.c — performEvictions、evictionPoolPopulate、estimateObjectIdleTime。
2. src/object.c — getMemoryDoctorReport、getMemoryOverheadData。
3. src/server.h — MAXMEMORY_*、LRU_CLOCK_RESOLUTION、LFU_INIT_VAL。

官方文档

4. Redis Documentation v7.x, Key eviction、maxmemory-samples、lfu-log-factor。A 级。

核心论文

5. Megiddo, N. & Modha, D., ARC: A Self-Tuning, Low Overhead Replacement Cache, USENIX FAST 2003（自适应替换对照；Redis 未实现 ARC）。A 级。

站内互链

6. 页面置换算法、Buffer Pool、storage/66 缓存工程（算法层）。
7. architecture/17 缓存架构（应用层击穿/雪崩）、第 2 篇 事件循环（主线程驱逐）、第 3 篇 对象（lru 字段）、第 7 篇 TTL、系列 index。