前言

Kafka 中有很多延時操作，比如對于耗時的網(wǎng)絡(luò)請求（比如 Produce 是等待 ISR 副本復(fù)制成功）會被封裝成 DelayOperation 進行延遲處理操作，防止阻塞 Kafka請求處理線程。

Kafka 沒有使用 JDK 自帶的 Timer 和 DelayQueue 實現(xiàn)。因為時間復(fù)雜度上這兩者插入和刪除操作都是 O(logn)，不能滿足 Kafka 的高性能要求。

冷知識：JDK Timer 和 DelayQueue 底層都是個優(yōu)先隊列，即采用了 minHeap 的數(shù)據(jù)結(jié)構(gòu)，最快需要執(zhí)行的任務(wù)排在隊列第一個，不一樣的是 Timer 中有個線程去拉取任務(wù)執(zhí)行，DelayQueue 其實就是個容器，需要配合其他線程工作。
ScheduledThreadPoolExecutor 是 JDK 的定時任務(wù)實現(xiàn)的一種方式，其實也就是 DelayQueue + 池化是線程的一個實現(xiàn)。

Kafka 基于時間輪實現(xiàn)了延時操作，時間輪算法的插入刪除操作都是 O(1) 的時間復(fù)雜度，滿足了 Kafka 對于性能的要求。除了 Kafka 以外，像 Netty 、ZooKeepr、Dubbo 這樣的開源項目都有使用到時間輪的實現(xiàn)。

那么時間輪回算法是怎么樣的，算法思想是什么？Kafka 中又是怎么實現(xiàn)它的。

Kafka 時間輪算法

時間輪回的算法思想可以通過我們?nèi)粘Ｉ钪械溺姳韥砝斫狻?/p>

Kafka 中的時間輪（TimingWheel）是一個存儲定時任務(wù)的環(huán)形隊列，底層采用數(shù)組實現(xiàn)，數(shù)組中的每個元素可以存放一個定時任務(wù)列表（TimerTaskList）。TimerTaskList是一個環(huán)形的雙向鏈表，鏈表中的每一項表示的都是定時任務(wù)項（TimerTaskEntry），其中封裝了真正的定時任務(wù)（TimerTask）。

圖中的幾個參數(shù)：

tickMs: 時間跨度
wheelSize: 時間輪回 bucket 的個數(shù)
startMs: 開始時間
interval：時間輪的整體時間跨度 = tickMs * wheelSize
currentTime: tickMs 的整數(shù)倍，代表時間輪當(dāng)前所處的時間
- currentTime可以將整個時間輪劃分為到期部分和未到期部分，currentTime當(dāng)前指向的時間格也屬于到期部分，表示剛好到期，需要處理此時間格所對應(yīng)的TimerTaskList中的所有任務(wù)

整個時間輪的總體跨度是不變的，隨著指針currentTime的不斷推進，當(dāng)前時間輪所能處理的時間段也在不斷后移，總體時間范圍在currentTime和currentTime+interval之間。

現(xiàn)在你可能會有疑問，這個抽象的 currentTime 怎么推進呢，別急著看下文

那么如何支持大跨度的定時任務(wù)呢？

如果要支持幾十萬毫秒的定時任務(wù)，難不成要擴容時間輪的那個數(shù)組？實際上這里有兩種解決方案：

使用增加輪次/圈數(shù)的概念（Netty 的 HashedWheelTimer ）
- 舉例來說，比如目前是 "0-7" 8個槽，41 % 8 + 1 = 2，即應(yīng)該放在槽位是 2，下標(biāo)是 1 的位置。然后 ( 41 - 1 ) / 8 = 5，即輪數(shù)記為 5。也就是說當(dāng)循環(huán) 5 打開之后掃到下標(biāo)的 1 的這個槽位會觸發(fā)這個任務(wù)。
- 具體實現(xiàn)細節(jié)這里不詳述
使用多層時間輪回的概念（Kafka 的 TimingWheel）
- 相較于上個方案，層級時間輪能更好控制時間粒度，可以應(yīng)對更加復(fù)雜的定時任務(wù)處理場景，適用的范圍更廣；

多層時間輪回就更像我們鐘表的概念了。秒針走的一圈、分針走的一圈和時針走的一圈就形成了一個多層時間輪的關(guān)系。

第N層時間輪走了一圈，等于 N+1 層時間輪走一格。即高一層時間輪的時間跨度等于當(dāng)前時間輪的整體跨度。

在任務(wù)插入時，如果第一層時間輪不滿足條件，就嘗試插入到高一層的時間輪，以此類推。

隨著時間推進，也會有一個時間輪降級的操作，原本延時較長的任務(wù)會從高一層時間輪重新提交到時間輪中，然后會被放在合適的低層次的時間輪當(dāng)中等待處理；

在 Kafka 中時間輪之間如何關(guān)聯(lián)呢，如果展現(xiàn)這種高一層的時間輪關(guān)系？

其實很簡單就是一個內(nèi)部對象的指針，指向自己高一層的時間輪對象。

另外還有一個問題，如何推進時間輪的前進，讓時間輪的時間往前走。

Netty 中的時間輪是通過工作線程按照固定的時間間隔 tickDuration 推進的
- 如果長時間沒有到期任務(wù)，這種方案會帶來推進的問題，從而造成一定的性能損耗；
Kafka 則是通過 DelayQueue 來推進，是一種空間換時間的思想；
- DelayQueue 中保存著所有的 TimerTaskList 對象，根據(jù)時間來排序，這樣延時越小的任務(wù)排在越前面。
- 外部通過一個線程（叫做ExpiredOperationReaper）從 DelayQueue 獲取超時的任務(wù)列表 TimerTaskList，然后根據(jù) TimerTaskList 的 過期時間來精確推進時間輪的時間 ，這樣就不會存在空推進的問題啦。

其實 Kafka 采用的是一種權(quán)衡的策略，把 DelayQueue 用在了合適的地方。DelayQueue 只存放了 TimerTaskList，并不是所有的 TimerTask，數(shù)量并不多，相比空推進帶來的影響是利大于弊的。

總結(jié)

Kafka 使用時間輪來實現(xiàn)延時隊列，因為其底層是任務(wù)的添加和刪除是基于鏈表實現(xiàn)的，是 O(1) 的時間復(fù)雜度，滿足高性能的要求；
對于時間跨度大的延時任務(wù)，Kafka 引入了層級時間輪，能更好控制時間粒度，可以應(yīng)對更加復(fù)雜的定時任務(wù)處理場景；
對于如何實現(xiàn)時間輪的推進和避免空推進影響性能，Kafka 采用空間換時間的思想，通過 DelayQueue 來推進時間輪，算是一個經(jīng)典的 trade off。

本文通過 Kafka 來講述了時間輪的算法設(shè)計思想，其中還提到了 Netty 時間輪算法的實現(xiàn)，可能會比較偏向理論，推薦去閱讀一下 Kafka 和 Netty 時間輪實現(xiàn)的源碼，并不是特別難，對比起來看會更有收獲。