定時器的實現(xiàn)方式有幾種？

1 前言

在開始正題之前，先閑聊幾句。有人說，計算機(jī)科學(xué)這個學(xué)科，軟件方向研究到頭就是數(shù)學(xué)，硬件方向研究到頭就是物理，最輕松的是中間這批使用者，可以不太懂物理，不太懂?dāng)?shù)學(xué)，依舊可以使用計算機(jī)作為自己謀生的工具。這個規(guī)律具有普適應(yīng)，再看看“定時器”這個例子，往應(yīng)用層研究，有 Quartz，Spring Schedule 等框架；往分布式研究，又有 SchedulerX，ElasticJob 等分布式任務(wù)調(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ù)在分布式領(lǐng)域很好地延伸，很多成熟的傳統(tǒng)技術(shù)可能在單機(jī) work well，但分布式場景需要很多額外的考慮。
3. 站在設(shè)計者的角度，如果從零開始設(shè)計一個輪子，怎么利用合適的算法、數(shù)據(jù)結(jié)構(gòu)，去實現(xiàn)它。

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

2 理解定時器

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

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

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

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

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

NewTask：將新任務(wù)加入任務(wù)集合

Cancel：取消某個任務(wù)

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

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

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

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

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

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

3.1 雙向有序鏈表

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

NewTask：O(N)

Cancel：O(1)

Run：O(1)

N：任務(wù)數(shù)

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

3.2 堆

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

NewTask：O(logN)

Cancel：O(logN)

Run：O(1)

N：任務(wù)數(shù)

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

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

3.3 時間輪

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

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

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

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

NewTask：O(1)

Cancel：O(1)

Run：O(M)

Tick：O(1)

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

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

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

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

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

3.4 層級時間輪

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

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

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

NewTask：O(H)

Cancel：O(H)

Run：O(M)

Tick：O(1)

H：層級數(shù)量

設(shè)想一下一個定時了 3 天，10 小時，50 分，30 秒的定時任務(wù)，在 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)在看來，它并不是一個好的設(shè)計。

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

2. Timer timer = newTimer();

3. timer.schedule(newTimerTask() {

4. @Override

5. publicvoid run() {

6. // do sth

7. }

8. }, 1000);

使用 Timer 實現(xiàn)任務(wù)調(diào)度的核心是 Timer 和 TimerTask。其中 Timer 負(fù)責(zé)設(shè)定 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 使用了唯一的線程負(fù)責(zé)了輪詢和任務(wù)的執(zhí)行。Timer 的優(yōu)點在于簡單易用，但也因為所有任務(wù)都是由同一個線程來調(diào)度，因此整個過程是串行執(zhí)行的，同一時間只能有一個任務(wù)在執(zhí)行，前一個任務(wù)的延遲或異常都將會影響到之后的任務(wù)。

輪詢時如果發(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í)行的定時任務(wù)

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)度多個任務(wù)的阻塞問題，并且任務(wù)的異常不會中斷 ScheduledExecutorService。

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

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

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

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

ScheduledExecutorService 底層使用的數(shù)據(jù)結(jié)構(gòu)為 PriorityQueue，任務(wù)調(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)，默認(rèn)構(gòu)造器會配置輪詢周期為 100ms，bucket 數(shù)量為 512。其使用方法和 JDK 的使用方式也十分相同。

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

2. privatefinalThread workerThread;// Thread

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

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

5 最佳實踐

5.1 選擇合適的定時器

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

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

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

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

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

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

5.3 全局定時器

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

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

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

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

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