最近看 Kafka 看到了時間輪算法，記得以前看 Netty 也看到過這玩意，沒太過關(guān)注。今天就來看看時間輪到底是什么東西。

為什么要用時間輪算法來實現(xiàn)延遲操作?

延時操作 Java 不是提供了 Timer 么？

還有 DelayQueue 配合線程池或者 ScheduledThreadPool 不香嗎？

我們先來簡單看看 Timer、DelayQueue 和 ScheduledThreadPool 的相關(guān)實現(xiàn)，看看它們是如何實現(xiàn)延時任務的，源碼之下無秘密。再來剖析下為何 Netty 和 Kafka 特意實現(xiàn)了時間輪來處理延遲任務。

如果在手機上閱讀其實純看字也行，不用看代碼，我都會先用文字描述清楚。不過電腦上看效果更佳。

Timer

Timer 可以實現(xiàn)延時任務，也可以實現(xiàn)周期性任務。我們先來看看 Timer 核心屬性和構(gòu)造器。

核心就是一個優(yōu)先隊列和封裝的執(zhí)行任務的線程，從這我們也可以看到一個 Timer 只有一個線程執(zhí)行任務。

再來看看如何實現(xiàn)延時和周期性任務的。我先簡單的概括一下，首先維持一個小頂堆，即最快需要執(zhí)行的任務排在優(yōu)先隊列的第一個，根據(jù)堆的特性我們知道插入和刪除的時間復雜度都是 O(logn)。

然后 TimerThread 不斷地拿排著的第一個任務的執(zhí)行時間和當前時間做對比。如果時間到了先看看這個任務是不是周期性執(zhí)行的任務，如果是則修改當前任務時間為下次執(zhí)行的時間，如果不是周期性任務則將任務從優(yōu)先隊列中移除。最后執(zhí)行任務。如果時間還未到則調(diào)用 wait() 等待。

再看下圖，整理下流程。

流程知道了再對著看下代碼，這塊就差不多了?？创a不爽的可以跳過代碼部分，影響不大。

先來看下 TaskQueue，就簡單看下插入任務的過程，就是個普通的堆插入操作。

再來看看 TimerThread 的 run 操作。

小結(jié)一下

可以看出 Timer 實際就是根據(jù)任務的執(zhí)行時間維護了一個優(yōu)先隊列，并且起了一個線程不斷地拉取任務執(zhí)行。

有什么弊端呢？

首先優(yōu)先隊列的插入和刪除的時間復雜度是O(logn)，當數(shù)據(jù)量大的時候，頻繁的入堆出堆性能有待考慮。

并且是單線程執(zhí)行，那么如果一個任務執(zhí)行的時間過久則會影響下一個任務的執(zhí)行時間(當然你任務的run要是異步執(zhí)行也行)。

并且從代碼可以看到對異常沒有做什么處理，那么一個任務出錯的時候會導致之后的任務都無法執(zhí)行。

?

ScheduledThreadPoolExecutor

在說 ScheduledThreadPoolExecutor 之前我們再看下 Timer 的注釋，注釋可都是干貨千萬不要錯過。我做了點修改，突出了下重點。

Java 5.0 introduced ScheduledThreadPoolExecutor, It is effectively a more versatile replacement for the Timer, it allows multiple service threads. Configuring with one thread makes it equivalent to Timer。

簡單翻譯下：1.5 引入了 ScheduledThreadPoolExecutor，它是一個具有更多功能的 Timer 的替代品，允許多個服務線程。如果設置一個服務線程和 Timer 沒啥差別。

從注釋看出相對于 Timer ，可能就是單線程跑任務和多線程跑任務的區(qū)別。我們來看下。

繼承了 ThreadPoolExecutor，實現(xiàn)了 ScheduledExecutorService?？梢远ㄐ圆僮骶褪钦＞€程池差不多了。區(qū)別就在于兩點，一個是 ScheduledFutureTask ，一個是 DelayedWorkQueue。

其實 DelayedWorkQueue 就是優(yōu)先隊列，也是利用數(shù)組實現(xiàn)的小頂堆。而 ScheduledFutureTask 繼承自 FutureTask 重寫了 run 方法，實現(xiàn)了周期性任務的需求。

小結(jié)一下

ScheduledThreadPoolExecutor 大致的流程和 Timer 差不多，也是維護一個優(yōu)先隊列，然后通過重寫 task 的 run 方法來實現(xiàn)周期性任務，主要差別在于能多線程運行任務，不會單線程阻塞。

并且 Java 線程池的設定是 task 出錯會把錯誤吃了，無聲無息的。因此一個任務出錯也不會影響之后的任務。

?

DelayQueue

Java 中還有個延遲隊列 DelayQueue，加入延遲隊列的元素都必須實現(xiàn) Delayed 接口。延遲隊列內(nèi)部是利用 PriorityQueue 實現(xiàn)的，所以還是利用優(yōu)先隊列！Delayed 接口繼承了Comparable 因此優(yōu)先隊列是通過 delay 來排序的。

然后我們再來看下延遲隊列是如何獲取元素的。

小結(jié)一下

也是利用優(yōu)先隊列實現(xiàn)的，元素通過實現(xiàn) Delayed ?接口來返回延遲的時間。不過延遲隊列就是個容器，需要其他線程來獲取和執(zhí)行任務。

這下是搞明白了 Timer 、ScheduledThreadPool 和 DelayQueue，總結(jié)的說下它們都是通過優(yōu)先隊列來獲取最早需要執(zhí)行的任務，因此插入和刪除任務的時間復雜度都為O(logn)，并且 Timer 、ScheduledThreadPool 的周期性任務是通過重置任務的下一次執(zhí)行時間來完成的。

問題就出在時間復雜度上，插入刪除時間復雜度是O(logn)，那么假設頻繁插入刪除次數(shù)為 m，總的時間復雜度就是O(mlogn)，這種時間復雜度滿足不了 Kafka 這類中間件對性能的要求，而時間輪算法的插入刪除時間復雜度是O(1)。我們來看看時間輪算法是如何實現(xiàn)的。

?

時間輪算法

俗話說藝術(shù)源于生活，技術(shù)也能從日常生活中找到靈感。咱們先來看塊表，嗯金色的表。

都看清楚了吧，時間輪就是和手表時鐘很相似的存在。時間輪用環(huán)形數(shù)組實現(xiàn)，數(shù)組的每個元素可以稱為槽，和 HashMap一樣稱呼。

槽的內(nèi)部用雙向鏈表存著待執(zhí)行的任務，添加和刪除的鏈表操作時間復雜度都是 O(1)，槽位本身也指代時間精度，比如一秒掃一個槽，那么這個時間輪的最高精度就是 1 秒。

也就是說延遲 1.2 秒的任務和 1.5 秒的任務會被加入到同一個槽中，然后在 1 秒的時候遍歷這個槽中的鏈表執(zhí)行任務。

從圖中可以看到此時指針指向的是第一個槽，一共有八個槽0~7，假設槽的時間單位為 1 秒，現(xiàn)在要加入一個延時 5 秒的任務，計算方式就是 5 % 8 + 1 = 6，即放在槽位為 6，下標為 5 的那個槽中。更具體的就是拼到槽的雙向鏈表的尾部。

然后每秒指針順時針移動一格，這樣就掃到了下一格，遍歷這格中的雙向鏈表執(zhí)行任務。然后再循環(huán)繼續(xù)。

可以看到插入任務從計算槽位到插入鏈表，時間復雜度都是O(1)。那假設現(xiàn)在要加入一個50秒后執(zhí)行的任務怎么辦？這槽好像不夠??？難道要加槽嘛？和HashMap一樣擴容？

不是的，常見有兩種方式，一種是通過增加輪次的概念。50 % 8 + 1 = 3，即應該放在槽位是 3，下標是 2 的位置。然后 (50 - 1) / 8 = 6，即輪數(shù)記為 6。也就是說當循環(huán) 6 輪之后掃到下標的 2 的這個槽位會觸發(fā)這個任務。Netty 中的 HashedWheelTimer 使用的就是這種方式。

還有一種是通過多層次的時間輪，這個和我們的手表就更像了，像我們秒針走一圈，分針走一格，分針走一圈，時針走一格。

多層次時間輪就是這樣實現(xiàn)的。假設上圖就是第一層，那么第一層走了一圈，第二層就走一格。

可以得知第二層的一格就是8秒，假設第二層也是 8 個槽，那么第二層走一圈，第三層走一格，可以得知第三層一格就是 64 秒。

那么一格三層，每層8個槽，一共 24 個槽時間輪就可以處理最多延遲 512 秒的任務。

而多層次時間輪還會有降級的操作，假設一個任務延遲 500 秒執(zhí)行，那么剛開始加進來肯定是放在第三層的，當時間過了 436 秒后，此時還需要 64 秒就會觸發(fā)任務的執(zhí)行，而此時相對而言它就是個延遲 64 秒后的任務，因此它會被降低放在第二層中，第一層還放不下它。

再過個 56 秒，相對而言它就是個延遲 8 秒后執(zhí)行的任務，因此它會再被降級放在第一層中，等待執(zhí)行。

降級是為了保證時間精度一致性。Kafka內(nèi)部用的就是多層次的時間輪算法。

Netty中的時間輪

在 Netty 中時間輪的實現(xiàn)類是 HashedWheelTimer，代碼中的 wheel 就是上圖畫的循環(huán)數(shù)組，mask 的設計和HashMap一樣，通過限制數(shù)組的大小為2的次方，利用位運算來替代取模運算，提高性能。tickDuration 就是每格的時間即精度?？梢钥吹脚鋫淞艘粋€工作線程來處理任務的執(zhí)行。

接下來我們再來看看任務是如何添加的。

可以看到任務并沒有直接添加到時間輪中，而是先入了一個 mpsc 隊列，我簡單說下 mpsc 是 JCTools 中的并發(fā)隊列，用在多個生產(chǎn)者可同時訪問隊列，但只有一個消費者會訪問隊列的情況。篇幅有限，有興趣的朋友自行了解實現(xiàn)。

然后我們再來看看工作線程是如何運作的。

很直觀沒什么花頭，我們先來看看 waitForNextTick，是如何得到下一次執(zhí)行時間的。

簡單的說就是通過 tickDuration 和此時已經(jīng)滴答的次數(shù)算出下一次需要檢查的時間，時候未到就sleep等著。

再來看下任務如何入槽的。

注釋的很清楚了，實現(xiàn)也和上述分析的一致。

最后再來看下如何執(zhí)行的。

就是通過輪數(shù)和時間雙重判斷，執(zhí)行完了移除任務。

小結(jié)一下

總體上看 Netty 的實現(xiàn)就是上文說的時間輪通過輪數(shù)的實現(xiàn)，完全一致。可以看出時間精度由 TickDuration 把控，并且工作線程的除了處理執(zhí)行到時的任務還做了其他操作，因此任務不一定會被精準的執(zhí)行。

而且任務的執(zhí)行如果不是新起一個線程，或者將任務扔到線程池執(zhí)行，那么耗時的任務會阻塞下個任務的執(zhí)行。

并且會有很多無用的 tick 推進，例如 TickDuration 為1秒，此時就一個延遲350秒的任務，那就是有349次無用的操作。

但是從另一面來看，如果任務都執(zhí)行很快(當然你也可以異步執(zhí)行)，并且任務數(shù)很多，通過分批執(zhí)行，并且增刪任務的時間復雜度都是O(1)來說。時間輪還是比通過優(yōu)先隊列實現(xiàn)的延時任務來的合適些。

?

Kafka 中的時間輪

上面我們說到 Kafka 中的時間輪是多層次時間輪實現(xiàn)，總的而言實現(xiàn)和上述說的思路一致。不過細節(jié)有些不同，并且做了點優(yōu)化。

先看看添加任務的方法。在添加的時候就設置任務執(zhí)行的絕對時間。

那么時間輪是如何推動的呢？Netty 中是通過固定的時間間隔掃描，時候未到就等待來進行時間輪的推動。上面我們分析到這樣會有空推進的情況。

而 Kafka 就利用了空間換時間的思想，通過 DelayQueue，來保存每個槽，通過每個槽的過期時間排序。這樣擁有最早需要執(zhí)行任務的槽會有優(yōu)先獲取。如果時候未到，那么 ?delayQueue.poll 就會阻塞著，這樣就不會有空推進的情況發(fā)送。

我們來看下推進的方法。

從上面的 add 方法我們知道每次對比都是根據(jù)expiration < currentTime + interval 來進行對比的，而advanceClock 就是用來推進更新 currentTime ?的。

小結(jié)一下

Kafka 用了多層次時間輪來實現(xiàn)，并且是按需創(chuàng)建時間輪，采用任務的絕對時間來判斷延期，并且對于每個槽(槽內(nèi)存放的也是任務的雙向鏈表)都會維護一個過期時間，利用 DelayQueue 來對每個槽的過期時間排序，來進行時間的推進，防止空推進的存在。

每次推進都會更新 currentTime 為當前時間戳，當然做了點微調(diào)使得 currentTime 是 tickMs 的整數(shù)倍。并且每次推進都會把能降級的任務重新插入降級。

可以看到這里的 DelayQueue 的元素是每個槽，而不是任務，因此數(shù)量就少很多了，這應該是權(quán)衡了對于槽操作的延時隊列的時間復雜度與空推進的影響。

?

總結(jié)

首先介紹了 Timer、DelayQueue 和 ScheduledThreadPool，它們都是基于優(yōu)先隊列實現(xiàn)的，O(logn) 的時間復雜度在任務數(shù)多的情況下頻繁的入隊出隊對性能來說有損耗。因此適合于任務數(shù)不多的情況。

Timer 是單線程的會有阻塞的風險，并且對異常沒有做處理，一個任務出錯 Timer 就掛了。而 ScheduledThreadPool 相比于 Timer 首先可以多線程來執(zhí)行任務，并且線程池對異常做了處理，使得任務之間不會有影響。

并且 Timer 和 ScheduledThreadPool 可以周期性執(zhí)行任務。而 DelayQueue 就是個具有優(yōu)先級的阻塞隊列。

對比而言時間輪更適合任務數(shù)很大的延時場景，它的任務插入和刪除時間復雜度都為O(1)。對于延遲超過時間輪所能表示的范圍有兩種處理方式，一是通過增加一個字段-輪數(shù)，Netty 就是這樣實現(xiàn)的。二是多層次時間輪，Kakfa 是這樣實現(xiàn)的。

相比而言 Netty 的實現(xiàn)會有空推進的問題，而 Kafka 采用 DelayQueue 以槽為單位，利用空間換時間的思想解決了空推進的問題。

可以看出延遲任務的實現(xiàn)都不是很精確的，并且或多或少都會有阻塞的情況，即使你異步執(zhí)行，線程不夠的情況下還是會阻塞。

巨人的肩膀

《深入理解Kafka:核心設計與實踐原理》

https://www.cnblogs.com/luozhiyun/p/12075326.html

有道無術(shù)，術(shù)可成；有術(shù)無道，止于術(shù)

歡迎大家關(guān)注Java之道公眾號

好文章，我在看??