基于 golang 从零到一实现时间轮算法 (一)-CSDN博客

前言

时间轮是用来解决海量百万级定时器或延时任务的最佳方案linux 的内核定时器就是采用该数据结构实现。

---

应用场景

1. 自动删除缓存中过期的 Key缓存中设置了 TTL 的 kv通过把该 key 对应的 TTL 以及回调方法注册到 timewheel到期直接删除
2. 延时任务将任务注册到 timewheel过期自动触发执行
3. 在 TcpServer 中用来管理海量 Tcp 连接的超时定时器如 zinx 的定时器 实现

简单时间轮

如上图一个普通的时间轮类似于时钟表盘指针pointer每隔一段时间前进一格intervaltick 一次一圈代表一个周期circle定时任务以链表双向方式置放在表盘的刻度处当指针前进到当前位置时遍历任务链表执行相应的任务。

基本模型构成

1. tickMs基本时间跨度时间轮由多个时间格组成每个时间格代表当前时间轮的基本时间跨度tickMs。
2. wheelSize时间单位个数时间轮的时间格个数是固定的可用wheelSize来表示那么整个时间轮的总体时间跨度interval可以通过公式tickMs × wheelSize计算得出。
3. currentTime当前所处时间时间轮还有一个表盘指针currentTime用来表示时间轮当前所处的时间currentTime是 tickMs 的整数倍。currentTime 可以将整个时间轮划分为到期部分和未到期部分currentTime当前指向的时间格也属于到期部分表示刚好到期需要处理此时间格所对应的 TimerTaskList 的所有任务。

从开发角度而言实现一个时间轮

1. 时间轮是一个由固定长度 length 的数组本例子中就是 [1,12]构造而成的环形队列
2. 时间轮的长度决定了延时任务的刻度假设上面的刻度为 1s即时间轮 1s 前进一格那么该时间轮只能表达延时任务在 1s 至 12s内的任务时间轮的长度也即时间轮的周期12s
3. 注册任务按照 当前刻度 + 延时时长 % 时间轮周期 计算得出假设当前指针在 5s的位置此时添加一个延时周期为 5s 的任务那么该任务需要注册到刻度为 10s 的格子对应的任务链表中
4. 数组中的每个元素都指向一个双向链表用于存储对应的延时任务
5. 时间轮的插入复杂度是 O(1)删除指定节点的复杂度是O(n)因为需要遍历双向链表以查找到要删除的节点
6. 当时间轮指针转动到对应的单元格时顺序执行双向链表中存储的任务基础时间轮的缺点是无法注册延时超过时间轮周期的任务如何解决呢

基础时间轮的缺点是无法注册延时超过时间轮周期的任务如何解决呢

解决方法 1加 circle 计数器

此方法相当于给双向链表中存储的任务加多一个 “圈数” 的维度

• 假设时间轮有8个刻度
• 计时器值 = 17
• 走两圈时间轮+多走1个刻度
• 在"0"这个桶中设置计时器
• 与计时器一同保留#圈数
• 在到期处理时如果#圈数 > 0则重新插入计时器

注意此策略中时间轮指针每前进一格需要把此格对应的任务链表中所有的任务的 circle 计数器都减 1如果 circle==0那么说明任务时间已到期执行该任务。

解决方法 2层级时间轮

这是一种典型的 “空间换时间” 的思路按照时间轮周期的倍数进行合理分层有两个优点

1. 避免任务堆积在某个 slot 上
2. 支持任意长时间的延时任务注册
   
   复用之前的案例第一层的时间轮 tickMs=1ms, wheelSize=20, interval=20ms。第二层的时间轮的 tickMs 为第一层时间轮的 interval即为 20ms。每一层时间轮的 wheelSize 是固定的都是 20那么第二层的时间轮的总体时间跨度 interval 为 400ms。以此类推这个 400ms 也是第三层的 tickMs 的大小第三层的时间轮的总体时间跨度为 8000ms。

关于层级时间轮可以参考普通的时间。多层时间轮的概念也非常清晰,将时间轮分为多个,每两个轮之间是进位的关系,例如最普遍的秒,分,时.即:

• 秒级时间轮上,设有60个槽, 每两个槽之间的时间为1s.
• 分钟级时间轮上,设有60s个槽,每两个槽之间的时间为1min
• 小时级时间轮上,设有24个槽,每两个槽之间的时间为1h
  
  这样,秒级每走60个槽,时间过去一分钟,秒级时间轮归零,分级时间轮走一个槽; 分级时间轮每走过60个槽,时间过去一小时,分级时间轮归零,小时级时间轮走一个槽.

通过三级时间轮,只需要遍历60+60+60 =180个槽,就可以成为一个精度为1s, 周期为60x60x60 = 216000s的定时调度器.

---

参考

https://zhuanlan.zhihu.com/p/658079556
https://pandaychen.github.io/2022/05/28/A-TIMEWHEEL-ANALYSIS/
https://juejin.cn/post/7083795682313633822

属于在以上博客基础上记录的个人笔记。