柚子快報邀請碼778899分享：時間輪算法理解、Kafka實現(xiàn)

http://yzkb.51969.com/

概述

TimingWheel，時間輪，簡單理解就是一種用來存儲若干個定時任務(wù)的環(huán)狀隊列（或數(shù)組），工作原理和鐘表的表盤類似。

關(guān)于環(huán)形隊列，請參考環(huán)形隊列。

時間輪由兩個部分組成，一個環(huán)狀數(shù)組，一個遍歷環(huán)狀數(shù)組的指針。

首先定義一個固定長度的環(huán)狀數(shù)組，隊列中的每一個元素代表一個時間格（可以精確到秒或毫秒。實際場景里，如Java或Linux下的cron定時任務(wù)，都是某一秒來觸發(fā)。在實時處理領(lǐng)域，則一般用毫秒），一個時間格可存放若干個定時任務(wù)（真實業(yè)務(wù)開發(fā)場景下，同時觸發(fā)多個任務(wù)），即任務(wù)列表。任務(wù)列表是一個環(huán)形的雙向鏈表，鏈表中的每一項表示的都是定時任務(wù)項，其中封裝真正的定時任務(wù)。 時間格代表時間輪的基本時間跨度或精度，假如一秒走一個時間格的話，則這個時間輪的精度就是1秒。當(dāng)指針指向某個數(shù)組時，就會把這個數(shù)組中存儲的任務(wù)取出來，然后遍歷鏈表逐個運(yùn)行里面的任務(wù)。

下圖是一個有12個時間格的時間輪，轉(zhuǎn)完一圈需要12s。當(dāng)需要新建一個3s后執(zhí)行的定時任務(wù)，只需要將定時任務(wù)放在下標(biāo)為3的時間格中即可。 當(dāng)需要創(chuàng)建一個15s后執(zhí)行的定時任務(wù)怎么辦呢？

此時可考慮引入圈數(shù)（也叫輪數(shù)）這一概念，即這個任務(wù)還是放在下標(biāo)為3的時間格中，圈數(shù)為2。除增加圈數(shù)這種方法之外，還有種多層次時間輪，Kafka采用的就是這種方案。

時間輪的好處：

減少定時任務(wù)添加和刪除的時間復(fù)雜度，提升性能；可保證每次執(zhí)行定時器任務(wù)都是O(1)復(fù)雜度，在定時器任務(wù)密集的情況下，性能優(yōu)勢非常明顯

實現(xiàn)

在很多開源組件里可看到時間輪算法的實現(xiàn)：Kafka、Netty、Dubbo、Caffeine。

值得一提的是，網(wǎng)絡(luò)上好多文章說ZooKeeper里也有時間輪算法的實現(xiàn)，并沒有。

Kafka

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

Kafka沒有使用JDK自帶的Timer和DelayQueue實現(xiàn)。底層都是個優(yōu)先隊列，即采用minHeap的數(shù)據(jù)結(jié)構(gòu)，最快需要執(zhí)行的任務(wù)排在隊列第一個，不同的是Timer中有個線程去拉取任務(wù)執(zhí)行，DelayQueue是個容器，需要配合其他線程工作。時間復(fù)雜度上這兩者插入和刪除操作都是O(logn)，不滿足性能要求。

ScheduledThreadPoolExecutor是JDK提供定時線程池，也是DelayQueue + 池化線程的一個實現(xiàn)。

Kafka基于時間輪實現(xiàn)延時操作，時間輪算法的插入刪除操作的時間復(fù)雜度都是O(1)，滿足性能要求。

源碼類為org.apache.kafka.server.util.timer.TimingWheel：

public class TimingWheel {

private final long tickMs;

private final long startMs;

private final int wheelSize;

private final AtomicInteger taskCounter;

private final DelayQueue queue;

private final long interval;

private final TimerTaskList[] buckets;

private long currentTimeMs;

private volatile TimingWheel overflowWheel = null;

}

幾個核心參數(shù)：

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

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

Kafka采用多層次時間輪來支持大跨度的定時任務(wù)，參考手表。 上圖時間輪，第1層的時間精度為1，第2層的時間精度為20，第3層的時間精度為400。假如需要添加一個350s后執(zhí)行的任務(wù)A的話（當(dāng)前時間是0s），這個任務(wù)會被放在第2層（第二層的時間跨度為20*20=400>350）的第350/20=17個時間格子。

當(dāng)?shù)谝粚愚D(zhuǎn)17圈之后，時間過去340s，第2層的指針此時來到第17個時間格子。此時第2層第17個格子的任務(wù)會被移動到第1層。任務(wù)A當(dāng)前是10s之后執(zhí)行，因此它會被移動到第1層的第10個時間格子。

在層與層之間的移動，叫做時間輪的升降級。時間輪比較適合任務(wù)數(shù)量比較多的定時任務(wù)場景，它的任務(wù)寫入和執(zhí)行的時間復(fù)雜度都是O(1)。

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

在Kafka中時間輪之間如何關(guān)聯(lián)呢，如何展現(xiàn)這種高一層的時間輪關(guān)系？ 一個內(nèi)部對象的指針，指向自己高一層的時間輪對象。

如何推進(jìn)時間輪的前進(jìn)，讓時間輪的時間往前走？ 通過DelayQueue來推進(jìn)，是一種空間換時間的思想；DelayQueue中保存著所有的TimerTaskList對象，根據(jù)時間來排序，這樣延時越小的任務(wù)排在越前面。外部通過一個ExpiredOperationReaper線程從DelayQueue中獲取超時的任務(wù)列表TimerTaskList，然后根據(jù)TimerTaskList的過期時間來精確推進(jìn)時間輪的時間，這樣就不會存在空推進(jìn)的問題。

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

總結(jié)

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

Netty

io.netty.util.HashedWheelTimer

Netty中的時間輪是通過工作線程按照固定的時間間隔tickDuration推進(jìn)的，如果長時間沒有到期任務(wù)，這種方案會帶來空推進(jìn)的問題，造成一定性能損耗；

Dubbo

org.apache.dubbo.common.timer.HashedWheelTimer，和Netty的源碼實現(xiàn)幾乎一樣。

Caffeine

com.github.benmanes.caffeine.cache.TimerWheel

內(nèi)部類Sentinel代表當(dāng)前任務(wù)，兩個內(nèi)部類AscendingIterator和DescendingIterator分別表示從時間輪取任務(wù)的兩個方式，

參考

Kafka時間輪算法設(shè)計HashedWheelTimer使用及源碼分析一個開源的時間輪算法介紹

柚子快報邀請碼778899分享：時間輪算法理解、Kafka實現(xiàn)

http://yzkb.51969.com/

好文鏈接