当前位置:首页 > 新型工业化 >定时器的实现方式有几种类型(定时器的实现方式有几种)

定时器的实现方式有几种类型(定时器的实现方式有几种)

1 简介

在进入正题之前,我们先闲聊几句。有人说,计算机学科,软件方向都是数学,硬件方向都是物理。最简单的是对于中层用户来说,他们对物理或数学不太了解,但仍然可以使用计算机谋生。的工具。该规则具有普遍适用性。我们再看一下“定时器”的例子。研究应用层的时候有Quartz、Spring Schedule等框架。研究分布式的时候,有SchedulerX、ElasticJob等分布式任务调度。在研究底层实现的时候,有不同的定时器实现原理、工作效率、数据结构……单纯的上手使用一个框架并不能体现你的个人水平。你如何才能让自己与他人区分开来?我觉得我们至少应该在某个方向上做出一些成绩:

定时器的实现方式有几种类型(定时器的实现方式有几种)

深入研究现有框架的实现原理,例如:阅读源码,将传统技术很好地延伸到分布式领域。很多成熟的传统技术在单机上可能可以很好地工作,但是分布式场景需要很多额外的考虑。从设计师的角度来看,如果你从头开始设计一个轮子,你如何使用合适的算法和数据结构来实现它。回到本文的主题,我首先讨论第三个主题:设计和实现定时器,可以使用哪些算法,可以使用哪些数据结构。我们先来说第一个话题:探索一些优秀的定时器实现方案。

2 理解定时器

定时器的应用场景很多,比如

使用TCP长连接时,客户端需要定时向服务器发送心跳请求。财务系统定期在每个月末生成报表。双110点,闪杀开关将定时开启。计时器就像水和空气一样,在各种场景中无处不在。一般定时任务的形式有:固定时间后触发、按照固定频率周期性触发、特定时间触发。什么是计时器?可以理解为这样一个数据结构:

存储一系列任务集,距离截止时间越近的任务,执行优先级越高。

从用户角度支持以下操作:

NewTask:向任务集合添加一个新任务

取消:取消任务

从任务调度的角度来看,我们还需要支持:

运行:执行一个定时任务到底

判断任务是否过期,基本上都是采用轮询的方式,每个时间片检查最新的任务是否过期。而且,NewTask和Cancel动作发生后,任务调度策略也会随之调整。

毕竟定时器还是通过线程轮询的方式实现的。

3 数据结构

我们主要衡量NewTask(新任务)、Cancel(取消任务)、Run(执行过期的定时任务)三个指标,并利用不同的数据结构分析它们的时间/空间复杂度。

3.1 双向有序链表

在Java中,LinkedList是一个天然的双向链表

新任务:O(N)

取消:O(1)

运行:O(1)

N:任务数量

NewTask O(N)很容易理解,根据expireTime找到合适的位置即可;取消O(1),当任务取消时,它会持有自己节点的引用,因此不需要查找其在链表中的位置,即可以实现当前节点的删除,即为什么我们使用双向链表而不是普通链表;运行O(1),由于整个双向链表是根据expireTime排序的,所以调度器只需要轮询第一个任务就可以了。

3.2 堆

在Java中,PriorityQueue是一个天然堆,可以使用传入的Comparator来确定其元素的优先级。

新任务:O(logN)

取消:O(logN)

运行:O(1)

N:任务数量

expireTime是Comparator的比较参数。 NewTask O(logN) 和Cancel O(logN) 分别对应在堆中插入和删除元素的时间复杂度;运行O(1),由expireTime形成的小根堆,我们总能在堆的顶部找到最快过期的项目Task。

与双序链表相比,NewTask 和Cancel 形成了堆和双序链表之间的权衡。但考虑到现实中,定时任务被取消的场景并不多,所以堆实现的定时器比双序链表要好。

3.3 时间轮

Netty针对I/O超时调度场景进行了优化,实现了HashedWheelTimer时间轮算法。

HashedWheelTimer是一个环形结构,可以类比为一个时钟。时钟上有很多水桶。每个桶可以存储多个任务。列表用于保存当时到期的所有任务。同时,随着时间的推移,指针会移动一格。旋转一格,执行相应桶上所有到期任务。该任务通过取模来确定应将其放入哪个桶中。与HashMap的原理类似,newTask对应put,List用于解决Hash冲突。

以上图为例,假设一个桶为1秒,则指针旋转一圈所代表的时间周期为8s。假设当前指针指向0,此时需要调度一个任务在3s后执行。显然,应该加上(0+3=3)的方格中,指针移动3次即可执行;如果任务要在10s后执行,则应等到指针完成一轮0和2方才执行,因此应放置2,并将第(1)轮保存到任务中。检查到期任务时,只会执行轮值为0的任务,桶上其他任务的轮值会减1。

看图中的bucket5,我们可以知道,有两个任务需要在$18+5=13s**之后执行,还有一个任务需要在$28+5=21s**之后执行。

新任务:O(1)

取消:O(1)

跑步:O(M)

刻度:O(1)

M:bucket,M~N/C,其中C为单轮的bucket数量,Netty中默认为512

时间轮算法的复杂度可能会被错误地表达。我个人觉得很难计算。仅供参考。另外,其复杂度还受到多个任务分配到同一个桶的影响。并且转动指针还有额外的开销。

传统定时器是面向任务的,而时间轮定时器是面向桶的。

构造Netty的HashedWheelTimer时有两个重要的参数:tickDuration和ticksPerWheel。

tickDuration:一个桶所代表的时间,默认100ms。 Netty认为大多数场景下不需要修改这个参数; ticksPerWheel:一轮包含多少个桶,默认为512。如果任务较多,可以增大该参数,也可以减小该参数。任务分配到同一存储桶的概率。

3.4 层级时间轮

Kafka优化了时间轮算法,实现了分层时间轮TimingWheel

如果任务的时间跨度很大,数量也很大,传统的HashedWheelTimer会导致任务的轮次很大,单个桶的任务列表会很长,持续很长时间。此时,轮盘赌可以按照时间粒度进行分类:

现在,每个任务不仅维护当前轮盘中的轮次,还计算所有下级轮盘中的轮次。当本层轮数为0时,根据下级轮值将任务委托给下级轮,最终在最低级轮上执行。

新任务:O(H)

取消:O(H)

跑步:O(M)

刻度:O(1)

H: 层数

想象一下计划任务的时间为3 天10 小时50 分钟30 秒。在tickDuration=1s的单层时间轮中,需要:$3246060+106060+5060+30**次指针移动才能实现。但在wheel1tickDuration=1天,wheel2tickDuration=1小时,wheel3tickDuration=1分钟,wheel4tickDuration=1秒的四层时间轮中,只需要$3+10+50+30**次指针移动!

与单层时间轮相比,分层时间轮在时间跨度较大时具有明显的优势。

4 常见实现

4.1 Timer

JDK中的Timer是一个很早期的实现,现在看来并不是一个好的设计。

//运行定时任务,一秒后执行

定时器timer=newTimer();

计时器.schedule(newTimerTask() {

@覆盖

公共无效运行(){

//做某事

}

}, 1000);

使用Timer实现任务调度的核心是Timer和TimerTask。其中,Timer负责设置TimerTask的开始和间隔执行时间。用户只需要创建一个TimerTask的继承类,实现自己的run方法,然后扔给Timer执行即可。

公共类定时器{

privatefinalTaskQueue 队列=newTaskQueue();

privatefinalTimerThread 线程=newTimerThread(queue);

}

其中,TaskQueue是一个使用数组实现的简单堆。之前我们已经介绍过堆数据结构的特点。另一个值得注意的属性是TimerThread。定时器使用唯一的线程来负责轮询和任务执行。 Timer的优点是简单易用,而且由于所有任务都是由同一个线程调度的,整个过程是串行执行的。同时只能执行一个任务,前一个任务的延迟或异常将被忽略。会影响后续工作。

如果轮询时发现currentTime heapFirst.executionTime,可以wait(executionTime - currentTime)以减少不必要的轮询时间。这是一种常用的优化。

定时器只能由单个线程调度。 TimerTask中发生异常会影响Timer的执行。由于这两个缺陷,JDK 1.5 支持一种新的计时器方案ScheduledExecutorService。

4.2 ScheduledExecutorService

//运行一秒后执行的定时任务

ScheduledExecutorService 服务=Executors.newScheduledThreadPool(10);

service.scheduleA(newRunnable() {

@覆盖

公共无效运行(){

//做某事

}

}, 1, TimeUnit.SECONDS);

与Timer相比,ScheduledExecutorService解决了同一个定时器调度多个任务的阻塞问题,并且任务异常不会中断ScheduledExecutorService。

ScheduledExecutorService提供了两种常用的周期性调度方法,ScheduleAtFixedRate和ScheduleWithFixedDelay。

ScheduleAtFixedRate 每次执行时间是从上一个任务开始往后推的一个时间间隔,即每次执行时间为: initialDelay、initialDelay+period、initialDelay+2*period、

ScheduleWithFixedDelay 每次执行时间是从上一个任务结束向后推回的时间间隔,即每次执行时间为:initialDelay、initialDelay+executeTime+delay、initialDelay+2executeTime+2delay、

可以看出,ScheduleAtFixedRate是基于固定时间间隔的任务调度,而ScheduleWithFixedDelay取决于每次任务执行的时长,是基于非固定时间间隔的任务调度。

ScheduledExecutorService 使用的底层数据结构是PriorityQueue。任务调度方法比较常规,不再详细介绍。

4.3 HashedWheelTimer

定时器timer=newHashedWheelTimer();

//相当于Timertimer=new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);

计时器.newTimeout(newTimerTask() {

@覆盖

publicvoid run(超时超时) throwsException {

//做某事

}

}, 1, TimeUnit.SECONDS);

Netty中HashedWheelTimer的内部数据结构之前已经介绍过。默认的构造函数配置轮询周期为100ms,桶数为512。它的用法也和JDK非常相似。

privatefinalWorker worker=newWorker();//可运行

privatefinalThreadworkerThread;//线程

由于篇幅限制,我不打算做详细的源码分析,但是HashedWheelTimer的上述两行代码告诉我们一个事实:HashedWheelTimer内部也是使用单线程来进行任务调度的。和JDK的Timer一样,它存在“前一个任务执行时间过长,影响后续定时任务执行”的问题。

了解HashedWheelTimer中的ticksPerWheel和tickDuration并合理配置它们可以使用户在适当的场景下获得最佳的性能。

5 最佳实践

5.1 选择合适的定时器

毫无疑问,JDK Timer使用的场景最窄,完全可以被后两者替代。 ScheduledExecutorService和HashedWheelTimer如何选择,还是要看场景。

ScheduledExecutorService 是面向任务的。当任务数量非常多时,使用堆(PriorityQueue)来维护任务的增删改查会导致性能下降,而HashedWheelTimer是面向桶的。设置合理的ticksPerWheel和tickDuration,无论任务数量多少都可以使用。限制。所以当工作量非常大的时候,HashedWheelTimer就能体现出它的优势。相反,如果任务量较小,HashedWheelTimer内部的Worker线程仍然会不断移动指针。虽然不是特别消耗性能,但至少不能说HashedWheelTimer就一定比ScheduledExecutorService更好。由于HashedWheelTimer开辟了一个桶数组,因此也会占用稍大的内存。上面的比较让我们得到一个最佳实践:当任务量很大时,使用HashedWheelTimer可以提高性能。比如服务治理框架中的心跳定时任务。当服务实例较多时,每个客户端需要定期发送心跳,每个服务器需要定期检测连接状态。这是一个非常适合使用HashedWheelTimer的场景。

5.2 单线程与业务线程池

我们需要注意HashedWheelTimer使用的是单线程调度任务。如果任务比较耗时,应该设置业务线程池,并使用HashedWheelTimer作为定时触发器。任务的实际执行交给业务线程池。

确保taskNStartTime - taskN-1StartTime taskN-1CostTime,那么就不用担心这个问题了。

5.3 全局定时器

实际使用HashedWheelTimer时,应将其视为全局任务调度程序,例如设计为静态的。永远记住一件事:HashedWheelTimer 对应于一个线程。如果每次都实例化HashedWheelTimer,一来线程会很多,二来时间轮算法就完全没有意义了。

5.4 为 HashedWheelTimer 设置合理的参数

两个参数ticksPerWheel 和tickDuration 特别重要。 ticksPerWheel 控制时间轮中的桶的数量并确定冲突的概率。 tickDuration 确定指针切换的频率。一方面会影响计时的准确性。另一方面,它决定了CPU的消耗。当任务数量非常多时,可以考虑增加ticksPerWheel;当时间精度要求不高时,可以适当增加tickDuration,但大多数情况下,不需要关心这个参数。

5.5 什么时候使用层级时间轮

当时间跨度较大时,增大单层时间轮的tickDuration可以减少空闲次数,但会导致时间精度降低。分层时间轮既可以避免精度的降低,又可以避免指针闲置次数的减少。如果有跨度较长的调度任务,可以通过分层时间轮进行调度。另外,还可以根据计时精度实例化多个不同功能的单层时间轮,如dayHashedWheelTimer、hourHashedWheelTimer、minHashedWheelTimer,并配置不同的tickDurations。这种方法虽然低级,但也不失为一种解决办法。

最新资讯

推荐资讯