时间轮算法理解、Kafka实现

概述

TimingWheel，时间轮，简单理解就是一种用来存储若干个定时任务的环状队列（或数组），工作原理和钟表的表盘类似。
关于环形队列，请参考环形队列。
时间轮由两个部分组成，一个环状数组，一个遍历环状数组的指针。
起首定义一个固定长度的环状数组，队列中的每一个元素代表一个时间格（可以正确到秒或毫秒。实际场景里，如Java或Linux下的cron定时任务，都是某一秒来触发。在实时处理领域，则一般用毫秒），一个时间格可存放若干个定时任务（真实业务开发场景下，同时触发多个任务），即任务列表。任务列表是一个环形的双向链表，链表中的每一项表示的都是定时任务项，其中封装真正的定时任务。

时间格代表时间轮的基本时间跨度或精度，假如一秒走一个时间格的话，则这个时间轮的精度就是1秒。当指针指向某个数组时，就会把这个数组中存储的任务取出来，然后遍历链表逐个运行里面的任务。
下图是一个有12个时间格的时间轮，转完一圈需要12s。当需要新建一个3s后实行的定时任务，只需要将定时任务放在下标为3的时间格中即可。

当需要创建一个15s后实行的定时任务怎么办呢？
此时可考虑引入圈数（也叫轮数）这一概念，即这个任务还是放在下标为3的时间格中，圈数为2。除增加圈数这种方法之外，还有种多条理时间轮，Kafka接纳的就是这种方案。
时间轮的长处：

• 减少定时任务添加和删除的时间复杂度，提升性能；
  
• 可保证每次实行定时器任务都是O(1)复杂度，在定时器任务密集的情况下，性能优势非常明显
  

实现

在许多开源组件里可看到时间轮算法的实现：Kafka、Netty、Dubbo、Caffeine。
值得一提的是，网络上很多多少文章说ZooKeeper里也偶然间轮算法的实现，并没有。
Kafka

Kafka中有许多延时操作，如耗时的网络请求（如Produce时等待ISR副本复制成功）会被封装成DelayOperation举行延迟处理操作，防止阻塞Kafka请求处理线程。
Kafka没有利用JDK自带的Timer和DelayQueue实现。底层都是个优先队列，即接纳minHeap的数据布局，最快需要实行的任务排在队列第一个，不同的是Timer中有个线程去拉取任务实行，DelayQueue是个容器，需要配合其他线程工作。时间复杂度上这两者插入和删除操作都是O(logn)，不满足性能要求。
ScheduledThreadPoolExecutor是JDK提供定时线程池，也是DelayQueue + 池化线程的一个实现。
Kafka基于时间轮实现延时操作，时间轮算法的插入删除操作的时间复杂度都是O(1)，满足性能要求。
源码类为org.apache.kafka.server.util.timer.TimingWheel：

1. public class TimingWheel {
2.     private final long tickMs;
3.     private final long startMs;
4.     private final int wheelSize;
5.     private final AtomicInteger taskCounter;
6.     private final DelayQueue<TimerTaskList> queue;
7.     private final long interval;
8.     private final TimerTaskList[] buckets;
9.     private long currentTimeMs;
10.     private volatile TimingWheel overflowWheel = null;
11. }

复制代码

几个核心参数：

• tickMs：时间跨度
  
• startMs：开始时间
  
• wheelSize：时间轮中bucket的个数
  
• interval：时间轮的整体时间跨度 = tickMs * wheelSize
  
• currentTimeMs：tickMs的整数倍，代表时间轮当前所处的时间。currentTimeMs可以将整个时间轮划分为到期部分和未到期部分，currentTimeMs当前指向的时间格也属于到期部分，表示刚好到期，需要处理此时间格所对应的TimerTaskList中的所有任务
  

整个时间轮的总体跨度是不变的，随着指针currentTimeMs的不停推进，当前时间轮所能处理的时间段也在不停后移，总体时间范围在currentTimeMs和currentTimeMs+interval之间。
Kafka接纳多条理时间轮来支持大跨度的定时任务，参考手表。

上图时间轮，第1层的时间精度为1，第2层的时间精度为20，第3层的时间精度为400。假如需要添加一个350s后实行的任务A的话（当前时间是0s），这个任务会被放在第2层（第二层的时间跨度为20*20=400>350）的第350/20=17个时间格子。
当第一层转17圈之后，时间已往340s，第2层的指针此时来到第17个时间格子。此时第2层第17个格子的任务会被移动到第1层。任务A当前是10s之后实行，因此它会被移动到第1层的第10个时间格子。
在层与层之间的移动，叫做时间轮的升降级。时间轮比较适合任务数量比较多的定时任务场景，它的任务写入和实行的时间复杂度都是O(1)。
随着时间推进，也会有一个时间轮降级的操作，本来延时较长的任务会从高一层时间轮重新提交到时间轮中，然后会被放在合适的低条理的时间轮当中等待处理。
在Kafka中时间轮之间如何关联呢，如何显现这种高一层的时间轮关系？
一个内部对象的指针，指向自己高一层的时间轮对象。
如何推进时间轮的进步，让时间轮的时间往前走？
通过DelayQueue来推进，是一种空间换时间的思想；DelayQueue中保存着所有的TimerTaskList对象，根据时间来排序，如许延时越小的任务排在越前面。外部通过一个ExpiredOperationReaper线程从DelayQueue中获取超时的任务列表TimerTaskList，然后根据TimerTaskList的过期时间来正确推进时间轮的时间，如许就不会存在空推进的标题。
Kafka接纳衡量的策略，把DelayQueue用在合适地方。DelayQueue只存放TimerTaskList，并不是所有的TimerTask，数量并不多，相比空推进带来的影响是利大于弊的。
总结

• Kafka利用时间轮来实现延时队列，因为其底层是任务的添加和删除是基于链表实现的，时间复杂度为O(1)，满足高性能的要求；
  
• 对于时间跨度大的延时任务，引入层级时间轮，能更好控制时间粒度，可以应对更加复杂的定时任务处理场景；
  
• 对于如何实现时间轮的推进和避免空推进影响性能，接纳空间换时间的思想，通过DelayQueue来推进时间轮。
  

Netty

io.netty.util.HashedWheelTimer
Netty中的时间轮是通过工作线程按照固定的时间间隔tickDuration推进的，如果长时间没有到期任务，这种方案会带来空推进的标题，造成肯定性能损耗；
Dubbo

org.apache.dubbo.common.timer.HashedWheelTimer，和Netty的源码实现几乎一样。
Caffeine

com.github.benmanes.caffeine.cache.TimerWheel
内部类Sentinel代表当前任务，两个内部类AscendingIterator和DescendingIterator分别表示从时间轮取任务的两个方式，
参考

• Kafka时间轮算法计划
  
• HashedWheelTimer利用及源码分析
  
• 一个开源的时间轮算法介绍
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。