时间轮算法

延迟任务的实现：

1. 优先队列存储任务，时间精度比较好 ，但是插入元素的时间是O(log(N))，元素多的时候比较慢，也就是无法满足大吞吐量的要求
2. 时间轮，牺牲了时间精度，插入的时间复杂度是O(1)；需要高吞吐的组件维持大量延迟任务，并且对及时性要求不高，比如IO事件处理

https://gitee.com/bossDuy/timewheel/blob/master/README.md

时间轮

原理

核心组成：

• 时间轮盘（数组）：整个环形数据结构
• 基准时间：数组中表示时间都是按照这个基准来表示的，第一个0-99ms就是 基准时间+0-99ms
• 槽位(slot)：时间轮上的分隔，每个槽位表示一段时间间隔
• 指针：指示当前时间，随时间推移顺时针移动
• 任务链表：挂载在每个槽位上的待执行任务集合
  

比如，我们设定一个slot为100ms，那么具体队对应的任务应该放到哪一个时间槽如下

因为每一个槽都是100ms，所以对于时间轮来讲 10ms和99ms 都是应该同时执行的，正如前面所说，时间轮牺牲了时间的精准度换得取任务时间复杂度为O(1)

对于超过数组长度所表示的时间，使用 目标时间对数组最大表示时间取余

实现的话可以通过数组和链表表示延时任务，时间轮通过定时的取扫描当前槽的任务是否需要执行

• 扫描的时候是需要扫描整个链表（存储任务的）的，还是O(N)，但是不需要扫描所有的延迟任务，被数组切割开了
• 插入任务的时候，只需要把任务计算到对应的位置然后插入，时间复杂度是O(1)