timer是kafka层级时间轮的go实现. 插入, 删除, 扫描超时的时间复杂度接近O(1), 使用层级时间轮和延迟队列的实现, 通过延迟队列来推进时间轮, 从而避免了空推进问题. 支持单机百万级超时任务. 精度方面非常优秀.
有几个概念:
timingWheel: 是一个存储定时任务的环形队列, 底层采用数组实现. 每一个元素都是一个时间格(对应着一个spoke).spoke: 桶或轮幅, 以下均称为轮幅, 轮幅有一个双向链表, 链表中的每一项都是taskEntry, 每一个taskEntry都封装了真正的定时任务task.wheelSize: 每层时间轮的时间格的个数, 每个时间格对应一个spoketaskEntry: 任务项都封装着真正的定时任务task: 定时任务.
在每一层时间轮中, 几个重要的概念
tickMs: 时间轮的基本时间跨度, 每个时间格代表一个时间跨度.interval: 时间轮的总体时间跨度. 可以通过公式计算:tickMs * wheelSizecurrentTime: 表盘指针, 绝对时间, 表示当前时间轮所处的时间. 对时间做了调整, 表示小于当前时间的最大时间跨度的整数倍. 假设当前时间戳为212ms, 当前时间轮基本时间跨度为20ms, 那么currentTime就是小于212ms且20的整数倍, 即200ms.currentTime将整个时间轮划分为到期部分和未到期部分,currentTime当前执行的时间格也属于到期部分, 表示刚好到期, 且需要处理当前时间格的spoke上所有任务.overflowWheel: 指向更高级别的时间轮
下层时间轮的tickMs就是上层时间轮的interval. 例如, wheelSize为16, 则:
- 第一层的
tickMs为1ms, 所以第一层的interval = 1ms * 16 = 16ms； - 第二层的
tickMs= 第一层的interval, 即16ms, 而第二层的interval = 16ms * 16 = 256ms. - 第三层的
tickMs= 第二层的interval, 即256ms, 而第二层的interval = 256ms * 16 = 4096ms, 以此类推.
NOTE: wheelSize采用16, tickMs采用1ms, 进行示例.
初始情况下, 表盘指针currentTime指向时间格0, 此时有一个定时为3ms的任务添加到时间轮, 会被放到时间格为3的spoke上.
随着时间的推移, 表盘指针currentTime不断推进, 过了3ms之后, 当currentTime指向时间格3时, 就需要将对应的spoke上的任务进行到期操作.
等会, 如何推进, 是每tickMs进行推进么? 这很有问题, 当推进1ms时, 到达时间格1, 这时提取对应spoke上的任务进行到期操作, 发现上面并没有任务, 存在空推进问题, 造成性能损耗, 这时借助DelayQueue来跳跃式推进时间轮, 跳过无任务的空时间格. DelayQueue是一个无界的阻塞队列, 用于存放实现了Delayed接口的对象, 它会根据对象的延迟时间来决定是否可以从中取出元素. 只有当对象的延迟时间到期后, 才能从队列中取出该对象.
现在我们引入DelayQueue来解决空推进问题, 同前面一样, 初始情况下, 表盘指针currentTime指向时间格0, 此时有一个定时为3ms的任务添加到时间轮, 会被放到时间格为3的spoke上. spoke持有一个未来到期的绝对时间expiration, 这时时间格3上的spoke会被加DelayQueue. 然后唤醒推进器从DelayQueue查看第一个元素, 根据spoke的延迟时间, 一直等到时间到期后, 推进器立即将currentTime推进并指向时间格3, 然后将对应spoke上的任务进行到期操作.
假如此时有一个定时为5ms的任务插入, 会被放到时间格8中; 此时又有一个定时为15ms的任务插入, 那么会复用原来的时间格, 会被放到时间格2中. 此时时间格8, 时间格2的spoke添加到DelayQueue, DelayQueue会根据最近延迟到期的时间进行延迟等待, 一直等到时间到期, 才进行推进.
假如此时有一个定时为40ms的任务插入, 当前时间轮无法容纳, 应该如何处理? 这时采用层级时间轮的概念, 当任务的到期时间超过了当前时间轮所表示的时间范围时, 就会尝试添加到更高级的时间轮中. 按这情况, 这个任务会被插到第二层时间轮的时间格2中并将对应spoke添加到DelayQueue, 此时如何还有一个300ms的定时任务, 这个任务将被插到第三层时间格1中并将对应spoke添加到DelayQueue.
随着时间的推移, 当第三层时间轮时间格1对应的时间到期时, 原本设定为300ms的定时任务还剩下300-256=46ms, 此时还不能执行这个任务的到期操作, 这里就会进行一个时间轮的降级, 会将这个剩余时间为46ms的定时任务重新提交到层级时间轮. 此时第一层时间跨度仍然不够, 但是第二层时间跨度已经足够插入这个定时任务, 所以会将该任务添加到第二层时间轮的时间格2中([32,48)).
再过32ms之后, 当第二层时间格5对应的时间到期后, 由于还剩8ms, 该任务还无法执行到期操作, 会再次被降级放到第一层时间轮的时间格8中. 再经过8ms, 此任务真正到期, 最终执行相应的到期操作
wheelSize |
1层 ( tickMs/interval) |
2层 ( tickMs/interval) |
3层 ( tickMs/interval) |
4层 ( tickMs/interval) |
5层 ( tickMs/interval) |
6层 ( tickMs/interval) |
7层 ( tickMs/interval) |
|---|---|---|---|---|---|---|---|
| 32 | 1ms(32ms) | 32ms(1024ms ≈ 1.024s) | 1024ms(32768ms ≈ 32.768s) | 32768ms(1048576ms ≈ 17.48m) | 1048576ms(33554432ms ≈ 9.32h) | 33554432ms(1073741824ms ≈ 12.42d) | 1073741824ms(34359738368ms ≈ 1.10y) |
| 64 | 1ms(64ms) | 64ms(4096ms ≈ 4.096s) | 4096ms(262144ms ≈ 4.37m) | 262144ms(16777216ms ≈ 4.66h) | 16777216ms(33554432ms ≈ 12.42d) | 33554432ms(1073741824ms ≈ 2.18y) | - |
| 128 | 1ms(128ms) | 128ms(16384ms ≈ 16.384s) | 16384ms(2097152ms ≈ 34.95m) | 2097152ms(268435456ms ≈ 3.11d) | 268435456ms(34359738368ms ≈ 1.10y) | - | - |
| 256 | 1ms(256ms) | 256ms(65536ms ≈ 65.536s) | 65536ms(16777216ms ≈ 4.66h) | 16777216ms(4294967296ms ≈ 49.71d) | 4294967296ms(1099511627776ms ≈ 34.87y) | - | - |
| 512 | 1ms(512ms) | 512ms(262144ms ≈ 4.37m) | 262144ms(134217728ms ≈ 1.55d ) | 134217728ms(68719476736ms ≈ 2.19y) | 68719476736ms(35184372088832ms ≈ 1115.7y) | - | - |
计算给定最大时间t, 计算所需最小层级n和时间格m:
tickMs/wheelSize |
30s (最小层级/总时间格) |
1天 (最小层级/总时间格) |
30天 (最小层级/总时间格) |
1年 (最小层级/总时间格) |
|---|---|---|---|---|
| 1ms/32 | 3/96 | 6/192 | 7/224 | 7/224 |
| 1ms/64 | 3/192 | 5/320 | 6/384 | 6/384 |
| 1ms/128 | 3/384 | 4/512 | 5/640 | 5/640 |
| 1ms/256 | 2/512 | 4/1024 | 4/1024 | 5/1280 |
| 1ms/512 | 2/1024 | 3/1536 | 4/2048 | 4/2048 |
综合来看, wheelSize = 128占用较少的内存, 任务在高级别轮中分布得更加稀疏.
绝大多数任务为秒级, 这样,大多数落在层级2或层级3, 128ms~16.384s均落在层级2. 层级3的tickMs为16.384s, 这样更容易的将任务拆分放在相应的时间格. 在推进任务时, 将任务从高级轮向低级轮进行迁移, 任务数会更少. 任务更稀疏.