時間輪

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

簡單時間輪

時間輪類似於我們的鐘表，當指針指到刻度上，我們就去執行對應的任務列表。例如，我們需要統計每個小時的登錄用戶數。

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

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

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

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

round 時間輪算法

我們發現，時間輪的時間刻度隨着時間精度而增加並不是一個好的問題解決思路。現在，我們將時間輪的精度設置爲秒，時間刻度個數固定爲 60。每一個任務擁有一個 round 字段。

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

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

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

分層時間輪

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

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

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

優點：

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

• 線程併發好：雖然引入了併發線程，但是線程數僅僅和時鐘輪的級數有關，並不會隨着任務的增長而變多

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

應用：

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/g-CV7fD4EvGpePXd7SL3Ag