定時器實現(xiàn)原理——時間輪

時間輪

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

簡單時間輪

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

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

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

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

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

round時間輪算法

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

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

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

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

分層時間輪

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

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

假設我們有2個任務是每天的100執(zhí)行一次，任務首先添加到時輪第1刻度上，當時輪到達第1刻度時，任務轉移到分輪上的第0刻度，當分輪達到第0刻度，任務轉移到秒輪，當秒輪達到第0刻度，任務一次執(zhí)行。

優(yōu)點：

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

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

分層時間輪的任務從一個時間輪轉移到另一個時間輪，有點像水表中小單位的表轉一圈進位到大單位一樣（但是分層時間輪是從大到小，因為從小到大的話，小單位的表輪詢判斷次數(shù)過多）

應用：

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

審核編輯 ：李倩