kafka时间轮-轮询方式
时间轮
kafka中存在大量的延时操作，比如延时生产，延时消费，延时删除等。kafka并没有使用JDK自带的Timer和DelayQuene来实现延时的功能，而是基于时间轮的概念自定义实现了一个用于延时操作的定时器（SystemTimer）。
复杂度
jdk的Timer和DelayQuene的插入和删除的复杂度为O（nlogn）
根据源码分析，Timer底层使用的TaskQueue，内部实现使用的是最小堆
kafka使用的时间轮接近于O（1）,不仅仅是kafka采用了时间轮，在 Netty，Akka, Quartz， ZooKeeper 等组件中都存在时间轮的踪影。
时间轮结构
Kafka 中的时间轮（ TimingWheel ）是 个存储定时任务的环形队列底层采用数组实现，数组中的每个元素可以存放一个定时任务列表（ TimerTaskList )。 TimerTaskList是一个环形的双向链表，链表中的每一项表示的都是定时任务项（ TimerTaskEntry ），其中封装了真正的定时任务 TimerTask。
如何使用时间轮
若时间轮的tickMs=1ms，wheelSize=20，那么可以计算得出interval为20ms。初始情况下表盘指针currentTime指向时间格0，此时有一个定时为2ms的任务插入进来会存放到时间格为2的TimerTaskList中。随着时间的不断推移，指针currentTime不断向前推进，过了2ms之后，当到达时间格2时，就需要将时间格2所对应的TimeTaskList中的任务做相应的到期操作。此时若又有一个定时为8ms的任务插入进来，则会存放到时间格10中，currentTime再过8ms后会指向时间格10。如果同时有一个定时为19ms的任务插入进来怎么办？新来的TimerTaskEntry会复用原来的TimerTaskList，所以它会插入到原本已经到期的时间格1中。总之，整个时间轮的总体跨度是不变的，随着指针currentTime的不断推进，当前时间轮所能处理的时间段也在不断后移，总体时间范围在currentTime和currentTime+interval之间。
层级时间轮
如果此时有个定时为350ms的任务该如何处理？直接扩充wheelSize的大小么？Kafka中不乏几万甚至几十万毫秒的定时任务，这个wheelSize的扩充没有底线，就算将所有的定时任务的到期时间都设定一个上限，比如100万毫秒，那么这个wheelSize为100万毫秒的时间轮不仅占用很大的内存空间，而且效率也会拉低。Kafka为此引入了层级时间轮的概念，当任务的到期时间超过了当前时间轮所表示的时间范围时，就会尝试添加到上层时间轮中。
该设计的原理源自于钟表，传统钟表就是一个三级时间轮，第一层时间轮tickMs=1s, wheelSize=60，interval=1min，此为秒钟；第二层tickMs=1min，wheelSize=60，interval=1hour，此为分钟；第三层tickMs=1hour，wheelSize为12，interval为12hours，此为时钟。
参考上图，复用之前的案例，第一层的时间轮tickMs=1ms, wheelSize=20, interval=20ms。第二层的时间轮的tickMs为第一层时间轮的interval，即为20ms。每一层时间轮的wheelSize是固定的，都是20，那么第二层的时间轮的总体时间跨度interval为400ms。以此类推，这个400ms也是第三层的tickMs的大小，第三层的时间轮的总体时间跨度为8000ms。
对于之前所说的350ms的定时任务，显然第一层时间轮不能满足条件，所以就升级到第二层时间轮中，最终被插入到第二层时间轮中时间格17所对应的TimerTaskList中。如果此时又有一个定时为450ms的任务，那么显然第二层时间轮也无法满足条件，所以又升级到第三层时间轮中，最终被插入到第三层时间轮中时间格1的TimerTaskList中。注意到在到期时间在[400ms,800ms)区间的多个任务（比如446ms、455ms以及473ms的定时任务）都会被放入到第三层时间轮的时间格1中，时间格1对应的TimerTaskList的超时时间为400ms。随着时间的流逝，当次TimerTaskList到期之时，原本定时为450ms的任务还剩下50ms的时间，还不能执行这个任务的到期操作。这里就有一个时间轮降级的操作，会将这个剩余时间为50ms的定时任务重新提交到层级时间轮中，此时第一层时间轮的总体时间跨度不够，而第二层足够，所以该任务被放到第二层时间轮到期时间为[40ms,60ms)的时间格中。再经历了40ms之后，此时这个任务又被“察觉”到，不过还剩余10ms，还是不能立即执行到期操作。所以还要再有一次时间轮的降级，此任务被添加到第一层时间轮到期时间为[10ms,11ms)的时间格中，之后再经历10ms后，此任务真正到期，最终执行相应的到期操作。
时间轮的推进
Kafka中的定时器借助了JDK中的DelayQueue来协助推进时间轮。具体做法是对于每个使用到的TimerTaskList都会加入到DelayQueue中，“每个使用到的TimerTaskList”特指有非哨兵节点的定时任务项TimerTaskEntry的TimerTaskList。DelayQueue会根据TimerTaskList对应的超时时间expiration来排序，最短expiration的TimerTaskList会被排在DelayQueue的队头。Kafka中会有一个线程来获取DelayQueue中的到期的任务列表，有意思的是这个线程所对应的名称叫做“ExpiredOperationReaper”，可以直译为“过期操作收割机”。当“收割机”线程获取到DelayQueue中的超时的任务列表TimerTaskList之后，既可以根据TimerTaskList的expiration来推进时间轮的时间，也可以就获取到的TimerTaskList执行相应的操作，对立面的TimerTaskEntry该执行过期操作的就执行过期操作，该降级时间轮的就降级时间轮。
文章开头明确指明的DelayQueue不适合Kafka这种高性能要求的定时任务，为何这里还要引入DelayQueue呢？注意对于定时任务项TimerTaskEntry插入和删除操作而言，TimingWheel时间复杂度为O(1)，性能高出DelayQueue很多，如果直接将TimerTaskEntry插入DelayQueue中，那么性能显然难以支撑。就算我们根据一定的规则将若干TimerTaskEntry划分到TimerTaskList这个组中，然后再将TimerTaskList插入到DelayQueue中，试想下如果这个TimerTaskList中又要多添加一个TimerTaskEntry该如何处理？对于DelayQueue而言，这类操作显然变得力不从心。
分析到这里可以发现，Kafka中的TimingWheel专门用来执行插入和删除TimerTaskEntry的操作，而DelayQueue专门负责时间推进的任务。再试想一下，DelayQueue中的第一个超时任务列表的expiration为200ms，第二个超时任务为840ms，这里获取DelayQueue的队头只需要O(1)的时间复杂度。如果采用每秒定时推进，那么获取到第一个超时的任务列表时执行的200次推进中有199次属于“空推进”，而获取到第二个超时任务时有需要执行639次“空推进”，这样会无故空耗机器的性能资源，这里采用DelayQueue来辅助以少量空间换时间，从而做到了“精准推进”。Kafka中的定时器真可谓是“知人善用”，用TimingWheel做最擅长的任务添加和删除操作，而用DelayQueue做最擅长的时间推进工作，相辅相成。
推进细节举例：
假如有两个时间轮，分别代表秒和分，以下称为“秒轮”和“分轮”，每个轮有60个bucket,那在DelayQuene中则存在120个元素。
假设现在有个5分12秒的任务，此任务会存在在“分轮”的第五个bucket中，DelayQuene经过5分钟后，pull()到这个bucket,将槽中的
所有任务循环一次，重新加到新的槽中（添加失败则直接执行）即可，那此时任务会被放到“秒轮”中的第十二个bucket中，
DelayQuene在15秒后会pull()到“秒轮”中的第十二个bucket，然后任务得以执行。