我们都是架构师！
关注架构师(JiaGouX)，添加“星标”
获取每天技术干货，一起成为牛逼架构师
技术群请加若飞：1321113940 进架构师群
投稿、合作、版权等邮箱：admin@137x.com
其他
从 Kafka 看时间轮算法设计
前言
冷知识：JDK Timer 和 DelayQueue 底层都是个优先队列，即采用了 minHeap 的数据结构，最快需要执行的任务排在队列第一个，不一样的是 Timer 中有个线程去拉取任务执行，DelayQueue 其实就是个容器，需要配合其他线程工作。ScheduledThreadPoolExecutor 是 JDK 的定时任务实现的一种方式，其实也就是 DelayQueue + 池化线程的一个实现。
Kafka 时间轮算法
tickMs: 时间跨度 wheelSize: 时间轮中 bucket 的个数 startMs: 开始时间 interval：时间轮的整体时间跨度 = tickMs * wheelSize currentTime: tickMs 的整数倍，代表时间轮当前所处的时间 currentTime可以将整个时间轮划分为到期部分和未到期部分，currentTime当前指向的时间格也属于到期部分，表示刚好到期，需要处理此时间格所对应的TimerTaskList中的所有任务
现在你可能会有疑问，这个抽象的 currentTime 怎么推进呢，别急看下文
那么如何支持大跨度的定时任务呢？
使用增加轮次/圈数的概念（Netty 的 HashedWheelTimer ） 举例来说，比如目前是 "0-7" 8个槽，41 % 8 + 1 = 2，即应该放在槽位是 2，下标是 1 的位置。然后 ( 41 - 1 ) / 8 = 5，即轮数记为 5。也就是说当循环 5 轮之后扫到下标的 1 的这个槽位会触发这个任务。 具体实现细节这里不详述 使用多层时间轮的概念 （Kafka 的 TimingWheel） 相较于上个方案，层级时间轮能更好控制时间粒度，可以应对更加复杂的定时任务处理场景，适用的范围更广；
在 Kafka 中时间轮之间如何关联呢，如何展现这种高一层的时间轮关系？
其实很简单就是一个内部对象的指针，指向自己高一层的时间轮对象。
另外还有一个问题，如何推进时间轮的前进，让时间轮的时间往前走
Netty 中的时间轮是通过工作线程按照固定的时间间隔 tickDuration 推进的 如果长时间没有到期任务，这种方案会带来空推进的问题，从而造成一定的性能损耗； Kafka 则是通过 DelayQueue 来推进，是一种空间换时间的思想； DelayQueue 中保存着所有的 TimerTaskList 对象，根据时间来排序，这样延时越小的任务排在越前面。 外部通过一个线程（叫做ExpiredOperationReaper）从 DelayQueue 中获取超时的任务列表 TimerTaskList，然后根据 TimerTaskList 的 过期时间来精确推进时间轮的时间，这样就不会存在空推进的问题啦。
总结
Kafka 使用时间轮来实现延时队列，因为其底层是任务的添加和删除是基于链表实现的，是 O(1) 的时间复杂度，满足高性能的要求； 对于时间跨度大的延时任务，Kafka 引入了层级时间轮，能更好控制时间粒度，可以应对更加复杂的定时任务处理场景； 对于如何实现时间轮的推进和避免空推进影响性能，Kafka 采用空间换时间的思想，通过 DelayQueue 来推进时间轮，算是一个经典的 trade off。
参考
《深入理解 Kafka》 《Netty 核心原理剖析与 RPC 实践》专栏
如喜欢本文，请点击右上角，把文章分享到朋友圈
如有想了解学习的技术点，请留言给若飞安排分享
·END·
相关阅读：
作者：Richard_Yi
来源：juejin.cn/post/7047405443961847816
版权申明：内容来源网络，版权归原创者所有。除非无法确认，我们都会标明作者及出处，如有侵权烦请告知，我们会立即删除并表示歉意。谢谢!