企业官网建设流程全解析

Caffeine 时间轮深度剖析：O(1) 实现缓存条目过期的完整指南

【免费下载链接】caffeineA high performance caching library for Java项目地址: https://gitcode.com/gh_mirrors/ca/caffeine

Caffeine 是 Java 生态中公认性能第一的内存缓存库（A high performance caching library for Java）。它支持按访问/写入时间过期、大小淘汰、异步刷新等能力。当缓存中同时存在百万条、且每条过期时间各不相同的条目时，如何"又快又省"地判断谁该过期？Caffeine 的答案是内置的TimerWheel 时间轮：一条分层时间轮，让"新增过期事件、取消过期事件、触发过期事件"三步全部达到O(1) 均摊复杂度。本文带你从零看懂它的原理。

一、问题背景：为什么缓存过期这么难？

先想一个朴素方案：给每条缓存条目设置一个独立定时器，时间到就删掉。听起来简单，但在百万级条目、高并发写入的场景下，独立定时器会带来海量线程唤醒和定时器对象开销——每写一条就付一次时间成本。

Caffeine 选择了另一条路：不逐条计时，而是把"到期时间"映射到一个环形桶数组上，整体惰性推进。核心实现在 TimerWheel.java，其类注释明确说明：这是一个分层时间轮（hierarchical timer wheel），基于经典论文Hashed and Hierarchical Timing Wheels的算法思想。

上图为 Caffeine 内部架构总览，右侧的 TimerWheel 齿轮正是本文主角：它向 Protected 队列发送 evict（淘汰）信号，而下方的expireEntries维护任务则是它的"驱动轮"。

二、Caffeine 五级时间轮结构详解

时间轮的本质是一个环形桶数组：指针按固定周期转动，每转到一个桶，就处理这个桶里所有"到点"的条目。Caffeine 把时间轮做成了 5 级联动的"分层时间轮"，定义在源码第 54–61 行：

static final int[] BUCKETS = { 64, 64, 32, 4, 1 }; // 每格跨度依次约为：1.07 秒、1.14 分钟、1.22 小时、1.63 天、6.5 天

设计有两个巧思：

• 跨度都取 2 的幂：桶下标通过"右移 + 位与掩码"（time >>> SHIFT[i] & (length - 1)）一次算出，完全避免除法和取模，在 CPU 层面近乎零成本。这是 O(1) 的第一个来源。
• 分层级联（cascading）：调度一个未来事件时，findBucket() 从秒轮开始找第一个"装得下"的轮子放入；当高层轮子转动一格，就会把事件"下放"到更精细的低层轮子。远期事件先挂顶层，不占细粒度轮的开销，级联成本被轮子转动次数摊薄——这是amortized O(1)的第二个来源。

三、O(1) 三大操作：增、删、触发

每个桶内部是一条双向循环链表，桶头是一个哨兵节点（Sentinel）。链表结构让三种操作都退化为"指针改两个"：

1. 调度（schedule）：新条目追加到目标桶链表尾部——纯 O(1)，无需排序。条目更新过期时间时，reschedule() 先摘除再重挂，同样 O(1)。
2. 取消（deschedule）：条目被删除或淘汰时，从链表中 unlink 自己——双向链表的优势在此，无需遍历定位。
3. 触发（expire）：轮子转动时整桶处理（见下节），单桶转移用transfer()一次链表拼接完成，不逐节点搬运。

对比优先级队列方案（每条 O(log n) 插入/删除），时间轮在条目过期时间高度分散的缓存场景下优势明显。

四、惰性推进与淘汰预算：不产生延迟尖刺的关键

时间轮最精妙的设计：它从不自己走，而是等缓存的维护周期到来时才推进。过期是"延迟执行"（deferred）的。

每当读写触发缓存维护时，BoundedLocalCache.expireVariableEntries() 会调用 TimerWheel.advance()，传入当前时间和一个淘汰预算EXPIRATION_THRESHOLD = 1_000：

• advance()从秒轮到顶轮依次计算"走了多少格"，逐桶扫描：
  • 条目真实过期时间已到 → 调用cache.evictEntry(node, RemovalCause.EXPIRED, ...)淘汰；
  • 尚未到期（例如从高层轮子下放下来但时间还没到）→ 重新调度到低层更精确的桶；
• 预算用完即停：淘汰满 1000 条后，时间轮被回拨到推进前的位置（nanos = previousTimeNanos），剩余积压留给下一次维护周期处理。

这套机制的意义在于：无论积压了多少过期条目，单次维护的耗时都有上界（最多处理 1000 条），不会在某一次get上突然卡顿。这正是"O(1) 均摊"的工程落地——用时间换平稳，用维护周期的小额预算平滑掉过期风暴。

上图是 Caffeine 与各主流缓存库的只读吞吐量基准对比。惰性时间轮让读路径几乎不为"过期检查"付费，这也是 Caffeine 长期领跑读性能的核心原因之一。

五、什么时候才会用到时间轮？

一个容易混淆的点：固定过期策略（expireAfterWrite/expireAfterAccess）因为所有条目寿命相同，Caffeine 只用简单的 FIFO 双端队列从尾部扫即可，不需要时间轮。

时间轮服务于可变过期（variable expiry）：当你用Expiry接口为每条 key/value 动态指定不同的过期时长时（例如热点数据存 1 小时、冷门数据存 5 分钟），条目在 维护任务中写入时 才会被timerWheel().schedule(node)挂上轮子。此外，getExpirationDelay()还能快速预估"下一个桶多久到期"，供维护调度参考。

配套的单元测试 TimerWheelTest.java 和性能基准 TimerWheelBenchmark.java 可作为验证其行为与性能的入口。

六、总结：三个设计要点值得借鉴

1. 环形桶 + 双向链表：把"排序/比较"问题转化为"定位桶 + 改指针"，增删触发全 O(1)；
2. 分层级联：远期事件挂粗粒度轮子，转动时逐层下放，空间与时间都被摊薄；
3. 惰性推进 + 预算回拨：过期检查搭维护周期的"顺风车"，单次耗时封顶，高并发下无延迟尖刺。

时间轮并非缓存专属——Kafka 的延迟消息、Netty 的定时任务（HashedWheelTimer）也采用同源思想。理解了 Caffeine 这份教科书级的 Java 实现，你在任何需要海量定时事件的系统里，都会自然想到这一招。

【免费下载链接】caffeineA high performance caching library for Java项目地址: https://gitcode.com/gh_mirrors/ca/caffeine