從 Kafka 看時(shí)間輪算法設(shè)計(jì)

前言

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

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

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

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

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

Kafka 時(shí)間輪算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

另外還有一個(gè)問題，如何推進(jìn)時(shí)間輪的前進(jìn)，讓時(shí)間輪的時(shí)間往前走。

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

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

總結(jié)

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

1.?造輪子！8個(gè)類手寫一個(gè)配置中心！
2.?不是我吹，這款 IDEA 插件你真沒用過！
3.?抗住千萬流量的大型分布式系統(tǒng)架構(gòu)設(shè)計(jì)
4.?網(wǎng)傳鐵飯碗職業(yè)排名，公務(wù)員僅排第八！
最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號(hào)并回復(fù)?Java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
PS：因公眾號(hào)平臺(tái)更改了推送規(guī)則，如果不想錯(cuò)過內(nèi)容，記得讀完點(diǎn)一下“在看”，加個(gè)“星標(biāo)”，這樣每次新文章推送才會(huì)第一時(shí)間出現(xiàn)在你的訂閱列表里。
點(diǎn)“在看”支持小哈呀，謝謝啦??！