1. 项目概述与技术背景1.1 为什么需要时间轮从一次真实性能问题说起先说个我自己的经历。去年在维护公司的一个消息推送网关时发现定时任务这块总是出幺蛾子。当时用的是ScheduledThreadPoolExecutor每个连接维护一个定时任务用于超时检测连接量一上来内存和CPU双双报警。排查发现大量定时任务其实是短期任务几秒甚至几百毫秒后就该到期但线程池里的每个任务都对应一个DelayedWorkQueue节点入队出队、锁竞争、唤醒开销全堆在一起性能自然上不去。后来我翻 Netty 源码时注意到了HashedWheelTimer第一反应是这名字有点意思——哈希加时间轮。研究完才发现它解决的核心问题和我的场景完全一致大量短期、零散的定时任务如何用最小的开销高效调度。简单说HashedWheelTimer是 Netty 中一个基于时间轮算法实现的定时任务调度器。它不像ScheduledThreadPoolExecutor那样用一个优先队列维护所有任务而是把时间划分成一个个固定的 tick滴答用环形数组存储任务指针每 tick 前进一格。提交任务时通过取模哈希计算任务应该放在哪个槽位指针转到对应槽位时直接遍历该槽位上的任务链表判断哪些到期就执行。这个设计思路的巧妙之处在于新增任务和到期任务检查的时间复杂度都接近 O(1)避免了优先队列在任务量大时的排序和插入开销。1.2 这个项目能解决哪些问题适合用HashedWheelTimer的场景我总结下来有这么几类连接超时管理像 Netty 服务端对每个 Channel 维护空闲检测、读超时、写超时这类任务数量大、单次执行时间极短、对绝对时间的精确性要求不高。心跳检测与重连机制客户端定时发送心跳服务端定时检查上次心跳时间超时则断开连接典型的时间轮应用。批量延迟任务比如延迟重试、延迟消息投递。注意这里说的是“批量”如果延迟任务很少比如一秒钟就几个时间轮反而没有优势。低精度的定时调度能容忍几十到几百毫秒误差的场景。时间轮的 tick 越小精度越高但代价是更频繁的指针扫描需要做权衡。至于适合谁来学习我觉得只要是写 Java 后端、做中间件、研究网络框架源码的人都应该花一个下午把HashedWheelTimer弄明白。它背后不只是一个类的实现更是一种“用空间换时间、用近似换效率”的工程思维理解了它再看很多定时调度、延迟队列的设计都会豁然开朗。2. 时间轮算法的整体设计与思路拆解2.1 从电梯间里的时钟说起时间轮的基本模型理解时间轮最好的类比是我们办公楼下电梯间的钟表。表盘被 12 个刻度分成 12 格指针每走一格表示一小时。假如你想设置一个“8小时后提醒我”你不需要盯着秒针数 28800 下你只需要记住“当前在 3 点的位置8 格以后是 11 点”然后该干嘛干嘛等指针转到 11 点的时候自然就知道该提醒了。时间轮算法就是把这个物理模型搬到了内存里。HashedWheelTimer内部维护一个环形数组数组的每个元素是一个链表头在代码里叫HashedWheelBucket数组长度叫wheelSize。另一个核心参数是tickDuration表示指针每走一格需要的时间。两者相乘就是这个时间轮能表达的最大延迟时间比如默认wheelSize512、tickDuration100ms那 wheel 一圈就是 512 × 100ms 51.2 秒。任务提交时算出它还差多少个 tick 到期然后对 wheelSize 取模决定放进哪个槽位。比如 tickDuration 是 100ms某任务需要在 1.5 秒后执行那就是 15 个 tick 后到期15 mod 512 15放进第 15 个槽位同时记录一个round圈数字段表示 15 除以 512 的商这里是 0。等等这里有个问题——如果任务延迟超过一整圈比如 60 秒呢60 秒 600 个 tick600 mod 512 88放入槽位 88round 600 / 512 1。指针第一次转到槽位 88 时发现该任务 round 为 1说明还没到跳过等指针跑完一整圈再次转到槽位 88 时把 round 减 1 变为 0此时任务才真正到期执行。注意这种设计下数组的每个槽位里可能有多个任务它们的到期时间并不相同而是“放在同一个槽位但 round 不同”。所以遍历某个槽位的链表时要逐个检查 round 是否为 0不为 0 的只减 round不执行。2.2 为什么选环形数组而不是优先队列很多人第一次接触时间轮会问ScheduledThreadPoolExecutor用二叉堆优先队列不是挺好吗插入和删除都是 O(log n)为什么还要做时间轮关键差异在于任务的分布特征。优先队列的每个节点都独立维护一块延时信息新增任务时需要在堆里做调整取出最近到期的任务也要调整堆结构。当任务量达到几万甚至几十万时堆操作的日志复杂度叠加锁竞争开销非常可观。环形数组的方案把“比较时间”这件事变成了“看位置”。新增一个任务只需要算一下它该进哪个槽位然后头插法丢进链表这个操作是 O(1) 的指针每 tick 前进一格只需处理当前槽位的链表而链表上的任务数量通常远小于总任务数。最理想的情况下任务的插入和触发都不需要全局排序。当然它也有明显的代价时间粒度被离散化了。原定 1.05 秒后执行的任务如果 tickDuration 是 100ms实际最早可能在 1.1 秒后才执行误差最多一个 tick。这正是那句经典的工程权衡——大多数超时检测、心跳场景根本不在乎这几十毫秒但换来的吞吐量提升是实打实的。2.3 哈希在时间轮里扮演什么角色名字里的Hashed指的就是取模运算。Java 里的取模对负数有特殊处理-1 % 512是 -1所以 Netty 源码里会看到对tick做index tick (wheelSize - 1)这类位运算。为什么可以用位运算因为代码里强制了wheelSize必须是 2 的幂这样才能用与操作代替取模进一步压缩计算开销。这里有个实际的例子默认 wheelSize 512二进制是 1000000000那么mask wheelSize - 1 511 0111111111。任意 tick 值跟 511 做与运算结果范围必然落在 0 到 511这就是哈希映射。因为 2 的幂这个约束整个哈希过程只需要一次位运算无需除法性能极好。我一直觉得把取模哈希和环形数组放在一起是时间轮最优雅的设计——哈希决定了“放哪个格子”环形结构决定了“格子怎么转”。3. 核心数据结构与关键源码实现解析3.1 三个核心类Timer、Bucket、TimeoutHashedWheelTimer的结构可以分为三层记熟这三个类整体逻辑就有了骨架第一层是HashedWheelTimer本身。它负责创建Worker线程、推进指针、维护整个环形数组。对外暴露三个方法start()、stop()、newTimeout()。其中newTimeout(TimerTask task, long delay, TimeUnit unit)是提交任务的核心入口。第二层是HashedWheelBucket。它是环形数组中的槽位本质是一个HashedWheelTimeout的双向链表。注意用的是双向链表因为删除中间节点时双向链表可以在 O(1) 时间内完成不需要从头遍历。第三层是HashedWheelTimeout。它包装了提交进来的TimerTask持有任务的到期时间deadline、所在槽位bucket、剩余圈数remainingRounds以及任务自身的状态。这三个类层层嵌套Timer 有多个 BucketBucket 有多个 TimeoutTimeout 里才是用户真正的任务逻辑。理解了这层结构再看源码就不会迷路。3.2 tickDuration 与 wheelSize 的数学关系先看两个参数的关系式。假设 wheelSize WtickDuration T时间轮一整圈的时间就是 W × T。任务延迟 delay 会被折算成 tick 数ticks delay / T * 1000单位换算后或者更严谨地说计算任务是“在第几个 tick 被触发”。Netty 源码中newTimeout的核心计算逻辑大致如下这是简化版本真实实现会更细long deadline System.nanoTime() unit.toNanos(delay) - startTime; long calculated deadline / tickDuration; long remainingRounds (calculated - tick) / wheelSize; int stopIndex (int) (calculated mask);这里有个小坑deadline减去了startTime也就是时间轮启动的时间。因为时间轮内部所有的 tick 计算都是相对启动时刻的不用绝对时间戳避免手动维护一个随时变化的基准点。remainingRounds的计算有意思。calculated是任务到期的总 tick 数tick是当前指针所在的 tick 数两者相减就是还需要多少个 tick 到期再除以 wheelSize 得到剩余圈数。比如当前 tick 是 10任务总 tick 是 520那么还差 510 个 tick510 / 512 0说明任务在接下来不到一圈内就会到期。3.3 任务入槽的完整流程演示我画过很多次时间轮任务入槽的流程图其实核心就是四步调用newTimeout()传入TimerTask和 delay。计算 deadline并校验 delay 不能为负。Netty 还做了一层保护如果 delay 超过Long.MAX_VALUE / 1000 / 1000直接抛异常防止溢出。如果时间轮尚未启动自动调用start()。启动由startTime和 Worker 线程共同完成。调用transferTimeoutsToBuckets()把任务真正放入对应的槽位。最后一步值得展开。为什么单独有个transferTimeoutsToBuckets方法因为任务提交时 Worker 线程可能正在推进指针如果每提交一个任务就立刻操作环形数组就需要加锁保护这在高并发下是性能杀手。Netty 的处理方式是newTimeout先把任务丢进一个Timeouts队列这是HashedWheelTimer内部的一个普通队列然后在每次处理 tick 时一次性把队列里的任务批量转移到 Bucket 中。这个设计彻底避免了写锁代价是最多延迟一个 tick 的入槽时间完全可接受。我摘一段关键逻辑帮助理解private void transferTimeoutsToBuckets() { for (int i 0; i 100000; i) { HashedWheelTimeout timeout timeouts.poll(); if (timeout null) { break; } if (timeout.state() ! HashedWheelTimeout.ST_INIT) { continue; } timeout.deadline startTime; long calculated timeout.deadline / tickDuration; long remainingRounds (calculated - tick) / wheelSize; timeout.remainingRounds remainingRounds; final long ticks Math.max(calculated, tick); int stopIndex (int) (ticks mask); HashedWheelBucket bucket wheel[stopIndex]; bucket.addTimeout(timeout); } }注意里面有个100000的循环上限这是防止某个 tick 时间内提交的任务太多无限转移导致 Worker 线程饿死。如果单次转移超过 10 万个任务剩下的只能等下一个 tick 再处理。实际场景中 10 万这个阈值已经非常大了但知道这个保护机制的存在有助于理解极端场景下的行为。4. 调度执行流程与 Worker 线程运转机制4.1 Worker 线程时间轮的心跳时间轮能转起来靠的是一个后台线程Worker。它在start()时通过ThreadFactory创建名字默认是HashedWheelTimer-1、HashedWheelTimer-2这样的格式。Worker 线程做的事可以抽象成一句话循环执行“等待一个 tick、转移队列任务、推进指针、处理当前槽位所有到期任务、处理取消任务”这五步。启动时的startTime是一个很重要的基准点。在start()方法中会把当前系统时间System.nanoTime()记录下来作为基准之后所有任务计算都用相对时间这避免了系统时间被调整时导致任务错乱。worker 线程的核心循环逻辑private void run() { do { final long deadline waitForNextTick(); if (deadline 0) { transferTimeoutsToBuckets(); tick; int idx (int) (tick mask); HashedWheelBucket bucket wheel[idx]; bucket.expireTimeouts(deadline); } } while (!WORKER_STATE_UPDATER.get(this) WORKER_STATE_SHUTDOWN); }4.2 waitForNextTick不是 busy loop 而是精准睡眠waitForNextTick()这个方法的实现值得单独讲。它的作用是在当前 tick 的起始时刻开始睡到下一个 tick 应该开始的时刻然后返回那个时刻的值。private long waitForNextTick() { long deadline tickDuration * (tick 1); for (;;) { long currentTime System.nanoTime() - startTime; long sleepTimeMs (deadline - currentTime 999999) / 1000000; if (sleepTimeMs 0) { break; } try { Thread.sleep(sleepTimeMs); } catch (InterruptedException e) { // 处理中断逻辑 } } return deadline; }看到那个(deadline - currentTime 999999) / 1000000了吗这是把纳秒转成毫秒并向上取整。为什么向上取整因为Thread.sleep的参数是毫秒级的向下取整会导致提前唤醒指针还没到时间就开始处理多了一轮空转。向上取整可以让线程多睡那么不到 1 毫秒总体更稳妥。还有一个细节Thread.sleep被中断时代码没有直接退出而是继续进入下一次循环重新计算剩余睡眠时间。这保证了即使有中断信号循环也会继续直到真正到点。这是线程协作式取消的一个标准写法——中断只作为信号具体是否退出由业务逻辑决定。4.3 槽位任务的执行expireTimeouts 的完整逻辑Worker 推进指针找到当前槽位后调用bucket.expireTimeouts(deadline)。这个方法会遍历槽位里的双向链表任务状态不是ST_INIT的直接移除。比如已经被取消的任务此时正好顺带清理掉。remainingRounds大于 0 的减 1本轮不执行继续留在链表里。这对应延迟时间超过一圈的任务。remainingRounds等于 0且deadline小于等于当前时间说明到期了。把任务从链表移除并通过expireTimeout里调用的task.run(timeout)执行用户逻辑。执行完成后再标记状态为ST_EXPIRED方便后续清理。有个细节容易忽略执行用户任务时Worker 线程会逐个调用任务的run方法如果某个任务执行时间过长会让整个 Worker 线程卡住后续所有任务都延迟。也就是说时间轮假设提交的任务都是短小精悍的。如果你要在任务里做耗时操作请自己丢到业务线程池去执行不要阻塞 Worker。我还观察到一个细节expireTimeouts里对每个过期任务执行时传入了 deadline 而不是当前时刻。这是因为任务的到期判定应该基于时间轮的内部时间基准而不是System.currentTimeMillis()内部一致性在前外部共识在后。5. HashedWheelTimer 的进阶细节与生产环境注意事项5.1 内存与性能为什么说它省内存时间轮的内存占用是预先分配好的一个长度为 wheelSize 的对象数组每个元素是一个 Bucket 链表头。不管有没有任务这 512 个 Bucket 都在。任务提交时不额外分配堆结构只是把HashedWheelTimeout对象挂到链表中。对比优先队列方案每个任务至少需要持有ScheduledFutureTask对象里面有堆索引、触发时间、状态等字段还涉及DelayedWorkQueue的扩容。当任务频繁提交、频繁取消时优先队列里的标记删除会产生空洞需要定期purge清理否则内存占用会缓慢增长。时间轮的方案则是任务放在固定数组里随指针推进自然移除不需要额外的 gc 压力。不过有个反向注意点如果 wheelSize 设置得太大即使没有任务数组本身也占内存。默认 512 个 Bucket 非常小但如果你调成1 20也就是一百万个槽位光数组引用就是 8MB。盲目调大 wheelSize 并不能提高精度精度只由 tickDuration 决定wheelSize 只决定最大延迟范围。所以不要盲目调参数。5.2 任务取消与状态流转HashedWheelTimeout的内部状态有四个ST_INIT初始态、ST_CANCELLED已取消、ST_EXPIRED已过期执行、ST_PROCESSED已处理但被标记。取消任务通过timeout.cancel()实现内部通过 CAS 把状态从ST_INIT改成ST_CANCELLED。取消的任务并不会立即从链表中移除只是打上标记。真正被清理是在 Worker 线程推进到该 Bucket 时遍历链表发现状态不对就顺手移除了。这种“惰性删除”的思路在 Java 的 LinkedList、HashMap 等底层实现里都有应用目的都是避免在并发环境下做复杂的写操作。所以如果你的业务代码大量依赖取消任务请注意主动调cancel()会返回是否成功但内存释放是异步的不会立刻发生。5.3 生产环境中的几个真实教训我把实际使用中踩过的坑整理成表格希望你能避开问题现象原因解决方法任务时不时出现几十毫秒的延迟tickDuration设置过大按业务精度需求设置比如 50ms~100ms不要小于 1ms否则空转浪费 CPU某个任务执行后后续所有任务全部延迟用户代码里做了耗时操作耗时操作丢到业务线程池执行不要让 Worker 线程阻塞时间轮空闲时 CPU 占用不为零tickDuration设置小于 10ms或线程忙轮询适当调大 tickDuration检查是否有大量短周期任务提交延迟极大的任务报错delay 超出Long.MAX_VALUE / 1000 / 1000拆分成多层时间轮或用其他调度方案任务执行顺序不可控同槽位任务按链表顺序执行不同槽位按 tick 顺序业务上不要强依赖任务执行顺序必要时加业务层排序5.4 与 ScheduledThreadPoolExecutor 的选型对比很多开发者纠结到底用哪个我整理了一个对比维度HashedWheelTimerScheduledThreadPoolExecutor新增任务复杂度O(1)O(log n)到期任务检查每 tick 扫描固定槽位堆顶起跳执行线程单线程 Worker默认多线程池时间精度误差约一个 tick纳秒级精确适合任务量大量短期任务少量精确任务耗时任务会阻塞 Worker可容纳耗时任务内存占用固定数组 少量对象堆结构随任务数增长一句话总结海量短任务、低精度、可控延迟选时间轮少量长任务、高精度、任务本身耗时长选线程池调度。两者也可以结合时间轮负责触发“检查时间到了”的信号实际工作丢给线程池执行。这也是很多生产级中间件的标配方案。6. 动手验证写一个简单的时间轮示例前面讲了这么多理论不写代码总是隔着一层。我建议你本地建一个测试工程把 Netty 依赖引进来跑一个最小示例体会一下。Maven 依赖dependency groupIdio.netty/groupId artifactIdnetty-common/artifactId version4.1.100.Final/version /dependency示例代码import io.netty.util.HashedWheelTimer; import io.netty.util.Timeout; import io.netty.util.TimerTask; import java.util.concurrent.TimeUnit; public class TimeWheelDemo { public static void main(String[] args) throws InterruptedException { // 每 100ms 走一格共 512 格最长一圈 51.2 秒 HashedWheelTimer timer new HashedWheelTimer( r - new Thread(r, my-timer), 100, TimeUnit.MILLISECONDS, 512); TimerTask task1 timeout - System.out.println(task1 executed at System.currentTimeMillis()); Timeout timeout1 timer.newTimeout(task1, 1, TimeUnit.SECONDS); TimerTask task2 timeout - System.out.println(task2 executed at System.currentTimeMillis()); timer.newTimeout(task2, 5, TimeUnit.SECONDS); // 取消 task1 if (timeout1.cancel()) { System.out.println(task1 cancelled); } Thread.sleep(6000); timer.stop(); } }注意timer.stop()会默认等待所有已提交任务执行完毕如果任务太多或单个任务执行时间长stop()本身也会阻塞。如果希望立刻停止并返回未执行任务可以用stop()的返回类型为SetTimeout或者用isStop()配合处理。我在实测中还注意到一个有意思的现象同一个任务在tickDuration 100ms的情况下实际执行时间和预期时间误差在 0~100ms 之间随机分布。误差来源有两个一是Thread.sleep的唤醒精度本身有波动二是任务提交时间点若刚好错过指针当前槽位就要等下一圈。理解了这个就不会纠结那几十毫秒的误差了。7. 总结的个人体会与一个小技巧分析HashedWheelTimer的源码是一次很过瘾的体验。它没有复杂的锁策略、没有高性能队列的激进优化用的全是最基础的数据结构和算法思想——环形数组、链表、CAS、位运算。但正是这种朴素的设计在特定场景下实现了惊人的吞吐量。我个人在实际项目里习惯把它用在连接管理上。每个客户端连接对应一个定时任务用于空闲检测毫秒级误差完全没关系但上万个连接同时在线时时间轮方案比优先队列顺畅得多。踩过几次坑之后我也学到一个教训时间轮不是一把万能钥匙。凡是需要精确到毫秒以下级别的调度或者任务本身执行耗时存在不确定性都应该优先考虑其他方案。最后分享一个扩展小技巧如果感觉单个时间轮无法满足超大范围的延迟需求比如要支持小时级别的延迟任务可以设计多层时间轮。像操作系统里经典的层次化时间轮第一层管秒级、第二层管分级、第三层管小时级高层的 tick 到来时把任务降级投递到底层。这是时间轮最常用的进阶玩法理解了基础版本的原理推导出多层结构其实是水到渠成的事。如果你正在为大量的超时任务、心跳检测发愁不妨先试着用HashedWheelTimer感受一下从 O(log n) 到 O(1) 带来的直观差异。
1)
