1 前言

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

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

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

2 理解定時(shí)器

很多場(chǎng)景會(huì)用到定時(shí)器，例如

1. 使用 TCP 長(zhǎng)連接時(shí)，客戶(hù)端需要定時(shí)向服務(wù)端發(fā)送心跳請(qǐng)求。
2. 財(cái)務(wù)系統(tǒng)每個(gè)月的月末定時(shí)生成對(duì)賬單。
3. 雙 11 的 0 點(diǎn)，定時(shí)開(kāi)啟秒殺開(kāi)關(guān)。

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

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

在用戶(hù)視角支持以下幾種操作：

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

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

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

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

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

說(shuō)到底，定時(shí)器還是靠線(xiàn)程輪詢(xún)實(shí)現(xiàn)的。

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

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

3.1 雙向有序鏈表

在 Java 中， LinkedList 是一個(gè)天然的雙向鏈表

NewTask：O(N)

Cancel：O(1)

Run：O(1)

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

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

3.2 堆

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

NewTask：O(logN)

Cancel：O(logN)

Run：O(1)

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

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

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

3.3 時(shí)間輪

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

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

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

再看圖中的 bucket5，我們可以知道在 $18+5=13s** 后，有兩個(gè)任務(wù)需要執(zhí)行，在 $28+5=21s** 后有一個(gè)任務(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

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

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

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

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

3.4 層級(jí)時(shí)間輪

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

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

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

NewTask：O(H)

Cancel：O(H)

Run：O(M)

Tick：O(1)

H：層級(jí)數(shù)量

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

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

4 常見(jiàn)實(shí)現(xiàn)

4.1 Timer

JDK 中的 Timer 是非常早期的實(shí)現(xiàn)，在現(xiàn)在看來(lái)，它并不是一個(gè)好的設(shè)計(jì)。

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

2. Timer timer = newTimer();

3. timer.schedule(newTimerTask() {

4. @Override

5. publicvoid run() {

6. // do sth

7. }

8. }, 1000);

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

1. publicclassTimer {

2. privatefinalTaskQueue queue = newTaskQueue();

3. privatefinalTimerThread thread = newTimerThread(queue);

4. }

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

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

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

出于這兩個(gè)缺陷，JDK 1.5 支持了新的定時(shí)器方案 ScheduledExecutorService。

4.2 ScheduledExecutorService

1. // 運(yùn)行一個(gè)一秒后執(zhí)行的定時(shí)任務(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 解決了同一個(gè)定時(shí)器調(diào)度多個(gè)任務(wù)的阻塞問(wèn)題，并且任務(wù)的異常不會(huì)中斷 ScheduledExecutorService。

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

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

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

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

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

4.3 HashedWheelTimer

1. Timer timer = newHashedWheelTimer();

2. //等價(jià)于 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)介紹過(guò)了 Netty 中 HashedWheelTimer 內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)構(gòu)造器會(huì)配置輪詢(xún)周期為 100ms，bucket 數(shù)量為 512。其使用方法和 JDK 的使用方式也十分相同。

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

2. privatefinalThread workerThread;// Thread

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

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

5 最佳實(shí)踐

5.1 選擇合適的定時(shí)器

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

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

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

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

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

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

5.3 全局定時(shí)器

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

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

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

5.5 什么時(shí)候使用層級(jí)時(shí)間輪

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