点击上方“
朱小厮的博客
”，选择“
设
为星标
”
做积极的人，而不是积极废人！
1 前言
在开始正题之前，先闲聊几句。有人说，计算机科学这个学科，软件方向研究到头就是数学，硬件方向研究到头就是物理，最轻松的是中间这批使用者，可以不太懂物理，不太懂数学，依旧可以使用计算机作为自己谋生的工具。这个规律具有普适应，再看看“定时器”这个例子，往应用层研究，有 Quartz，Spring Schedule 等框架；往分布式研究，又有 SchedulerX，ElasticJob 等分布式任务调度；往底层实现研究，又有不同的定时器实现原理，工作效率，数据结构…简单上手使用一个框架，并不能体现出个人的水平，如何与他人构成区分度？我觉得至少要在某一个方向有所建树：
-
深入研究某个现有框架的实现原理，例如：读源码
-
将一个传统技术在分布式领域很好地延伸，很多成熟的传统技术可能在单机 work well，但分布式场景需要很多额外的考虑。
-
站在设计者的角度，如果从零开始设计一个轮子，怎么利用合适的算法、数据结构，去实现它。
回到这篇文章的主题，我首先会围绕第三个话题讨论：设计实现一个定时器，可以使用什么算法，采用什么数据结构。接着再聊聊第一个话题：探讨一些优秀的定时器实现方案。
2 理解定时器
很多场景会用到定时器，例如
-
使用 TCP 长连接时，客户端需要定时向服务端发送心跳请求。
-
财务系统每个月的月末定时生成对账单。
-
双 11 的 0 点，定时开启秒杀开关。
定时器像水和空气一般，普遍存在于各个场景中，一般定时任务的形式表现为：经过固定时间后触发、按照固定频率周期性触发、在某个时刻触发。定时器是什么？可以理解为这样一个数据结构：
存储一系列的任务集合，并且 Deadline 越接近的任务，拥有越高的执行优先级
在用户视角支持以下几种操作：
NewTask：将新任务加入任务集合
Cancel：取消某个任务
在任务调度的视角还要支持：
Run：执行一个到底的定时任务
判断一个任务是否到期，基本会采用轮询的方式，
每隔一个时间片
去检查
最近的任务
是否到期，并且，在 NewTask 和 Cancel 的行为发生之后，任务调度策略也会出现调整。
说到底，定时器还是靠线程轮询实现的。
3 数据结构
我们主要衡量 NewTask（新增任务），Cancel（取消任务），Run（执行到期的定时任务）这三个指标，分析他们使用不同数据结构的时间/空间复杂度。
3.1 双向有序链表
在 Java 中，
LinkedList
是一个天然的双向链表
NewTask：O(N)
Cancel：O(1)
Run：O(1)
N：任务数
NewTask O(N) 很容易理解，按照 expireTime 查找合适的位置即可；Cancel O(1) ，任务在 Cancel 时，会持有自己节点的引用，所以不需要查找其在链表中所在的位置，即可实现当前节点的删除，这也是为什么我们使用双向链表而不是普通链表的原因是 ；Run O(1)，由于整个双向链表是基于 expireTime 有序的，所以调度器只需要轮询第一个任务即可。
3.2 堆
在 Java 中，
PriorityQueue
是一个天然的堆，可以利用传入的
Comparator
来决定其中元素的优先级。
NewTask：O(logN)
Cancel：O(logN)
Run：O(1)
N：任务数
expireTime 是
Comparator
的对比参数。NewTask O(logN) 和 Cancel O(logN) 分别对应堆插入和删除元素的时间复杂度 ；Run O(1)，由 expireTime 形成的小根堆，我们总能在堆顶找到最快的即将过期的任务。
堆与双向有序链表相比，NewTask 和 Cancel 形成了 trade off，但考虑到现实中，定时任务取消的场景并不是很多，所以堆实现的定时器要比双向有序链表优秀。
3.3 时间轮
Netty 针对 I/O 超时调度的场景进行了优化，实现了
HashedWheelTimer
时间轮算法。
HashedWheelTimer
是一个环形结构，可以用时钟来类比，钟面上有很多 bucket ，每一个 bucket 上可以存放多个任务，使用一个 List 保存该时刻到期的所有任务，同时一个指针随着时间流逝一格一格转动，并执行对应 bucket 上所有到期的任务。任务通过
取模
决定应该放入哪个 bucket 。和 HashMap 的原理类似，newTask 对应 put，使用 List 来解决 Hash 冲突。
以上图为例，假设一个 bucket 是 1 秒，则指针转动一轮表示的时间段为 8s，假设当前指针指向 0，此时需要调度一个 3s 后执行的任务，显然应该加入到 (0+3=3) 的方格中，指针再走 3 次就可以执行了；如果任务要在 10s 后执行，应该等指针走完一轮零 2 格再执行，因此应放入 2，同时将 round（1）保存到任务中。检查到期任务时只执行 round 为 0 的， bucket 上其他任务的 round 减 1。
再看图中的 bucket5，我们可以知道在 $1
8+5=13s$ 后，有两个任务需要执行，在 $2
8+5=21s$ 后有一个任务需要执行。
NewTask：O(1)
Cancel：O(1)
Run：O(M)
Tick：O(1)
M： bucket ，M ~ N/C ，其中 C 为单轮 bucket 数，Netty 中默认为 512
时间轮算法的复杂度可能表达有误，我个人觉得比较难算，仅供参考。另外，其复杂度还受到多个任务分配到同一个 bucket 的影响。并且多了一个转动指针的开销。
传统定时器是面向任务的，时间轮定时器是面向 bucket 的。
构造 Netty 的
HashedWheelTimer
时有两个重要的参数：
tickDuration
和
ticksPerWheel
。
-
tickDuration
：即一个 bucket 代表的时间，默认为 100ms，Netty 认为大多数场景下不需要修改这个参数；
-
ticksPerWheel
：一轮含有多少个 bucket ，默认为 512 个，如果任务较多可以增大这个参数，降低任务分配到同一个 bucket 的概率。
3.4 层级时间轮
Kafka 针对时间轮算法进行了优化，实现了层级时间轮
TimingWheel
如果任务的时间跨度很大，数量也多，传统的
HashedWheelTimer
会造成任务的
round
很大，单个 bucket 的任务 List 很长，并会维持很长一段时间。这时可将轮盘按时间粒度分级：
现在，每个任务除了要维护在当前轮盘的
round
，还要计算在所有下级轮盘的
round
。当本层的
round
为0时，任务按下级
round
值被下放到下级轮子，最终在最底层的轮盘得到执行。
NewTask：O(H)
Cancel：O(H)
Run：O(M)
Tick：O(1)
H：层级数量
设想一下一个定时了 3 天，10 小时，50 分，30 秒的定时任务，在 tickDuration = 1s 的单层时间轮中，需要经过：$3
24
60
60+10
60
60+50
60+30$ 次指针的拨动才能被执行。但在 wheel1 tickDuration = 1 天，wheel2 tickDuration = 1 小时，wheel3 tickDuration = 1 分，wheel4 tickDuration = 1 秒 的四层时间轮中，只需要经过 $3+10+50+30$ 次指针的拨动！
相比单层时间轮，层级时间轮在时间跨度较大时存在明显的优势。
4 常见实现
4.1 Timer
JDK 中的
Timer
是非常早期的实现，在现在看来，它并不是一个好的设计。
// 运行一个一秒后执行的定时任务
Timer timer = new Timer();
timer.schedule(new TimerTask() {
@Override
public void run() {
// do sth
}
}, 1000);
使用
Timer
实现任务调度的核心是
Timer
和
TimerTask
。其中
Timer
负责设定
TimerTask
的起始与间隔执行时间。使用者只需要创建一个
TimerTask
的继承类，实现自己的
run
方法，然后将其丢给
Timer
去执行即可。
public class Timer {
private final TaskQueue queue = new
TaskQueue();
private final TimerThread thread = new TimerThread(queue);
}
其中 TaskQueue 是使用数组实现的一个简易的堆，前面我们已经介绍过了堆这个数据结构的特点。另外一个值得注意的属性便是
TimerThread
，一个
Timer
使用了唯一的线程负责了轮询和任务的执行。
Timer
的优点在于简单易用，但也因为所有任务都是由同一个线程来调度，因此整个过程是串行执行的，同一时间只能有一个任务在执行，前一个任务的延迟或异常都将会影响到之后的任务。
轮询时如果发现 currentTime < heapFirst.executionTime，可以 wait(executionTime - currentTime) 来减少不必要的轮询时间。这是普遍被使用的一个优化。
-
Timer
只能被单线程调度
-
TimerTask
中出现的异常会影响到
Timer
的执行。
出于这两个缺陷，JDK 1.5 支持了新的定时器方案
ScheduledExecutorService
。
4.2 ScheduledExecutorService
// 运行一个一秒后执行的定时任务
ScheduledExecutorService service = Executors.newScheduledThreadPool(10);
service.scheduleA(new Runnable() {
@Override
public void run() {
//do sth
}
}, 1
, TimeUnit.SECONDS);
相比
Timer
，
ScheduledExecutorService
解决了同一个定时器调度多个任务的阻塞问题，并且任务的异常不会中断
ScheduledExecutorService
。
ScheduledExecutorService
提供了两种常用的周期调度方法 ScheduleAtFixedRate 和 ScheduleWithFixedDelay。
ScheduleAtFixedRate 每次执行时间为上一次任务开始起向后推一个时间间隔，即每次执行时间为 : $initialDelay$, $initialDelay+period$, $initialDelay+2*period$, …
ScheduleWithFixedDelay 每次执行时间为上一次任务结束起向后推一个时间间隔，即每次执行时间为：$initialDelay$, $initialDelay+executeTime+delay$, $initialDelay+2
executeTime+2
delay$, ...
由此可见，ScheduleAtFixedRate 是基于固定时间间隔进行任务调度，ScheduleWithFixedDelay 取决于每次任务执行的时间长短，是基于不固定时间间隔的任务调度。
ScheduledExecutorService
底层使用的数据结构为
PriorityQueue
，任务调度方式较为常规，不做特别介绍了。
4.3 HashedWheelTimer
Timer timer = new HashedWheelTimer();
//等价于 Timer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);
timer.newTimeout(new TimerTask() {
@Override
public void run(Timeout timeout) throws Exception {
//do sth
}
}, 1, TimeUnit.SECONDS);
前面已经介绍过了 Netty 中
HashedWheelTimer
内部的数据结构，默认构造器会配置轮询周期为 100ms，bucket 数量为 512。其使用方法和 JDK 的使用方式也十分相同。
private
