1、背景

時間輪算法可以用于高效的執行大量的定時任務。

在Netty中的一個典型應用場景是判斷某個連接是否idle，如果idle（如客戶端由于網絡原因導致到服務器的心跳無法送達），則服務器會主動斷開連接，釋放資源。得益于Netty NIO的優異性能，基于Netty開發的服務器可以維持大量的長連接，單臺8核16G的云主機可以同時維持幾十萬長連接，及時掐掉不活躍的連接就顯得尤其重要。

2、算法簡介

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

網上盜個圖，時間輪算法可以通過上圖來描述。假設時間輪大小為8，1s轉一格，每格指向一個鏈表，保存著待執行的任務。

假設，當前位于2，現在要添加一個3s后指向的任務，則2+3=5，在第5格的鏈表中添加一個節點指向任務即可，標識round=0。

假設，當前位于2，現在要添加一個10s后指向的任務，則（2+10）% 8 = 4，則在第4格添加一個節點指向任務，并標識round=1，則當時間輪第二次經過第4格時，即會執行任務。

時間輪只會執行round=0的任務，并會把該格子上的其他任務的round減1。

算法的原理非常淺顯易懂，但是閱讀源碼實現還是有益的。

3、源碼解析

1、構造方法

參數：

1）threadFactory

用于生成工作線程

2）tickDuration和unit

每格的時間間隔，默認100ms

3）ticksPerWheel

一圈下來有幾格，默認512，特別的，如果傳入的不是2的N次方，則會調整為大于等于該參數的第一個2的N次方，好處是可以優化hash值的計算

4）leakDetection

如果false，那么只有工作線程不是后臺線程時才會追蹤資源泄露，這個參數可以忽略

5）maxPendingTimeouts

最大的pending數量，默認-1，表示不限制

注：可以看到構造方法執行結束時，工作線程并沒有啟動，那么應該是在第一次添加任務的時候啟動的，我們繼續看添加任務的newTimeout方法

2、newTimeout

首先，通過一個原子變量來計數當前的任務數，如果設置最大pending且超過了，則會直接throw Exception

其次，便是調用start方法來正式啟用worker線程，為了防止重復調用，使用了一個原子操作，并且調用完畢之后會CountDownLatch.await阻塞住，直到線程完全起來才返回

?

可以看到，方法是public的，也即用戶可以顯示的調用，而無需等待第一次添加任務時再啟動

最后，便是包裝一個HashedWheelTimeout對象（計算出了deadline），丟給隊列，等待工作線程處理，那么接下來的重點就是看worker線程的實現了

?

3、Worker線程

工作線程啟動的第一步是初始化startTime，并調用countDown來通知start方法，初始化結束了

其次便是一個循環，循環內的行為就是每隔一段跳一格的操作了，我們看具體的操作：

1）首先調用waitForNextTick()

?

首先計算一下當前tick下的deadline，減去startTime，得到sleepTimeMs，隨后sleep一下。這里面有幾個小細節：

計算sleepTimeMs先加999999，應該是不足1ms的，補足1ms

因為每次執行定時任務消耗的時候是不受控制的，因此算出來的sleepTimeMs可能為負，這個時候就可以直接返回了執行下一個格子里的任務了

如果currentTime==Long.MIN_VALUE，會直接返回一個負數，這個應該是為了處理時間輪執行了很長時間導致的long值溢出，具體了解的可以評論里告訴，不勝感激

下面還有一個，如果是windows平臺，先除以10再乘以10，是因為windows平臺下最小調度單位是10ms，如果不處理成10ms的倍數，可能導致sleep更不準了

最后，如果線程被打斷了，并且是shutdown狀態，會直接返回負數，并在隨后的while判斷中挑出循環

2）隨后調用processCanceldTasks()

該方法是為了處理那些被取消的任務，任務存放在一個queue中

?

3）transferTimeoutsToBuckets()

該方法是從timeouts（就是前面newTimeout是放進去的那個queue）的queue中取出任務，放到格子里（HashedWheelBucket是一個鏈表），為了防止這個操作銷毀太多時間，導致更多的任務時間不準，因此一次最多操作10w個。幾個注意點：

計算stopIndes時，含義是取模，因為mask是2的N次方減1，因此%和&可以等價操作，即x % (mask + 1) == x & mask，這個技巧在jdk的集合類中也被使用到

為了防止出現任務延遲太久，因此在計算模之前，還先取max in (calculated, tick），從而讓那些本應該在 過去執行的任務，在這期先快速執行掉

?

4）expireTimeouts(deadline)

這是HashedWheelBucket的一個方法，就是來執行該格子里那些已經過期的任務

這步的操作比較簡單，就是一次遍歷鏈表，如果remainingRounds（剩下的圈數）小于等于0，那么就把他移除并執行expire方法（即TimerTask的run方法）；如果任務被取消了，則直接移除；否則remainingRounds減一，等待下一圈

?

5）如果中間時間輪的狀態不再是started，那么就會跳出循環，并依次取出各個bucket上的未執行且沒有被取消的任務，stop方法會返回這個列表

4、總結

? 時間輪算法理解起來很簡單，實現也似乎不難，但是通過閱讀源碼，可以看到，其中還是有很多很多的小細節需要注意，這個就不容易了

? 而且通過閱讀源碼，可以看到，整個時間輪的調度都是在一個線程里完成的，因此對于那些耗時較大的定時任務，如果直接扔進去處理顯然會影響其他任務的正常執行，例子如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?

?

轉載：https://sq.163yun.com/blog/article/177510753845874688

總結

以上是生活随笔為你收集整理的时间轮算法解析（Netty HashedWheelTimer源码解读）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。