调度与限流 #01：时间轮（Hashed Timing Wheel）

时间轮（Hashed Timing Wheel）是一种 O(1) 插入/删除的定时任务调度算法，被 Netty、Kafka、Linux 内核等广泛用于高并发延迟任务场景。

相关文章：层级时间轮 · 最小堆定时器

目录

问题背景

为什么 DelayQueue（最小堆）不够用？

传统定时任务调度常用 最小堆（Min-Heap） 实现的 DelayQueue：

• 堆顶始终是最近到期的任务
• 插入新任务：O(log N) — 需要上浮维护堆序
• 取消任务：O(log N) — 需要下沉维护堆序
• 每次 tick 触发：O(1)（只弹堆顶）

在百万级并发连接场景下（如 Netty 管理 100 万个 Channel，每个 Channel 有读写超时任务），N = 1,000,000 时：

log2(1,000,000) ≈ 20 次比较/次操作
1,000,000 次插入 × 20 = 20,000,000 次比较

锁竞争也是瓶颈：多线程同时插入/删除同一个堆，必须加全局锁。

时间轮的核心洞察

任务的触发时间只依赖于"距离当前还有几个 tick"，而不是绝对时间戳的大小关系。

把时间切成等长的 tick，用一个环形数组（大小 N）建立从"槽位编号"到"该槽所有任务"的映射。插入时只需一次取模运算定位槽位，复杂度降为 O(1)。

核心数据结构

struct TimingWheel {
    int        N              // 槽位总数，必须是 2 的幂（便于取模用位与）
    TaskList[] wheel          // 环形数组，wheel[i] 存放到期槽位为 i 的任务链表
    int        currentTick    // 当前指针位置，范围 [0, N-1]
    long       tickDuration   // 每个 tick 的时长，单位：毫秒
    long       startTime      // 时间轮启动的绝对时间戳（ms）
    Thread     workerThread   // 后台 tick 推进线程
}

struct Task {
    Runnable   callback       // 任务逻辑
    int        remainingRounds // 剩余圈数（单层轮延伸用）
    boolean    cancelled      // 是否已取消
    Task*      next           // 链表指针
}

关键约束：

• N 取 2 的幂（如 512）时，slot % N 可优化为 slot & (N-1)，避免除法
• tickDuration 决定精度下限（Netty 默认 100ms）
• 每个槽位是一个无锁链表（Netty 使用 MPSC 队列）

schedule() 伪代码

function schedule(task, delayMs):
    // 1. 计算任务需要经过几个 tick 才触发
    ticks = ceil(delayMs / tickDuration)

    // 2. 计算目标槽位（取模映射到环形数组）
    targetSlot = (currentTick + ticks) % N

    // 3. 计算剩余圈数（单层轮处理超长延迟）
    task.remainingRounds = ticks / N   // 整除，取圈数

    // 4. 将任务头插入目标槽位的链表
    wheel[targetSlot].prepend(task)

    return task  // 返回句柄，供 cancel() 使用

时间复杂度分析：

• 步骤 1-3：纯算术运算，O(1)
• 步骤 4：链表头插，O(1)
• 全程无锁（Netty 用 MPSC 队列），无需全局锁

tick() 伪代码

// 由 workerThread 每隔 tickDuration 毫秒调用一次
function tick():
    // 1. 取当前槽位的所有任务
    tasks = wheel[currentTick]
    wheel[currentTick] = emptyList()  // 清空槽位

    // 2. 遍历链表
    for each task in tasks:
        if task.cancelled:
            continue            // 跳过已取消任务

        if task.remainingRounds > 0:
            task.remainingRounds -= 1
            // 放回同一槽位，等待下一圈
            wheel[currentTick].append(task)
        else:
            // rounds == 0，真正到期，异步提交执行
            executor.submit(task.callback)

    // 3. 推进指针
    currentTick = (currentTick + 1) % N

注意：任务回调应提交给独立线程池执行，不得在 tick() 中同步执行，否则耗时任务会阻塞时钟推进。

执行追踪

配置：N=8，tickDuration=1s，startTime=t0

操作序列（均在 t=2s 时执行，即 currentTick=2）：

schedule(A, delay=5s)  →  ticks=5, targetSlot=(2+5)%8=7, rounds=5/8=0
schedule(B, delay=3s)  →  ticks=3, targetSlot=(2+3)%8=5, rounds=3/8=0
schedule(C, delay=11s) →  ticks=11, targetSlot=(2+11)%8=5, rounds=11/8=1

槽位初始状态（t=2s 后）：

slot: [0][ ][ ][ ][ ][B,C][ ][A]
                        5       7
currentTick = 2 ↑

逐 tick 演示：

单层时间轮的局限与 round 计数

问题

单层时间轮的最大可表示延迟为 N × tickDuration。

例如 N=512，tickDuration=100ms，最大延迟 = 51.2s。

超出范围的延迟（如 60s）用 round 计数处理：

ticks = 600          // 60s / 100ms
targetSlot = (currentTick + 600) % 512 = currentTick + 88
rounds = 600 / 512 = 1  // 需要走完 1 整圈再触发

round 计数的 tick() 逻辑（回顾）

if task.remainingRounds > 0:
    task.remainingRounds -= 1
    wheel[currentTick].append(task)  // 留在原槽，等下一圈
else:
    executor.submit(task.callback)   // 真正执行

分层时间轮（进阶）

当延迟范围跨越很大（小时/天级别），round 计数会导致每次 tick 都要遍历大量未到期任务。分层时间轮（类似时钟的时/分/秒三层结构）是更优解：

• 低层轮：tickDuration=1ms，N=1000（覆盖 1s）
• 中层轮：tickDuration=1s，N=60（覆盖 1min）
• 高层轮：tickDuration=1min，N=60（覆盖 1hr）

高层任务降级到低层时才进行精确插入，避免 round 遍历开销。

异常与边界场景

场景 1：任务执行时间 > tickDuration（任务积压）

现象：slot 中有一个耗时 500ms 的任务，tickDuration=100ms，tick() 被阻塞 500ms。

后果：后续 4 个 tick 全部延迟，累积误差达秒级。

正确做法：tick() 中只提交任务到线程池，不直接执行：

executor.submit(task.callback)  // 非阻塞，O(1)

Netty 的 HashedWheelTimer 强制用异步方式，回调在独立线程执行。

场景 2：cancel 已到期任务

现象：调用 cancel() 时任务可能已在线程池队列中等待执行。

处理方案：

function cancel(task):
    task.cancelled = true  // CAS 原子置位

// tick() 中检查
if task.cancelled:
    continue  // 跳过，不执行

已提交线程池的任务若已开始执行，cancel 无法阻止。这是"best-effort cancel"语义，与 Future.cancel(false) 一致。

场景 3：tick 精度误差（线程调度抖动）

现象：workerThread 依赖 Thread.sleep(tickDuration) 推进，OS 调度抖动可能导致实际睡眠时间为 tickDuration ± 几十毫秒。

Netty 的处理：

// 计算下一个 tick 的绝对截止时间
deadline = startTime + (currentTick + 1) * tickDuration

// 补偿睡眠
sleepTime = deadline - System.currentTimeMillis()
if sleepTime > 0:
    Thread.sleep(sleepTime)
// 若 sleepTime <= 0，说明已经超时，直接推进，不睡眠

这样即使某次 tick 稍晚，下一次 tick 会自动缩短等待时间，误差不累积。

场景 4：同一槽位大量任务（哈希冲突）

现象：N=512 时，10 万个任务全部映射到同一槽位（如都设置 delay=512s），该槽链表长度 = 100,000。

tick() 遍历复杂度退化：O(链表长度)，单次 tick 耗时激增。

缓解方案：

1. 适当增大 N（减少哈希碰撞概率）
2. 将链表换成分桶结构（二级哈希）
3. 使用分层时间轮，避免大量长延迟任务聚集在同一槽

Netty HashedWheelTimer 实现细节

整体架构

HashedWheelTimer
├── wheel[]              // HashedWheelBucket[512]（默认）
├── workerThread         // 单一 Worker 线程，推进 tick
├── timeouts (MPSC)      // 待加入轮的任务队列（多生产者单消费者）
└── cancelledTimeouts    // 待清理的已取消任务队列

Worker 线程主循环

// 简化的 Netty Worker 伪代码
while (WORKER_STATE == STARTED) {
    long deadline = waitForNextTick()   // 精准睡眠到下一个 tick
    processCancelledTasks()             // 清理取消的任务
    transferTimeoutsToBuckets()         // 将 MPSC 队列中的新任务转入 wheel
    wheel[tick & mask].expireTimeouts(deadline)  // 执行到期任务
    tick++
}

MPSC 队列的作用

• 多个业务线程（生产者）同时调用 newTimeout() 添加任务
• 单一 Worker 线程（消费者）在每次 tick 开始前批量消费
• 使用 JCTools 的 MpscQueue，无锁，避免 synchronized 竞争

pendingTimeouts 计数

// 防止任务无限堆积
if (pendingTimeouts.incrementAndGet() > maxPendingTimeouts) {
    throw new RejectedExecutionException("too many pending timeouts");
}

与最小堆定时器对比

结论：对于 Netty 管理百万 Channel 超时、Kafka 延迟队列、Linux 内核定时器等场景，时间轮的 O(1) 插入和无锁设计是压倒性优势。

参考资料

1. Varghese & Lauck (1987) — Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility — 时间轮原始论文，SOSP'87
2. Netty 源码 — io.netty.util.HashedWheelTimer（GitHub: netty/netty）
3. Kafka DelayedOperationPurgatory — 使用分层时间轮实现延迟操作（Kafka 源码 kafka.utils.timer）
4. Linux Kernel — include/linux/timer.h，内核定时器基于分层时间轮实现
5. 《Netty 权威指南》李林锋 — 第 18 章，HashedWheelTimer 原理与使用