考古现场 #09 · REDIS约 3000 字 · 10 分钟 · 源码版本 redis-stableRedis 8.10.1 · 所有行号可复核先说结论给一亿个 key 记过期时间要花多少内存Redis 花了十五年用采样算法优化删除效率直到 7.4/8.0 才换了个思路——换数据结构。ebuckets 把临近过期的项按时间聚簇进分桶让每项的过期元数据成本从约 40 字节压到 8 字节量级。这不是快了一点是换了一个量纲。这道题每个人都在面试里背过答案惰性删除加定期采样。但背完就过去了。真正值得问的是这套采样方案内存账本上到底亏在哪答案藏在 Redis 8.x 的 src/ebuckets.h 里——这个文件的头注释前 117 行本身就是一篇官方设计文档我们今天就从它开始挖。一、旧世界的账本每条 TTL 一次全款购房先看旧账本长什么样。在 redisDb 结构里除了主 keyspace还有一个专门的 expires 字典server.h:1228kvstore *expires。每个设置了 TTL 的 key除了自己的键值对还要在 expires 字典里再占一个哈希槽位。槽位里存什么一个 64 位毫秒时间戳外加字典 entry 的开销、key 指针、分配器碎片——粗算下来一条 TTL 记账几十个字节而且不管你的业务 TTL 是 5 秒还是 5 天全都平铺在这一个字典里彼此毫无关联。按 50 字节一算一亿个带 TTL 的 key 光是过期记账就是 5GB 上下——还没算这一个亿散落在字典各处带来的缓存不友好。删除侧的办法是采样主动过期每轮从 expires 字典里随机摸一把摸到过期的就删访问时撞上过期 key 则由惰性删除兜底expireIfNeeded。参数至今刻在 expire.c 头部expire.c:96-100行代码96#define ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 20 /* Keys for each DB loop. */97#define ACTIVE_EXPIRE_CYCLE_FAST_DURATION 1000 /* Microseconds. */98#define ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 25 /* Max % of CPU to use. */99#define ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE 10 /* % of stale keys after which */src/expire.c:96-100 · 每轮采样 20 个 key、快速周期限 1 毫秒、CPU 限额 25%、脏度超 10% 才加码采样循环的主体在 activeExpireCycleexpire.c:287 起每轮按 config_keys_per_loop 抽查412-413 行统计过期比例超过 10% 就继续下一轮同时受 CPU 时间上限约束347 行。抽查用的探针也很有年代感——直接下探到哈希表的桶数组逐槽看415-424 行的注释坦白这段代码和 dict.c 耦合但十年没怎么变过。惰性删除补漏访问到 key 时才检查。抽查这个动作本身就说明了一切面对一亿个散落的到期时间系统连下一个谁要过期都答不上来只能靠随机采样去撞。这套机制的核心矛盾在于它只优化什么时候删从不优化过期信息存在哪。一亿条散落的到期时间戳字典照样开一亿个槽互相之间隔着随机分布的内存距离。算法已经卷到极限了——25% 的 CPU 预算就这么多采样永远是在赌概率。二、ebuckets把到期时间本身变成索引ebuckets.h 的头注释开宗明义先算了一笔内存账ebuckets.h:16-23行代码16* Instead of holding a distinct item in each leaf of the rax-tree we can aggregate17* items into small segments and hold it in each leaf. This way we can avoid18* frequent modification of the rax-tree, since many of the modifications19* will be done only at the segment level. It will also save memory because20* rax-tree can be costly, around 40 bytes per leaf (with rax-key limited to 621* bytes). Whereas each additional item in the segment will cost the size of the22* next pointer in a list (8 bytes) and few more bytes for maintenance of the23* segment.src/ebuckets.h:16-23 · 官方原话rax 叶子约 40 字节段内追加一项只要一个 next 指针 8 字节注意这个数字出处40 字节对 8 字节的对比不是营销文案是 ebuckets.h 第 20-22 行白纸黑字写的。压缩手段是聚簇把过期时间相近的项聚进同一个 segment一个 segment 作为一个叶子挂在 rax 树本质是基树/B 树上rax 的 key 就是桶的过期时间下界。树只在桶这一层维护桶里成百上千个临近过期的项每多加一个只花一个链表指针。原先每个叶子独占一条记录的模式变成了一个叶子挂一段班车。层级结构一共四层ebuckets.h:25-47ebuckets顶层小时就是链表、大了才转 rax105-109 行→ bucket一个时间段区间→ segment单链表封顶 EB_SEG_MAX_ITEMS→ item自己内嵌过期元数据。segment 有个聪明的设计——循环单链表38-42 行只存一个 next 指针省内存但最后一个元素回指段头这样从中间删除某一项时不用再爬 rax 树找前驱。桶满了怎么办裂桶。注释里给了一个具体例子ebuckets.h:57-60区间 [11-76] 的桶装到 16 项满了就按实际数据裂成 [11-36] 和 [37-76] 两桶。但如果满桶里所有项的过期时间一模一样就裂不动了——这时改挂扩展段62-75 行同一条时间线上链多一节车厢。原来如此这是把插入时维护有序结构的成本转移给了过期批量到站的收益——临近过期的项物理上住在同一块内存里主动过期时按桶扫过去缓存命中率是采样算法永远给不了的。这套设计还带一个务实的降级路径ebuckets 不是一上来就建树。头注释 105-109 行写明项少的时候它就是一个朴素的链表越过阈值才升级成 rax——几个 key 的库没必要为百十来字节付一棵树的固定开销。数据结构跟着数据量走和哈希表 rehash、listpack 转 hashtable 是同一个工程哲学只不过这里连过期索引本身都遵循它。增删两边也是对仗的。加一个项先按过期时间算出桶 keyEB_BUCKET_KEY(exptime) exptime PRECISIONebuckets.h:146顺树而下找到对应 segment挂在链尾多数情况树纹丝不动删一个项靠 ExpireMeta 里的 firstItemBucket/lastItemBucket 标志直接定位上下文173-180 行的注释这两个标志就是为了让段内操作不必从树根重新爬起。连内存整理都做了适配——ebScanDefrag314 行允许 defrag 线程带着分配器回调进来扫段挪内存游标式分片不打断主流程。一个只服务过期这一件事的专用结构把通用结构的每一分浪费都抠掉了。三、ExpireMeta一条 TTL 被压进了 48 个比特树省了每项自己的过期时间也存在压缩空间。ebuckets 要求每项内嵌一个 ExpireMeta 结构ebuckets.h:161-212行代码162typedef struct ExpireMeta {163/* 48bits of unix-time in msec. This value is sufficient to represent, in164* unix-time, until the date of 02 August, 10889165*/166uint32_t expireTimeLo; /* Low bits of expireTime. */167uint16_t expireTimeHi; /* High bits of expireTime. */169unsigned int lastInSegment : 1; /* Last item in segment. */173unsigned int firstItemBucket : 1; /* First item in bucket. */177unsigned int lastItemBucket : 1; /* Last item in bucket. */181unsigned int numItems : 5; /* Only first item in segment. */184unsigned int trash : 1;193unsigned int userData : 3;204void *next;src/ebuckets.h:162-204 · 时间戳砍成 48 位段管理信息用位域塞进缝隙三处刀法值得细看。第一刀unix 毫秒时间戳本来要 64 位ebuckets 砍成 48 位——注释算得很得意48 位毫秒时间戳够用到公元 10889 年 8 月 2 日163-164 行砍掉 16 位就是每个时间戳省 2 字节。读取时 ebGetMetaExpTime 把 Lo/Hi 两截拼回来317-319 行。第二刀lastInSegment、firstItemBucket 这些段管理标志全是 1 比特位域numItems 只在段首维护181 行。第三刀连这项是不是残留垃圾都用一个 trash 位标记184 行删除后这个 ExpireMeta 空间还能被安全复用O(1) 查 TTL 时顺便验真伪。原来如此所谓位宽压缩不是黑魔法就是死磕每一比特都要物尽其用——48 位够了就不用 64 位一个标志位能解决的问题绝不新开一个 int。还有一层保险rax 的 key 精度刻意放粗。头注释 77-95 行解释主动过期容忍 1 秒级的粗粒度被动删除仍然毫秒精确这样 rax key 从 6 字节缩到约 4.5 字节树更浅、分叉更少。当前代码里 EB_BUCKET_KEY_PRECISION 还是 0注释里留着一行 /* TBD: modify to 10 */ebuckets.h:143——一个还没拧下去的优化旋钮被源码诚实地记录着。四、HFE过期粒度下探到 hash 字段级ebuckets 的第一个大客户是 7.4 引入的 HFEHash Field Expiration——hash 的单个字段可以单独设 TTL。这直接炸出了老方案的另一个痛点字段级过期如果沿用 expires 字典内存开销会按字段数而不是key 数增长采样算法更是无从下手字典里根本没有这些字段。HFE 的存储编码有两套。小 hash 用 listpackExt_hash.c 的注释说得非常直白t_hash.c:1222-1234在 listpack 的 field-value 对后面再追加一项 TTL整个 listpack 变成三元组序列没设 TTL 的字段存零编码只花 2 字节整个 listpack 按 TTL 升序排列最先过期的字段永远排最前面行代码1232* Fields in the listpack will be ordered by TTL. Field with the smallest expiry1233* time will be the first item. Fields without TTL will be at the end of the1234* listpack. This way, it is easier/faster to find expired items.src/t_hash.c:1232-1234 · 按 TTL 排序后找过期字段从搜索问题变成了从头截断问题大 hashOBJ_ENCODING_HT则走 ebuckets 正主路线每个 hash 自己的字典元数据里挂一个 hfe 实例过期时直接 ebExpire(dictExpireMeta-hfe, hashFieldExpireBucketsType, info)t_hash.c:3691-3694。字段过期时间被聚簇进分桶主动过期按桶收割——t_hash.c:1352-1355 的 listpack 版本也享受同样待遇遍历时一旦碰到没过期的字段就立刻 break因为后面按时间排着队肯定都还没到点。删除也便宜一次 lpDeleteRange(lp, 0, expired * 3)t_hash.c:1377把头部整段截掉。hash 里最后一个字段也过期了怎么办hashTypeExpire 的收尾逻辑t_hash.c:3719-3727给了答案整个 hash 从 keyspace 里删掉照常发 del 通知——字段级过期的语义完全对齐 key 级过期连 keyspace notification 都有专门的事件每批字段过期会发 hexpired 事件3708 行计数器 server.stat_expired_subkeys 同步累加1364 行。你在 INFO 里看到的过期字段数源头就在这两行。全局协调靠 redisDb 里新加的 estore *subexpiresserver.h:1229每条 hash 用自己最早的字段过期时间注册进去activeExpireCycle 每轮开头先调 activeSubexpiresCycleexpire.c:387注释明说先做字段过期因为 ebuckets 为主动过期而生。字段级主动过期还有独立配额expire.c:102HFE_DB_BASE_ACTIVE_EXPIRE_FIELDS_PER_SEC 10000和 key 级采样互不挤占。原来如此HFE 不是给 hash 加了个定时器列表而是把 key 级过期的整套内存经济学原样复制到了字段级——每个字段的过期元数据只花一个 next 指针加 48 个比特。五、可搬运的结论带走这三条本文就没白读① 当采样算法开始赌概率先怀疑数据表示。25% CPU 上限、10% 脏度阈值这套参数调了十年没本质变化。ebuckets 的突破点不在删得更快而在让临近过期的数据物理相邻。你的系统里如果有按概率清理的定时任务先问问数据为什么是随机分布的。② 聚簇 共享索引是内存压缩的通用公式。40 字节一条记录变成本桶第 N 项只花 8 字节省的是每个人都复制一份索引的钱。时间轮、LSM、跳表分层本质都是这个公式。③ 位宽压缩要敢于按业务上限裁剪。48 位时间戳够用到 10889 年是源码注释里的原话。确定上限、砍掉冗余位、留 trash 位防误用——这套刀法可以直接搬到你自己的元数据设计里。 下一期预告 · 考古现场 #10《边加载边追平Redis 全量同步的双通道革命》。考古工具说明本系列所有结论均经检索定位 行号精读双源验证——先用全文索引从 Redis 源码块中定位证据再回到源码逐行复核。文中行号基于 redis-stableRedis 8.10.1src/ 目录其他版本可能偏移欢迎对照你手头的源码树验证。本文是「中间件考古」系列第 09 篇。星标本号每周一篇行号级源码深潜。引用说明本文仅少量摘录 Redis 源码RSALv2/SSPLv1/AGPLv3 三选一许可证详见仓库 LICENSE用于技术解读版权归原作者所有。转载本文请保留出处与作者信息。