Kafka时间轮算法

Kafka 中存在一些定时任务(DelayedOperation)，如 DelayedFetch、DelayedProduce、DelayedHeartbeat 等，在 Kafka 中，定时任务的添加、轮转、执行、消亡等是通过时间轮来实现的。(时间轮并不是 Kafka 独有的设计，而是一种通用的实现方式，Netty 中也有用到时间轮的方式)

1.  时间轮是什么

Kafka 时间轮由多个环形数组组成，每个环形数组包含 20 个时间单位，表示一个时间维度（一轮），如：第一层时间轮，数组中的每个元素代表 1ms，一圈就是 20ms，当延迟时间大于 20ms 时，就“进位”到第二层时间轮，第二层中，每“一格”表示 20ms，依此类推…

对于一个延迟任务，大体包含三个过程：进入时间轮、降级和到期执行。

• 进入时间轮

1. 根据延迟时间计算对应的时间轮“层次”（如钟表中的“小时级”还是“分钟级”还是“秒级”，实际上是一个不断“升级”的过程，直到找到合适的“层次”）

2. 计算在该轮中的位置，并插入该位置（每个 bucket 是一个双向链表，可能包含多个延迟任务，这也是时间轮提高效率的一大原因，后面会提到）

3. 若该 bucket 是首次插入，需要将该 bucket 加入 DelayQueue 中（DelayQueue 的引入是为了解决“空推进”，后面会提到）

• 降级

1. 当时间“推进”到某个 bucket 时，说明该 bucket 中的任务在当前时间轮中的时间已经走完，需要进行“降级”，即进入更小粒度的时间轮中，reinsert 的过程和进入时间轮是类似的

• 到期执行

1. 在 reinsert 的过程中，若发现已经到期，则执行这些任务

整体过程大致如下：

2.  时间的“推进”

一种直观的想法是，像现实中的钟表一样，“一格一格”地走，这样就需要有一个线程一直不停的执行，而大多数情况下，时间轮中的 bucket 大部分是空的，指针的“推进”就没有实质作用，因此，为了减少这种“空推进”，Kafka 引入了 DelayQueue，以 bucket 为单位入队，每当有 bucket 到期，即 queue.poll 能拿到结果时，才进行时间的“推进”，减少了 ExpiredOperationReaper 线程空转的开销。

3.  为什么要用时间轮

用到延迟任务时，比较直接的想法是 DelayQueue、ScheduledThreadPoolExecutor 这些，而时间轮相比之下，最大的优势是在时间复杂度上：

时间复杂度对比：

因此，理论上，当任务较多时，TimingWheel 的时间性能优势会更明显

总结一下 Kafka 时间轮性能高的几个主要原因：

（1）时间轮的结构+双向列表 bucket，使得插入操作可以达到 O(1)的时间复杂度

（2）Bucket 的设计让多个任务“合并”，使得同一个 bucket 的多次插入只需要在 delayQueue 中入队一次，同时减少了 delayQueue 中元素数量，堆的深度也减小，delayqueue 的插入和弹出操作开销也更小