從 Kafka 看時間輪算法設計

前言

Kafka 中有很多延時操作，比如對於耗時的網絡請求（比如 Produce 時等待 ISR 副本複製成功）會被封裝成 DelayOperation 進行延遲處理操作，防止阻塞 Kafka 請求處理線程。

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

冷知識：JDK Timer 和 DelayQueue 底層都是個優先隊列，即採用了 minHeap 的數據結構，最快需要執行的任務排在隊列第一個，不一樣的是 Timer 中有個線程去拉取任務執行，DelayQueue 其實就是個容器，需要配合其他線程工作。ScheduledThreadPoolExecutor 是 JDK 的定時任務實現的一種方式，其實也就是 DelayQueue + 池化線程的一個實現。

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

那麼時間輪算法是怎麼樣的，算法思想是什麼？Kafka 中又是怎麼實現它的。

Kafka 時間輪算法

時間輪的算法思想可以通過我們日常生活中的鐘表來理解。

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

圖中的幾個參數：

• tickMs: 時間跨度

• wheelSize: 時間輪中 bucket 的個數

• startMs: 開始時間

• interval：時間輪的整體時間跨度 = tickMs * wheelSize

• currentTime: tickMs 的整數倍，代表時間輪當前所處的時間

• currentTime 可以將整個時間輪劃分爲到期部分和未到期部分，currentTime 當前指向的時間格也屬於到期部分，表示剛好到期，需要處理此時間格所對應的 TimerTaskList 中的所有任務

整個時間輪的總體跨度是不變的，隨着指針 currentTime 的不斷推進，當前時間輪所能處理的時間段也在不斷後移，總體時間範圍在 currentTime 和 currentTime+interval 之間。

現在你可能會有疑問，這個抽象的 currentTime 怎麼推進呢，別急看下文

那麼如何支持大跨度的定時任務呢？

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

• 使用增加輪次 / 圈數的概念（Netty 的 HashedWheelTimer ）

• 舉例來說，比如目前是 "0-7" 8 個槽，41 % 8 + 1 = 2，即應該放在槽位是 2，下標是 1 的位置。然後 (41 - 1) / 8 = 5，即輪數記爲 5。也就是說當循環 5 輪之後掃到下標的 1 的這個槽位會觸發這個任務。

• 具體實現細節這裏不詳述

• 使用多層時間輪的概念 （Kafka 的 TimingWheel）

• 相較於上個方案，層級時間輪能更好控制時間粒度，可以應對更加複雜的定時任務處理場景，適用的範圍更廣；

多層時間輪就更像我們鐘錶的概念了。秒針走的一圈、分針走的一圈和時針走的一圈就形成了一個多層時間輪的關係。

第 N 層時間輪走了一圈，等於 N+1 層時間輪走一格。即高一層時間輪的時間跨度等於當前時間輪的整體跨度。

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

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

在 Kafka 中時間輪之間如何關聯呢，如何展現這種高一層的時間輪關係？

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

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

• Netty 中的時間輪是通過工作線程按照固定的時間間隔 tickDuration 推進的

• 如果長時間沒有到期任務，這種方案會帶來空推進的問題，從而造成一定的性能損耗；

• Kafka 則是通過 DelayQueue 來推進，是一種空間換時間的思想；

• DelayQueue 中保存着所有的 TimerTaskList 對象，根據時間來排序，這樣延時越小的任務排在越前面。

• 外部通過一個線程（叫做 ExpiredOperationReaper）從 DelayQueue 中獲取超時的任務列表 TimerTaskList，然後根據 TimerTaskList 的 過期時間來精確推進時間輪的時間，這樣就不會存在空推進的問題啦。

其實 Kafka 採用的是一種權衡的策略，把 DelayQueue 用在了合適的地方。DelayQueue 只存放了 TimerTaskList，並不是所有的 TimerTask，數量並不多，相比空推進帶來的影響是利大於弊的。

總結

• Kafka 使用時間輪來實現延時隊列，因爲其底層是任務的添加和刪除是基於鏈表實現的，是 O(1) 的時間複雜度，滿足高性能的要求；

• 對於時間跨度大的延時任務，Kafka 引入了層級時間輪，能更好控制時間粒度，可以應對更加複雜的定時任務處理場景；

• 對於如何實現時間輪的推進和避免空推進影響性能，Kafka 採用空間換時間的思想，通過 DelayQueue 來推進時間輪，算是一個經典的 trade off。

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

參考

• 《深入理解 Kafka》

• 《Netty 核心原理剖析與 RPC 實踐》專欄

作者：Richard_Yi

來源：juejin.cn/post/7047405443961847816

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/xZ4x9vCLPk4peTbjGFQyXQ