一、什么是時(shí)間輪

時(shí)間輪其實(shí)就是一種環(huán)形的數(shù)據(jù)結(jié)構(gòu)，可以想象成時(shí)鐘，分成很多格子，一個(gè)格子代表一段時(shí)間（這個(gè)時(shí)間越短，Timer的精度越高）。并用一個(gè)雙向鏈表存儲(chǔ)放在該格子上的延時(shí)任務(wù)，同時(shí)一個(gè)指針隨著時(shí)間一格一格轉(zhuǎn)動(dòng)，并執(zhí)行相應(yīng)格子中的到期任務(wù)。任務(wù)通過取模決定放入哪個(gè)格子。

二、時(shí)間輪結(jié)構(gòu)

tickMs：表示一個(gè)槽所代表的時(shí)間范圍，kafka的默認(rèn)值為1ms

wheelSize：表示該時(shí)間輪有多少個(gè)槽，kafka的默認(rèn)值是20

startMs：表示該時(shí)間輪的開始時(shí)間

interval：時(shí)間輪所能表示的時(shí)間跨度，也就是tickMs*wheelSize

currentTime：表示當(dāng)前時(shí)間，也就是時(shí)間輪指針指向的時(shí)間

buckets：表示TimerTaskList的數(shù)組，即各個(gè)槽，每個(gè)bucket都有一個(gè)TimerTaskList。

TimerTaskList：存儲(chǔ)TimerTaskEntry的雙向鏈表

TimerTaskEntry：延遲任務(wù)，有兩個(gè)值delayTime和expireTime

delayTime：TimerTask延遲時(shí)間

expireTime：TimerTask過期時(shí)間

queue：存儲(chǔ)TimerTaskList的延遲隊(duì)列，這些TimerTaskList都被加到這個(gè)延遲隊(duì)列中，expireTime最小的槽會(huì)排在隊(duì)列的最前面。

taskCounter：表示該時(shí)間輪的任務(wù)總數(shù)

三、運(yùn)行原理

當(dāng)定時(shí)器新增一個(gè)延遲任務(wù)時(shí)，通過buckets[expiration / tickMs % wheelSize]先計(jì)算出它應(yīng)該屬于哪個(gè)槽。比如延遲任務(wù)的delayMs=2ms，當(dāng)前時(shí)間currentTime是0ms，則expiration=delayMs+startMs=2ms，通過前面的公式算出它應(yīng)該落于2號(hào)槽。并把任務(wù)封裝成TimerTaskEntry然后加入到TimerTaskList鏈表中。

kafka會(huì)啟動(dòng)一個(gè)線程，通過定時(shí)器去推動(dòng)時(shí)間輪的指針轉(zhuǎn)動(dòng)。其實(shí)現(xiàn)原理其實(shí)就是通過queue.poll()取出放在最前面的槽的TimerTaskList。由于queue是一個(gè)延遲隊(duì)列，如果隊(duì)列中的expireTime沒有到達(dá)，該操作會(huì)阻塞住，直到expireTime到達(dá)。如果通過queue.poll()取到了TimerTaskList，說明該槽里面的任務(wù)時(shí)間都已經(jīng)到達(dá)。這時(shí)候就可以遍歷該TimerTaskList中的任務(wù)，然后執(zhí)行對(duì)應(yīng)的操作了。

定時(shí)器中只需持有TimingWheel的第一層時(shí)間輪的引用，并不會(huì)直接持有其他高層的時(shí)間輪，但是每一層時(shí)間輪都會(huì)有一個(gè)引用（overflowWheel）指向更高一層的應(yīng)用，以此層級(jí)調(diào)用而可以實(shí)現(xiàn)定時(shí)器間接持有各個(gè)層級(jí)時(shí)間輪的引用。

四、時(shí)間溢出處理

在kafka的默認(rèn)實(shí)現(xiàn)中，tickMs=1Ms，wheelSize=20，這就表示該時(shí)間輪所能表示的延遲時(shí)間范圍是0~20Ms，那如果延遲時(shí)間超過20Ms要如何處理呢？Kafka對(duì)時(shí)間輪做了一層改進(jìn)，使時(shí)間輪變成層級(jí)的時(shí)間輪。

一開始，第一層的時(shí)間輪所能表示時(shí)間范圍是0~20Ms之間，假設(shè)現(xiàn)在出現(xiàn)一個(gè)任務(wù)的延遲時(shí)間是200Ms，那么kafka會(huì)再創(chuàng)建一層時(shí)間輪，我們稱之為第二層時(shí)間輪。

也就是第二層時(shí)間輪每一個(gè)槽所能表示的時(shí)間是第一層時(shí)間輪所能表示的時(shí)間范圍，也就是20Ms。槽的數(shù)量還是一樣，其他的屬性也是繼承自第一層時(shí)間輪。這時(shí)第二層時(shí)間輪所能表示的時(shí)間范圍就是0~400Ms了

同理，如果第二層時(shí)間輪的時(shí)間范圍還容納不了新的延遲任務(wù)，就會(huì)創(chuàng)建第三層、第四層...

五、時(shí)間輪用來解決什么問題

如果一個(gè)系統(tǒng)中存在著大量的調(diào)度任務(wù)，而大量的調(diào)度任務(wù)如果每一個(gè)都使用自己的調(diào)度器來管理任務(wù)的生命周期的話，浪費(fèi)cpu的資源并且很低效。

時(shí)間輪是一種高效來利用線程資源來進(jìn)行批量化調(diào)度的一種調(diào)度模型。把大批量的調(diào)度任務(wù)全部都綁定到同一個(gè)調(diào)度器上面，使用這一個(gè)調(diào)度器來進(jìn)行所有任務(wù)的管理（manager），觸發(fā)（trigger）以及運(yùn)行（runnable）。能夠高效的管理各種延時(shí)任務(wù)，周期任務(wù)，通知任務(wù)等等。

執(zhí)行過程

1、時(shí)間輪

Kafka中一個(gè)時(shí)間輪TimingWheel是由20個(gè)時(shí)間格組成，wheelSize = 20；每格的時(shí)間跨度是1ms，tickMs = 1ms。參照Kafka，圖中也用了20個(gè)灰邊小圓表示時(shí)間格，為了動(dòng)畫演示可以看得清楚，我們這里每個(gè)小圓的時(shí)間跨度是1s。

整個(gè)時(shí)間輪的時(shí)間跨度就是 tickMs * wheelSize ，也就是 20s。從0s到19s，我們都分別有一個(gè)灰邊小圓來承載。

Kafka的時(shí)間輪還有一個(gè)表盤指針 currentTime，表示時(shí)間輪當(dāng)前所處的時(shí)間。也就是圖中用黑色粗線表示的圓，隨著時(shí)間推移, 這個(gè)指針也會(huì)不斷前進(jìn);

添加定時(shí)任務(wù)

每一個(gè)定時(shí)任務(wù)都有延時(shí)時(shí)間delayTime，和過期時(shí)間ExpiredTime。比如當(dāng)前時(shí)間是0s，我們添加了個(gè)延時(shí)時(shí)間為2s的任務(wù)，那么這個(gè)任務(wù)的過期時(shí)間就是2s，也就是當(dāng)前時(shí)間0s再走兩秒，變成了2s的時(shí)候，就到了觸發(fā)這個(gè)定時(shí)任務(wù)的時(shí)間。

初始的時(shí)候, 時(shí)間輪的指針定格在0。此時(shí)添加一個(gè)超時(shí)時(shí)間為2s的任務(wù), 那么這個(gè)任務(wù)將會(huì)插入到第二個(gè)時(shí)間格中。

如果這個(gè)時(shí)候又插入一個(gè)延時(shí)時(shí)間為8s的任務(wù)進(jìn)來, 這個(gè)任務(wù)的過期時(shí)間就是在當(dāng)前時(shí)間2s的基礎(chǔ)上加8s, 也就是10s, 那么這個(gè)任務(wù)將會(huì)插入到過期時(shí)間為10s的時(shí)間格中。

2、"動(dòng)態(tài)"時(shí)間輪

那么如果在當(dāng)前時(shí)間是2s的時(shí)候, 插入一個(gè)延時(shí)時(shí)間為19s的任務(wù)時(shí),這個(gè)任務(wù)的過期時(shí)間就是在當(dāng)前時(shí)間2s的基礎(chǔ)上加19s, 也就是21s。

當(dāng)前的時(shí)間輪是沒有過期時(shí)間為21s的時(shí)間格。這個(gè)任務(wù)將會(huì)插入到過期時(shí)間為1s的時(shí)間格中

復(fù)用時(shí)間格

其實(shí)呢，當(dāng)指針定格在2s的位置時(shí), 時(shí)間格0s, 1s和2s就已經(jīng)是過期的時(shí)間格。也就是說指針可以用來劃分過期的時(shí)間格[0,2]和未來的時(shí)間格 [3,19]。而過期的時(shí)間格可以繼續(xù)復(fù)用。比如過期的時(shí)間格0s就變成了20s, 存放過期時(shí)間為20s的任務(wù)。理解了時(shí)間格的復(fù)用之后，再看回剛剛的例子，當(dāng)前時(shí)間是2s時(shí)，添加延時(shí)時(shí)間為19s的任務(wù)，那么這個(gè)任務(wù)就會(huì)插入到過期時(shí)間為21s的時(shí)間格中。

3、時(shí)間輪升級(jí)

如果在當(dāng)前時(shí)間是2s的時(shí)候, 插入一個(gè)延時(shí)時(shí)間為22s的任務(wù), 這個(gè)任務(wù)的過期時(shí)間就是在2s的基礎(chǔ)上加22s，也就是24s。

顯然當(dāng)前時(shí)間輪是無法找到過期時(shí)間格為24秒的時(shí)間格，因?yàn)楫?dāng)前過期時(shí)間最大的時(shí)間格才到21s。而且我們也沒辦法像前面那樣再復(fù)用時(shí)間格，因?yàn)槌诉^期時(shí)間為2s的時(shí)間格，其他的時(shí)間格都還沒過期呢。當(dāng)前時(shí)間輪無法承載這個(gè)定時(shí)任務(wù),那么應(yīng)該怎么辦呢?

當(dāng)然我們可以選擇擴(kuò)展時(shí)間輪上的時(shí)間格, 但是這樣一來，時(shí)間輪就失去了意義。

4、層級(jí)時(shí)間輪

如圖是一個(gè)兩層的時(shí)間輪:

第二層時(shí)間輪也是由20個(gè)時(shí)間格組成, 每個(gè)時(shí)間格的跨度是20s。

圖中展示了每個(gè)時(shí)間格對(duì)應(yīng)的過期時(shí)間范圍, 我們可以清晰地看到, 第二層時(shí)間輪的第0個(gè)時(shí)間格的過期時(shí)間范圍是 [0,19]。也就是說, 第二層時(shí)間輪的一個(gè)時(shí)間格就可以表示第一層時(shí)間輪的所有(20個(gè))時(shí)間格;

添加定時(shí)任務(wù)

在當(dāng)前時(shí)間是2s的時(shí)候, 插入一個(gè)延時(shí)時(shí)間為22s的任務(wù)，該任務(wù)過期時(shí)間為24s。

當(dāng)?shù)谝粚訒r(shí)間輪容納不下時(shí)，進(jìn)入第二層時(shí)間輪，并插入到過期時(shí)間為[20,39]的時(shí)間格中。

如果在當(dāng)前時(shí)間是2s的時(shí)候, 插入一個(gè)延時(shí)時(shí)間為350s的任務(wù), 這個(gè)任務(wù)的過期時(shí)間就是在2s的基礎(chǔ)上加350s，也就是352s。

從圖中可以看到，該任務(wù)插入到第二層時(shí)間輪過期時(shí)間為[340,359]s的時(shí)間格中，也就是第17格的位置。

5、"動(dòng)態(tài)"層級(jí)時(shí)間輪

從圖中可以看到，當(dāng)?shù)谝粚訒r(shí)間輪的指針定格在1s時(shí)，超時(shí)時(shí)間0s的時(shí)間格就過期了。而這個(gè)時(shí)候，第二層時(shí)間輪第0個(gè)時(shí)間格的時(shí)間范圍就從[0,19]分為了過期的[0],和未過期的[1,19]。而過期的[0]就會(huì)被新的過期時(shí)間[400]復(fù)用。

第二層時(shí)間輪第0個(gè)時(shí)間格的過期時(shí)間范圍演變?nèi)缦?#xff1a;

[0-19]

[400][1,19]

[400,401][2,19]

......

[400,419]

所以，如果在當(dāng)前時(shí)間是2s的時(shí)候, 插入一個(gè)延時(shí)時(shí)間為399s的任務(wù), 這個(gè)任務(wù)的過期時(shí)間就是在2s的基礎(chǔ)上加399s，也就是401s。如圖，這個(gè)任務(wù)還是會(huì)插到第二層時(shí)間輪第0個(gè)時(shí)間格中去。

6、時(shí)間輪降級(jí)

在當(dāng)前時(shí)間是2s的時(shí)候, 插入一個(gè)延時(shí)時(shí)間為22s的任務(wù)，該任務(wù)過期時(shí)間為24s。最后進(jìn)入第二層時(shí)間輪，并插入到過期時(shí)間為[20,39]的時(shí)間格中。

當(dāng)指針走到20s的時(shí)候，原本超時(shí)時(shí)間為24s的任務(wù)會(huì)被取出來，重新加入時(shí)間輪。此時(shí)該定時(shí)任務(wù)的延時(shí)時(shí)間從原本的22s，到現(xiàn)在還剩下4s（22s-18s）。最后停留在第一層時(shí)間輪超時(shí)時(shí)間為24s的時(shí)間格，也就是第4個(gè)時(shí)間格。

從這里可以看出時(shí)間輪的巧妙之處，兩層時(shí)間輪只用了40個(gè)數(shù)組元素，卻可以承載[0-399s]的定時(shí)任務(wù)。而三層時(shí)間輪用60個(gè)數(shù)組元素，就可以承載[0-7999s]的定時(shí)任務(wù)！

總結(jié)

以上是生活随笔為你收集整理的时间轮(TimingWheel)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。