今天這篇文章所聊的話題染坯，非常重要！不論是你想在面試中脫穎而出丘逸，還是你想要搞懂?Netty单鹿、Kafka、Zookeeper?等等中間件的原理深纲，你都務(wù)必要把這篇文章仔細(xì)閱讀完仲锄！一遍看不懂就多看幾遍，相信我湃鹊，你一定會(huì)有收獲昼窗！總之，搞懂時(shí)間輪算法真的非常有必要Ｌ紊帷！唆途！

另外富雅，我建議你在搞懂了時(shí)間輪算法的原理之后，可以參考一些開源項(xiàng)目對(duì)時(shí)間輪算法的實(shí)現(xiàn)肛搬，自己也手寫一個(gè)没佑。?下面是正文！

最近看 Kafka 看到了時(shí)間輪算法温赔，記得以前看 Netty 也看到過(guò)這玩意蛤奢，沒(méi)太過(guò)關(guān)注。今天就來(lái)看看時(shí)間輪到底是什么東西陶贼。

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

延時(shí)操作 Java 不是提供了 Timer 么啤贩？

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

我們先來(lái)簡(jiǎn)單看看 Timer拜秧、DelayQueue 和 ScheduledThreadPool 的相關(guān)實(shí)現(xiàn)痹屹，看看它們是如何實(shí)現(xiàn)延時(shí)任務(wù)的，源碼之下無(wú)秘密枉氮。再來(lái)剖析下為何 Netty 和 Kafka 特意實(shí)現(xiàn)了時(shí)間輪來(lái)處理延遲任務(wù)志衍。

如果在手機(jī)上閱讀其實(shí)純看字也行暖庄，不用看代碼，我都會(huì)先用文字描述清楚楼肪。不過(guò)電腦上看效果更佳培廓。

Timer

Timer 可以實(shí)現(xiàn)延時(shí)任務(wù)，也可以實(shí)現(xiàn)周期性任務(wù)春叫。我們先來(lái)看看 Timer 核心屬性和構(gòu)造器肩钠。

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

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

然后 TimerThread 不斷地拿排著的第一個(gè)任務(wù)的執(zhí)行時(shí)間和當(dāng)前時(shí)間做對(duì)比莉给。如果時(shí)間到了先看看這個(gè)任務(wù)是不是周期性執(zhí)行的任務(wù)毙石，如果是則修改當(dāng)前任務(wù)時(shí)間為下次執(zhí)行的時(shí)間，如果不是周期性任務(wù)則將任務(wù)從優(yōu)先隊(duì)列中移除颓遏。最后執(zhí)行任務(wù)徐矩。如果時(shí)間還未到則調(diào)用?wait()?等待。

再看下圖叁幢，整理下流程滤灯。

流程知道了再對(duì)著看下代碼，這塊就差不多了曼玩×壑瑁看代碼不爽的可以跳過(guò)代碼部分，影響不大黍判。

先來(lái)看下 TaskQueue豫尽，就簡(jiǎn)單看下插入任務(wù)的過(guò)程，就是個(gè)普通的堆插入操作顷帖。

再來(lái)看看 TimerThread 的?run?操作美旧。

小結(jié)一下

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

有什么弊端呢榴嗅？

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

并且是單線程執(zhí)行，那么如果一個(gè)任務(wù)執(zhí)行的時(shí)間過(guò)久則會(huì)影響下一個(gè)任務(wù)的執(zhí)行時(shí)間(當(dāng)然你任務(wù)的run要是異步執(zhí)行也行)吊说。

并且從代碼可以看到對(duì)異常沒(méi)有做什么處理论咏，那么一個(gè)任務(wù)出錯(cuò)的時(shí)候會(huì)導(dǎo)致之后的任務(wù)都無(wú)法執(zhí)行优炬。

ScheduledThreadPoolExecutor

在說(shuō) ScheduledThreadPoolExecutor 之前我們?cè)倏聪?Timer 的注釋，注釋可都是干貨千萬(wàn)不要錯(cuò)過(guò)厅贪。我做了點(diǎn)修改蠢护，突出了下重點(diǎn)。

簡(jiǎn)單翻譯下：1.5 引入了 ScheduledThreadPoolExecutor养涮，它是一個(gè)具有更多功能的 Timer 的替代品葵硕，允許多個(gè)服務(wù)線程。如果設(shè)置一個(gè)服務(wù)線程和 Timer 沒(méi)啥差別贯吓。

從注釋看出相對(duì)于 Timer 懈凹，可能就是單線程跑任務(wù)和多線程跑任務(wù)的區(qū)別。我們來(lái)看下悄谐。

繼承了 ThreadPoolExecutor介评，實(shí)現(xiàn)了 ScheduledExecutorService∨澜ⅲ可以定性操作就是正常線程池差不多了们陆。區(qū)別就在于兩點(diǎn)，一個(gè)是 ScheduledFutureTask 情屹，一個(gè)是 DelayedWorkQueue坪仇。

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

小結(jié)一下

ScheduledThreadPoolExecutor 大致的流程和 Timer 差不多惜颇，也是維護(hù)一個(gè)優(yōu)先隊(duì)列雾袱，然后通過(guò)重寫 task 的 run 方法來(lái)實(shí)現(xiàn)周期性任務(wù)，主要差別在于能多線程運(yùn)行任務(wù)官还，不會(huì)單線程阻塞。

并且 Java 線程池的設(shè)定是 task 出錯(cuò)會(huì)把錯(cuò)誤吃了毒坛，無(wú)聲無(wú)息的望伦。因此一個(gè)任務(wù)出錯(cuò)也不會(huì)影響之后的任務(wù)。

DelayQueue

Java 中還有個(gè)延遲隊(duì)列 DelayQueue煎殷，加入延遲隊(duì)列的元素都必須實(shí)現(xiàn) Delayed 接口屯伞。延遲隊(duì)列內(nèi)部是利用 PriorityQueue 實(shí)現(xiàn)的，所以還是利用優(yōu)先隊(duì)列豪直！Delayed 接口繼承了Comparable 因此優(yōu)先隊(duì)列是通過(guò) delay 來(lái)排序的劣摇。

然后我們?cè)賮?lái)看下延遲隊(duì)列是如何獲取元素的。

小結(jié)一下

也是利用優(yōu)先隊(duì)列實(shí)現(xiàn)的弓乙，元素通過(guò)實(shí)現(xiàn) Delayed ?接口來(lái)返回延遲的時(shí)間末融。不過(guò)延遲隊(duì)列就是個(gè)容器钧惧，需要其他線程來(lái)獲取和執(zhí)行任務(wù)。

這下是搞明白了 Timer 勾习、ScheduledThreadPool 和 DelayQueue浓瞪，總結(jié)的說(shuō)下它們都是通過(guò)優(yōu)先隊(duì)列來(lái)獲取最早需要執(zhí)行的任務(wù)，因此插入和刪除任務(wù)的時(shí)間復(fù)雜度都為O(logn)巧婶，并且 Timer 乾颁、ScheduledThreadPool 的周期性任務(wù)是通過(guò)重置任務(wù)的下一次執(zhí)行時(shí)間來(lái)完成的。

問(wèn)題就出在時(shí)間復(fù)雜度上艺栈，插入刪除時(shí)間復(fù)雜度是O(logn)英岭，那么假設(shè)頻繁插入刪除次數(shù)為 m，總的時(shí)間復(fù)雜度就是O(mlogn)湿右，這種時(shí)間復(fù)雜度滿足不了 Kafka 這類中間件對(duì)性能的要求诅妹，而時(shí)間輪算法的插入刪除時(shí)間復(fù)雜度是O(1)。我們來(lái)看看時(shí)間輪算法是如何實(shí)現(xiàn)的诅需。

時(shí)間輪算法

俗話說(shuō)藝術(shù)源于生活漾唉，技術(shù)也能從日常生活中找到靈感。咱們先來(lái)看塊表堰塌，嗯金色的表赵刑。

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

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

也就是說(shuō)延遲 1.2 秒的任務(wù)和 1.5 秒的任務(wù)會(huì)被加入到同一個(gè)槽中贼急，然后在 1 秒的時(shí)候遍歷這個(gè)槽中的鏈表執(zhí)行任務(wù)茅茂。

從圖中可以看到此時(shí)指針指向的是第一個(gè)槽，一共有八個(gè)槽0~7太抓，假設(shè)槽的時(shí)間單位為 1 秒空闲，現(xiàn)在要加入一個(gè)延時(shí) 5 秒的任務(wù)，計(jì)算方式就是 5 % 8 + 1 = 6走敌，即放在槽位為 6碴倾，下標(biāo)為 5 的那個(gè)槽中。更具體的就是拼到槽的雙向鏈表的尾部。

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

可以看到插入任務(wù)從計(jì)算槽位到插入鏈表片迅，時(shí)間復(fù)雜度都是O(1)。那假設(shè)現(xiàn)在要加入一個(gè)50秒后執(zhí)行的任務(wù)怎么辦皆辽？這槽好像不夠案躺摺？難道要加槽嘛驱闷？和HashMap一樣擴(kuò)容耻台？

不是的，常見有兩種方式空另，一種是通過(guò)增加輪次的概念盆耽。50 % 8 + 1 = 3，即應(yīng)該放在槽位是 3扼菠，下標(biāo)是 2 的位置摄杂。然后 (50 - 1) / 8 = 6，即輪數(shù)記為 6循榆。也就是說(shuō)當(dāng)循環(huán) 6 輪之后掃到下標(biāo)的 2 的這個(gè)槽位會(huì)觸發(fā)這個(gè)任務(wù)析恢。Netty 中的 HashedWheelTimer 使用的就是這種方式。

還有一種是通過(guò)多層次的時(shí)間輪秧饮，這個(gè)和我們的手表就更像了映挂，像我們秒針走一圈，分針走一格盗尸，分針走一圈柑船，時(shí)針走一格。

多層次時(shí)間輪就是這樣實(shí)現(xiàn)的泼各。假設(shè)上圖就是第一層鞍时，那么第一層走了一圈，第二層就走一格扣蜻。

可以得知第二層的一格就是8秒寸癌，假設(shè)第二層也是 8 個(gè)槽，那么第二層走一圈弱贼，第三層走一格，可以得知第三層一格就是 64 秒磷蛹。

那么一格三層吮旅，每層8個(gè)槽，一共 24 個(gè)槽時(shí)間輪就可以處理最多延遲 512 秒的任務(wù)。

而多層次時(shí)間輪還會(huì)有降級(jí)的操作庇勃，假設(shè)一個(gè)任務(wù)延遲 500 秒執(zhí)行檬嘀，那么剛開始加進(jìn)來(lái)肯定是放在第三層的，當(dāng)時(shí)間過(guò)了 436 秒后责嚷，此時(shí)還需要 64 秒就會(huì)觸發(fā)任務(wù)的執(zhí)行鸳兽，而此時(shí)相對(duì)而言它就是個(gè)延遲 64 秒后的任務(wù)，因此它會(huì)被降低放在第二層中罕拂，第一層還放不下它揍异。

再過(guò)個(gè) 56 秒，相對(duì)而言它就是個(gè)延遲 8 秒后執(zhí)行的任務(wù)爆班，因此它會(huì)再被降級(jí)放在第一層中衷掷，等待執(zhí)行。

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

Netty中的時(shí)間輪

在 Netty 中時(shí)間輪的實(shí)現(xiàn)類是 HashedWheelTimer，代碼中的 wheel 就是上圖畫的循環(huán)數(shù)組枢舶，mask 的設(shè)計(jì)和HashMap一樣懦胞，通過(guò)限制數(shù)組的大小為2的次方，利用位運(yùn)算來(lái)替代取模運(yùn)算凉泄，提高性能躏尉。tickDuration 就是每格的時(shí)間即精度【衫В可以看到配備了一個(gè)工作線程來(lái)處理任務(wù)的執(zhí)行醇份。

接下來(lái)我們?cè)賮?lái)看看任務(wù)是如何添加的。

可以看到任務(wù)并沒(méi)有直接添加到時(shí)間輪中吼具，而是先入了一個(gè) mpsc 隊(duì)列僚纷，我簡(jiǎn)單說(shuō)下 mpsc 是 JCTools 中的并發(fā)隊(duì)列，用在多個(gè)生產(chǎn)者可同時(shí)訪問(wèn)隊(duì)列拗盒，但只有一個(gè)消費(fèi)者會(huì)訪問(wèn)隊(duì)列的情況怖竭。篇幅有限，有興趣的朋友自行了解實(shí)現(xiàn)陡蝇。

然后我們?cè)賮?lái)看看工作線程是如何運(yùn)作的痊臭。

很直觀沒(méi)什么花頭，我們先來(lái)看看 waitForNextTick登夫，是如何得到下一次執(zhí)行時(shí)間的广匙。

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

再來(lái)看下任務(wù)如何入槽的鸦致。

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

最后再來(lái)看下如何執(zhí)行的分唾。

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

小結(jié)一下

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

而且任務(wù)的執(zhí)行如果不是新起一個(gè)線程鞍爱，或者將任務(wù)扔到線程池執(zhí)行鹃觉，那么耗時(shí)的任務(wù)會(huì)阻塞下個(gè)任務(wù)的執(zhí)行。

并且會(huì)有很多無(wú)用的 tick 推進(jìn)睹逃，例如 TickDuration 為1秒盗扇，此時(shí)就一個(gè)延遲350秒的任務(wù)，那就是有349次無(wú)用的操作沉填。

但是從另一面來(lái)看疗隶，如果任務(wù)都執(zhí)行很快(當(dāng)然你也可以異步執(zhí)行)，并且任務(wù)數(shù)很多翼闹，通過(guò)分批執(zhí)行斑鼻，并且增刪任務(wù)的時(shí)間復(fù)雜度都是O(1)來(lái)說(shuō)。時(shí)間輪還是比通過(guò)優(yōu)先隊(duì)列實(shí)現(xiàn)的延時(shí)任務(wù)來(lái)的合適些猎荠。

Kafka 中的時(shí)間輪

上面我們說(shuō)到 Kafka 中的時(shí)間輪是多層次時(shí)間輪實(shí)現(xiàn)坚弱，總的而言實(shí)現(xiàn)和上述說(shuō)的思路一致。不過(guò)細(xì)節(jié)有些不同关摇，并且做了點(diǎn)優(yōu)化荒叶。

先看看添加任務(wù)的方法。在添加的時(shí)候就設(shè)置任務(wù)執(zhí)行的絕對(duì)時(shí)間输虱。

那么時(shí)間輪是如何推動(dòng)的呢些楣？Netty 中是通過(guò)固定的時(shí)間間隔掃描，時(shí)候未到就等待來(lái)進(jìn)行時(shí)間輪的推動(dòng)宪睹。上面我們分析到這樣會(huì)有空推進(jìn)的情況愁茁。

而 Kafka 就利用了空間換時(shí)間的思想，通過(guò) DelayQueue亭病，來(lái)保存每個(gè)槽鹅很，通過(guò)每個(gè)槽的過(guò)期時(shí)間排序。這樣擁有最早需要執(zhí)行任務(wù)的槽會(huì)有優(yōu)先獲取罪帖。如果時(shí)候未到促煮，那么 ?delayQueue.poll 就會(huì)阻塞著食听，這樣就不會(huì)有空推進(jìn)的情況發(fā)送。

我們來(lái)看下推進(jìn)的方法污茵。

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

小結(jié)一下

Kafka 用了多層次時(shí)間輪來(lái)實(shí)現(xiàn)泞当，并且是按需創(chuàng)建時(shí)間輪，采用任務(wù)的絕對(duì)時(shí)間來(lái)判斷延期民珍，并且對(duì)于每個(gè)槽(槽內(nèi)存放的也是任務(wù)的雙向鏈表)都會(huì)維護(hù)一個(gè)過(guò)期時(shí)間襟士，利用 DelayQueue 來(lái)對(duì)每個(gè)槽的過(guò)期時(shí)間排序，來(lái)進(jìn)行時(shí)間的推進(jìn)嚷量，防止空推進(jìn)的存在陋桂。

每次推進(jìn)都會(huì)更新 currentTime 為當(dāng)前時(shí)間戳，當(dāng)然做了點(diǎn)微調(diào)使得 currentTime 是 tickMs 的整數(shù)倍蝶溶。并且每次推進(jìn)都會(huì)把能降級(jí)的任務(wù)重新插入降級(jí)嗜历。

可以看到這里的 DelayQueue 的元素是每個(gè)槽，而不是任務(wù)抖所，因此數(shù)量就少很多了梨州，這應(yīng)該是權(quán)衡了對(duì)于槽操作的延時(shí)隊(duì)列的時(shí)間復(fù)雜度與空推進(jìn)的影響。

總結(jié)

首先介紹了 Timer田轧、DelayQueue 和 ScheduledThreadPool暴匠，它們都是基于優(yōu)先隊(duì)列實(shí)現(xiàn)的，O(logn) 的時(shí)間復(fù)雜度在任務(wù)數(shù)多的情況下頻繁的入隊(duì)出隊(duì)對(duì)性能來(lái)說(shuō)有損耗傻粘。因此適合于任務(wù)數(shù)不多的情況每窖。

Timer 是單線程的會(huì)有阻塞的風(fēng)險(xiǎn)，并且對(duì)異常沒(méi)有做處理弦悉，一個(gè)任務(wù)出錯(cuò) Timer 就掛了窒典。而 ScheduledThreadPool 相比于 Timer 首先可以多線程來(lái)執(zhí)行任務(wù)，并且線程池對(duì)異常做了處理警绩，使得任務(wù)之間不會(huì)有影響崇败。

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

對(duì)比而言時(shí)間輪更適合任務(wù)數(shù)很大的延時(shí)場(chǎng)景后室，它的任務(wù)插入和刪除時(shí)間復(fù)雜度都為O(1)。對(duì)于延遲超過(guò)時(shí)間輪所能表示的范圍有兩種處理方式混狠，一是通過(guò)增加一個(gè)字段-輪數(shù)岸霹，Netty 就是這樣實(shí)現(xiàn)的。二是多層次時(shí)間輪将饺，Kakfa 是這樣實(shí)現(xiàn)的贡避。

相比而言 Netty 的實(shí)現(xiàn)會(huì)有空推進(jìn)的問(wèn)題痛黎，而 Kafka 采用 DelayQueue 以槽為單位，利用空間換時(shí)間的思想解決了空推進(jìn)的問(wèn)題刮吧。

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