Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >系统梳理主流定时器算法实现的差异以及应用

系统梳理主流定时器算法实现的差异以及应用

原创
作者头像
江帅帅
修改于 2020-06-09 02:20:10
修改于 2020-06-09 02:20:10
1.7K0
举报
文章被收录于专栏:大数据工程师大数据工程师

这一篇文章系统的梳理主流定时器算法实现的差异以及应用地方。

1. 定时器介绍

程序里的定时器主要实现的功能是在未来的某个时间点执行相应的逻辑。在定时器模型中,一般有如下几个定义。 

interval:间隔时间,即定时器需要在interval时间后执行

StartTimer:添加一个定时器任务

StopTimer:结束一个定时器任务

PerTickBookkeeping: 检查定时器系统中,是否有定时器实例已经到期,相当于定义了最小时间粒度。

常见的实现方法有如下几种:

链表

排序链表

最小堆

时间轮 

接下来我们一起看下这些方法的具体实现原理。

2. 定时器实现方法

2.1 链表实现

链表的实现方法比较粗糙。链表用于存储所有的定时器,每个定时器都含有interval 和 elapse 两个时间参数,elapse表示当前被tickTimer了多少次。当elapse 和interval相等时,表示定时器到期。

在此方案中,添加定时器就是在链表的末尾新增一个节点,时间复杂度是 O(1)。如果想要删除一个定时器的话,我们需要遍历链表找到对应的定时器,时间复杂度是O(n)。此方案下,每隔elapse时间,系统调用信号进行超时检查,即PerTickBookkeeping。每次PerTickBookkeeping需要对链表所有定时器进行 elapse++,因此可以看出PerTickBookkeeping的时间复杂度是O(N)。可以看出此方案过于粗暴,所以使用场景极少

2.2 排序双向链表实现

排序双向链表是在链表实现上的优化。优化思路是降低时间复杂度。

首先,每次PerTickBookkeeping需要自增所有定时器的elapse变量,如果我们将interval变为绝对时间,那么我们只需要比较当前时间和interval时间是否相等,减少了对每个定时器的操作。如果不需要对每个定时器进行操作,我们将定时器进行排序,那么每次PerTickBookkeeping都只需要判断第一个定时器,时间复杂度为O(1)。相应的,为了维持链表顺序,每次新增定时器需要进行链表排序时间复杂度为 O(N)。每次删除定时器时,由于会持有自己节点的引用,所以不需要查找其在链表中所在的位置,所以时间复杂度为O(1),双向链表的好处。

图1 双向链表实现示意图
图1 双向链表实现示意图

2.3 时间轮实现

时间轮示意图如下:

图2 时间轮
图2 时间轮

时间轮的数据结构是数组 + 链表。 他的时间轮为数组,新增和删除一个任务,时间复杂度都是O(1)。PerTickBookkeeping每次转动一格,时间复杂度也是O(1)。

2.4 最小堆实现

最小堆是堆的一种, (堆是一种二叉树), 指的是堆中任何一个父节点都小于子节点, 子节点顺序不作要求。

二叉排序树(BST)指的是: 左子树节点小于父节点, 右子树节点大于父节点, 对所有节点适用

图3 最小堆
图3 最小堆

树的基本操作是插入节点和删除节点。对最小堆而言,为了将一个元素X插入最小堆,我们可以在树的下一个空闲位置创建一个空穴。如果X可以放在空穴中而不被破坏堆的序,则插入完成。否则就执行上滤操作,即交换空穴和它的父节点上的元素。不断执行上述过程,直到X可以被放入空穴,则插入操作完成。因此我们可以知道最小堆的插入时间复杂度是O(lgN)。最小堆的删除和插入逻辑基本类似,如果不做优化,时间复杂度也是O(lgN),但是实际实现方案上,做了延迟删除操作,时间复杂度为O(1)。

延迟删除即设置定时器的执行回调函数为空,每次最小堆超时,将触发pop_heap,pop会重新调整最小堆,最终删除的定时器将调整到堆顶,但是回调函数不处理。

可以看到PerTickBookkeeping只处理堆顶定时器,时间复杂度O(1)。最小堆可以使用数组来进行表示,数组中,当前下标n的左子节点为2N + 1,当前下标n的右子节点小标为2N + 2。

图4 最小堆的数组表示
图4 最小堆的数组表示

3. 定时器不同实现对比

3.1 时间复杂度对比

图5 不同实现时间复杂度
图5 不同实现时间复杂度

从上面的介绍来看,时间轮的时间复杂度最小、性能最好。

3.2 使用场景来看

在任务量小的场景下:最小堆实现,可以根据堆顶设置超时时间,数组存储结构,节省内存消耗,使用最小堆可以得到比较好的效果。而时间轮定时器,由于需要维护一个线程用来拨动指针,且需要开辟一个bucket数组,消耗内存大,使用时间轮会较为浪费资源。在任务量大的场景下:最小堆的插入复杂度是O(lgN), 相比时间轮O(1) 会造成性能下降。更适合使用时间轮实现。在业界,服务治理的心跳检测等功能需要维护大量的链接心跳,因此时间轮是首选。

更多免费技术资料及视频
更多免费技术资料及视频

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
文心一言 VS 讯飞星火 VS chatgpt (69)-- 算法导论6.5 8题
要在 O(log n) 时间内完成 HEAP-DELETE 操作,可以使用以下方法:
福大大架构师每日一题
2023/08/10
2000
文心一言 VS 讯飞星火 VS chatgpt (69)-- 算法导论6.5 8题
【nodejs原理&源码杂记(8)】Timer模块与基于二叉堆的定时器
Timer模块相关的逻辑较为复杂,不仅包含JavaScript层的实现,也包括C++编写的与底层libuv协作的代码,想要完整地看明白是比较困难的,本章仅以setTimeout这个API的实现机制为主线,讲述源码中的JavaScript相关的实现部分,这部分只需要一些数据结构的基本知识就可以理解。
大史不说话
2019/06/25
7150
【nodejs原理&源码杂记(8)】Timer模块与基于二叉堆的定时器
如何实现一个定时器?
定时器在各种场景都需要用到,比如游戏的Buff实现,Redis中的过期任务,Linux中的定时任务等等。顾名思义,定时器的主要用途是执行定时任务。
范蠡
2021/04/08
1.7K0
如何实现一个定时器?
GitHub标星3w+的项目,全面了解算法和数据结构知识
导语:今天分享一个开源项目,里面汇总了程序员技术面试时需要了解的算法和数据结构知识,并且还提供了相应的代码,目前 GitHub 上标星 35000 star,值得一看。
AI科技大本营
2019/08/20
7780
GitHub标星3w+的项目,全面了解算法和数据结构知识
Linux定时器实现
通过排序链表来保存定时器,由于链表是排序好的,所以获取最小(最早到期)的定时器的时间复杂度为 O(1)。但插入需要遍历整个链表,所以时间复杂度为 O(n)。如下图:
用户7686797
2020/08/25
3.3K0
GitHub 标星 3w+,很全面的算法和数据结构知识
今天分享一个开源项目,里面汇总了程序员技术面试时需要了解的 算法和数据结构知识,并且还提供了相应的代码,目前 GitHub 上标星 35000 star,值得一看。
五分钟学算法
2019/07/10
1.9K0
GitHub 标星 3w+,很全面的算法和数据结构知识
《基于单层时间轮与无锁数组操控的容器化定时器协同管理方法》---背景介绍
定时管理系统作为计算机系统的关键组件,在服务器、实时系统、网络通信等领域发挥着不可或缺的作用。其核心功能是按照预设时间点触发任务,保障系统的有序运行。以云计算分布式容器通信场景为例,系统需频繁设置定时器,用于确认在规定时间内是否收到应答,若超时未收到,则判定为超时失败。
用户11477875
2025/02/25
1130
定时器有几种实现方式?
在开始正题之前,先闲聊几句。有人说,计算机科学这个学科,软件方向研究到头就是数学,硬件方向研究到头就是物理,最轻松的是中间这批使用者,可以不太懂物理,不太懂数学,依旧可以使用计算机作为自己谋生的工具。这个规律具有普适应,再看看“定时器”这个例子,往应用层研究,有 Quartz,Spring Schedule 等框架;往分布式研究,又有 SchedulerX,ElasticJob 等分布式任务调度;往底层实现研究,又有不同的定时器实现原理,工作效率,数据结构…简单上手使用一个框架,并不能体现出个人的水平,如何与他人构成区分度?我觉得至少要在某一个方向有所建树:
kirito-moe
2019/03/15
4.8K0
时间轮java实现「建议收藏」
在开发高性能服务器中,定时器总是不可或缺的。 常见的定时器实现三种,分别是:排序链表,最小堆,时间轮。 之前用的定时器是基于最小堆的,如果程序中的定时器数量比较少,基于最小堆的定时器一般可以满足需求,且实现简单。
全栈程序员站长
2022/11/15
1.2K0
时间轮java实现「建议收藏」
深入Linux C/C++ Timer定时器的实现核心原理
我曾以为像定时器这样基础的功能,操作系统会有一个完备的实现。当需要开启一个定时任务的时候,会有一个优雅的、如下形式的接口:
sunsky
2020/12/21
11.7K1
深入Linux C/C++ Timer定时器的实现核心原理
一文读懂堆与栈的区别
堆(Heap)与栈(Stack)是开发人员必须面对的两个概念,在理解这两个概念时,需要放到具体的场景下,因为不同场景下,堆与栈代表不同的含义。一般情况下,有两层含义: (1)程序内存布局场景下,堆与栈表示两种内存管理方式; (2)数据结构场景下,堆与栈表示两种常用的数据结构。
恋喵大鲤鱼
2022/05/09
1.3K0
一文读懂堆与栈的区别
堆与栈区别
堆(Heap)与栈(Stack)是开发人员必须面对的两个概念,在理解这两个概念时,需要放到具体的场景下,因为不同场景下,堆与栈代表不同的含义。一般情况下,有两层含义:
Anymarvel
2020/07/27
1.4K0
堆与栈区别
定时器的实现原理
定时任务在很多场景都需要用到,比如游戏的 Buff 实现,Redis 中的过期任务,Linux 中的定时任务,电商未支付订单的关闭等等。
恋喵大鲤鱼
2023/10/12
3760
定时器的实现原理
文心一言 VS 讯飞星火 VS chatgpt (142)-- 算法导论12.1 2题
在二叉搜索树(Binary Search Tree, BST)和最小堆(Min Heap)中,元素的排列顺序都是根据其关键字的大小。然而,它们之间存在着重要的区别。
福大大架构师每日一题
2023/11/25
1940
文心一言 VS 讯飞星火 VS chatgpt (142)-- 算法导论12.1 2题
数据结构--堆的深度解析
堆(Heap)是一种非常重要的非线性数据结构,广泛应用于各种算法和问题解决中,如优先队列、堆排序、Top-k 问题等。本文将深入解析堆的定义、类型、操作、应用及其优缺点。
平凡之路.
2024/10/09
7030
数据结构--堆的深度解析
常见的数据结构及应用
数据结构是计算机存储、组织数据的方式。在工作中,我们通常会直接使用已经封装好的集合API,这样可以更高效地完成任务。但是作为一名程序员,掌握数据结构是非常重要的,因为它可以帮助我们更好地理解和设计算法,从而提高程序的效率和可靠性。
王二蛋
2024/04/26
3330
常见的数据结构
实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素。
分母为零
2019/12/04
9270
时间驱动:探索计时器方案和革命性的时间轮技术
(1)心跳检测 (2)游戏中的技能冷却 (3)倒计时 (4)其他需要延迟处理的功能 定时器,就是指定某个时间处理某个事情。
Lion 莱恩呀
2024/09/21
2140
时间驱动:探索计时器方案和革命性的时间轮技术
数据结构:堆(Heap)
堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。
sunsky
2020/10/28
1.7K0
数据结构:堆(Heap)
吴师兄导读:如何快速入门数据结构和算法
吴师兄导读:有哪些常见的数据结构?基本操作是什么?常见的排序算法是如何实现的?各有什么优缺点?本文简要分享算法基础、常见的数据结构以及排序算法,给同学们带来一堂数据结构和算法的基础课。
五分钟学算法
2020/08/21
1.7K0
吴师兄导读:如何快速入门数据结构和算法
相关推荐
文心一言 VS 讯飞星火 VS chatgpt (69)-- 算法导论6.5 8题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档