知道什么是时间轮算法吗？在Netty和Kafka中如何应用的？( 二 ) _时间轮算法

并且 Java 线程池的设定是 task 出错会把错误吃了，无声无息的。因此一个任务出错也不会影响之后的任务。
DelayQueueJava 中还有个延迟队列 DelayQueue ，加入延迟队列的元素都必须实现 Delayed 接口。延迟队列内部是利用 PriorityQueue 实现的，所以还是利用优先队列！Delayed 接口继承了Comparable 因此优先队列是通过 delay 来排序的。

文章插图

然后我们再来看下延迟队列是如何获取元素的。

文章插图

小结一下也是利用优先队列实现的，元素通过实现 Delayed 接口来返回延迟的时间。不过延迟队列就是个容器，需要其他线程来获取和执行任务。
这下是搞明白了 Timer 、ScheduledThreadPool 和 DelayQueue ，总结的说下它们都是通过优先队列来获取最早需要执行的任务，因此插入和删除任务的时间复杂度都为O(logn) ，并且 Timer 、ScheduledThreadPool 的周期性任务是通过重置任务的下一次执行时间来完成的。
问题就出在时间复杂度上，插入删除时间复杂度是O(logn) ，那么假设频繁插入删除次数为 m ，总的时间复杂度就是O(mlogn) ，这种时间复杂度满足不了 Kafka 这类中间件对性能的要求，而时间轮算法的插入删除时间复杂度是O(1) 。我们来看看时间轮算法是如何实现的。
时间轮算法俗话说艺术源于生活，技术也能从日常生活中找到灵感。咱们先来看块表，嗯金色的表。

文章插图

都看清楚了吧，时间轮就是和手表时钟很相似的存在。时间轮用环形数组实现，数组的每个元素可以称为槽，和 HashMap一样称呼。
槽的内部用双向链表存着待执行的任务，添加和删除的链表操作时间复杂度都是 O(1) ，槽位本身也指代时间精度，比如一秒扫一个槽，那么这个时间轮的最高精度就是 1 秒。
也就是说延迟 1.2 秒的任务和 1.5 秒的任务会被加入到同一个槽中，然后在 1 秒的时候遍历这个槽中的链表执行任务。

文章插图

从图中可以看到此时指针指向的是第一个槽，一共有八个槽0~7 ，假设槽的时间单位为 1 秒，现在要加入一个延时 5 秒的任务，计算方式就是 5 % 8 + 1 = 6 ，即放在槽位为 6 ，下标为 5 的那个槽中。更具体的就是拼到槽的双向链表的尾部。
然后每秒指针顺时针移动一格，这样就扫到了下一格，遍历这格中的双向链表执行任务。然后再循环继续。
可以看到插入任务从计算槽位到插入链表，时间复杂度都是O(1) 。那假设现在要加入一个50秒后执行的任务怎么办？这槽好像不够啊？难道要加槽嘛？和HashMap一样扩容？
不是的，常见有两种方式，一种是通过增加轮次的概念。50 % 8 + 1 = 3 ，即应该放在槽位是 3 ，下标是 2 的位置。然后 (50 - 1) / 8 = 6 ，即轮数记为 6 。也就是说当循环 6 轮之后扫到下标的 2 的这个槽位会触发这个任务。Netty 中的 HashedWheelTimer 使用的就是这种方式。
还有一种是通过多层次的时间轮，这个和我们的手表就更像了，像我们秒针走一圈，分针走一格，分针走一圈，时针走一格。
多层次时间轮就是这样实现的。假设上图就是第一层，那么第一层走了一圈，第二层就走一格。
可以得知第二层的一格就是8秒，假设第二层也是 8 个槽，那么第二层走一圈，第三层走一格，可以得知第三层一格就是 64 秒。
那么一格三层，每层8个槽，一共 24 个槽时间轮就可以处理最多延迟 512 秒的任务。