簡(jiǎn)單時(shí)間輪算法詳解

時(shí)間輪

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

簡(jiǎn)單時(shí)間輪

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

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

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

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

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

round時(shí)間輪算法

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

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

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

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

分層時(shí)間輪

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

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

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

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

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

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

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

應(yīng)用：

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

審核編輯：湯梓紅