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

article/2025/7/28 2:23:40

时间轮

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

简单时间轮

时间轮类似于我们的钟表,当指针指到刻度上,我们就去执行对应的任务列表。例如,我们需要统计每个小时的登录用户数。

 

时间轮算法中,轮询线程遍历到某一个时间刻度后,总是执行对应刻度上任务队列中的所有任务(通常是将任务扔给异步线程池来处理),而不再需要遍历检查所有任务的时间戳是否达到要求(不用每次从小顶堆堆顶,取数据来和时间比较,然后堆化这些操作)。

现在我们即使有n个任务,轮询线程也没有必要,每轮遍历n次,我们只需要按照时间刻度来轮训即可。

不过,小时作为时间单位粒度太大,我们有时候往往会希望基于分钟、秒等作为时间刻度。最直接的方式是增加时间刻度,通过增加时间刻度,我们可以基于更精细的时间单位(分钟)来进行定时任务的执行。但是,这种实现方式有如下的缺陷:

当我们刻度增多时,而任务相对较少,效率就会下降,假如我们只有以秒为刻度,一天 24 * 60 * 60 = 86400秒,我们可能只占用几十或几百个刻度,大部分时间刻度所占用的内存空间是没有任何意义的。

round时间轮算法

我们发现,时间轮的时间刻度随着时间精度而增加并不是一个好的问题解决思路。现在,我们将时间轮的精度设置为秒,时间刻度个数固定为 60。每一个任务拥有一个 round 字段。

轮询线程的执行逻辑是:每隔一秒处理一个时间刻度上任务队列中的所有任务,任务的 round 字段减 1,接着判断如果 round 字段的值变为 0,那么将任务移出任务队列,交给异步线程池来执行对应任务。如果是重复执行任务,那么再将任务添加到任务队列中。

轮询线程遍历一次时间轮需要 60 秒。如果一个任务需要间隔 x 秒执行一次,那么其 round 字段的值为 x/60(整除),任务位于第 (x%60)(取余)个刻度对应的任务队列中。例如任务需要间隔 130 秒执行一次,那么 round 字段的值为 2,此任务位于第 10 号时间刻度的任务队列中。

 

这种方式虽然简化了时间轮的刻度个数,但是并没有减少轮询次数,效率还是相对较低。时间轮每次处理一个时间刻度,就需要处理其上任务队列的所有任务。其运行效率甚至与基于普通任务队列实现的定时任务框架没有区别。

分层时间轮

分层的时间轮算法在生活中有对应的模型,那就是水表:

 

我们可以将一天类似水表一样,分为多个轮,时、分和秒三个级别的时间轮,每一个轮的刻度分别为24、60、60个刻度。分层时间轮如下:

 

假设我们有2个任务是每天的1:00:00执行一次,任务首先添加到时轮第1刻度上,当时轮到达第1刻度时,任务转移到分轮上的第0刻度,当分轮达到第0刻度,任务转移到秒轮,当秒轮达到第0刻度,任务一次执行。

优点:

  • 轮询效率变高:不需要计算round值,其次任务队列中的任务一旦被遍历,就是需要被处理的(没有空轮询问题);
  • 线程并发好:虽然引入了并发线程,但是线程数仅仅和时钟轮的级数有关,并不会随着任务的增长而变多

分层时间轮的任务从一个时间轮转移到另一个时间轮,有点像水表中小单位的表转一圈进位到大单位一样(但是分层时间轮是从大到小,因为从小到大的话,小单位的表轮询判断次数过多)

应用:

时间轮的使用在各大框架与中间件中有使用,xxl-job,netty都对时间轮都自己的实现。思路基本上与分层的时间轮策略一致。


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

相关文章

时间轮算法

一、时间轮算法 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。对于这…

斐波那契数列(Fibonacci)

有一对兔子,出生后第3个月起每个月都生一对免子。小兔子长到第3个月后每个月又生一对兔子。假设所有兔子都不死,问40个月的免子总数为多少?解题思路: 这是一个有趣的古典数学问题。可以从表1看出兔子繁殖的规律。 …

【递归 动态规划 备忘录法】Fibonacci数列(斐波那契数列)(C++)

一、什么是Fibonacci数列 斐波那契数列指的是这样一个数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…用文字来说,就是从第3项开始,每一项都等于前两项之和。至于包不包括0,一番查阅后没有得到证实… 不过重要的是“第3项开始…

算法-斐波那契数列Fibonacci

斐波那契数列 Fibonacci 斐波那契数列是这样的数列: 0、1、1、2、3、5, 8、13、21、34 …… 下一项是上两项的和。 2 是上两项的和(1+1) 3 是上两项的和(1+2)、 5 是(2+3)、 依此类推! 更多有意思的介绍可以见参考链接; 算法 1. 直接递归 初步想法就是采用递归的…

回顾斐波那契数列

一 概述 斐波那契数列(Fibonacci sequence),又称黄金分割数列。该数列是指递归方法定义为: F(0) 0,F(0) 1,F(n) F(n-1) F(n-2) (n ≥ 2,n ∈ N*) 的数列。 具体表现形式为:0&am…

题:斐波那契数列(Fibonacci数列)——一个数最少几步变成斐波那契数列的数

题目描述: Fibonacci数列就形如:0, 1, 1, 2, 3, 5, 8, 13, ...,在Fibonacci数列中的数我们称为Fibonacci数。给你一 个N,你想让其变为一个Fibonacci数,每一步你可以把当前数字X变为X-1或者X1,现在给你一个…

Fibonacci数列前20项(斐波那契数列)

HZKs Blog 本文标题: Fibonacci数列前20项(斐波那契数列) 本文链接: https://blog.zekun.fun/2021/coding/cppfibonacci数列前20项斐波那契数列/ 题目描述 Fibonacci数列的特点:第1,2个数为1,1。从第3个数开始,概述是前面两个数之…