Kafka时间轮原理

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

1.1      时间轮是什么

参考网上的两张图(摘自 https://blog.csdn.net/u013256816/article/details/80697456

这两张图就比较清楚的说明了Kafka时间轮的结构了:类似现实中的钟表,由多个环形数组组成,每个环形数组包含20个时间单位,表示一个时间维度(一轮),如:第一层时间轮,数组中的每个元素代表1ms,一圈就是20ms,当延迟时间大于20ms时,就“进位”到第二层时间轮,第二层中,每“一格”表示20ms,依此类推

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

Ÿ   进入时间轮

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

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

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

    

Ÿ   降级

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

    

Ÿ   到期执行

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

    

整体过程大致如下:

        

1.2      时间的“推进”

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

1.3      为什么要用时间轮

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

时间复杂度对比:


插入任务

任务到期弹出

DelayQueue

内部是PriorityQueue,小顶堆,插入复杂度:O(logN)

O(logN)

TimingWheel(包括配套的DelayQueue

bucket插入 O(1) +   delayQueue插入 O(logM) (当重复插入bucket时,不需要delayQueue的插入操作,且delayQueue的插入因bucket元素较少,耗时也更少(M<<N))TimingWheel本身是O(1)的,但Kafka为了减少“空推进”,配合使用了DelayQueue

O(logM)M<<NTimingWheel由于bucket中可能有多个task,弹出操作也合并了,总的弹出操作数会少很多)

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

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

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

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


合智互联客户成功服务热线:400-1565-661

admin
admin管理员

上一篇:GaussDB(DWS)性能调优系列实战篇一:十八般武艺之总体调优策略
下一篇:API生态的发展与机遇:从5000组数据看API生态与开发者现状

留言评论

暂无留言
取消
扫码支持