<返回更多

如何从 Kafka 看 时间轮 算法设计

2021-12-27    Java技术那些事
加入收藏

前言

Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。

Kafka 没有使用 JDK 自带的 Timer 和 DelayQueue 实现。因为时间复杂度上这两者插入和删除操作都是 O(logn),不能满足 Kafka 的高性能要求。

冷知识:JDK Timer 和 DelayQueue 底层都是个优先队列,即采用了 minHeap 的数据结构,最快需要执行的任务排在队列第一个,不一样的是 Timer 中有个线程去拉取任务执行,DelayQueue 其实就是个容器,需要配合其他线程工作。
ScheduledThreadPoolExecutor 是 JDK 的定时任务实现的一种方式,其实也就是 DelayQueue + 池化是线程的一个实现。

Kafka 基于时间轮实现了延时操作,时间轮算法的插入删除操作都是 O(1) 的时间复杂度,满足了 Kafka 对于性能的要求。除了 Kafka 以外,像.NETty 、ZooKeepr、Dubbo 这样的开源项目都有使用到时间轮的实现。

那么时间轮回算法是怎么样的,算法思想是什么?Kafka 中又是怎么实现它的。

Kafka 时间轮算法

时间轮回的算法思想可以通过我们日常生活中的钟表来理解。

Kafka 中的时间轮(TimingWheel)是一个存储定时任务的环形队列,底层采用数组实现,数组中的每个元素可以存放一个定时任务列表(TimerTaskList)。TimerTaskList是一个环形的双向链表,链表中的每一项表示的都是定时任务项(TimerTaskEntry),其中封装了真正的定时任务(TimerTask)。

如何从 Kafka 看 时间轮 算法设计

 

图中的几个参数:

整个时间轮的总体跨度是不变的,随着指针currentTime的不断推进,当前时间轮所能处理的时间段也在不断后移,总体时间范围在currentTime和currentTime+interval之间。

现在你可能会有疑问,这个抽象的 currentTime 怎么推进呢,别急着看下文

那么如何支持大跨度的定时任务呢?

如果要支持几十万毫秒的定时任务,难不成要扩容时间轮的那个数组?实际上这里有两种解决方案:

多层时间轮回就更像我们钟表的概念了。秒针走的一圈、分针走的一圈和时针走的一圈就形成了一个多层时间轮的关系。

如何从 Kafka 看 时间轮 算法设计

 

第N层时间轮走了一圈,等于 N+1 层时间轮走一格。即高一层时间轮的时间跨度等于当前时间轮的整体跨度。

在任务插入时,如果第一层时间轮不满足条件,就尝试插入到高一层的时间轮,以此类推。

随着时间推进,也会有一个时间轮降级的操作,原本延时较长的任务会从高一层时间轮重新提交到时间轮中,然后会被放在合适的低层次的时间轮当中等待处理;

在 Kafka 中时间轮之间如何关联呢,如果展现这种高一层的时间轮关系?

其实很简单就是一个内部对象的指针,指向自己高一层的时间轮对象。

另外还有一个问题,如何推进时间轮的前进,让时间轮的时间往前走。

其实 Kafka 采用的是一种权衡的策略,把 DelayQueue 用在了合适的地方。DelayQueue 只存放了 TimerTaskList,并不是所有的 TimerTask,数量并不多,相比空推进带来的影响是利大于弊的。

总结

本文通过 Kafka 来讲述了时间轮的算法设计思想,其中还提到了 Netty 时间轮算法的实现,可能会比较偏向理论,推荐去阅读一下 Kafka 和 Netty 时间轮实现的源码,并不是特别难,对比起来看会更有收获。

原文
https://ricstudio.top/archives/timewheel-in-kafka

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>