哈希时间轮

哈希时间轮

Kafka 使用的是一种改进的时间轮算法，称为哈希时间轮（Hashed Wheel Timer）。

单层时间轮有一个绕不开的硬约束：要覆盖多长的延时，就得准备多少个刻度。tick 是 1 秒、想覆盖 7 天，轮子上就得有 60 万个格子，其中 59 万个永远空着。哈希时间轮的思路是把这个约束拆开——延时不再需要”一个刻度一个格子”，只要”一个桶能装下它”就够了。

它的做法分两步。第一步，把延时换算成”圈数加圈内偏移”：

第一步：把延时换算成「圈数 + 圈内偏移」

  延时 3 秒   （tick = 1 秒，轮长 6 格）
    ticks  = ceil(3 / 1) = 3
    rounds = 3 / 6 = 0      ← 还没转满一圈
    offset = 3 % 6 = 3      ← 落在圈内第 3 格

  延时 20 秒
    ticks  = 20
    rounds = 20 / 6 = 3     ← 还要再转 3 圈
    offset = 20 % 6 = 2     ← 圈内第 2 格

第二步：把「圈内偏移」哈希到桶上

  bucket = (cursor + offset) % bucketCount

  轮子只有 6 个桶，20 秒和 3 秒的任务可以共享同一个桶，
  区别只在于 rounds 分别是 3 和 0。

由此得到哈希时间轮最核心的一条性质：轮子的内存占用只和桶数有关，和最大延时无关。延时是 1 小时还是 30 天，桶数都是那么多。

这里还有一个容易被忽略的设计选择：桶数不必等于轮长。轮长（tick 数）决定一圈代表多长时间，桶数决定哈希的碰撞程度——桶数越多，碰撞越少，但每个桶的链表越长。Kafka 把这两个维度做成了独立的参数。

桶是怎么串起来的

每个桶不是数组，而是一条任务链表。任务插入时挂在链表尾部，出期时从链表头部摘下来。

bucket[2]:
  ┌────────┐   ┌────────┐   ┌────────┐
  │ Task A │──▶│ Task B │──▶│ Task C │
  │rounds=0│   │rounds=1│   │rounds=2│
  └────────┘   └────────┘   └────────┘
       ↑
    链表头，最先被检查

插入：append 到链表尾      O(1)
取出：从链表头摘一个      O(1)

用链表而不是数组或集合，是因为任务的增删非常频繁，而链表增删是常数时间；同时链表节点通常内嵌在定时器对象里（intrusive list），插入任务不产生额外分配，对 GC 友好。

一个桶里往往同时挂着不同圈数的任务：指针扫到这个桶时，只有 rounds 为 0 的任务真正到期，其余的只是把圈数减一，继续挂在桶里等下一轮。

圈数是怎么处理的

超出轮长的那部分延时，是哈希时间轮能”支持任意延时”的关键。两种主流处理方式：

方式一：圈数计数器（Kafka 的做法）

任务进入桶时就带着一个 rounds 值。每次指针扫到该桶，rounds 减一；减到 0 时任务到期。

任务延时 20 秒，轮长 6 格（1 秒/格）
  → rounds = 3，offset = 2

第 1 圈扫到桶 2：rounds 3 → 2，不触发
第 2 圈扫到桶 2：rounds 2 → 1，不触发
第 3 圈扫到桶 2：rounds 1 → 0，不触发
第 4 圈扫到桶 2：rounds 0 → 触发 ✅

优点是实现简单，每个任务多一个计数字段。代价是长延时任务会被反复扫描：延时 30 圈的任务，要被扫 30 次。

方式二：级联降级（Netty 风格）

任务到期被摘出来时，如果 deadline 还没到，就把它重新投到”未来第 rounds 格”对应的桶里。相当于把超出部分推给下一个更高的时间层级。

任务延时 20 秒，轮长 6 格
  → 首次落在桶 2，rounds = 3

第 1 圈：桶 2 的任务被扫出，发现 rounds = 3 大于 0
        → 重新插入到 (cursor + 3) % 6 的桶里，rounds 减 1
        → 任务往后"挪"了 3 格，而不是原地等待

这种方式让长延时任务在轮子里不断往后挪，扫描次数更均匀，代价是每次挪动都要做一次插入。

---

核心改进

相对单层时间轮，哈希时间轮做了三处关键改进。

改进一：用圈数承载溢出，轮长不再等于最大延时。

单层时间轮里，“能覆盖的最长延时”直接等于”轮长乘 tick”。哈希时间轮把这个限制拆成了两段：圈内偏移决定”什么时候第一次被扫到”，圈数决定”还要等几轮才真正到期”。于是轮子可以很小，延时却可以任意长。

改进二：桶是链表而不是数组。

固定数量的桶，每个桶挂一条链表。桶的数量决定了内存上限，与任务数无关；链表的头插尾出保证了插入和取出都是 O(1)。

改进三：按时间单位分桶，保住短延时的精度。

单纯的哈希轮有个副作用：桶的宽度是固定的，短延时和长延时被塞进同一批桶里，谁都不准。更聪明的做法是按时间单位做梯度划分——毫秒级的延时（请求超时）用毫秒桶，秒级用秒桶，分钟级用分钟桶，更长的用小时桶、天桶。Kafka 的 TimeUnit 枚举正是按这个梯度划分的，这类实现会先把延时归到合适的单位桶里，再在桶内用哈希定位。

按单位分桶之后，精度和跨度就解耦了：短延时依然是毫秒级精度，长延时也不会占用额外的桶。

按时间单位梯度分桶：

  延时区间          使用的桶      桶内精度
  ─────────────────────────────────────────
  1 毫秒 ~ 1 秒     毫秒桶        1 毫秒
  1 秒 ~ 1 分钟      秒桶          1 秒
  1 分钟 ~ 1 小时    分钟桶        1 分钟
  1 小时 ~ 1 天      小时桶        1 小时
  1 天 以上          天桶          1 天

  代价：要维护多组桶数组，调度线程按单位分别推进

支持任意延时

“支持任意延时”这句话要拆成两个层面来理解：延时范围不设上限，以及触发精度不低于一个 tick。

延时范围不设上限，靠的是圈数。 前面已经推导过：ticks 超过轮长以后，超出的部分变成 rounds，轮子不需要变长。理论上，只要一个 long 装得下毫秒时间戳，延时就可以做到任意长。

延时上限的推导：

  ticks   = ceil(delay / tickDuration)
  rounds  = ticks / ticksPerWheel          ← 与延时成正比的整数
  offset  = ticks % ticksPerWheel          ← 恒定落在轮长之内

  轮子大小 = ticksPerWheel 个桶            ← 与延时无关 ✅
  单任务内存 = 一个 deadline + 一个 rounds   ← 固定 ✅

  延时 1 小时   → rounds = 3600 / 6 = 600
  延时 30 天    → rounds = 2592000 / 6 = 432000

触发精度不低于一个 tick，靠的是绝对截止时间兜底。 桶只是用来”大致提醒”调度器”这一格有东西要处理”，真正到期与否要用任务的绝对 deadline 判断。Kafka 在桶里额外维护了一个桶级计数：如果桶里最早的任务还有一个 tick 才到期，调度器就再等一个 tick，而不是提前触发。这样每个任务的实际触发误差被限制在一个 tick 以内，而不是”桶对齐误差”。

轮盘上的两个刻度：

  桶对齐（bucket alignment）
    任务被放在桶里时会被"取整"，看起来像提前或延后了一个桶宽
    → 用绝对 deadline 复核，误差被拉回一个 tick 以内

  圈数取整（round alignment）
    任务跨圈时可能被多扫一轮
    → 用 rounds 精确计数，不会漏也不会早

把哈希时间轮和另外两种结构放在一起对比，边界就清楚了：

---

优势

1. ✅ 支持短延时的高性能处理
2. ✅ 内存占用固定
3. ✅ 实现相对简单

这三条对应的是哈希时间轮真正的价值。

短延时依然很快。 哈希并没有牺牲短延时的性能。延时 3 秒的任务，一圈之内就到期，和单层时间轮走的是同一条路径：算 ticks、算 offset、头插链表、指针扫到就摘出来。没有额外的排序、没有堆调整，也没有额外的数据库往返。真正受益的是那些”量大、时间集中”的场景——比如同时到期的连接超时。

内存占用固定。 轮子占用 O(buckets)，与最大延时无关，与任务数也只差一个链表节点的开销。相比”为了支持 7 天延时而开 60 万个槽位”的单层轮，这是数量级的差别。这也是它能放进 Kafka 这种对内存敏感的基础设施里的原因。

实现相对简单。 相比层级时间轮的层间降级，哈希时间轮只需要维护一组桶和一个圈数计数器，没有”任务该降级到哪一层”这类判断。对想自己实现一个延时调度器的团队来说，这个复杂度是可以接受的。

但也有必须说清楚的代价。

第一，精度被桶宽”抹平”了一部分。 桶是离散的，落在同一个桶里的任务会被一起扫出来。如果业务要求”同一秒内入队的任务按严格 FIFO 执行”，哈希轮做不到，需要在任务内部再带一个序列号做二次排序。

第二，长延时任务的重复扫描不可忽视。 用圈数计数时，一个要等 24 小时的任务（tick 为 1 秒、轮长 60 格）会被扫到 1440 次。这些扫描绝大多数只做了”圈数减一”这一个动作，代价不高，但确实存在。级联降级能缓解这一点，代价是实现复杂度上升。

第三，进程重启依然全部丢失。 哈希时间轮和单层时间轮在这一点上完全一样：它是内存结构，没有持久化。所以它永远不能单独承担”任务事实来源”的职责，只能配合一个可靠存储使用——《Redis ZSet 方案》里的 ZSet、数据库里的 delay_tasks 表，或者 Kafka 本身。

第四，调度线程一旦被阻塞就会积压。 时间轮的推进是单线程按节奏进行的，如果这一拍的扫描没做完，下一拍就会堆积，最终出现”一大批任务在同一时刻集中触发”的惊群。生产上要给调度线程单独隔离，并监控每次 tick 的耗时。

最后一句总结：哈希时间轮解决的是”任意延时”和”有界内存”这对矛盾，但它不解决”可靠存储”和”进程重启”。 前者靠《层级时间轮》和《Redis ZSet 方案》配合，后者只能由持久化存储来兜底。

上一章节

时间轮原理

下一章节

层级时间轮