性能文章>一文完全理解定时器实现技术>

一文完全理解定时器实现技术原创

7613210

上一篇热文《构建企业级业务高可用的延时消息中台》引起了大家的讨论,评论里讨论除了时间轮算法外的其他高性能算法实现延迟消息的定时器。这一篇文章系统的梳理主流定时器算法实现的差异以及应用地方。

定时器介绍

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

interval:间隔时间,即定时器需要在interval时间后执行
StartTimer:添加一个定时器任务
StopTimer:结束一个定时器任务
PerTickBookkeeping: 检查定时器系统中,是否有定时器实例已经到期,相当于定义了最小时间粒度。

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

链表
排序链表
最小堆
时间轮

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

定时器实现方法

链表实现

链表的实现方法比较粗糙。链表用于存储所有的定时器,每个定时器都含有interval 和 elapse 两个时间参数,elapse表示当前被tickTimer了多少次。当elapse 和interval相等时,表示定时器到期。
在此方案中,添加定时器就是在链表的末尾新增一个节点,时间复杂度是 O(1)。
如果想要删除一个定时器的话,我们需要遍历链表找到对应的定时器,时间复杂度是O(n)。
此方案下,每隔elapse时间,系统调用信号进行超时检查,即PerTickBookkeeping。每次PerTickBookkeeping需要对链表所有定时器进行 elapse++,因此可以看出PerTickBookkeeping的时间复杂度是O(N)。
可以看出此方案过于粗暴,所以使用场景极少。

排序双向链表实现

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

image.png

时间轮实现

相信上一篇文章《构建企业级业务高可用的延时消息中台》我们已经对时间轮有了很深刻的了解。时间轮示意图如下:

image.png

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

最小堆实现

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

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

image.png

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

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

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

image.png

定时器不同实现对比

时间复杂度对比

image.png

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

使用场景来看

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

分类:标签:
请先登录,查看2条精彩评论吧
快去登录吧,你将获得
  • 浏览更多精彩评论
  • 和开发者讨论交流,共同进步

为你推荐

从一起GC血案谈到反射原理
前言 首先回答一下提问者的问题。这主要是由于存在大量反射而产生的临时类加载器和 ASM 临时生成的类,这些类会被保留在 Metaspace,一旦 Metaspace 即将满的时候,就会触发 Fu
类初始化导致死锁
一张图简单描述死锁 如上图,Thread1 拿到了 object1,Thread2 拿到了 object2,但是现在 Thread1 需要拿到 object2 的锁才能继续往下,Thread2 又要拿到 object1 才能继续往下
在调试器里看LINUX内核态栈溢出
图灵最先发明了栈,但没有给它取名字。德国人鲍尔也“发明”了栈,取名叫酒窖。澳大利亚人汉布林也“发明”了栈,取名叫弹夹。1959年,戴克斯特拉在度假时想到了Stack这个名字,后来被广泛使用。
不起眼,但是足以让你收获的JVM内存案例
今天的这个案例我觉得应该会让你涨姿势吧,不管你对JVM有多熟悉,看到这篇文章,应该还是会有点小惊讶的,不过我觉得这个案例我分享出来,是想表达不管多么奇怪的现象请一定要追究下去,会让你慢慢变得强大起来,
如何通过反射获得方法的真实参数名(以及扩展研究)
前段时间,在做一个小的工程时,遇到了需要通过反射获得方法真实参数名的场景,在这里我遇到了一些小小的问题,后来在部门老大的指导下,我解决了这个问题。通过解决这个问题,附带着我了解到了很多新的知识,我觉得
谨防JDK8重复类定义造成的内存泄漏
概述 如今JDK8成了主流,大家都紧锣密鼓地进行着升级,享受着JDK8带来的各种便利,然而有时候升级并没有那么顺利?比如说今天要说的这个问题。我们都知道JDK8在内存模型上最大的改变是,放弃了Perm
JDK13 GA发布:5大特性解读
JDK13 GA版本 5大新特性如下: 350: Dynamic CDS Archives 351: ZGC: Uncommit Unused Memory 353: Reimplement the
一文完全理解定时器实现技术
上一篇热文《[构建企业级业务高可用的延时消息中台](https://heapdump.cn/article/641128)》引起了大家的讨论,评论里讨论除了时间轮算法外的其他高性能算法实现延迟