本文從追溯時(shí)間輪算法的出現(xiàn)，介紹了時(shí)間輪算法未出現(xiàn)前，基于隊(duì)列的定時(shí)任務(wù)實(shí)現(xiàn)，以及基于隊(duì)列的定時(shí)任務(wù)實(shí)現(xiàn)所存在的缺陷。接著我們介紹了時(shí)間輪算法的算法思想及其數(shù)據(jù)結(jié)構(gòu)，詳細(xì)闡述了三種時(shí)間輪模型的數(shù)據(jù)結(jié)構(gòu)和優(yōu)劣性。

再次，我們介紹時(shí)間輪算法在 Dubbo 框架中的應(yīng)用，并給出了它在 Dubbo 中的主要實(shí)現(xiàn)方式。

最后，我們以項(xiàng)目中的某個(gè)服務(wù)架構(gòu)優(yōu)化出發(fā)，介紹了目前設(shè)計(jì)中存在的缺陷，并借助來(lái)自中間件團(tuán)隊(duì)的，包含時(shí)間輪算法實(shí)現(xiàn)的延遲 MQ，給出了優(yōu)化設(shè)計(jì)的方法。

第一章    定時(shí)任務(wù)及時(shí)間輪算法發(fā)展

1.1 時(shí)間輪算法的出現(xiàn)

在計(jì)算程序中，定時(shí)器用于指定一個(gè)具體的時(shí)間點(diǎn)去執(zhí)行某一個(gè)既定的任務(wù)。而時(shí)間輪算法就是這樣一種能夠?qū)崿F(xiàn)延遲功能（定時(shí)器）的巧妙算法。時(shí)間輪算法首次出現(xiàn)在1997年 George Varghese 和 Anthony Lauck 發(fā)表于IEEE期刊，名為“Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility”的論文上。此文章指出，實(shí)現(xiàn)操作系統(tǒng)定時(shí)器模塊的常規(guī)算法需要 O（n）的時(shí)間復(fù)雜度啟動(dòng)和維護(hù)計(jì)時(shí)器，對(duì)于更大問(wèn)題規(guī)模（n），這樣的時(shí)間開銷是巨大的，文中提出并證明了，通過(guò)一種環(huán)狀桶的數(shù)據(jù)結(jié)構(gòu)，可以做到使用 O（1）的時(shí)間復(fù)雜度，就可以啟動(dòng)，停止和維護(hù)計(jì)時(shí)器，并介紹了對(duì)時(shí)間間隔劃分的處理，第一種方式是將所有的計(jì)時(shí)器時(shí)間間隔進(jìn)行散列（Hash），這些時(shí)間間隔被散列到時(shí)間輪上特定的槽位中（Slot），第二種方式是利用多粒度定時(shí)輪組成具有層級(jí)結(jié)構(gòu)的組合，以擴(kuò)展更大的時(shí)間范圍。這兩種結(jié)構(gòu)將在第二章中詳細(xì)介紹。

1.2 基于隊(duì)列的定時(shí)任務(wù)執(zhí)行模型

在計(jì)算機(jī)的世界中，只有待解決的問(wèn)題大規(guī)模化以后，算法的價(jià)值才能夠得到最大化的體現(xiàn)。在介紹時(shí)間輪算法之前，我們有必要介紹另一種定時(shí)任務(wù)的實(shí)現(xiàn)，即基于隊(duì)列的定時(shí)任務(wù)。隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)無(wú)論是在操作系統(tǒng)中還是各編程語(yǔ)言如 Java 中都被大量使用，本文不再展開贅述。

下面從線程模型、定時(shí)任務(wù)種類和任務(wù)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)三個(gè)方面展開詳細(xì)介紹：

（1）線程模型

用戶線程：負(fù)責(zé)定時(shí)任務(wù)的注冊(cè)；

輪詢線程：負(fù)責(zé)從任務(wù)隊(duì)列中掃描出符合執(zhí)行條件的任務(wù)，例如任務(wù)的待執(zhí)行時(shí)間已經(jīng)到達(dá)，輪詢線程將從隊(duì)列中取出該任務(wù)，并交由異步線程池處理該任務(wù)。

異步線程池：專門負(fù)責(zé)任務(wù)的執(zhí)行。

（2）定時(shí)任務(wù)

定時(shí)任務(wù)主要分為一次性執(zhí)行的定時(shí)任務(wù)（Dubbo 中超時(shí)判斷）以及重復(fù)執(zhí)行的定時(shí)任務(wù)，這兩種定時(shí)任務(wù)都很好理解，一次性執(zhí)行的定時(shí)任務(wù)在規(guī)定的未來(lái)某一時(shí)刻或距離現(xiàn)在的一段固定時(shí)長(zhǎng)后執(zhí)行，分別對(duì)應(yīng)絕對(duì)值和相對(duì)值的概念。

而重復(fù)執(zhí)行的定時(shí)任務(wù)是在一次性執(zhí)行任務(wù)的基礎(chǔ)上多次重復(fù)執(zhí)行，這意味著，在上述線程協(xié)調(diào)工作中，當(dāng)重復(fù)執(zhí)行任務(wù)執(zhí)行完成一次后，將被重新放回任務(wù)隊(duì)列中。  

（3）任務(wù)隊(duì)列數(shù)據(jù)結(jié)構(gòu)

 從最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)出發(fā)，假設(shè)我們選用最基本的隊(duì)列，或者考慮到增減任務(wù)的方便，選擇雙向鏈表做為任務(wù)隊(duì)列，為任務(wù)隊(duì)列中的每個(gè)任務(wù)提供一個(gè)時(shí)間戳字段，這種實(shí)現(xiàn)的策略會(huì)產(chǎn)生哪些問(wèn)題？

最大的問(wèn)題是在查詢上，假設(shè)任務(wù)隊(duì)列中存在一些任務(wù)，那么為了找出達(dá)到規(guī)定時(shí)刻的待執(zhí)行任務(wù)，輪詢線程需要掃描全部任務(wù)，此種數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度為 O（n），而且存在大量的空輪詢，即大部分的任務(wù)都沒(méi)有達(dá)到執(zhí)行時(shí)間，這種效率幾乎是不可接受的。

為了提升查詢效率，可以嘗試從數(shù)據(jù)結(jié)構(gòu)出發(fā)，利用有序隊(duì)列，在計(jì)算機(jī)的算法中，有序性可以顯著提高遍歷的效率，這樣一來(lái)，定時(shí)任務(wù)隊(duì)列輪詢線程從頭向尾遍歷時(shí)，在發(fā)現(xiàn)任意任務(wù)未達(dá)到規(guī)定執(zhí)行時(shí)間戳后，就可以停止遍歷。

但是維護(hù)有序性也需要付出代價(jià)，普通任務(wù)隊(duì)列入隊(duì)一個(gè)任務(wù)的時(shí)間復(fù)雜度僅僅是 O（1），而有序任務(wù)隊(duì)列入隊(duì)一個(gè)任務(wù)的時(shí)間復(fù)雜度為 O（nlogn）。其次，我們可以借鑒分治的思想，將任務(wù)隊(duì)列分成n份，利用多線程遍歷，在線程完全并發(fā)執(zhí)行的情況下，問(wèn)題規(guī)模簡(jiǎn)化到原來(lái)的1/n。但是多線程也會(huì) CPU 執(zhí)行效率降低。

綜上分析，定時(shí)任務(wù)框架需要具有如下要素：

1. 嚴(yán)格高效的數(shù)據(jù)結(jié)構(gòu)，并不能基于簡(jiǎn)單的隊(duì)列結(jié)構(gòu)來(lái)存儲(chǔ)任務(wù)，否則輪詢的執(zhí)行效率永遠(yuǎn)無(wú)法提高。
2. 簡(jiǎn)單的并發(fā)模型：CPU 的線程非常寶貴，不應(yīng)占用過(guò)多線程資源。

時(shí)間輪算法解決了上述基于隊(duì)列的定時(shí)任務(wù)執(zhí)行模型的缺陷，因此時(shí)間輪算法思想在后面互聯(lián)網(wǎng)技術(shù)發(fā)展中得到了大量應(yīng)用，我們熟悉的 Linux Crontab，以及 Java 開發(fā)中常用的 Dubbo、Netty、Quartz、Akka、ZooKeeper、Kafka 等，幾乎所有的時(shí)間任務(wù)調(diào)度都采用了時(shí)間輪算法的思想。

值得一提的是，在 Dubbo 中，為了增強(qiáng)系統(tǒng)容錯(cuò)，很多地方需要用到只需一次執(zhí)行的任務(wù)調(diào)度，比如消費(fèi)者需要知道各個(gè) RPC 調(diào)用是否超時(shí)，而在 Dubbo 最開始的實(shí)現(xiàn)中，是采用將所有的返回結(jié)果（defaultFuture），都放入一個(gè)集合中，并通過(guò)一個(gè)定時(shí)任務(wù)，間隔掃描所有的 future，逐個(gè)判斷是否超時(shí)。這樣邏輯簡(jiǎn)單，但是浪費(fèi)性能，后面 Dubbo 借鑒了 Netty，引入了時(shí)間輪。

第二章    時(shí)間輪算法思想介紹及應(yīng)用場(chǎng)景介紹

2.1 時(shí)間輪簡(jiǎn)介

時(shí)間輪實(shí)質(zhì)上是一種高效利用線程資源的任務(wù)調(diào)度模型，將大批量的任務(wù)全部整合進(jìn)一個(gè)調(diào)度器中，從而對(duì)任務(wù)進(jìn)行統(tǒng)一的調(diào)度管理，針對(duì)定時(shí)任務(wù)，延時(shí)任務(wù)等事件的調(diào)度效率非常高。

時(shí)間輪算法的核心是：第一章中描述的對(duì)任務(wù)隊(duì)列進(jìn)行輪詢的線程不再負(fù)責(zé)遍歷所有的任務(wù)，而是僅僅遍歷時(shí)間刻度。時(shí)間輪算法好比指針不斷在時(shí)鐘上旋轉(zhuǎn)、遍歷，如果發(fā)現(xiàn)某一時(shí)刻上有任務(wù)（任務(wù)隊(duì)列），那么就會(huì)將任務(wù)隊(duì)列上的所有任務(wù)都執(zhí)行一遍，這樣便大幅度的減少了額外的掃描操作。

第一章中，我們提出了一個(gè)高效的定時(shí)任務(wù)框架需要具備嚴(yán)格高效的數(shù)據(jù)結(jié)構(gòu)和簡(jiǎn)單的并發(fā)模型兩個(gè)特點(diǎn)，而時(shí)間輪模型正是具備了這樣的特點(diǎn)。

基于時(shí)間輪算法思想，后續(xù)也出現(xiàn)了很多種時(shí)間輪模型，目前流行的大致有三種，分別為簡(jiǎn)單時(shí)間輪模型、帶有 round 的時(shí)間輪模型以及分層時(shí)間輪模型，下面將依次介紹這三種時(shí)間輪模型。

2.2 時(shí)間輪模型

2.2.1 簡(jiǎn)單時(shí)間輪模型

簡(jiǎn)單時(shí)間輪模型不再使用隊(duì)列作為數(shù)據(jù)結(jié)構(gòu)，而是使用數(shù)組加鏈表的形式（很經(jīng)典的組合）， 如下圖所示，該時(shí)間輪通過(guò)數(shù)組實(shí)現(xiàn)，可以很方便地通過(guò)下標(biāo)定位到定時(shí)任務(wù)鏈路，因此，添加、刪除、執(zhí)行定時(shí)任務(wù)的時(shí)間復(fù)雜度為 O（1）。

 圖2.2.1 簡(jiǎn)單時(shí)間輪模型

顯然，這種簡(jiǎn)單時(shí)間輪就解決了任務(wù)隊(duì)列中遍歷效率低下的問(wèn)題，輪詢線程遍歷到某一個(gè)時(shí)間刻度后，總是執(zhí)行對(duì)應(yīng)刻度上任務(wù)隊(duì)列中的所有任務(wù)（通常是將任務(wù)扔給異步線程池來(lái)處理），而不再需要遍歷檢查所有任務(wù)的時(shí)間戳是否達(dá)到要求。

通過(guò)增加槽（slot）的數(shù)量，可以細(xì)化的時(shí)間粒度以及得到更大的時(shí)間跨度，但是這樣的實(shí)現(xiàn)方式有巨大的缺陷：

1. 當(dāng)時(shí)間粒度小，時(shí)間跨度大，而任務(wù)又很少的時(shí)候，時(shí)間槽的輪詢效率變低。
2. 當(dāng)時(shí)間粒度小，時(shí)間槽數(shù)量多，而任務(wù)又很少時(shí)，很多槽位占用的內(nèi)存空間是沒(méi)有意義的。

2.2.2 帶有 round 的時(shí)間輪模型

類比循環(huán)數(shù)組的思想，后人設(shè)計(jì)了帶 round 的時(shí)間輪，這種時(shí)間輪的結(jié)構(gòu)如下圖所示：

 圖2.2.2 帶有round的時(shí)間輪模型

如圖2.2.2所示，expire 代表到期時(shí)間，round 表示時(shí)間輪要在轉(zhuǎn)動(dòng)幾圈之后才執(zhí)行任務(wù)，也就是說(shuō)當(dāng)指針轉(zhuǎn)到某個(gè) bucket 時(shí)，不能像簡(jiǎn)單的單時(shí)間輪那樣直接執(zhí)行 bucket 下所有的任務(wù)。而且要去遍歷該 bucket 下的鏈表，判斷時(shí)間輪轉(zhuǎn)動(dòng)的次數(shù)是否等于節(jié)點(diǎn)中的 round 值，只有當(dāng) expire 和 round 都相同的情況下，才能執(zhí)行任務(wù)。

這種結(jié)構(gòu)的時(shí)間輪明顯減少了所需刻度的個(gè)數(shù)，即彌補(bǔ)了簡(jiǎn)單時(shí)間輪在時(shí)間槽位較多，而任務(wù)較少情況下內(nèi)存空間浪費(fèi)的問(wèn)題。

但是這種結(jié)構(gòu)的時(shí)間輪并不能減少輪詢線程的輪詢次數(shù)，效率相對(duì)較低。

2.2.3 分層時(shí)間輪模型

分層時(shí)間輪也是一種對(duì)簡(jiǎn)單時(shí)間輪的改良方案，它的設(shè)計(jì)理念可以類比于日常生活中的時(shí)鐘，分別有時(shí)、分、秒三個(gè)層級(jí)，并且每個(gè)輪盤分別具有24、60、60個(gè)刻度，因此，只需要144個(gè)刻度，即可表示一天的時(shí)間，而這種表示方式的優(yōu)勢(shì)在于，倍數(shù)級(jí)別時(shí)間表示的新增，只需要常數(shù)級(jí)別的刻度增加。例如，在144個(gè)刻度可表示的一天時(shí)間的基礎(chǔ)上，新增30個(gè)刻度，即可精細(xì)表示一個(gè)月的時(shí)間。

 圖2.2.3 分層時(shí)間輪模型

分層時(shí)間輪的工作方式為低層級(jí)的時(shí)間輪帶動(dòng)高層級(jí)的時(shí)間輪轉(zhuǎn)動(dòng)，圖中箭頭為任務(wù)的“下放”，例如，2號(hào)8點(diǎn)40分0秒執(zhí)行的任務(wù)，當(dāng)天輪轉(zhuǎn)動(dòng)到刻度2時(shí)，會(huì)將第2天的任務(wù)，下放到對(duì)應(yīng)時(shí)輪刻度為8的槽位中，當(dāng)時(shí)輪轉(zhuǎn)動(dòng)到8時(shí)，會(huì)將任務(wù)繼續(xù)下放到分輪刻度為40的槽位中，直至到最低層次的時(shí)間輪，轉(zhuǎn)動(dòng)到該槽位時(shí)，將該槽位中的任務(wù)，全部執(zhí)行。

針對(duì)時(shí)間復(fù)雜度，這種時(shí)間輪對(duì)比帶有 round 的時(shí)間輪不再遍歷計(jì)算對(duì)比任務(wù)的 round，而是直接全部取出執(zhí)行。

針對(duì)空間復(fù)雜度，分層時(shí)間輪利用維度上升的思路對(duì)時(shí)間輪進(jìn)行分層，每個(gè)層級(jí)的時(shí)間粒度對(duì)應(yīng)一個(gè)時(shí)間輪，多個(gè)時(shí)間輪之間進(jìn)行級(jí)聯(lián)協(xié)作。

2.3 時(shí)間輪應(yīng)用場(chǎng)景介紹

時(shí)間輪作為高效的調(diào)度模型，在各種場(chǎng)景均有廣泛的應(yīng)用，常見(jiàn)的場(chǎng)景主要有如下幾個(gè)：

（1）定時(shí)器

時(shí)間輪常用于實(shí)現(xiàn)定時(shí)器，可以在指定時(shí)間執(zhí)行特定任務(wù)。定時(shí)器可以用于周期性任務(wù)、超時(shí)任務(wù)等，如輪詢 I/O 事件、定期刷新緩存、定時(shí)清理垃圾數(shù)據(jù)等。

（2）負(fù)載均衡

時(shí)間輪可以用于實(shí)現(xiàn)負(fù)載均衡算法，將請(qǐng)求分配到不同的服務(wù)器上，避免單個(gè)服務(wù)器負(fù)載過(guò)重。時(shí)間輪可以根據(jù)服務(wù)器的負(fù)載情況來(lái)動(dòng)態(tài)調(diào)整分配策略，實(shí)現(xiàn)動(dòng)態(tài)負(fù)載均衡。

（3）事件驅(qū)動(dòng)

時(shí)間輪可以用于實(shí)現(xiàn)事件驅(qū)動(dòng)模型，將事件分配到不同的處理器上，提高并發(fā)處理能力。事件可以是 I/O 事件、定時(shí)事件、用戶事件等，時(shí)間輪可以根據(jù)事件的類型和優(yōu)先級(jí)來(lái)動(dòng)態(tài)調(diào)整分配策略，實(shí)現(xiàn)高效的事件驅(qū)動(dòng)模型。

（4）數(shù)據(jù)庫(kù)管理

時(shí)間輪可以用于實(shí)現(xiàn)數(shù)據(jù)庫(kù)管理，將數(shù)據(jù)分配到不同的存儲(chǔ)設(shè)備上，提高數(shù)據(jù)讀寫效率。時(shí)間輪可以根據(jù)數(shù)據(jù)的類型、大小和訪問(wèn)頻率等來(lái)動(dòng)態(tài)調(diào)整數(shù)據(jù)分配策略，實(shí)現(xiàn)高效的數(shù)據(jù)庫(kù)管理。

（5）其他應(yīng)用

時(shí)間輪還可以用于其他一些應(yīng)用，如消息隊(duì)列、任務(wù)調(diào)度、網(wǎng)絡(luò)流量控制等，具體應(yīng)用取決于具體的需求和場(chǎng)景。

第三章     時(shí)間輪在 Dubbo 的應(yīng)用與實(shí)現(xiàn)

3.1 Dubbo 中時(shí)間輪的應(yīng)用

Dubbo 的設(shè)計(jì)中，客戶端在調(diào)用服務(wù)端的時(shí)候，會(huì)對(duì)任務(wù)進(jìn)行計(jì)時(shí)，如果任務(wù)超時(shí)，那么會(huì)被檢測(cè)到，并重試請(qǐng)求。在 Dubbo 最開始的實(shí)現(xiàn)中，是采用將所有的返回結(jié)果（defaultFuture），都放入一個(gè)集合中，并通過(guò)一個(gè)定時(shí)任務(wù)，間隔掃描所有的 future，逐個(gè)判斷是否超時(shí)。

這樣邏輯簡(jiǎn)單，但是浪費(fèi)性能，后面 Dubbo 借鑒了 Netty，引入了時(shí)間輪。任務(wù)交由時(shí)間輪管理，由專門的線程進(jìn)行調(diào)度。

3.2 Dubbo 中時(shí)間輪的實(shí)現(xiàn)

Dubbo 中時(shí)間輪算法的實(shí)現(xiàn)，主要有一個(gè)類和三個(gè)接口：

首先是 Timer 接口，這個(gè)一個(gè)調(diào)度的核心接口，主要用于后臺(tái)的一次性調(diào)度，我們僅介紹 newTimeOut 方法，這個(gè)方法就是把一個(gè)任務(wù)扔給調(diào)度器執(zhí)行，第一個(gè)參數(shù)類型 TimerTask，即需要執(zhí)行的任務(wù)。

接下來(lái)是 TimeTask 接口，它只有一個(gè)方法 run，參數(shù)類型是 Timeout，我們注意到上面 Timer 接口的 newTimeout  這個(gè)方法返回的參數(shù)就是 Timeout，和此處的入?yún)⑾嗤?，?shí)際這里傳入的 Timeout 參數(shù)就是 newTimeout 的返回值。

Timeout 對(duì)象與 TimerTask 對(duì)象一一對(duì)應(yīng)，兩者的關(guān)系類似于線程池返的 Future 對(duì)象與提交到線程池中的任務(wù)對(duì)象之間的關(guān)系。

最后是 TimeOut 接口，它代表的是對(duì)一次任務(wù)的處理，其中有幾個(gè)方法，從介紹上即可看出各方法用途，這里不再贅述。

上述幾個(gè)接口從邏輯上構(gòu)成了一個(gè)任務(wù)調(diào)度系統(tǒng)。下面是任務(wù)調(diào)度系統(tǒng)的核心，即時(shí)間輪調(diào)度器的實(shí)現(xiàn)-- HashedWheelTimer。

仔細(xì)看它的類上注釋可以發(fā)現(xiàn)，該方法并不能提供精確的計(jì)時(shí)，而是檢測(cè)每個(gè) tick 中（也就是時(shí)間輪中的一個(gè)時(shí)間槽），是否有 TimerTask，其期望執(zhí)行時(shí)間已經(jīng)落后于當(dāng)前時(shí)間，如果是則執(zhí)行該任務(wù)。任務(wù)執(zhí)行時(shí)間的精確度可以通過(guò)細(xì)化時(shí)間槽來(lái)提升。

默認(rèn)的 tick duration 是100毫秒，大部分網(wǎng)絡(luò)應(yīng)用中，I/O 超時(shí)并非必須是精準(zhǔn)的，例如5秒超時(shí)，實(shí)際上稍晚一會(huì)也是可以的，因此這個(gè)默認(rèn)值無(wú)需修改。

這個(gè)類維護(hù)了一種稱為“wheel”的數(shù)據(jù)結(jié)構(gòu)，也就是我們說(shuō)的時(shí)間輪。簡(jiǎn)單地說(shuō)，一個(gè) wheel 就是一個(gè) hash table，它的 hash 函數(shù)是任務(wù)的截止時(shí)間，也就是我們要通過(guò) hash 函數(shù)把這個(gè)任務(wù)放到它應(yīng)該在的時(shí)間槽中，這樣隨著時(shí)間的推移，當(dāng)我們進(jìn)入某個(gè)時(shí)間槽中時(shí)，這個(gè)槽中的任務(wù)也剛好到了它該執(zhí)行的時(shí)間。

這樣就避免了在每一個(gè)槽中都需要檢測(cè)所有任務(wù)是否需要執(zhí)行。在 HashedWheelTimer 的構(gòu)造函數(shù)中，最重要的是 createWheel 方法，忽略基本的參數(shù)校驗(yàn)，只看方法主流程，首先是對(duì)時(shí)間槽數(shù)量的規(guī)范化處理，處理方式為將構(gòu)造時(shí)傳入的數(shù)量，修改為大于等于它的最小的2的次冪。為什么這樣處理以及處理的具體方式，有興趣可以研究下源代碼。

接著則是創(chuàng)建時(shí)間槽數(shù)組，最后是初始化時(shí)間槽數(shù)組的每個(gè)參數(shù)。

下面介紹下 newTimeout 方法，這個(gè)方法的主要作用是向調(diào)度器中添加一個(gè)待執(zhí)行的任務(wù)，同樣忽略基本的參數(shù)校驗(yàn)，主體流程為：

1. 第一步將等待調(diào)度的任務(wù)數(shù)+1，如果超過(guò)了最大限制，則-1并拋出異常。
2. 第二步則調(diào)用 start 方法，啟動(dòng)時(shí)間輪。
3. 第三步計(jì)算當(dāng)前任務(wù)的截止時(shí)間，并做防溢出處理。
4. 構(gòu)造一個(gè) TimeOut ，并放入等待隊(duì)列。

這里我們展開比較重要的 start 方法，首先獲取 worker 的運(yùn)行狀態(tài)，如果是初始化狀態(tài)，則更新成已啟動(dòng)狀態(tài)，啟動(dòng) workThread 線程，若是其他狀態(tài)，則做其他相應(yīng)的處理。接著是等待 workThread 將 startTime 初始化完成（在 Worker 的 run 方法中初始化完成），之所以需要等待 startTime 初始化完成，是因?yàn)?newTimeout 方法中，start 方法調(diào)用后也用到了這個(gè) startTime，不這樣做，任務(wù)的截止時(shí)間計(jì)算會(huì)有問(wèn)題。

至此，我們介紹了利用 HashedWheelTimer 添加一個(gè)任務(wù)的主體流程，接下來(lái)是時(shí)間輪的內(nèi)部運(yùn)轉(zhuǎn)。

首先是 HashedWheelTimer 的內(nèi)部類 Worker，其中 run 方法的主體流程如下：

1.初始化 startTime，這里與上文中 start 方法內(nèi)部對(duì)應(yīng)。初始化后，利用閉鎖 CountDownLatch 通知等待線程往下執(zhí)行。

2.當(dāng)定時(shí)器處于已啟動(dòng)狀態(tài)時(shí)，不停地推進(jìn) ticket，推進(jìn)的過(guò)程分解為：

• 等待下一個(gè) ticket 的到來(lái)。
• ticket 到來(lái)后，計(jì)算該 ticket 對(duì)應(yīng)時(shí)間輪的槽位（取模運(yùn)算）。
• 處理已取消的任務(wù)隊(duì)列。
• 獲取當(dāng)前時(shí)間槽，并將待處理任務(wù)隊(duì)列中的任務(wù)放到槽中。
• 執(zhí)行當(dāng)前時(shí)間槽中的任務(wù)。

3. 如果時(shí)間輪已經(jīng)停止了，則執(zhí)行以下流程：

• 清理所有時(shí)間槽中的未處理任務(wù)調(diào)度。
• 清理待處理任務(wù)調(diào)度隊(duì)列，將未取消的加入到未處理集合中。
• 處理已取消的任務(wù)隊(duì)列。

我們重點(diǎn)關(guān)注下定時(shí)器啟動(dòng)狀態(tài)下的第3步，獲取當(dāng)前時(shí)間槽，并將待處理任務(wù)隊(duì)列中的任務(wù)放到槽中的方法 transferTimeoutsToBuckets，其流程為以下幾個(gè)步驟（這里規(guī)定循環(huán)了有限次，防止待處理隊(duì)列過(guò)大，導(dǎo)致本次添加到槽耗費(fèi)時(shí)間過(guò)長(zhǎng)）：

• 從待處理任務(wù)調(diào)度隊(duì)列中取出第一個(gè)任務(wù)，進(jìn)行校驗(yàn)。
• 根據(jù)取出的待處理任務(wù)調(diào)度，計(jì)算出一個(gè)槽。
• 設(shè)置此任務(wù)調(diào)度的剩余圈數(shù)（從這里看出 Dubbo 用的是我們?cè)?.2.2中介紹的“帶有 round 的時(shí)間輪”）。
• 取計(jì)算出的槽和當(dāng)前槽中的較大者，并進(jìn)行取模。
• 將此任務(wù)調(diào)度加入對(duì)應(yīng)的槽中。

總結(jié)：這部分內(nèi)容我們分別從向調(diào)度器中添加任務(wù)的主體流程和時(shí)間輪內(nèi)部運(yùn)轉(zhuǎn)兩個(gè)部分，簡(jiǎn)單介紹了 Dubbo 中時(shí)間輪的實(shí)現(xiàn)。

如果感興趣，可以學(xué)習(xí)其源代碼，里面很多代碼設(shè)計(jì)非常巧妙，比如 startTime 初始化及初始化完成后的線程間通信實(shí)現(xiàn)，這些設(shè)計(jì)思路對(duì)筆者這樣的初學(xué)者來(lái)說(shuō)很有益處。

第四章    時(shí)間輪算法的應(yīng)用展望

筆者在剛開始工作時(shí)，設(shè)計(jì)過(guò)一個(gè)叫做下載中心的服務(wù)，這個(gè)服務(wù)的功能為導(dǎo)出和下載項(xiàng)目中的數(shù)據(jù)文件，實(shí)際的定位是為了減少異步線程過(guò)多而影響各個(gè)核心業(yè)務(wù)，因此將其功能抽取出來(lái)，從而達(dá)到減少核心業(yè)務(wù)壓力的目標(biāo)。

下載中心的初步設(shè)計(jì)，考慮到并發(fā)請(qǐng)求以及文件過(guò)大帶來(lái)的內(nèi)存溢出問(wèn)題，除了采取各種方式避免外，整體思路是，預(yù)計(jì)特別大的文件，先將任務(wù)記錄進(jìn)行持久化，并通過(guò)后臺(tái)線程池慢慢執(zhí)行這些任務(wù)，通過(guò)任務(wù)記錄，主動(dòng)拉取數(shù)據(jù)、生成文件等。

模型類似于 Netty 中的 BOSS-WORKER 的模式，BOSS 線程負(fù)責(zé)定時(shí)從數(shù)據(jù)庫(kù)中查出未消費(fèi)的任務(wù)，并將其分配給 worker 線程池進(jìn)行消費(fèi)，如圖4.1所示。

 圖4.1 改造前應(yīng)用服務(wù)任務(wù)消費(fèi)模式示意圖

當(dāng)前設(shè)計(jì)雖然可以做到防止內(nèi)存溢出等問(wèn)題，但是這樣的設(shè)計(jì)也存在一定的缺陷：

1. 如果后續(xù)用戶量增多，可以考慮水平擴(kuò)充服務(wù)的數(shù)量，但是用于持久化任務(wù)記錄的數(shù)據(jù)庫(kù)會(huì)成為瓶頸。
2. 即使 BOSS 線程不難做到避免任務(wù)的重復(fù)消費(fèi)，但是待執(zhí)行任務(wù)的查詢效率會(huì)大大降低。
3. 整個(gè)服務(wù)太過(guò)于依賴 BOSS 線程。

因此，考慮一種方式替代這種 BOSS-WORKER 模式，目前想到的一種方式為 MQ 消息隊(duì)列，將待執(zhí)行的任務(wù)信息投至 MQ 隊(duì)列當(dāng)中，然后該服務(wù)對(duì)其進(jìn)行消費(fèi)。這樣的做法，即可解決上述3個(gè)問(wèn)題，并具備維持任務(wù)有序性的優(yōu)勢(shì)。

但是內(nèi)存易溢出的問(wèn)題仍然存在，因此，考慮限制消費(fèi)任務(wù)的線程并發(fā)數(shù)量。如果超過(guò)這個(gè)數(shù)量，則不再消費(fèi)任務(wù)，而是重新投遞任務(wù)至 MQ 隊(duì)列中。這里，我們有更好的做法，即需要將任務(wù)重新投遞至 MQ 隊(duì)列時(shí)，做一些延時(shí)的處理，防止反復(fù)重新投遞任務(wù)。整體流程如圖4.2所示：

圖4.2 改造后應(yīng)用服務(wù)任務(wù)消費(fèi)模式示意圖

圖中，綠色模塊為整個(gè)系統(tǒng)設(shè)計(jì)中的用以調(diào)度定時(shí)任務(wù)的任務(wù)調(diào)度模塊，利用時(shí)間輪來(lái)統(tǒng)一管理這些定時(shí)任務(wù)。

對(duì)于短暫延時(shí)和長(zhǎng)延遲的消息，我們都期望延時(shí)盡可能的精確，而對(duì)于長(zhǎng)延時(shí)的消息，我們還要對(duì)其進(jìn)行持久化，也就是暫存。等到消息快要到期時(shí)，再重新取出，進(jìn)行投遞。

而這種長(zhǎng)延時(shí)消息的持久化，與我們圖4.1所示定時(shí)從數(shù)據(jù)庫(kù)取任務(wù)所遇到的瓶頸是一致的。

我們更期望有成熟的框架，能夠提供 1.長(zhǎng)延遲任務(wù)的持久化 以及 2. 任務(wù)調(diào)度 的能力。從中間件平臺(tái)組提供的 MQ 中，我們發(fā)現(xiàn)目前它是已經(jīng)支持 包含這兩個(gè)能力的延遲 MQ 功能的。延遲 MQ 架構(gòu)大致如下圖所示：

           圖4.3 延遲MQ消息處理流程圖

具體延遲消息的發(fā)送和處理的流程如下圖所示：

圖4.4 延遲消息發(fā)送和處理流程示意圖

實(shí)際上，該延遲 MQ 的實(shí)現(xiàn)，正是由時(shí)間輪實(shí)現(xiàn)的調(diào)度 以及利用 MongoDB 數(shù)據(jù)庫(kù) 實(shí)現(xiàn)的持久化，這與我們所期望的能力完全一致，完全可以滿足我們的需求。

總結(jié)

本文從定時(shí)任務(wù)和時(shí)間輪算法的起源開始，對(duì)時(shí)間輪算法進(jìn)行了介紹。詳細(xì)的闡述了時(shí)間輪的算法思想，以及簡(jiǎn)單時(shí)間輪、帶 round 的時(shí)間輪以及分層時(shí)間輪這三種常見(jiàn)的時(shí)間輪模型，并給出了對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

接著以 Dubbo 為例，介紹了時(shí)間輪模型在 Dubbo 中的應(yīng)用，從源碼出發(fā)，介紹了該算法在 Dubbo 中的主要實(shí)現(xiàn)。

最后，我們介紹了筆者自身所做過(guò)的一個(gè)小模塊，展開分析了該模塊功能目前所遇到的瓶頸，并給出了通過(guò)融合了時(shí)間輪算法的延遲 MQ 來(lái)優(yōu)化當(dāng)前設(shè)計(jì)的思路。

參考文獻(xiàn)：

Hashed and Hierarchical Timing Wheels: EfficientData Structures for Implementing a Timer Facility.