简单描述时间轮

article/2025/7/28 0:44:20

时间轮

作用

也是用来作定时器触发任务，只是他更高效，时间复杂度为O(1)。

运行原理

为了方便理解我们参考钟表，它分为3个层次：时、分、秒，只有秒针在运动，走动一格时间为1秒，走一圈为1分钟，分针走一圈为1小时。
同样的，时间轮也分为多层，同样的只有第一层在运动，第一层走完，第二层走一格，第二层走完，第三次走一格，依次类推！！！
这样做就能用几个数组，代表一段较长的时间区间，左下图能计算0 - 135（ 5333 ），如果将层1数组长度设置为60，第二层设置为60，第三层设置12，第四层去掉，则就是右下图的时钟了，时间区间为 0 - 42200（6060*12）秒
在这里插入图片描述

时间与每层的索引关系

举个简单的4层时间轮例子（如左上图），假设最小计时单位为1（姑且理解为秒）
时间轮初始为0，那么给定任意时间time，求time落在每层时间轮的索引！
显然这是一个数学关系：
第一层：int first_index = time%5
第二层： int sencond_index = time/5 % 3
第三层： int third_index = time/5/3%3
第四层： int forth_index = time/5/3/3%3
如果不是很理解，可以举时钟的例子，假设当前时间为 3820 秒，求时分秒指针在哪个位置？ 显然：
秒：3820%60 = 40
分：3820/60%60 = 3；
时：3820/60/60%12 = 1；

如何把事件与时间轮结合？

从数据结构设计

时间轮是由多个定长数组组成的，我们只需要把事件接在数组中就可以了，由于同一时刻会有多个事件，考虑先添加的事件先执行，使用链表来把事件连接起来，因此时间轮是一个 定长的包含链表的数组

事件添加过程

只要知道了时间，就能得到给定的时间所在的层数与索引，就能找到该位置对应的事件链表，然后把事件添加进去

执行过程

为了方便说明，依然以下图为例，以time作为从0开始时间，单位为秒，每过一秒 time+1。
事件执行永远只在1层，每过1秒数组索引右移一位，同时执行该数组里面的事件，执行完后删除事件，完整遍历后，需要把2层的事件更新到1层来执行，2层的事件都执行完后，需要把3层的事件更新到1、2，依此类推，直到最后一层。事件更新后又回到起始位置进行新一轮的事件执行过程。
显然，任务执行的过程很容易理解，用time对5求余就能知道事件执行到了那一刻，那么何时分发呢？注意看下图标红部分，因为举的例子层数和每层的数组长度都很少，先不考虑第四次，很容易知道当time等于 5、10、15、20、25、30、35、40、45时需要先分发事件在执行，不难看出：
time% 5 == 0 时需要找把2层的事件更新到1层 （5）
time%15 == 0 时需要找把3层的事件更新到2、1层 （53）
time%45 == 0 时需要找把4层的事件更新到3、2、1层 （53*3）
…
**注意：**时间轮会有自己的最大计时区间，区间范围取决于时间轮层数及每层数组的大小，下图只有135秒的计时范围
在这里插入图片描述

实现过程

以我自己的demo为例。
数据结构：
1、定义任务节点，组成任务链，节点应该包含需要执行的任务和任务执行的时间（以时间轮为起始点的时间）
2、定长链表数组，组成多层轮子，链表的节点为1定义的节点
3、定义时间变量，记录时间轮从起始时刻到当前的时间
成员函数：
1、增加节点函数
2、任务执行函数
3、数据更新函数（主要是为了从下层时间轮拿任务节点）
源代码有注释
头文件

//任务节点
class Node{
public:qint64 expire = 0;Node *next = nullptr;
};
//任务节点链表
class NodeList{
public:Node head;Node *tail = nullptr;
};
class TimeWheel
{
public:TimeWheel();const static qint64 FIRST_MAST = 8;const static qint64 EACH_MAST  = 6;const static qint64 WHEEL_LEVEL = 5;const static qint64 v = 1;const static qint64 WHEEL_EACH_NUM = v<<EACH_MAST;const static qint64 WHEEL_FIRST_NUM = (v<<FIRST_MAST);//定长链表数组NodeList first_wheel[WHEEL_FIRST_NUM];NodeList other_level_wheel[WHEEL_LEVEL-1][WHEEL_EACH_NUM];void addNodeInList(NodeList&,Node*node);Node* clearNodeList(NodeList&);void dispatchNode(NodeList&);qint64 curtime;//单位为时间轮的单位刻度void checkWheelUpdate();//数据更新函数void addNode(Node *node);//添加节点函数void addNode(int expire);void execScale();void execTask();//任务执行函数};#endif // TIMEWHEEL_H

源文件

#include "timewheel.h"
#include <QDebug>
TimeWheel::TimeWheel()
{curtime = 0;qDebug()<<"WHEEL_FIRST_NUM:"<<WHEEL_FIRST_NUM;qDebug()<<"WHEEL_EACH_NUM:"<<WHEEL_EACH_NUM;
}void TimeWheel::addNodeInList(NodeList&list,Node*node)
{if(list.head.next == nullptr){list.head.next = node;list.tail = node;}else{list.tail->next = node;list.tail = node;}}void TimeWheel::addNode(int expire)
{Node *node = new Node;node->expire = curtime + expire;node->next = nullptr;addNode(node);}/*注意节点的expire时间用来确认事件应该放在数组的哪个位置delay 用来判断在哪层时间轮	
*/
void TimeWheel::addNode(Node *node)
{int t = node->expire;int delay = node->expire - curtime;int index = 0;if(delay < WHEEL_FIRST_NUM){index = t % WHEEL_FIRST_NUM;addNodeInList(first_wheel[index],node);}else if(delay < WHEEL_EACH_NUM * WHEEL_FIRST_NUM){index = t/ WHEEL_FIRST_NUM%WHEEL_EACH_NUM;addNodeInList(other_level_wheel[0][index],node);}else if(delay < WHEEL_EACH_NUM*WHEEL_EACH_NUM * WHEEL_FIRST_NUM){index = t/ (WHEEL_EACH_NUM * WHEEL_FIRST_NUM)%WHEEL_EACH_NUM;addNodeInList(other_level_wheel[1][index],node);}else if(delay < WHEEL_EACH_NUM * WHEEL_FIRST_NUM){index = t/ (WHEEL_EACH_NUM *WHEEL_EACH_NUM * WHEEL_FIRST_NUM)%WHEEL_EACH_NUM;addNodeInList(other_level_wheel[2][index],node);}else if(delay < WHEEL_EACH_NUM * WHEEL_FIRST_NUM){index = t/ (WHEEL_EACH_NUM *WHEEL_EACH_NUM *WHEEL_EACH_NUM * WHEEL_FIRST_NUM)%WHEEL_EACH_NUM;addNodeInList(other_level_wheel[3][index],node);}}void TimeWheel::dispatchNode(NodeList& list)
{Node *curnode = list.head.next;//将节点分发时，需要清楚当前链表上的节点list.head.next = nullptr;list.tail = &list.head;while (curnode != nullptr) {Node *tmpnode = curnode;curnode = curnode->next;//因为添加节点时要保证节点为1个，而不是一个链表//固将链表的连接点打断tmpnode->next = nullptr;addNode(tmpnode);}
}Node* TimeWheel::clearNodeList(NodeList&list)
{Node*node = list.head.next;list.head.next = nullptr;list.tail = &list.head;return node;
}void TimeWheel::execTask(){int index = curtime % WHEEL_FIRST_NUM;Node *curnode = clearNodeList(first_wheel[index]);while (curnode != nullptr) {//执行定时节点任务qDebug()<<"expire time:"<<curnode->expire;Node *nextnode = curnode->next;delete curnode;curnode =  nextnode;}}void TimeWheel::execScale()
{execTask();//执行任务checkWheelUpdate();//检测更新curtime++;//时间刻度更新
}void TimeWheel::checkWheelUpdate()
{qint64 dispatch_radio = WHEEL_FIRST_NUM;qint64 dispatch_mask = curtime % dispatch_radio;qint64 tmpa = WHEEL_FIRST_NUM;int level = 0;while(curtime != 0 && dispatch_mask == 0){dispatch_radio *= WHEEL_EACH_NUM;dispatch_mask = curtime % dispatch_radio ;if(dispatch_mask == 0 ){//如果整除，则往下一层找level++;tmpa *= WHEEL_EACH_NUM;continue;}int index = curtime/tmpa%WHEEL_EACH_NUM;dispatchNode(other_level_wheel[level][index]);}
}

由于时间轮每层的数组的长度可以定义为任何值，并且时间轮涉及到了很多乘法和除法和取余，所以可以考虑使用位运算来替代运行。

完整Demo源码

qt c++代码


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

相关文章

再谈时间轮

再谈时间轮

时间轮很早前就很流行了&#xff0c;在很多优秀开源框架中都有用到&#xff0c;像kafka、netty。也算是现在工程师基本都了解的一个知识储备了。有幸在工作中造过两次轮子&#xff0c;所以今天聊聊时间轮。 时间轮是一种高性能定时器。 时间轮&#xff0c;顾名思义&#xff0c…
阅读更多...
时间轮原理及其在框架中的应用

时间轮原理及其在框架中的应用

一、时间轮简介 1.1 为什么要使用时间轮 在平时开发中&#xff0c;经常会与定时任务打交道。下面举几个定时任务处理的例子。 1&#xff09;心跳检测。在Dubbo中&#xff0c;需要有心跳机制来维持Consumer与Provider的长连接&#xff0c;默认的心跳间隔是60s。当Provider在3…
阅读更多...
时间轮分析

时间轮分析

背景 在需要完成重试机制或者心跳机制一类的业务&#xff0c;除了使用excutors做定时任务。还可以使用时间轮完成这类需求 分析 使用dubbo中的心跳重试作为案例分析时间轮的使用 源码分析 在HeaderExchangeClient启动的时候调用startHeartBeatTask()开启心跳任务&#xff0…
阅读更多...
Netty时间轮

Netty时间轮

概述 时间轮是一个高性能&#xff0c;低消耗的数据结构&#xff0c;它适合用非准实时&#xff0c;延迟的短平快任务&#xff0c;例如心跳检测。在netty和kafka中都有使用。 比如Netty动辄管理100w的连接&#xff0c;每一个连接都会有很多超时任务。比如发送超时、心跳检测间隔等…
阅读更多...
高性能定时器时间轮的实现

高性能定时器时间轮的实现

时间轮的概念 关于定时器有很多种&#xff0c;有基于升序的定时器时间链表&#xff0c;但是这种链表存在效率的不足&#xff0c;就是当插入定时器的时候时间复杂度是O(n).今天&#xff0c;我们来认识一下高性能定时器时间轮。 如上图所示&#xff0c;就是一个时间轮的基本轮廓…
阅读更多...
深度剖析 -- 时间轮算法（TimingWheel）是如何实现的？

深度剖析 -- 时间轮算法（TimingWheel）是如何实现的？

前言 时间轮的应用场景很多&#xff0c;在 Netty、Akka、Quartz、ZooKeeper 、Kafka等组件中都存在时间轮的踪影。我们下面讲解的时间轮的实现以JRaft中的为例子进行讲解&#xff0c;因为JRaft这部分的代码是参考Netty的&#xff0c;所以大家也可以去Netty中去寻找源码实现。 …
阅读更多...
Kafka原理--时间轮(延时操作)

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

原文网址&#xff1a;Kafka原理--时间轮(延时操作)_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍Kafka的时间轮的原理。 Kafka没有延迟队列功能供用户使用&#xff0c;本文介绍的延时操作仅仅是Kafka内部的使用&#xff0c;用户无法使用。 Kafka延时操作 Kafka中存在大量的…
阅读更多...
时间轮算法HashedWheelTimer

时间轮算法HashedWheelTimer

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

时间轮-理论篇

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

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

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

时间轮-Java实现篇

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

时间轮timewheel算法

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

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

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

时间轮算法

一、时间轮算法 1. 时间轮的基本概念 Kafka中存在大量的延时操作&#xff0c;如延时生产、延时消费等&#xff1b;而JDK中自带的 Timer 和 DelayQueue 的插入和删除操作的平均复杂度为 O&#xff08;nlogn&#xff09;&#xff0c;无法满足 Kafka 的高性能要求&#xff0c;因…
阅读更多...
时间轮算法（TimingWheel）

时间轮算法（TimingWheel）

时间轮算法的应用非常广泛&#xff0c;在 Dubbo、Netty、Kafka、ZooKeeper、Quartz 的组件中都有时间轮思想的应用&#xff0c;甚至在 Linux 内核中都有用到。 其思想理论基础可以参考论文&#xff1a;http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pd…
阅读更多...
那些惊艳的算法们（三）—— 时间轮

那些惊艳的算法们（三）—— 时间轮

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

1、时间轮

一、什么是时间轮&#xff1f; 作为一个粗人&#xff0c;咱不扯什么高级的词汇&#xff0c;直接上图&#xff1a; 上面是一张时间轮的示意图&#xff0c;可以看到&#xff0c;这个时间轮就像一个钟表一样&#xff0c;它有刻度&#xff0c;图中画了9个格子&#xff0c;每个格子…
阅读更多...
浅谈时间轮算法

浅谈时间轮算法

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

时间轮（TimingWheel）算法总结

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

时间轮 （史上最全）

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

Copyright @ 2022~2023