TimeWheel - 时间轮
时间轮的种类
时间刻度不够用时,解决的办法有三种:
- 增大时间轮的刻度
- 缺点:刻度太多导致时间轮走到的多数刻度没有任务执行,利用率变低,同时也会导致存储空间变大。(空间复杂度较高)
- 列表中的任务添加round属性
- 缺点:每次移动刻度都需要遍历任务列表,会增加耗时。(时间复杂度较高)
- 分层时间轮
- 针对空间复杂度的问题:每个时间粒度对应一个时间轮,多个时间轮之间进行级联协作。
- 针对时间复杂度的问题:不用遍历计算round,列表中的任务直接全部取出来执行。
分层时间轮的例子
- 现有三个任务:
- 任务一:间隔30秒。
- 任务二:间隔1分钟30秒。
- 任务三:间隔1小时1分钟30秒。
- 三个任务涉及到三个时间单位,可以设置三个时间轮:秒轮、分轮、时轮。
- 初始添加任务时,将任务一添加到秒轮上,任务二添加到分轮上,任务三添加到时轮上。
- 以任务三为例:
- 当时轮移动到1小时时,取出时轮该刻度上的任务三,添加到分轮上,由分轮接管该任务。
- 当分轮移动到1分钟时,取出分轮该刻度上的任务三,添加到秒轮上,由秒轮接管该任务。
- 当秒轮移动到30秒时,取出秒轮该刻度上的任务三,移除该任务,并执行该任务。
分层时间轮的设计
![]() TimeWheelManager类
|
![]() TimeWheel类
|
![]() TimeWheelBucket类
|
![]() TimeWheelTimerTask类
|
需要注意的边界条件
- 需要考虑执行间隔为0,而且执行次数为无限次的情况。
- 需要考虑卡帧的情况,防止出现卡帧后遗漏任务,或者任务统一被卡帧延迟的问题。
- 超出时间轮容量的任务,可以先都放在最后一格,在走到最后一格的时候再进行时间槽的分配。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 鹏の箱庭!