Kafka原理--时间轮(延时操作)

article/2025/7/28 1:20:09

原文网址:Kafka原理--时间轮(延时操作)_IT利刃出鞘的博客-CSDN博客

简介

说明

        本文介绍Kafka的时间轮的原理。

        Kafka没有延迟队列功能供用户使用,本文介绍的延时操作仅仅是Kafka内部的使用,用户无法使用。

Kafka延时操作

        Kafka中存在大量的延迟操作,比如延迟生产、延迟拉取以及延迟删除等。Kafka并没有使用JDK自带的Timer或者DelayQueue来实现延迟的功能,而是基于时间轮自定义了一个用于实现延迟功能的定时器(SystemTimer)。JDK的Timer和DelayQueue插入和删除操作的平均时间复杂度为O(nlog(n)),并不能满足Kafka的高性能要求,而基于时间轮可以将插入和删除操作的时间复杂度都降为O(1)。时间轮的应用并非Kafka独有,其应用场景还有很多,在Netty、Akka、Quartz、Zookeeper等组件中都存在时间轮的踪影。

时间轮结构

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

到期与未到期的划分

        时间轮由多个时间格组成,每个时间格代表当前时间轮的基本时间跨度(tickMs)。时间轮的时间格个数是固定的,可用wheelSize来表示,整个时间轮的总体时间跨度(interval)可以通过公式 tickMs × wheelSize计算得出。时间轮还有一个表盘指针(currentTime),用来表示时间轮当前所处的时间,currentTime是tickMs的整数倍。currentTime可以将整个时间轮划分为到期部分和未到期部分,currentTime当前指向的时间格也属于到期部分,表示刚好到期,需要处理此时间格所对应的TimerTaskList的所有任务。

任务的插入

        若时间轮的tickMs=1ms,wheelSize=20,那么可以计算得出interval为20ms。初始情况下表盘指针currentTime指向时间格0,此时有一个定时为2ms的任务插入进来会存放到时间格为2的TimerTaskList中。随着时间的不断推移,指针currentTime不断向前推进,过了2ms之后,当到达时间格2时,就需要将时间格2所对应的TimeTaskList中的任务做相应的到期操作。此时若又有一个定时为8ms的任务插入进来,则会存放到时间格10中,currentTime再过8ms后会指向时间格10。如果同时有一个定时为19ms的任务插入进来怎么办?新来的TimerTaskEntry会复用原来的TimerTaskList,所以它会插入到原本已经到期的时间格1中。总之,整个时间轮的总体跨度是不变的,随着指针currentTime的不断推进,当前时间轮所能处理的时间段也在不断后移,总体时间范围在currentTime和currentTime+interval之间。

时间超出范围的处理

        如果此时有个定时为350ms的任务该如何处理?直接扩充wheelSize的大小么?Kafka中不乏几万甚至几十万毫秒的定时任务,这个wheelSize的扩充没有底线,就算将所有的定时任务的到期时间都设定一个上限,比如100万毫秒,那么这个wheelSize为100万毫秒的时间轮不仅占用很大的内存空间,而且效率也会拉低。Kafka为此引入了层级时间轮的概念,当任务的到期时间超过了当前时间轮所表示的时间范围时,就会尝试添加到上层时间轮中。

        参考上图,复用之前的案例,第一层的时间轮tickMs=1ms, wheelSize=20, interval=20ms。第二层的时间轮的tickMs为第一层时间轮的interval,即为20ms。每一层时间轮的wheelSize是固定的,都是20,那么第二层的时间轮的总体时间跨度interval为400ms。以此类推,这个400ms也是第三层的tickMs的大小,第三层的时间轮的总体时间跨度为8000ms。

        对于之前所说的350ms的定时任务,显然第一层时间轮不能满足条件,所以就升级到第二层时间轮中,最终被插入到第二层时间轮中时间格17所对应的TimerTaskList中。如果此时又有一个定时为450ms的任务,那么显然第二层时间轮也无法满足条件,所以又升级到第三层时间轮中,最终被插入到第三层时间轮中时间格1的TimerTaskList中。注意到在到期时间在[400ms,800ms)区间的多个任务(比如446ms、455ms以及473ms的定时任务)都会被放入到第三层时间轮的时间格1中,时间格1对应的TimerTaskList的超时时间为400ms。随着时间的流逝,当次TimerTaskList到期之时,原本定时为450ms的任务还剩下50ms的时间,还不能执行这个任务的到期操作。这里就有一个时间轮降级的操作,会将这个剩余时间为50ms的定时任务重新提交到层级时间轮中,此时第一层时间轮的总体时间跨度不够,而第二层足够,所以该任务被放到第二层时间轮到期时间为[40ms,60ms)的时间格中。再经历了40ms之后,此时这个任务又被“察觉”到,不过还剩余10ms,还是不能立即执行到期操作。所以还要再有一次时间轮的降级,此任务被添加到第一层时间轮到期时间为[10ms,11ms)的时间格中,之后再经历10ms后,此任务真正到期,最终执行相应的到期操作。

        设计源于生活。我们常见的钟表就是一种具有三层结构的时间轮,第一层时间轮tickMs=1s, wheelSize=60,interval=1min,此为秒钟;第二层tickMs=1min,wheelSize=60,interval=1hour,此为分钟;第三层tickMs=1hour,wheelSize为12,interval为12hours,此为时钟。

        在Kafka中第一层时间轮的参数同上面的案例一样:tickMs=1ms, wheelSize=20, interval=20ms,各个层级的wheelSize也固定为20,所以各个层级的tickMs和interval也可以相应的推算出来。Kafka在具体实现时间轮TimingWheel时还有一些小细节:

        TimingWheel在创建的时候以当前系统时间为第一层时间轮的起始时间(startMs),这里的当前系统时间并没有简单的调用System.currentTimeMillis(),而是调用了Time.SYSTEM.hiResClockMs,这是因为currentTimeMillis()方法的时间精度依赖于操作系统的具体实现,有些操作系统下并不能达到毫秒级的精度,而Time.SYSTEM.hiResClockMs实质上是采用了System.nanoTime()/1_000_000来将精度调整到毫秒级。也有其他的某些骚操作可以实现毫秒级的精度,但是笔者并不推荐,System.nanoTime()/1_000_000是最有效的方法。(如对此有想法,可在留言区探讨。)

        TimingWheel中的每个双向环形链表TimerTaskList都会有一个哨兵节点(sentinel),引入哨兵节点可以简化边界条件。哨兵节点也称为哑元节点(dummy node),它是一个附加的链表节点,该节点作为第一个节点,它的值域中并不存储任何东西,只是为了操作的方便而引入的。如果一个链表有哨兵节点的话,那么线性表的第一个元素应该是链表的第二个节点。
除了第一层时间轮,其余高层时间轮的起始时间(startMs)都设置为创建此层时间轮时前面第一轮的currentTime。每一层的currentTime都必须是tickMs的整数倍,如果不满足则会将currentTime修剪为tickMs的整数倍,以此与时间轮中的时间格的到期时间范围对应起来。修剪方法为:currentTime = startMs - (startMs % tickMs)。currentTime会随着时间推移而推荐,但是不会改变为tickMs的整数倍的既定事实。若某一时刻的时间为timeMs,那么此时时间轮的currentTime = timeMs - (timeMs % tickMs),时间每推进一次,每个层级的时间轮的currentTime都会依据此公式推进。

        Kafka中的定时器只需持有TimingWheel的第一层时间轮的引用,并不会直接持有其他高层的时间轮,但是每一层时间轮都会有一个引用(overflowWheel)指向更高一层的应用,以此层级调用而可以实现定时器间接持有各个层级时间轮的引用。

时间的推进

        Kafka中的定时器借助了JDK中的DelayQueue来协助推进时间轮。具体做法是对于每个使用到的TimerTaskList都会加入到DelayQueue中,“每个使用到的TimerTaskList”特指有非哨兵节点的定时任务项TimerTaskEntry的TimerTaskList。DelayQueue会根据TimerTaskList对应的超时时间expiration来排序,最短expiration的TimerTaskList会被排在DelayQueue的队头。Kafka中会有一个线程来获取DelayQueue中的到期的任务列表,有意思的是这个线程所对应的名称叫做“ExpiredOperationReaper”,可以直译为“过期操作收割机”,和“SkimpyOffsetMap”的取名有的一拼。当“收割机”线程获取到DelayQueue中的超时的任务列表TimerTaskList之后,既可以根据TimerTaskList的expiration来推进时间轮的时间,也可以就获取到的TimerTaskList执行相应的操作,对立面的TimerTaskEntry该执行过期操作的就执行过期操作,该降级时间轮的就降级时间轮。

        读者读到这里或许又非常的困惑,文章开头明确指明的DelayQueue不适合Kafka这种高性能要求的定时任务,为何这里还要引入DelayQueue呢?注意对于定时任务项TimerTaskEntry插入和删除操作而言,TimingWheel时间复杂度为O(1),性能高出DelayQueue很多,如果直接将TimerTaskEntry插入DelayQueue中,那么性能显然难以支撑。就算我们根据一定的规则将若干TimerTaskEntry划分到TimerTaskList这个组中,然后再将TimerTaskList插入到DelayQueue中,试想下如果这个TimerTaskList中又要多添加一个TimerTaskEntry该如何处理?对于DelayQueue而言,这类操作显然变得力不从心。

        可以发现,Kafka中的TimingWheel专门用来执行插入和删除TimerTaskEntry的操作,而DelayQueue专门负责时间推进的任务。再试想一下,DelayQueue中的第一个超时任务列表的expiration为200ms,第二个超时任务为840ms,这里获取DelayQueue的队头只需要O(1)的时间复杂度。如果采用每秒定时推进,那么获取到第一个超时的任务列表时执行的200次推进中有199次属于“空推进”,而获取到第二个超时任务时有需要执行639次“空推进”,这样会无故空耗机器的性能资源,这里采用DelayQueue来辅助以少量空间换时间,从而做到了“精准推进”。Kafka中的定时器真可谓是“知人善用”,用TimingWheel做最擅长的任务添加和删除操作,而用DelayQueue做最擅长的时间推进工作,相辅相成。

其他网址

Kafka时间轮(TimingWheel)和Kafka中的延时操作-CSDN博客

Kafka解惑之时间轮(TimingWheel)_朱小厮的博客-CSDN博客_kafka 时间轮


http://chatgpt.dhexx.cn/article/gpA10r9G.shtml

相关文章

时间轮算法HashedWheelTimer

文章目录 一.HashedWheelTimer是什么?二.能干什么?为什么需要这个东西?优点适用场景 三.怎么用?使用步骤1.引入pom2.使用举例 四.时间轮原理五.使用注意点1.一个HashedWheelTimer对象只有一个worker线程2.每次添加的任务只会执行一次3.时间轮的参数非常重要4.所有的任务都是…

时间轮-理论篇

1. 引言 定时任务再开发过程中无处不在,定时发送消息,定时更新数据库表的状态,Linux系统定时执行脚本等等。这些操作都离不开定时任务,那么这些定时任务是怎么实现的是否又去想过。如果让开发者自己去实现一个定时任务又该怎么实…

定时任务的实现原理:时间轮算法

文章目录 前言时间轮定时使用方式时间轮定时内部原理时间轮定时源码剖析构造方法添加任务工作线程启动工作线程run方法指针跳动将队列任务放入时间轮中链表任务遍历定时任务执行 前言 最近在思考实现定时任务的几种方式,比如 quartz,delay queue&#xf…

时间轮-Java实现篇

在前面的文章《时间轮-理论篇》讲了时间轮的一些理论知识,然后根据理论知识。我们自己来实现一个简单的时间轮。 1. 理论抽象 将时间轮的理论进行抽象,主要有两个方面: 时间轮的转动每一个时间间隔任务的处理,从时间间隔的Buke…

时间轮timewheel算法

时间轮是个不太常见,但在部分场景有较高使用价值的工具。 时间轮常用于延时任务,在Netty、akka、Quartz、Zookeeper等高性能组件中都存在时间轮定时器的踪影。 从定时任务说起 自然界中定时任务无处不在,太阳每天东升西落,候鸟的…

定时器实现原理——时间轮

时间轮 时间轮算法是通过一个时间轮去维护定时任务,按照一定的时间单位对时间轮进行划分刻度。然后根据任务延时计算任务落在该时间轮的第几个刻度上,如果任务时长超出了刻度数量,则需要增加一个参数记录时间轮需要转动的圈数。 简单时间轮…

时间轮算法

一、时间轮算法 1. 时间轮的基本概念 Kafka中存在大量的延时操作,如延时生产、延时消费等;而JDK中自带的 Timer 和 DelayQueue 的插入和删除操作的平均复杂度为 O(nlogn),无法满足 Kafka 的高性能要求,因…

时间轮算法(TimingWheel)

时间轮算法的应用非常广泛,在 Dubbo、Netty、Kafka、ZooKeeper、Quartz 的组件中都有时间轮思想的应用,甚至在 Linux 内核中都有用到。 其思想理论基础可以参考论文:http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pd…

那些惊艳的算法们(三)—— 时间轮

从定时任务说起 自然界中定时任务无处不在,太阳每天东升西落,候鸟的迁徙,树木的年轮,人们每天按时上班,每个月按时发工资、交房租,四季轮换,潮涨潮落,等等,从某种意义上…

1、时间轮

一、什么是时间轮? 作为一个粗人,咱不扯什么高级的词汇,直接上图: 上面是一张时间轮的示意图,可以看到,这个时间轮就像一个钟表一样,它有刻度,图中画了9个格子,每个格子…

浅谈时间轮算法

浅谈时间轮算法 基于队列的定时任务执行模型缺陷 在计算机世界中,只有待解决的问题变得大规模后,算法的价值才能够最大化的体现。时间轮算法可以将插入和删除操作的时间复杂度都降为 O(1),在大规模问题下还能够达到非常好的运行效果。 如果…

时间轮(TimingWheel)算法总结

通过阅读篇文章您可以很容易理解平时所使用的开源框架是如何进行任务调度的。而且对于以后业务上碰到需要做时间任务调度的需求,也可以尝试着用实践论算法去实现。 一、时间轮的应用 其实早在1987年,时间轮算法的论文已经发布。论文名称:Hash…

时间轮 (史上最全)

缓存之王 Caffeine 中,涉及到100w级、1000W级、甚至亿级元素的过期问题,如何进行高性能的定时调度,是一个难题。 注: 本文从 对 海量调度任务场景中, 高性能的时间轮算法, 做了一个 系统化、由浅入深的 穿透…

时间轮(Timing Wheel)案例和原理

什么是时间轮(Timing Wheel) 时间轮(Timing Wheel)是George Varghese和Tony Lauck在1996年的论文Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility实现的,它在Linux内核中使用广泛,是Linux内核定时器…

时间轮(TimingWheel)

一、什么是时间轮 时间轮其实就是一种环形的数据结构,可以想象成时钟,分成很多格子,一个格子代表一段时间(这个时间越短,Timer的精度越高)。并用一个双向链表存储放在该格子上的延时任务,同时一…

高性能定时器3——时间轮

​ 在网络程序中我们通常要处理三种事件,网络I/O事件、信号以及定时事件,我们可以使用I/O复用系统调用(select、poll、epoll)将这三类事件进行统一处理。我们通常使用定时器来检测一个客户端的活动状态,服务器程序通常…

C#,斐波那契数列(Fibonacci Sequence)的八种算法与源代码

一、莱昂纳多斐波那契(Leonardo Fibonacci) 斐波那契公元1170年生于意大利比萨,卒于1250年,被人称作“比萨的莱昂纳多”,是一名闻名于欧洲的数学家,其主要的著作有《算盘书》、《实用几何》和《四艺经》等。…

matlab斐波那契数列画图,斐波拉契数列 斐波那契数列 matlab程序

斐波那契数列数列从第3项开始,每一项都等于前两项之和。 例子:数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368 应用: 生活斐波那契 斐波那契数列中的斐波脾气有点大,表面温和到别人误以为很好欺…

快速计算斐波那契数列(Fibonacci数列)

本文最后更新于 619 天前,其中的信息可能已经有所发展或是发生改变。 题目描述 输入一个正整数n,求Fibonacci数列的第n个数。Fibonacci数列的特点:第1,2个数为1,1。从第3个数开始,概述是前面两个数之和。即: 要求输入的…

递归求斐波那契数列

斐波那契数列 题目描述:编写一个函数,求斐波那契数列的第n项的值。 首先,对于斐波那契数列,我们是非常熟悉了,对斐波那契定义为如下:f(0)0,f(1)0,f(2)1,……f(n)f(n-1)f(n-2),其中n>1。对于这…