固定数组时间轮的槽过载优化：桶链表与批次执行

liulilittle

169人浏览 · 2026-06-14 17:58:52

liulilittle · 2026-06-14 17:58:52 发布

固定数组时间轮的槽过载优化：桶链表与批次执行

时间轮是处理海量定时任务的标准结构，它把时间切分成固定长度的槽，每个槽挂一个定时器链表。tick 推进时扫描当前槽链表，触发所有到期任务。理想情况下，每次 tick 的复杂度是 O(K)，K 为该槽上的到期定时器数，通常是常数。但当瞬时大量任务堆积在同一个槽时——比如 1ms 精度的轮子，某个时刻同时到了上万个超时——遍历链表会拖慢整个 tick，后续槽的处理被推迟，定时精度整体恶化。

这篇笔记记录一种简单直接的工程优化：让一个槽可以挂多个子桶（桶链表），并限制每次 tick 触发的任务数量，用可接受的延迟抖动换取处理时间的上界。

1. 基础结构：数组 + 双向链表

先看最简模型。一个时间轮就是一个定长数组 slots[N]，每个元素是双向链表的头指针。定时器节点内嵌 prev/next 指针，插入时计算到期槽位 (cur + delay_ticks) % N 并加入链表头，tick 时遍历该槽链表、触发回调并摘除。数组大小固定，没有动态分配。

当槽内定时器很少时，这完全够用。

2. 槽过载：一个桶装不下

当某个槽的链表过长，单次 tick 遍历成本可能超过一个槽的时长（比如 1ms），形成雪崩。直观解法是横向扩展——一个槽不再只是一个链表，而是一串“小桶”，每个小桶内部又是一个定时器链表。

原结构： slot[i] -> Node -> Node -> ... (单链表)
新结构： slot[i] -> Bucket1 -> Bucket2 -> ...
                    |            |
                    v            v
                  Node链表     Node链表

桶单元（Bucket） 是一个固定或动态分配的小结构：

内部包含一个定时器双向链表的头指针（和尾指针，便于尾部插入）。
一个 next 指针，指向同槽的下一个桶单元。
可选：当前桶内的定时器数量，用于快速判断是否已满。

这样就把一个长链表切分成了多个短链表，每个桶单元内部长度可控（比如限制最多 128 个节点）。当某个桶满了，就从预分配的对象池里取一个空桶，挂到桶链尾部。

3. 插入定时器：选定桶并挂载

插入流程不变：先根据延迟计算出目标槽索引 idx。然后找到该槽的桶链，一般是追加到最后一个桶单元（这样可以保证先入先出）。如果最后一个桶已满，就新建一个桶单元接在后面，再插入。

伪逻辑：

bucket = slots[idx].tail_bucket;
if bucket is full:
    bucket = alloc_bucket();
    slots[idx].tail_bucket.next = bucket;
    slots[idx].tail_bucket = bucket;
insert timer node into bucket.timer_list;

这里完全保持了 O(1) 插入。

4. 批次执行：每次 tick 只触发固定数量

为了避免一次 tick 触发整个槽的几百上千个任务，我们引入一个批次上限 BATCH_SIZE（例如 128）。每次 tick 处理当前槽时，只触发最多 BATCH_SIZE 个任务，然后停止。未处理完的任务继续留在桶内，等待下次 tick 再处理。

这会使部分任务的真实触发时间延后几个 tick，但只要批次上限设置合理（比如最大延迟 = BATCH_SIZE × tick_interval），这个额外延迟是可量化的、受控的。对于大多数超时场景（如 30s 连接超时，1ms tick），延时几个毫秒完全可以接受。

处理流程（每个 tick）：

取当前槽索引 cur = (cur + 1) % N。
设置计数器 processed = 0。
从该槽的第一个桶单元开始，遍历其内部定时器链表。
对于每个定时器，如果已到期且未取消，触发回调，从链表删除，processed++；如果 processed == BATCH_SIZE，记录当前桶和节点位置（断点），结束本轮。
如果当前桶处理完毕，移到下一个桶继续，直到批次用完或所有桶清空。
下次 tick 到同一个槽时，从断点继续处理。

这样，每次 tick 的工作量严格受 BATCH_SIZE 控制，保证了时间轮的推进节奏不会被突然的流量高峰打乱。