本文從追溯時間輪算法的出現，介紹了時間輪算法未出現前，基于隊列的定時任務實現，以及基于隊列的定時任務實現所存在的缺陷。接著我們介紹了時間輪算法的算法思想及其數據結構，詳細闡述了三種時間輪模型的數據結構和優劣性。

再次，我們介紹時間輪算法在 Dubbo 框架中的應用，并給出了它在 Dubbo 中的主要實現方式。

最后，我們以項目中的某個服務架構優化出發，介紹了目前設計中存在的缺陷，并借助來自中間件團隊的，包含時間輪算法實現的延遲 MQ，給出了優化設計的方法。

第一章    定時任務及時間輪算法發展

1.1 時間輪算法的出現

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

1.2 基于隊列的定時任務執行模型

在計算機的世界中，只有待解決的問題大規模化以后，算法的價值才能夠得到最大化的體現。在介紹時間輪算法之前，我們有必要介紹另一種定時任務的實現，即基于隊列的定時任務。隊列這種數據結構無論是在操作系統中還是各編程語言如 Java 中都被大量使用，本文不再展開贅述。

下面從線程模型、定時任務種類和任務隊列的數據結構三個方面展開詳細介紹：

（1）線程模型

用戶線程：負責定時任務的注冊；

輪詢線程：負責從任務隊列中掃描出符合執行條件的任務，例如任務的待執行時間已經到達，輪詢線程將從隊列中取出該任務，并交由異步線程池處理該任務。

異步線程池：專門負責任務的執行。

（2）定時任務

定時任務主要分為一次性執行的定時任務（Dubbo 中超時判斷）以及重復執行的定時任務，這兩種定時任務都很好理解，一次性執行的定時任務在規定的未來某一時刻或距離現在的一段固定時長后執行，分別對應絕對值和相對值的概念。

而重復執行的定時任務是在一次性執行任務的基礎上多次重復執行，這意味著，在上述線程協調工作中，當重復執行任務執行完成一次后，將被重新放回任務隊列中。  

（3）任務隊列數據結構

 從最簡單的數據結構出發，假設我們選用最基本的隊列，或者考慮到增減任務的方便，選擇雙向鏈表做為任務隊列，為任務隊列中的每個任務提供一個時間戳字段，這種實現的策略會產生哪些問題？

最大的問題是在查詢上，假設任務隊列中存在一些任務，那么為了找出達到規定時刻的待執行任務，輪詢線程需要掃描全部任務，此種數據結構的時間復雜度為 O（n），而且存在大量的空輪詢，即大部分的任務都沒有達到執行時間，這種效率幾乎是不可接受的。

為了提升查詢效率，可以嘗試從數據結構出發，利用有序隊列，在計算機的算法中，有序性可以顯著提高遍歷的效率，這樣一來，定時任務隊列輪詢線程從頭向尾遍歷時，在發現任意任務未達到規定執行時間戳后，就可以停止遍歷。

但是維護有序性也需要付出代價，普通任務隊列入隊一個任務的時間復雜度僅僅是 O（1），而有序任務隊列入隊一個任務的時間復雜度為 O（nlogn）。其次，我們可以借鑒分治的思想，將任務隊列分成n份，利用多線程遍歷，在線程完全并發執行的情況下，問題規模簡化到原來的1/n。但是多線程也會 CPU 執行效率降低。

綜上分析，定時任務框架需要具有如下要素：

1. 嚴格高效的數據結構，并不能基于簡單的隊列結構來存儲任務，否則輪詢的執行效率永遠無法提高。
2. 簡單的并發模型：CPU 的線程非常寶貴，不應占用過多線程資源。

時間輪算法解決了上述基于隊列的定時任務執行模型的缺陷，因此時間輪算法思想在后面互聯網技術發展中得到了大量應用，我們熟悉的 Linux Crontab，以及 Java 開發中常用的 Dubbo、Netty、Quartz、Akka、ZooKeeper、Kafka 等，幾乎所有的時間任務調度都采用了時間輪算法的思想。

值得一提的是，在 Dubbo 中，為了增強系統容錯，很多地方需要用到只需一次執行的任務調度，比如消費者需要知道各個 RPC 調用是否超時，而在 Dubbo 最開始的實現中，是采用將所有的返回結果（defaultFuture），都放入一個集合中，并通過一個定時任務，間隔掃描所有的 future，逐個判斷是否超時。這樣邏輯簡單，但是浪費性能，后面 Dubbo 借鑒了 Netty，引入了時間輪。

第二章    時間輪算法思想介紹及應用場景介紹

2.1 時間輪簡介

時間輪實質上是一種高效利用線程資源的任務調度模型，將大批量的任務全部整合進一個調度器中，從而對任務進行統一的調度管理，針對定時任務，延時任務等事件的調度效率非常高。

時間輪算法的核心是：第一章中描述的對任務隊列進行輪詢的線程不再負責遍歷所有的任務，而是僅僅遍歷時間刻度。時間輪算法好比指針不斷在時鐘上旋轉、遍歷，如果發現某一時刻上有任務（任務隊列），那么就會將任務隊列上的所有任務都執行一遍，這樣便大幅度的減少了額外的掃描操作。

第一章中，我們提出了一個高效的定時任務框架需要具備嚴格高效的數據結構和簡單的并發模型兩個特點，而時間輪模型正是具備了這樣的特點。

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

2.2 時間輪模型

2.2.1 簡單時間輪模型

簡單時間輪模型不再使用隊列作為數據結構，而是使用數組加鏈表的形式（很經典的組合）， 如下圖所示，該時間輪通過數組實現，可以很方便地通過下標定位到定時任務鏈路，因此，添加、刪除、執行定時任務的時間復雜度為 O（1）。

 圖2.2.1 簡單時間輪模型

顯然，這種簡單時間輪就解決了任務隊列中遍歷效率低下的問題，輪詢線程遍歷到某一個時間刻度后，總是執行對應刻度上任務隊列中的所有任務（通常是將任務扔給異步線程池來處理），而不再需要遍歷檢查所有任務的時間戳是否達到要求。

通過增加槽（slot）的數量，可以細化的時間粒度以及得到更大的時間跨度，但是這樣的實現方式有巨大的缺陷：

1. 當時間粒度小，時間跨度大，而任務又很少的時候，時間槽的輪詢效率變低。
2. 當時間粒度小，時間槽數量多，而任務又很少時，很多槽位占用的內存空間是沒有意義的。

2.2.2 帶有 round 的時間輪模型

類比循環數組的思想，后人設計了帶 round 的時間輪，這種時間輪的結構如下圖所示：

 圖2.2.2 帶有round的時間輪模型

如圖2.2.2所示，expire 代表到期時間，round 表示時間輪要在轉動幾圈之后才執行任務，也就是說當指針轉到某個 bucket 時，不能像簡單的單時間輪那樣直接執行 bucket 下所有的任務。而且要去遍歷該 bucket 下的鏈表，判斷時間輪轉動的次數是否等于節點中的 round 值，只有當 expire 和 round 都相同的情況下，才能執行任務。

這種結構的時間輪明顯減少了所需刻度的個數，即彌補了簡單時間輪在時間槽位較多，而任務較少情況下內存空間浪費的問題。

但是這種結構的時間輪并不能減少輪詢線程的輪詢次數，效率相對較低。

2.2.3 分層時間輪模型

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

 圖2.2.3 分層時間輪模型

分層時間輪的工作方式為低層級的時間輪帶動高層級的時間輪轉動，圖中箭頭為任務的“下放”，例如，2號8點40分0秒執行的任務，當天輪轉動到刻度2時，會將第2天的任務，下放到對應時輪刻度為8的槽位中，當時輪轉動到8時，會將任務繼續下放到分輪刻度為40的槽位中，直至到最低層次的時間輪，轉動到該槽位時，將該槽位中的任務，全部執行。

針對時間復雜度，這種時間輪對比帶有 round 的時間輪不再遍歷計算對比任務的 round，而是直接全部取出執行。

針對空間復雜度，分層時間輪利用維度上升的思路對時間輪進行分層，每個層級的時間粒度對應一個時間輪，多個時間輪之間進行級聯協作。

2.3 時間輪應用場景介紹

時間輪作為高效的調度模型，在各種場景均有廣泛的應用，常見的場景主要有如下幾個：

（1）定時器

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

（2）負載均衡

時間輪可以用于實現負載均衡算法，將請求分配到不同的服務器上，避免單個服務器負載過重。時間輪可以根據服務器的負載情況來動態調整分配策略，實現動態負載均衡。

（3）事件驅動

時間輪可以用于實現事件驅動模型，將事件分配到不同的處理器上，提高并發處理能力。事件可以是 I/O 事件、定時事件、用戶事件等，時間輪可以根據事件的類型和優先級來動態調整分配策略，實現高效的事件驅動模型。

（4）數據庫管理

時間輪可以用于實現數據庫管理，將數據分配到不同的存儲設備上，提高數據讀寫效率。時間輪可以根據數據的類型、大小和訪問頻率等來動態調整數據分配策略，實現高效的數據庫管理。

（5）其他應用

時間輪還可以用于其他一些應用，如消息隊列、任務調度、網絡流量控制等，具體應用取決于具體的需求和場景。

第三章     時間輪在 Dubbo 的應用與實現

3.1 Dubbo 中時間輪的應用

Dubbo 的設計中，客戶端在調用服務端的時候，會對任務進行計時，如果任務超時，那么會被檢測到，并重試請求。在 Dubbo 最開始的實現中，是采用將所有的返回結果（defaultFuture），都放入一個集合中，并通過一個定時任務，間隔掃描所有的 future，逐個判斷是否超時。

這樣邏輯簡單，但是浪費性能，后面 Dubbo 借鑒了 Netty，引入了時間輪。任務交由時間輪管理，由專門的線程進行調度。

3.2 Dubbo 中時間輪的實現

Dubbo 中時間輪算法的實現，主要有一個類和三個接口：

首先是 Timer 接口，這個一個調度的核心接口，主要用于后臺的一次性調度，我們僅介紹 newTimeOut 方法，這個方法就是把一個任務扔給調度器執行，第一個參數類型 TimerTask，即需要執行的任務。

接下來是 TimeTask 接口，它只有一個方法 run，參數類型是 Timeout，我們注意到上面 Timer 接口的 newTimeout  這個方法返回的參數就是 Timeout，和此處的入參相同，實際這里傳入的 Timeout 參數就是 newTimeout 的返回值。

Timeout 對象與 TimerTask 對象一一對應，兩者的關系類似于線程池返的 Future 對象與提交到線程池中的任務對象之間的關系。

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

上述幾個接口從邏輯上構成了一個任務調度系統。下面是任務調度系統的核心，即時間輪調度器的實現-- HashedWheelTimer。

仔細看它的類上注釋可以發現，該方法并不能提供精確的計時，而是檢測每個 tick 中（也就是時間輪中的一個時間槽），是否有 TimerTask，其期望執行時間已經落后于當前時間，如果是則執行該任務。任務執行時間的精確度可以通過細化時間槽來提升。

默認的 tick duration 是100毫秒，大部分網絡應用中，I/O 超時并非必須是精準的，例如5秒超時，實際上稍晚一會也是可以的，因此這個默認值無需修改。

這個類維護了一種稱為“wheel”的數據結構，也就是我們說的時間輪。簡單地說，一個 wheel 就是一個 hash table，它的 hash 函數是任務的截止時間，也就是我們要通過 hash 函數把這個任務放到它應該在的時間槽中，這樣隨著時間的推移，當我們進入某個時間槽中時，這個槽中的任務也剛好到了它該執行的時間。

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

接著則是創建時間槽數組，最后是初始化時間槽數組的每個參數。

下面介紹下 newTimeout 方法，這個方法的主要作用是向調度器中添加一個待執行的任務，同樣忽略基本的參數校驗，主體流程為：

1. 第一步將等待調度的任務數+1，如果超過了最大限制，則-1并拋出異常。
2. 第二步則調用 start 方法，啟動時間輪。
3. 第三步計算當前任務的截止時間，并做防溢出處理。
4. 構造一個 TimeOut ，并放入等待隊列。

這里我們展開比較重要的 start 方法，首先獲取 worker 的運行狀態，如果是初始化狀態，則更新成已啟動狀態，啟動 workThread 線程，若是其他狀態，則做其他相應的處理。接著是等待 workThread 將 startTime 初始化完成（在 Worker 的 run 方法中初始化完成），之所以需要等待 startTime 初始化完成，是因為 newTimeout 方法中，start 方法調用后也用到了這個 startTime，不這樣做，任務的截止時間計算會有問題。

至此，我們介紹了利用 HashedWheelTimer 添加一個任務的主體流程，接下來是時間輪的內部運轉。

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

1.初始化 startTime，這里與上文中 start 方法內部對應。初始化后，利用閉鎖 CountDownLatch 通知等待線程往下執行。

2.當定時器處于已啟動狀態時，不停地推進 ticket，推進的過程分解為：

• 等待下一個 ticket 的到來。
• ticket 到來后，計算該 ticket 對應時間輪的槽位（取模運算）。
• 處理已取消的任務隊列。
• 獲取當前時間槽，并將待處理任務隊列中的任務放到槽中。
• 執行當前時間槽中的任務。

3. 如果時間輪已經停止了，則執行以下流程：

• 清理所有時間槽中的未處理任務調度。
• 清理待處理任務調度隊列，將未取消的加入到未處理集合中。
• 處理已取消的任務隊列。

我們重點關注下定時器啟動狀態下的第3步，獲取當前時間槽，并將待處理任務隊列中的任務放到槽中的方法 transferTimeoutsToBuckets，其流程為以下幾個步驟（這里規定循環了有限次，防止待處理隊列過大，導致本次添加到槽耗費時間過長）：

• 從待處理任務調度隊列中取出第一個任務，進行校驗。
• 根據取出的待處理任務調度，計算出一個槽。
• 設置此任務調度的剩余圈數（從這里看出 Dubbo 用的是我們在2.2.2中介紹的“帶有 round 的時間輪”）。
• 取計算出的槽和當前槽中的較大者，并進行取模。
• 將此任務調度加入對應的槽中。

總結：這部分內容我們分別從向調度器中添加任務的主體流程和時間輪內部運轉兩個部分，簡單介紹了 Dubbo 中時間輪的實現。

如果感興趣，可以學習其源代碼，里面很多代碼設計非常巧妙，比如 startTime 初始化及初始化完成后的線程間通信實現，這些設計思路對筆者這樣的初學者來說很有益處。

第四章    時間輪算法的應用展望

筆者在剛開始工作時，設計過一個叫做下載中心的服務，這個服務的功能為導出和下載項目中的數據文件，實際的定位是為了減少異步線程過多而影響各個核心業務，因此將其功能抽取出來，從而達到減少核心業務壓力的目標。

下載中心的初步設計，考慮到并發請求以及文件過大帶來的內存溢出問題，除了采取各種方式避免外，整體思路是，預計特別大的文件，先將任務記錄進行持久化，并通過后臺線程池慢慢執行這些任務，通過任務記錄，主動拉取數據、生成文件等。

模型類似于 Netty 中的 BOSS-WORKER 的模式，BOSS 線程負責定時從數據庫中查出未消費的任務，并將其分配給 worker 線程池進行消費，如圖4.1所示。

 圖4.1 改造前應用服務任務消費模式示意圖

當前設計雖然可以做到防止內存溢出等問題，但是這樣的設計也存在一定的缺陷：

1. 如果后續用戶量增多，可以考慮水平擴充服務的數量，但是用于持久化任務記錄的數據庫會成為瓶頸。
2. 即使 BOSS 線程不難做到避免任務的重復消費，但是待執行任務的查詢效率會大大降低。
3. 整個服務太過于依賴 BOSS 線程。

因此，考慮一種方式替代這種 BOSS-WORKER 模式，目前想到的一種方式為 MQ 消息隊列，將待執行的任務信息投至 MQ 隊列當中，然后該服務對其進行消費。這樣的做法，即可解決上述3個問題，并具備維持任務有序性的優勢。

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

圖4.2 改造后應用服務任務消費模式示意圖

圖中，綠色模塊為整個系統設計中的用以調度定時任務的任務調度模塊，利用時間輪來統一管理這些定時任務。

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

而這種長延時消息的持久化，與我們圖4.1所示定時從數據庫取任務所遇到的瓶頸是一致的。

我們更期望有成熟的框架，能夠提供 1.長延遲任務的持久化 以及 2. 任務調度 的能力。從中間件平臺組提供的 MQ 中，我們發現目前它是已經支持 包含這兩個能力的延遲 MQ 功能的。延遲 MQ 架構大致如下圖所示：

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

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

圖4.4 延遲消息發送和處理流程示意圖

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

總結

本文從定時任務和時間輪算法的起源開始，對時間輪算法進行了介紹。詳細的闡述了時間輪的算法思想，以及簡單時間輪、帶 round 的時間輪以及分層時間輪這三種常見的時間輪模型，并給出了對應的數據結構實現。

接著以 Dubbo 為例，介紹了時間輪模型在 Dubbo 中的應用，從源碼出發，介紹了該算法在 Dubbo 中的主要實現。

最后，我們介紹了筆者自身所做過的一個小模塊，展開分析了該模塊功能目前所遇到的瓶頸，并給出了通過融合了時間輪算法的延遲 MQ 來優化當前設計的思路。

參考文獻：

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