一、时间轮算法
1. 时间轮的基本概念
Kafka中存在大量的延时操作，如延时生产、延时消费等；而JDK中自带的 Timer 和 DelayQueue 的插入和删除操作的平均复杂度为 O（nlogn），无法满足 Kafka 的高性能要求，因此 Kafka 基于时间轮算法自定义实现了一个用于延时功能的定时器，从而到达 O(1) 的时间复杂度，本文就对时间轮算法进行介绍：
Kafka 的时间轮 (TimingWheel) 实际就是一个存储定时任务的环形队列，底层采用数组实现，数组的每一个元素可以存放一个定时任务队列（TimerTaskList）。TimerTaskList 是一个环形的双向链表，链表中的每一项为定时任务项（TimerTaskEntry），其中封装了真正的定时任务（TimerTask）。
时间轮由固定个数（wheelSize）的时间格组成，每个时间格代表当前时间轮的基本时间跨度（tickMs），整个时间轮的总体时间跨度（interval）为 tickMs*wheelSize。
时间轮还有一个表盘指针（currentTime）,用来表示时间轮当前所处的时间，currentTime是 tickMs 的整数倍。 currentTime 可以将整个时间轮划分为到期部分和未到期部分，currentTime 当前指向的时间格刚好到期，需要处理此时间格对应的 TimerTaskList 中的所有任务。
2. 时间轮的轮转：
- 假定时间轮的 tickMs = 1ms， wheelSize = 20
- 初始情况下，currentTime指向0，若此时插入一个延时2ms的任务，则会被存进时间格为2的 TimerTaskList 中，该插入操作的时间复杂度为 O(1)
- 过了2ms后，指针到达时间格2，就会将时间格2对应的 TimerTaskList 中的任务进行相应到期操作。
- 此时，若又有一个定时为8ms的任务插入，则会被存入到时间格10中
- 如果又同时又有一个延时19ms的任务插入，则会复用原来的 TimerTaskList，插入原本已经到期的时间格1
3. 层级时间轮
时间轮按照上述的方式运转，但是可以看到该时间轮的时间范围（interval）是有限的（tickMs*wheelSize），如果任务的延时超过了该时间范围（interval），如此时要插入一个延时为350ms的任务，则涉及到了层级时间轮，需要将该任务添加到上层时间轮中
第二层的时间轮的 tickMs 为第一层时间轮的 interval （20*1ms = 20ms），而每一层时间轮的 wheelSize 是固定的，都是20，因此第二层时间轮的时间跨度为 400ms，以此类推，第三层时间轮的时间跨度为8000ms
接下来看看延时350ms的任务的执行：
- 该任务被放到第二层时间轮的时间格17中 [340ms, 360ms)
- 时间运转到340ms时，该任务还剩下10ms 的时间，还不能执行这个任务的到期操作，因此会进行时间轮的降级
- 该任务会被降级到下层时间轮到期时间为 [10ms, 11ms）的时间格中
- 之后再经历10ms，任务真正到期，最终执行到期操作
4.时间轮的推进
接下来还存在一个问题，Kafka的时间是怎么推进的？如果类似采用 JDK 中的 scheduleAtFixedRate逐秒推进，显然是不合理的，这会造成很多时间帧的“空推进”，导致时间轮也失去了大部分的意义
Kafka中的定时器借助 JDK 中的 DelayQueue 来协助推进时间轮。其将每个使用到的 TimerTaskList 都加入 DelayQueue，DelayQueue会根据 TimerTaskList 对应的超时时间进行排序，最快到期的 TimerTaskList 会被排在队头。
Kafka 中有一个特定线程会去队头获取到期的 TimerTaskList ，进而对里面的 TimerTaskEntry 执行过期操作。
读到这里可能会困惑，开头明确指明了 DelayQueue 的时间复杂度太高，这里为何还要引入 DelayQueue呢。注意如果将TimerTaskEntry 直接插入 DelayQueue 中，性能显然是难以支撑的。而根据一定的规则将若干 TimerTaskEntry 划分到 TimerTaskList 这个组，再将 TimerTaskList 插入 DelayQueue，显然就大大降低了时间复杂度。且通过 DelayQueue推进时间又显著减少了时间的“空推进”，减少无故空耗机器的性能资源，通过以少量空间换时间做到“精准推进”。
