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

再过个 56 秒，相对而言它就是个延迟 8 秒后执行的任务，因此它会再被降级放在第一层中，等待执行。
降级是为了保证时间精度一致性。Kafka内部用的就是多层次的时间轮算法。
Netty中的时间轮在 Netty 中时间轮的实现类是 HashedWheelTimer ，代码中的 wheel 就是上图画的循环数组， mask 的设计和HashMap一样，通过限制数组的大小为2的次方，利用位运算来替代取模运算，提高性能。tickDuration 就是每格的时间即精度。可以看到配备了一个工作线程来处理任务的执行。

文章插图

接下来我们再来看看任务是如何添加的。

文章插图

可以看到任务并没有直接添加到时间轮中，而是先入了一个 mpsc 队列，我简单说下 mpsc 是 JCTools 中的并发队列，用在多个生产者可同时访问队列，但只有一个消费者会访问队列的情况。篇幅有限，有兴趣的朋友自行了解实现。
然后我们再来看看工作线程是如何运作的。

文章插图

很直观没什么花头，我们先来看看 waitForNextTick ，是如何得到下一次执行时间的。

文章插图

简单的说就是通过 tickDuration 和此时已经滴答的次数算出下一次需要检查的时间，时候未到就sleep等着。
再来看下任务如何入槽的。

文章插图

注释的很清楚了，实现也和上述分析的一致。
最后再来看下如何执行的。

文章插图

就是通过轮数和时间双重判断，执行完了移除任务。
小结一下总体上看 Netty 的实现就是上文说的时间轮通过轮数的实现，完全一致。可以看出时间精度由 TickDuration 把控，并且工作线程的除了处理执行到时的任务还做了其他操作，因此任务不一定会被精准的执行。
而且任务的执行如果不是新起一个线程，或者将任务扔到线程池执行，那么耗时的任务会阻塞下个任务的执行。
并且会有很多无用的 tick 推进，例如 TickDuration 为1秒，此时就一个延迟350秒的任务，那就是有349次无用的操作。
但是从另一面来看，如果任务都执行很快(当然你也可以异步执行) ，并且任务数很大，通过分批执行，并且增删任务的时间复杂度都是O(1)来说。时间轮还是比通过优先队列实现的延时任务来的合适些。
Kafka 中的时间轮上面我们说到 Kafka 中的时间轮是多层次时间轮实现，总的而言实现和上述说的思路一致。不过细节有些不同，并且做了点优化。
先看看添加任务的方法。在添加的时候就设置任务执行的绝对时间。

文章插图

那么时间轮是如何推动的呢？Netty 中是通过固定的时间间隔扫描，时候未到就等待来进行时间轮的推动。上面我们分析到这样会有空推进的情况。
而 Kafka 就利用了空间换时间的思想，通过 DelayQueue ，来保存每个槽，通过每个槽的过期时间排序。这样拥有最早需要执行任务的槽会有优先获取。如果时候未到，那么 delayQueue.poll 就会阻塞着，这样就不会有空推进的情况发送。
我们来看下推进的方法。

文章插图

从上面的 add 方法我们知道每次对比都是根据expiration < currentTime + interval 来进行对比的，而advanceClock 就是用来推进更新 currentTime 的。
小结一下Kafka 用了多层次时间轮来实现，并且是按需创建时间轮，采用任务的绝对时间来判断延期，并且对于每个槽(槽内存放的也是任务的双向链表)都会维护一个过期时间，利用 DelayQueue 来对每个槽的过期时间排序，来进行时间的推进，防止空推进的存在。