Kafka如何实现延迟队列？

Kafka并没有使⽤JDK⾃带的Timer或者DelayQueue来实现延迟的功能，⽽是基于时间轮自定义了⼀个⽤于实现延迟功能的定时器（SystemTimer）。

JDK的Timer和DelayQueue插⼊和删除操作的平均时间复杂度为O(nlog(n))，并不能满⾜Kafka的⾼性能要求，而基于时间轮可以将插⼊和删除操作的时间复杂度都降为**O(1)**。

时间轮的应⽤并⾮Kafka独有，其应⽤场景还有很多，在Netty、Akka、Quartz、Zookeeper等组件中都存在时间轮的踪影。底层使⽤数组实现，数组中的每个元素可以存放⼀个TimerTaskList对象。

TimerTaskList是⼀个环形双向链表，在其中的链表项TimerTaskEntry中封装了真正的定时任务TimerTask.Kafka中到底是怎么推进时间的呢？Kafka中的定时器借助了JDK中的DelayQueue来协助推进时间轮。

具体做法是对于每个使⽤到的TimerTaskList都会加⼊到DelayQueue中。Kafka中的TimingWheel专⻔⽤来执⾏插⼊和删除TimerTaskEntry的操作，而DelayQueue专⻔负责时间推进的任务。再试想⼀下，DelayQueue中的第⼀个超时任务列表的expiration为200****ms，第⼆个超时任务为840ms，这⾥获取DelayQueue的队头只需要O(1)的时间复杂度。

如果采⽤每秒定时推进，那么获取到第⼀个超时的任务列表时执⾏的200次推进中有199次属于“空推进”，而获取到第⼆个超时任务时有需要执⾏639次“空推进”，这样会无故空耗机器的性能资源，这⾥采用DelayQueue来辅助以少量空间换时间，从⽽做到了“精准推进”。

Kafka中的定时器真可谓是“知⼈善⽤”，⽤TimingWheel做最擅⻓的任务添加和删除操作，⽽⽤DelayQueue做最擅⻓的时间推进⼯作，相辅相成