12. 惰性与摊销:渐进式 rehash 与过期删除

0. 本章先解决什么问题

有些操作单次代价巨大:搬迁一张百万桶的哈希表、删除百万个过期 key、把整个程序载入内存。硬着头皮一次做完,就是一次长停顿。这一族机制的思路:

惰性:推迟到真正需要的那一刻才做,没人要就永远不做
摊销:拆碎了摊到之后的每次小操作里,每次多干一点点
共同点:大代价不再一次性支付,代价的”形状”从一根尖刺
变成一片薄雾(或者变成别人头上的一根小刺)

Redis 是这对思想最密集的用户:渐进式 rehash、过期删除、lazy free 三件套全在这一章讲透,然后向下接操作系统的按需调页,向上接 Java 集合的均摊扩容、JVM 的懒加载和 JIT、框架的延迟加载。

惰性与摊销的通用结构

这张图怎么读

左边是一次性支付:一根长尖刺挡住所有请求。右边是两种拆法:惰性把它推到”被用到”的时刻,摊销把它切碎进每次操作。下方是各层实例。

1. Redis 渐进式 rehash:摊销的教科书

1.1 为什么不能一次搬完

dict 是数组加链表的哈希表(结构在 dict),负载因子高了要扩容,扩容要把所有 entry 按新桶数重新哈希搬家。Java 的 HashMap 就是一次性搬完,单机内存操作没人在意。Redis 不行:

一张一亿 key 的 dict,一次性 rehash 要秒级
第 1 章的铁律: 事件循环里不许有慢操作
一次 rehash = 全体客户端卡一秒 = 生产事故
所以必须把这一秒切碎

1.2 双表结构和搬迁规则

dict 里常备两张表: ht0和 ht1
外加一个游标 rehashidx(-1 表示没在搬)

开始 rehash: 给 ht[1] 分配新容量(扩容为第一个 >= 2 倍
used 的 2 的幂),rehashidx 置 0
搬迁的两个驱动源:

顺路搬: 每次增删改查这个 dict,顺手把 ht[0] 上
rehashidx 指向的桶整个搬去 ht[1],游标加一
(空桶会连跳,但有上限,防止连续空桶把一次操作拖长)
定时搬: serverCron 里每次给 1 毫秒的预算主动搬一批,
防止冷 dict(没人访问)永远搬不完
搬完: ht[0] 释放,ht[1] 转正成 ht[0],rehashidx 回 -1

1.3 搬迁期间的读写规则

两张表并存时,每个操作都要多想一步,规则设计得非常讲究:

查找/删除:先查 ht[0],没有再查 ht1
新增:只写 ht[1]
-> 保证 ht[0] 只减不增,搬迁必然有终点
(如果新增还进 ht[0],搬迁可能永远追不上写入)
期间的代价:每个操作多查一张表、顺手搬一个桶,
单次操作的常数变大,但没有任何一次操作是慢的

1.4 触发条件里还藏着上一章的联动

扩容:负载因子 >= 1 时扩容;
但如果正在 BGSAVE/AOF 重写,阈值提高到 5 才扩
原因: 第 10 章的 fork 写时复制。rehash 是海量内存写操作,
会把共享页大面积拷出来,撞上快照期就是内存尖刺的平方
-> 宁可先忍受高负载因子的链表变长
缩容:负载因子 < 0.1 时缩容,同样渐进

一个机制的触发条件里写着对另一个机制的忌惮,这种咬合是判断”真懂了”的试金石。

2. Redis 过期删除:惰性和定期的双保险

2.1 三种可选策略先摆开

一个 key 到了过期时间,什么时候真正删掉它?三个选项:

定时删除:每个 key 挂一个定时器,到点就删
最精准,但百万 key 百万定时器,定时器管理本身压垮 CPU,弃用
惰性删除:不主动删,谁访问这个 key,访问前先检查过期,过期才删
零额外开销,但没人访问的过期 key 永远赖在内存里
定期删除:周期性抽查一批,删掉其中过期的
开销可控,清理不彻底
Redis 的选择:惰性 + 定期双保险,各补对方的洞

2.2 惰性删除:expireIfNeeded

每条读写命令执行前,都先对目标 key 做一次过期检查:过期了就先删掉(或标记删除),再按”key 不存在”继续执行命令。访问路径顺路完成清理,这是”谁需要谁付钱”的惰性本色。

2.3 定期删除:activeExpireCycle 的抽样循环

惰性删除的洞(没人访问的 key 永远不清)由定期任务补,它的算法值得逐行记:

serverCron 周期触发(默认每秒 10 次),对每个库:

从”设了过期时间的 key”里随机抽 20 个
删掉其中已过期的
如果这 20 个里过期的超过 25%,说明过期堆积严重,
回到第 1 步继续抽(脏得越狠,清得越勤)
无论如何,整个循环有时间上限(约 25 毫秒量级),
到点收工,剩下的下轮再说

这个设计的每一笔都在平衡”清理彻底”和”不卡主线程”:抽样代替全扫(全扫百万 key 又是一根尖刺)、25% 的反馈闸门(按脏的程度自适应力度)、硬时间上限(第 1 章铁律的又一次落实)。

2.4 三个配套语义

从库的过期:从库不主动删过期 key,等主库删了以后
同步过来的 DEL 命令(保证主从一致,删除权归主库)。
从库上读到”已过期但主库还没删”的 key 时按不存在返回
内存淘汰是另一件事:过期删除管”到期的”,
maxmemory 淘汰管”内存满了”(第 3 章的八种策略),
一个 key 可能没到期就被淘汰,也可能过了期还没被清
统计口径:过期但未删除的 key 不算在有效数据里,
但仍占内存,这就是”明明设了 TTL 内存却不下降”的常见答案

完整源码在过期与淘汰。

3. lazy free:把释放也惰性掉

删除大对象的内存释放是 O(n) 的(百万成员的集合要逐个 free),第 1 章提过它是卡事件循环的经典元凶。4.0 的答案:

UNLINK: 从键空间摘除引用(瞬间完成,别人再也看不见它),
实际的内存释放丢给后台线程慢慢做
FLUSHALL ASYNC / FLUSHDB ASYNC: 同理,换库表引用,旧库后台清
配置化: lazyfree-lazy-eviction / expire / server-del 让
淘汰、过期、隐式删除也走异步释放
思想: “逻辑删除”和”物理回收”分离,
前者必须立刻(正确性),后者可以惰性(纯代价)

MySQL 的删除同款思路:DELETE 只在页内打标记(第 2 章讲过文件不缩小),purge 线程之后清理;undo 的清理也由后台按可见性推进(第 10 章长事务挡的就是它)。“标记 + 后台回收”是删除操作的通用形态。

4. 操作系统:按需调页,惰性的祖师爷

第 2 章缺页机制铺过底,这里按惰性视角归位:

exec 加载程序:不真读代码进内存,只建好页表映射,
执行到哪页,缺页异常现场加载哪页
-> 巨大的二进制秒级启动,没跑到的代码永远不占内存
malloc 大块内存:只登记地址区间,摸到才给物理页
fork:第 10 章的 COW 本质就是”把拷贝惰性到写时”
mmap 文件:映射建好,读哪页加载哪页,
Kafka 索引、RocksDB 都靠它把”读文件”变成”读内存”
页缓存的写回:脏页攒着延后刷(把”落盘”惰性化),
这条已经在第 3、4 章反复出现

5. Java 世界的惰性与摊销

5.1 ArrayList 扩容:均摊 O(1) 的算术

扩容策略: 满了就按 1.5 倍申请新数组,全量拷贝
一次扩容是 O(n),但摊开算:
从 1 个元素长到 n 个,总拷贝量是 n 的等比级数和,约 2n~3n
平摊到每次 add 上是常数 -> 均摊 O(1)
关键区分: 均摊 O(1) 和每次 O(1) 是两回事,
那一次 O(n) 真实存在,落在触发扩容的那个倒霉调用上
工程姿势: 已知容量就 new ArrayList<>(10000),
把所有尖刺提前到构造时一次付清
HashMap 的 resize 同理一次性搬完(对照 1.1: 单机内存
操作可以接受尖刺,Redis 的事件循环不能,同一个问题
两种答案的分界线就是”停顿有没有全局受害者”)

5.2 JVM:类加载和 JIT 都是惰性

类加载:类不是启动时全加载的,首次主动使用
(new、静态访问、反射)才触发加载和初始化
-> 启动快;代价是配置错误延迟爆炸
(错误的类路径要等第一次用到那个类才报 NoClassDefFoundError)
JIT 分层编译:所有代码先解释执行(零编译成本),
调用次数攒够了升 C1 编译,热点中的热点再升 C2 深度优化
-> “值得优化”这个判断本身被惰性化了:
用运行时统计代替提前猜测,编译预算全花在真热点上
代价: 预热期。压测要先跑几分钟再采数,就是在等 JIT 付完惰性的账

5.3 框架:延迟加载和它的 N+1 陷阱

Spring lazy-init: Bean 推迟到首次注入/获取时创建,
换启动速度,代价同类加载: 配置错误运行时才炸
MyBatis 延迟加载: 关联对象先不查,返回一个代理,
真正访问 order.getUser() 时才触发第二条 SQL
陷阱 N+1: 循环里访问 100 个订单的 user,
就是 1 条主查询 + 100 条惰性触发的子查询
-> 惰性把”一次大 join”拆成了”N 次小查询”,
固定成本(往返)被乘了 N 倍,恰好撞在上一章批处理的枪口上
处方: 循环场景改 join 一次取全,或批量预载
Stream 惰性求值: 中间操作(map/filter)只记账不执行,
终结操作(collect/forEach)才把整条流水线跑起来,
让短路操作(findFirst/limit)可以只算需要的部分

6. 反噬:代价没有消失,只是换了形状和债主

尖刺转移: 摊销的那一次 O(n) 落在触发者头上
(扩容的那次 add、缺页的那次访问、预热期的那批请求),
P99 延迟毛刺经常就是各种惰性机制在收账
错误延迟: 惰性把”启动时就能发现的问题”推到运行时
(懒加载 Bean 的错配、首次触类的 NoClassDefFoundError),
关键路径的东西宁可饿汉式,把失败留在启动阶段
债务堆积: 惰性依赖”之后有机会做”,
机会不来债就滚雪球: 没人访问的过期 key 靠定期任务兜底,
定期任务预算不足时内存持续虚高;
compaction 追不上写入时读放大失控(第 4 章 LSM 的账)
常数变大: 摊销期间每个操作都背额外工作
(rehash 双表查找、渐进搬桶),吞吐略降是买停顿平滑的价
选型判据一句话: 停顿有全局受害者(事件循环、在线服务)就摊销,
没有就让尖刺一次付清(离线任务、构造时预分配);
关键路径饿汉,非关键路径惰性

7. 联系实际:排查清单

现象:Redis 设了 TTL,内存却不见下降
方向:过期 key 没被访问也没被抽中,仍占内存;
量大时查定期删除预算,或业务侧主动触碰
现象:Redis 平稳运行,某段时间每个命令都略变慢
方向:正在渐进式 rehash(INFO 里 dict 状态可见),
双表查找 + 顺路搬桶的常数,属正常,看着它搬完即可
现象:接口 P99 偶发毛刺,和流量无关
方向:排查各类”收账时刻”: 扩容、GC、缺页、
JIT 去优化、AOF 重写的 fork

现象: 应用启动秒开,第一波请求集体超时
方向: 惰性的账在预热期集中支付: 类加载 + JIT 解释执行

连接池空仓 + 本地缓存全冷;上线要带预热流量

现象:页面循环取关联数据,SQL 日志刷出上百条相似查询
方向:MyBatis 延迟加载的 N+1,改 join 或批量预载
现象:MySQL DELETE 了一半数据,磁盘反而更忙
方向:purge 线程在后台收账,标记删除的清理不是免费的

8. 学完本章你能解决什么问题

惰性和摊销的区别是什么,共同改变的是代价的什么属性?
渐进式 rehash 的双表、游标、两个驱动源、读写规则分别是什么?
“新增只写 ht[1]“这条规则在保什么性质?
rehash 为什么在 BGSAVE 期间提高扩容阈值?
三种过期删除策略的取舍是什么,Redis 的双保险各补谁的洞?
activeExpireCycle 的 20 个、25%、时间上限各在平衡什么?
从库为什么不主动删过期 key?
UNLINK 和 DEL 的本质区别是什么,“逻辑删除与物理回收分离”还在哪出现?
均摊 O(1) 和每次 O(1) 差在哪,工程上怎么把尖刺提前付清?
N+1 问题怎么由惰性产生,为什么说它撞在批处理的枪口上?

核心一句话:大代价要么推迟到被需要时(惰性),要么拆碎进每次操作(摊销);代价从不消失,只换形状和债主,尖刺转移、错误延迟、债务堆积就是三种收账方式;停顿有没有全局受害者,决定该让谁买单。

laziness - amortization