1 前言

在開始正題之前，先閑聊幾句。有人說，計算機科學這個學科，軟件方向研究到頭就是數(shù)學，硬件方向研究到頭就是物理，最輕松的是中間這批使用者，可以不太懂物理，不太懂數(shù)學，依舊可以使用計算機作為自己謀生的工具。這個規(guī)律具有普適應，再看看“定時器”這個例子，往應用層研究，有 Quartz，Spring Schedule 等框架；往分布式研究，又有 SchedulerX，ElasticJob 等分布式任務調(diào)度；往底層實現(xiàn)研究，又有不同的定時器實現(xiàn)原理，工作效率，數(shù)據(jù)結(jié)構(gòu)…簡單上手使用一個框架，并不能體現(xiàn)出個人的水平，如何與他人構(gòu)成區(qū)分度？我覺得至少要在某一個方向有所建樹：

1. 深入研究某個現(xiàn)有框架的實現(xiàn)原理，例如：讀源碼
2. 將一個傳統(tǒng)技術(shù)在分布式領域很好地延伸，很多成熟的傳統(tǒng)技術(shù)可能在單機 work well，但分布式場景需要很多額外的考慮。
3. 站在設計者的角度，如果從零開始設計一個輪子，怎么利用合適的算法、數(shù)據(jù)結(jié)構(gòu)，去實現(xiàn)它。

回到這篇文章的主題，我首先會圍繞第三個話題討論：設計實現(xiàn)一個定時器，可以使用什么算法，采用什么數(shù)據(jù)結(jié)構(gòu)。接著再聊聊第一個話題：探討一些優(yōu)秀的定時器實現(xiàn)方案。

2 理解定時器

很多場景會用到定時器，例如

1. 使用 TCP 長連接時，客戶端需要定時向服務端發(fā)送心跳請求。
2. 財務系統(tǒng)每個月的月末定時生成對賬單。
3. 雙 11 的 0 點，定時開啟秒殺開關。

定時器像水和空氣一般，普遍存在于各個場景中，一般定時任務的形式表現(xiàn)為：經(jīng)過固定時間后觸發(fā)、按照固定頻率周期性觸發(fā)、在某個時刻觸發(fā)。定時器是什么？可以理解為這樣一個數(shù)據(jù)結(jié)構(gòu)：

存儲一系列的任務集合，并且 Deadline 越接近的任務，擁有越高的執(zhí)行優(yōu)先級

在用戶視角支持以下幾種操作：

NewTask：將新任務加入任務集合

Cancel：取消某個任務

在任務調(diào)度的視角還要支持：

Run：執(zhí)行一個到底的定時任務

判斷一個任務是否到期，基本會采用輪詢的方式，每隔一個時間片 去檢查 最近的任務 是否到期，并且，在 NewTask 和 Cancel 的行為發(fā)生之后，任務調(diào)度策略也會出現(xiàn)調(diào)整。

說到底，定時器還是靠線程輪詢實現(xiàn)的。

3 數(shù)據(jù)結(jié)構(gòu)

我們主要衡量 NewTask（新增任務），Cancel（取消任務），Run（執(zhí)行到期的定時任務）這三個指標，分析他們使用不同數(shù)據(jù)結(jié)構(gòu)的時間/空間復雜度。

3.1 雙向有序鏈表

在 Java 中， LinkedList 是一個天然的雙向鏈表

NewTask：O(N)

Cancel：O(1)

Run：O(1)

N：任務數(shù)

NewTask O(N) 很容易理解，按照 expireTime 查找合適的位置即可；Cancel O(1) ，任務在 Cancel 時，會持有自己節(jié)點的引用，所以不需要查找其在鏈表中所在的位置，即可實現(xiàn)當前節(jié)點的刪除，這也是為什么我們使用雙向鏈表而不是普通鏈表的原因是 ；Run O(1)，由于整個雙向鏈表是基于 expireTime 有序的，所以調(diào)度器只需要輪詢第一個任務即可。

3.2 堆

在 Java 中， PriorityQueue 是一個天然的堆，可以利用傳入的 Comparator 來決定其中元素的優(yōu)先級。

NewTask：O(logN)

Cancel：O(logN)

Run：O(1)

N：任務數(shù)

expireTime 是 Comparator 的對比參數(shù)。NewTask O(logN) 和 Cancel O(logN) 分別對應堆插入和刪除元素的時間復雜度 ；Run O(1)，由 expireTime 形成的小根堆，我們總能在堆頂找到最快的即將過期的任務。

堆與雙向有序鏈表相比，NewTask 和 Cancel 形成了 trade off，但考慮到現(xiàn)實中，定時任務取消的場景并不是很多，所以堆實現(xiàn)的定時器要比雙向有序鏈表優(yōu)秀。

3.3 時間輪

Netty 針對 I/O 超時調(diào)度的場景進行了優(yōu)化，實現(xiàn)了 HashedWheelTimer 時間輪算法。

HashedWheelTimer 是一個環(huán)形結(jié)構(gòu)，可以用時鐘來類比，鐘面上有很多 bucket ，每一個 bucket 上可以存放多個任務，使用一個 List 保存該時刻到期的所有任務，同時一個指針隨著時間流逝一格一格轉(zhuǎn)動，并執(zhí)行對應 bucket 上所有到期的任務。任務通過 取模決定應該放入哪個 bucket 。和 HashMap 的原理類似，newTask 對應 put，使用 List 來解決 Hash 沖突。

以上圖為例，假設一個 bucket 是 1 秒，則指針轉(zhuǎn)動一輪表示的時間段為 8s，假設當前指針指向 0，此時需要調(diào)度一個 3s 后執(zhí)行的任務，顯然應該加入到 (0+3=3) 的方格中，指針再走 3 次就可以執(zhí)行了；如果任務要在 10s 后執(zhí)行，應該等指針走完一輪零 2 格再執(zhí)行，因此應放入 2，同時將 round（1）保存到任務中。檢查到期任務時只執(zhí)行 round 為 0 的， bucket 上其他任務的 round 減 1。

再看圖中的 bucket5，我們可以知道在 $18+5=13s** 后，有兩個任務需要執(zhí)行，在 $28+5=21s** 后有一個任務需要執(zhí)行。

NewTask：O(1)

Cancel：O(1)

Run：O(M)

Tick：O(1)

M：bucket ，M ~ N/C ，其中 C 為單輪 bucket 數(shù)，Netty 中默認為 512

時間輪算法的復雜度可能表達有誤，我個人覺得比較難算，僅供參考。另外，其復雜度還受到多個任務分配到同一個 bucket 的影響。并且多了一個轉(zhuǎn)動指針的開銷。

傳統(tǒng)定時器是面向任務的，時間輪定時器是面向 bucket 的。

構(gòu)造 Netty 的 HashedWheelTimer 時有兩個重要的參數(shù)：tickDuration 和 ticksPerWheel。

1. tickDuration：即一個 bucket 代表的時間，默認為 100ms，Netty 認為大多數(shù)場景下不需要修改這個參數(shù)；
2. ticksPerWheel：一輪含有多少個 bucket ，默認為 512 個，如果任務較多可以增大這個參數(shù)，降低任務分配到同一個 bucket 的概率。

3.4 層級時間輪

Kafka 針對時間輪算法進行了優(yōu)化，實現(xiàn)了層級時間輪 TimingWheel

如果任務的時間跨度很大，數(shù)量也多，傳統(tǒng)的 HashedWheelTimer 會造成任務的 round 很大，單個 bucket 的任務 List 很長，并會維持很長一段時間。這時可將輪盤按時間粒度分級：

現(xiàn)在，每個任務除了要維護在當前輪盤的 round，還要計算在所有下級輪盤的 round。當本層的 round為0時，任務按下級 round 值被下放到下級輪子，最終在最底層的輪盤得到執(zhí)行。

NewTask：O(H)

Cancel：O(H)

Run：O(M)

Tick：O(1)

H：層級數(shù)量

設想一下一個定時了 3 天，10 小時，50 分，30 秒的定時任務，在 tickDuration = 1s 的單層時間輪中，需要經(jīng)過：$3246060+106060+5060+30** 次指針的撥動才能被執(zhí)行。但在 wheel1 tickDuration = 1 天，wheel2 tickDuration = 1 小時，wheel3 tickDuration = 1 分，wheel4 tickDuration = 1 秒 的四層時間輪中，只需要經(jīng)過 $3+10+50+30** 次指針的撥動！

相比單層時間輪，層級時間輪在時間跨度較大時存在明顯的優(yōu)勢。

4 常見實現(xiàn)

4.1 Timer

JDK 中的 Timer 是非常早期的實現(xiàn)，在現(xiàn)在看來，它并不是一個好的設計。

1. // 運行一個一秒后執(zhí)行的定時任務

2. Timer timer = newTimer();

3. timer.schedule(newTimerTask() {

4. @Override

5. publicvoid run() {

6. // do sth

7. }

8. }, 1000);

使用 Timer 實現(xiàn)任務調(diào)度的核心是 Timer 和 TimerTask。其中 Timer 負責設定 TimerTask的起始與間隔執(zhí)行時間。使用者只需要創(chuàng)建一個 TimerTask 的繼承類，實現(xiàn)自己的 run 方法，然后將其丟給 Timer 去執(zhí)行即可。

1. publicclassTimer {

2. privatefinalTaskQueue queue = newTaskQueue();

3. privatefinalTimerThread thread = newTimerThread(queue);

4. }

其中 TaskQueue 是使用數(shù)組實現(xiàn)的一個簡易的堆，前面我們已經(jīng)介紹過了堆這個數(shù)據(jù)結(jié)構(gòu)的特點。另外一個值得注意的屬性便是 TimerThread，一個 Timer 使用了唯一的線程負責了輪詢和任務的執(zhí)行。Timer 的優(yōu)點在于簡單易用，但也因為所有任務都是由同一個線程來調(diào)度，因此整個過程是串行執(zhí)行的，同一時間只能有一個任務在執(zhí)行，前一個任務的延遲或異常都將會影響到之后的任務。

輪詢時如果發(fā)現(xiàn) currentTime < heapFirst.executionTime，可以 wait(executionTime - currentTime) 來減少不必要的輪詢時間。這是普遍被使用的一個優(yōu)化。

1. Timer 只能被單線程調(diào)度
2. TimerTask 中出現(xiàn)的異常會影響到 Timer 的執(zhí)行。

出于這兩個缺陷，JDK 1.5 支持了新的定時器方案 ScheduledExecutorService。

4.2 ScheduledExecutorService

1. // 運行一個一秒后執(zhí)行的定時任務

2. ScheduledExecutorService service = Executors.newScheduledThreadPool(10);

3. service.scheduleA(newRunnable() {

4. @Override

5. publicvoid run() {

6. //do sth

7. }

8. }, 1, TimeUnit.SECONDS);

相比 Timer， ScheduledExecutorService 解決了同一個定時器調(diào)度多個任務的阻塞問題，并且任務的異常不會中斷 ScheduledExecutorService。

ScheduledExecutorService 提供了兩種常用的周期調(diào)度方法 ScheduleAtFixedRate 和 ScheduleWithFixedDelay。

ScheduleAtFixedRate 每次執(zhí)行時間為上一次任務開始起向后推一個時間間隔，即每次執(zhí)行時間為 : initialDelay, initialDelay+period, initialDelay+2*period, …

ScheduleWithFixedDelay 每次執(zhí)行時間為上一次任務結(jié)束起向后推一個時間間隔，即每次執(zhí)行時間為：initialDelay, initialDelay+executeTime+delay, initialDelay+2executeTime+2delay, ...

由此可見，ScheduleAtFixedRate 是基于固定時間間隔進行任務調(diào)度，ScheduleWithFixedDelay 取決于每次任務執(zhí)行的時間長短，是基于不固定時間間隔的任務調(diào)度。

ScheduledExecutorService 底層使用的數(shù)據(jù)結(jié)構(gòu)為 PriorityQueue，任務調(diào)度方式較為常規(guī)，不做特別介紹了。

4.3 HashedWheelTimer

1. Timer timer = newHashedWheelTimer();

2. //等價于 Timer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);

3. timer.newTimeout(newTimerTask() {

4. @Override

5. publicvoid run(Timeout timeout) throwsException {

6. //do sth

7. }

8. }, 1, TimeUnit.SECONDS);

前面已經(jīng)介紹過了 Netty 中 HashedWheelTimer 內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，默認構(gòu)造器會配置輪詢周期為 100ms，bucket 數(shù)量為 512。其使用方法和 JDK 的使用方式也十分相同。

1. privatefinalWorker worker = newWorker();// Runnable

2. privatefinalThread workerThread;// Thread

由于篇幅限制，我并不打算做詳細的源碼分析，但上述兩行來自 HashedWheelTimer 的代碼告訴了我們一個事實：HashedWheelTimer 內(nèi)部也同樣是使用了單個線程來進行任務調(diào)度。他跟 JDK 的 Timer 一樣，存在”前一個任務執(zhí)行時間過長，影響后續(xù)定時任務執(zhí)行的問題“。

理解 HashedWheelTimer 中的 ticksPerWheel，tickDuration，對二者進行合理的配置，可以使得用戶在合適的場景得到最佳的性能。

5 最佳實踐

5.1 選擇合適的定時器

毋庸置疑，JDK 的 Timer 使用的場景是最窄的，完全可以被后兩者取代。如何在 ScheduledExecutorService 和 HashedWheelTimer 之間如何做選擇，還是要區(qū)分場景來看待。

1. ScheduledExecutorService 是面向任務的，當任務數(shù)非常大時，使用堆(PriorityQueue)維護任務的新增、刪除會造成性能的下降，而 HashedWheelTimer 是面向 bucket 的，設置合理的 ticksPerWheel，tickDuration ，可以不受任務量的限制。所以在任務量非常大時， HashedWheelTimer 可以表現(xiàn)出它的優(yōu)勢。
2. 相反，如果任務量少， HashedWheelTimer 內(nèi)部的 Worker 線程依舊會不停的撥動指針，雖然不是特別消耗性能，但至少不能說： HashedWheelTimer 一定比 ScheduledExecutorService 優(yōu)秀。
3. HashedWheelTimer 由于開辟了一個 bucket 數(shù)組，占用的內(nèi)存也會稍大。

上述的對比，讓我們得到了一個最佳實踐：在任務量非常大時，使用 HashedWheelTimer 可以獲得性能的提升。例如服務治理框架中的心跳定時任務，當服務實例非常多時，每一個客戶端都需要定時發(fā)送心跳，每一個服務端都需要定時檢測連接狀態(tài)，這是一個非常適合使用 HashedWheelTimer 的場景。

5.2 單線程與業(yè)務線程池

我們需要注意 HashedWheelTimer 使用的是單線程調(diào)度任務，如果任務比較耗時，應當設置一個業(yè)務線程池，將 HashedWheelTimer 當做一個定時觸發(fā)器，任務的實際執(zhí)行，交給業(yè)務線程池。

確保 taskNStartTime - taskN-1StartTime > taskN-1CostTime，則無需擔心這個問題。

5.3 全局定時器

實際使用 HashedWheelTimer 時，應當將其當做一個全局的任務調(diào)度器，例如設計成 static 。時刻謹記一點：HashedWheelTimer 對應一個線程，如果每次實例化 HashedWheelTimer，首先是線程會很多，其次是時間輪算法將會完全失去意義。

5.4 為 HashedWheelTimer 設置合理的參數(shù)

ticksPerWheel，tickDuration 這兩個參數(shù)尤為重要，ticksPerWheel 控制了時間輪中 bucket 的數(shù)量，決定了沖突發(fā)生的概率，tickDuration 決定了指針撥動的頻率，一方面會影響定時的精度，一方面決定 CPU 的消耗量。當任務數(shù)量非常大時，考慮增大 ticksPerWheel；當時間精度要求不高時，可以適當加大 tickDuration，不過大多數(shù)情況下，不需要 care 這個參數(shù)。

5.5 什么時候使用層級時間輪

當時間跨度很大時，提升單層時間輪的 tickDuration 可以減少空轉(zhuǎn)次數(shù)，但會導致時間精度變低，層級時間輪既可以避免精度降低，又避免了指針空轉(zhuǎn)的次數(shù)。如果有長時間跨度的定時任務，則可以交給層級時間輪去調(diào)度。此外，也可以按照定時精度實例化多個不同作用的單層時間輪，dayHashedWheelTimer、hourHashedWheelTimer、minHashedWheelTimer，配置不同的 tickDuration，此法雖 low，但不失為一個解決方案。