定时器的实现方式有几种类型（定时器的实现方式有几种）

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。这种方法虽然低级，但也不失为一种解决办法。