時間輪

時間輪算法是通過一個時間輪去維護(hù)定時任務(wù)，按照一定的時間單位對時間輪進(jìn)行劃分刻度。然后根據(jù)任務(wù)延時計算任務(wù)落在該時間輪的第幾個刻度上，如果任務(wù)時長超出了刻度數(shù)量，則需要增加一個參數(shù)記錄時間輪需要轉(zhuǎn)動的圈數(shù)。

簡單時間輪

時間輪類似于我們的鐘表，當(dāng)指針指到刻度上，我們就去執(zhí)行對應(yīng)的任務(wù)列表。例如，我們需要統(tǒng)計每個小時的登錄用戶數(shù)。

時間輪算法中，輪詢線程遍歷到某一個時間刻度后，總是執(zhí)行對應(yīng)刻度上任務(wù)隊列中的所有任務(wù)（通常是將任務(wù)扔給異步線程池來處理），而不再需要遍歷檢查所有任務(wù)的時間戳是否達(dá)到要求（不用每次從小頂堆堆頂，取數(shù)據(jù)來和時間比較，然后堆化這些操作）。

現(xiàn)在我們即使有n個任務(wù)，輪詢線程也沒有必要，每輪遍歷n次，我們只需要按照時間刻度來輪訓(xùn)即可。

不過，小時作為時間單位粒度太大，我們有時候往往會希望基于分鐘、秒等作為時間刻度。最直接的方式是增加時間刻度，通過增加時間刻度，我們可以基于更精細(xì)的時間單位（分鐘）來進(jìn)行定時任務(wù)的執(zhí)行。但是，這種實(shí)現(xiàn)方式有如下的缺陷：

當(dāng)我們刻度增多時，而任務(wù)相對較少，效率就會下降，假如我們只有以秒為刻度，一天 24 * 60 * 60 = 86400秒，我們可能只占用幾十或幾百個刻度，大部分時間刻度所占用的內(nèi)存空間是沒有任何意義的。

round時間輪算法

我們發(fā)現(xiàn)，時間輪的時間刻度隨著時間精度而增加并不是一個好的問題解決思路?，F(xiàn)在，我們將時間輪的精度設(shè)置為秒，時間刻度個數(shù)固定為 60。每一個任務(wù)擁有一個 round 字段。

輪詢線程的執(zhí)行邏輯是：每隔一秒處理一個時間刻度上任務(wù)隊列中的所有任務(wù)，任務(wù)的 round 字段減 1，接著判斷如果 round 字段的值變?yōu)?0，那么將任務(wù)移出任務(wù)隊列，交給異步線程池來執(zhí)行對應(yīng)任務(wù)。如果是重復(fù)執(zhí)行任務(wù)，那么再將任務(wù)添加到任務(wù)隊列中。

輪詢線程遍歷一次時間輪需要 60 秒。如果一個任務(wù)需要間隔 x 秒執(zhí)行一次，那么其 round 字段的值為 x/60（整除），任務(wù)位于第 (x%60)（取余）個刻度對應(yīng)的任務(wù)隊列中。例如任務(wù)需要間隔 130 秒執(zhí)行一次，那么 round 字段的值為 2，此任務(wù)位于第 10 號時間刻度的任務(wù)隊列中。

這種方式雖然簡化了時間輪的刻度個數(shù)，但是并沒有減少輪詢次數(shù)，效率還是相對較低。時間輪每次處理一個時間刻度，就需要處理其上任務(wù)隊列的所有任務(wù)。其運(yùn)行效率甚至與基于普通任務(wù)隊列實(shí)現(xiàn)的定時任務(wù)框架沒有區(qū)別。

分層時間輪

分層的時間輪算法在生活中有對應(yīng)的模型，那就是水表：

我們可以將一天類似水表一樣，分為多個輪，時、分和秒三個級別的時間輪，每一個輪的刻度分別為24、60、60個刻度。分層時間輪如下：

假設(shè)我們有2個任務(wù)是每天的100執(zhí)行一次，任務(wù)首先添加到時輪第1刻度上，當(dāng)時輪到達(dá)第1刻度時，任務(wù)轉(zhuǎn)移到分輪上的第0刻度，當(dāng)分輪達(dá)到第0刻度，任務(wù)轉(zhuǎn)移到秒輪，當(dāng)秒輪達(dá)到第0刻度，任務(wù)一次執(zhí)行。

優(yōu)點(diǎn)：

輪詢效率變高：不需要計算round值，其次任務(wù)隊列中的任務(wù)一旦被遍歷，就是需要被處理的（沒有空輪詢問題）；

線程并發(fā)好：雖然引入了并發(fā)線程，但是線程數(shù)僅僅和時鐘輪的級數(shù)有關(guān)，并不會隨著任務(wù)的增長而變多

分層時間輪的任務(wù)從一個時間輪轉(zhuǎn)移到另一個時間輪，有點(diǎn)像水表中小單位的表轉(zhuǎn)一圈進(jìn)位到大單位一樣（但是分層時間輪是從大到小，因?yàn)閺男〉酱蟮脑?，小單位的表輪詢判斷次?shù)過多）

應(yīng)用：

時間輪的使用在各大框架與中間件中有使用，xxl-job，netty都對時間輪都自己的實(shí)現(xiàn)。思路基本上與分層的時間輪策略一致。

審核編輯 ：李倩