通過本文你將了解到時間輪算法思想申眼，層級時間輪，時間輪的升級和降級蝉衣。
時間輪括尸，是一種實現(xiàn)延遲功能（定時器）的巧妙算法，在Netty病毡，Zookeeper濒翻，Kafka等各種框架中，甚至Linux內(nèi)核中都有用到剪验。
本文將參考Kafka的時間輪作為例子講解肴焊。
0 設(shè)計源于生活
開始之前給大家看塊寶珀中華年歷表。
這款手表的表盤融合了中華歷法中各種博大精深的計時元素功戚。
上方位置的小表盤顯示時辰數(shù)字及字符,24小時一周期;年份視窗顯示當(dāng)年所屬生肖,12年一周期;
左邊位置顯示農(nóng)歷月,12個月一周期; 農(nóng)歷日, 30天一周期;
右邊位置顯示五行元素和十天干,10年一周期;
下方的表盤顯示月相盈虧娶眷。
至于價格.....這個話題略過。
而時間輪啸臀，其設(shè)計正是來源于生活中的時鐘届宠。
1 時間輪
如圖就是一個簡單的時間輪：
圖中大圓的圓心位置表示的是當(dāng)前的時間，隨著時間推移, 圓心處的時間也會不斷跳動乘粒。
下面我們對著這個圖豌注，來說說Kafka的時間輪TimingWheel。
Kafka時間輪的底層就是一個環(huán)形數(shù)組灯萍，而數(shù)組中每個元素都存放一個雙向鏈表TimerTaskList轧铁，鏈表中封裝了很多延時任務(wù)。
Kafka中一個時間輪TimingWheel是由20個時間格組成旦棉，wheelSize = 20齿风；每格的時間跨度是1ms，tickMs = 1ms绑洛。參照Kafka救斑，上圖中也用了20個灰邊小圓表示時間格，為了動畫演示可以看得清楚真屯，我們這里每個小圓的時間跨度是1s脸候。
所以現(xiàn)在整個時間輪的時間跨度就是 tickMs * wheelSize ，也就是 20s。從0s到19s运沦，我們都分別有一個灰邊小圓來承載泵额。
Kafka的時間輪還有一個表盤指針 currentTime，表示時間輪當(dāng)前所處的時間携添。也就是圖中用黑色粗線表示的圓梯刚，隨著時間推移, 這個指針也會不斷前進;
添加定時任務(wù)
有了時間輪，現(xiàn)在可以往里面添加定時任務(wù)了薪寓。我們用一個粉紅色的小圓來表示一個定時任務(wù)。
這里先講一下設(shè)定澜共，每一個定時任務(wù)都有延時時間delayTime向叉，和過期時間ExpiredTime。
比如當(dāng)前時間是10s嗦董，我們添加了個延時時間為2s的任務(wù)母谎，那么這個任務(wù)的過期時間就是12s，也就是當(dāng)前時間10s再走兩秒京革，變成了12s的時候奇唤，就到了觸發(fā)這個定時任務(wù)的時間。
而時間輪上代表時間格的灰邊小圓上顯示的數(shù)字匹摇，可以理解為任務(wù)的過期時間咬扇。
講清楚這些設(shè)定后，我們就開始添加定時任務(wù)吧廊勃。
初始的時候, 時間輪的指針定格在0懈贺。此時添加一個超時時間為2s的任務(wù), 那么這個任務(wù)將會插入到第二個時間格中。
當(dāng)時間輪的指針到達第二個時間格時, 會處理該時間格上對應(yīng)的任務(wù)坡垫。在動畫上就是讓紅色的小圓消失!
如果這個時候又插入一個延時時間為8s的任務(wù)進來, 這個任務(wù)的過期時間就是在當(dāng)前時間2s的基礎(chǔ)上加8s, 也就是10s, 那么這個任務(wù)將會插入到過期時間為10s的時間格中梭灿。
2 "動態(tài)"時間輪
到目前為止，一切都很好理解冰悠。
那么如果在當(dāng)前時間是2s的時候, 插入一個延時時間為19s的任務(wù)時, 這個任務(wù)的過期時間就是在當(dāng)前時間2s的基礎(chǔ)上加19s, 也就是21s堡妒。
請看下圖，當(dāng)前的時間輪是沒有過期時間為21s的時間格溉卓。這個任務(wù)將會插入到過期時間為1s的時間格中皮迟，這是怎么回事呢？
復(fù)用時間格
為了解答上面的問題的诵，我們先來點魔法万栅， 讓時間輪上的時間都動起來！
其實呢西疤，當(dāng)指針定格在2s的位置時, 時間格0s, 1s和2s就已經(jīng)是過期的時間格烦粒。
也就是說指針可以用來劃分過期的時間格[0,2]和未來的時間格 [3,19]。而過期的時間格可以繼續(xù)復(fù)用。比如過期的時間格0s就變成了20s, 存放過期時間為20s的任務(wù)扰她。
理解了時間格的復(fù)用之后兽掰，再看回剛剛的例子，當(dāng)前時間是2s時徒役，添加延時時間為19s的任務(wù)孽尽，那么這個任務(wù)就會插入到過期時間為21s的時間格中。
3 時間輪升級
下面忧勿，新的問題來了杉女，請坐好扶穩(wěn)。
如果在當(dāng)前時間是2s的時候, 插入一個延時時間為22s的任務(wù), 這個任務(wù)的過期時間就是在2s的基礎(chǔ)上加22s鸳吸，也就是24s熏挎。
顯然當(dāng)前時間輪是無法找到過期時間格為24秒的時間格，因為當(dāng)前過期時間最大的時間格才到21s晌砾。而且我們也沒辦法像前面那樣再復(fù)用時間格坎拐，因為除了過期時間為2s的時間格，其他的時間格都還沒過期呢养匈。當(dāng)前時間輪無法承載這個定時任務(wù), 那么應(yīng)該怎么辦呢?
當(dāng)然我們可以選擇擴展時間輪上的時間格, 但是這樣一來哼勇，時間輪就失去了意義。
是時候要升級時間輪了呕乎！
我們先來理解下多層時間輪之間的聯(lián)系积担。
4 層級時間輪
如圖是一個兩層的時間輪:
第二層時間輪也是由20個時間格組成, 每個時間格的跨度是20s。
圖中展示了每個時間格對應(yīng)的過期時間范圍, 我們可以清晰地看到, 第二層時間輪的第0個時間格的過期時間范圍是 [0,19]猬仁。也就是說, 第二層時間輪的一個時間格就可以表示第一層時間輪的所有(20個)時間格;
為了進一步理清第一層時間輪和第二層時間輪的關(guān)系, 我們拉著時間的小手, 一起觀看下面的動圖:
可以看到磅轻，第二層時間輪同樣也有自己的指針, 每當(dāng)?shù)谝粚訒r間輪走完一個周期，第二層時間輪的指針就會推進一格逐虚。
添加定時任務(wù)
回到一開始的問題聋溜，在當(dāng)前時間是2s的時候, 插入一個延時時間為22s的任務(wù)，該任務(wù)過期時間為24s叭爱。
當(dāng)?shù)谝粚訒r間輪容納不下時撮躁，進入第二層時間輪，并插入到過期時間為[20,39]的時間格中买雾。
我們再來個例子把曼，如果在當(dāng)前時間是2s的時候, 插入一個延時時間為350s的任務(wù), 這個任務(wù)的過期時間就是在2s的基礎(chǔ)上加350s，也就是352s漓穿。
從圖中可以看到嗤军，該任務(wù)插入到第二層時間輪過期時間為[340,359]s的時間格中，也就是第17格的位置晃危。
5 "動態(tài)"層級時間輪
通常來說, 第二層時間輪的第0個時間格是用來表示第一層時間輪的, 這一格是存放不了任務(wù)的, 因為超時時間0-20s的任務(wù), 第一層時間輪就可以處理了叙赚。
但是! 事情往往沒這么簡單, 我們時間輪上的時間格都是可以復(fù)用的! 那么這在第二層時間輪上又是怎么體現(xiàn)的呢?
下面是魔法時間老客， 我們讓時間輪上的過期時間都動起來！
從圖中可以看到震叮，當(dāng)?shù)谝粚訒r間輪的指針定格在1s時胧砰，超時時間0s的時間格就過期了。而這個時候苇瓣，第二層時間輪第0個時間格的時間范圍就從[0,19]分為了過期的[0],和未過期的[1,19]尉间。而過期的[0]就會被新的過期時間[400]復(fù)用。
第二層時間輪第0個時間格的過期時間范圍演變?nèi)缦拢?/p>
[0-19]
[400][1,19]
[400,401][2,19]
......
[400,419]
所以击罪，如果在當(dāng)前時間是2s的時候, 插入一個延時時間為399s的任務(wù), 這個任務(wù)的過期時間就是在2s的基礎(chǔ)上加399s哲嘲，也就是401s。如圖媳禁，這個任務(wù)還是會插到第二層時間輪第0個時間格中去撤蚊。
6 時間輪降級
還是用回這個大家都已經(jīng)耳熟能詳?shù)睦樱诋?dāng)前時間是2s的時候, 插入一個延時時間為22s的任務(wù)损话，該任務(wù)過期時間為24s。最后進入第二層時間輪槽唾，并插入到過期時間為[20,39]的時間格中丧枪。
當(dāng)二層時間輪上的定時任務(wù)到期后，時間輪是怎么做的呢庞萍？
從圖中可以看到拧烦，隨著當(dāng)前時間從2s繼續(xù)往前推進，一直到20s的時候钝计，總共經(jīng)過了18s恋博。此時第二層時間輪中，超時時間為[20-39s]的時間格上的任務(wù)到期私恬。
原本超時時間為24s的任務(wù)會被取出來债沮，重新加入時間輪。此時該定時任務(wù)的延時時間從原本的22s本鸣，到現(xiàn)在還剩下4s（22s-18s）疫衩。最后停留在第一層時間輪超時時間為24s的時間格，也就是第4個時間格荣德。
隨著當(dāng)前時間繼續(xù)推進闷煤，再經(jīng)過4s后，該定時任務(wù)到期被執(zhí)行涮瞻。
從這里可以看出時間輪的巧妙之處鲤拿，兩層時間輪只用了40個數(shù)組元素，卻可以承載[0-399s]的定時任務(wù)署咽。而三層時間輪用60個數(shù)組元素近顷，就可以承載[0-7999s]的定時任務(wù)！
7 時間輪的推進
從動畫中可以注意到, 隨著時間推進, 時間輪的指針循環(huán)往復(fù)地定格在每一個時間格上, 每一次都要判斷當(dāng)前定格的時間格里是不是有任務(wù)存在;
其中有很多時間格都是沒有任務(wù)的, 指針定格在這種空的時間格中, 就是一次"空推進";
比如說, 插入一個延時時間400s的任務(wù), 指針就要執(zhí)行399次"空推進", 這是一種浪費!
那么Kafka是怎么解決這個問題的呢？這就要從延遲隊列DelayQueue開始講起了幕庐！
時間輪搭配延遲隊列DelayQueue久锥，會發(fā)生什么化學(xué)反應(yīng)呢？請關(guān)注公眾號【字節(jié)武裝】后續(xù)更新异剥。
