設為“星標”，好文章不錯過！
1 定時任務
Netty、Quartz、Kafka 以及 Linux 都有定時任務功能。
JDK 自帶的java.util.Timer和DelayedQueue可實現簡單的定時任務，底層用的是堆，存取複雜度都是 O(nlog(n))，但無法支撐海量定時任務。
在任務量大、性能要求高的場景，為了將任務存取及取消操作時間複雜度降為 O(1)，會採用時間輪算法。
2 時間輪模型及其應用
一種高效批量管理定時任務的調度模型。一般會實現成一個環形結構，類似一個時鐘，分為很多槽，一個槽代表一個時間間隔，每個槽使用雙向鏈表存儲定時任務。
指針周期性跳動，跳動到一個槽位，就執行該槽位的定時任務。
Hashed Timing Wheel 結構示意圖
適用場景
故障恢復
流量控制
調度算法
控制網絡中的數據包生命周期
計時器維護代價高，如果
處理器在每個時鐘滴答聲中都會中斷
使用精細粒度計時器
未完成的計時器很多
需要高效的定時器算法以減少總體中斷的開銷。
單層時間輪的容量和精度都是有限的，對於精度要求特別高、時間跨度特別大或是海量定時任務需要調度的場景，通常會使用多級時間輪以及持久化存儲與時間輪結合的方案。
模型和性能指標
模型中的規則
客戶端調用：
START_TIMER（時間間隔，Request_ID，Expiry_Action）
STOP_TIMER（Request_ID）
計時器tick調用：
PER_TICK_BOOKKEEPING
EXPIRY_PROCESSING
性能指標
空間
數據結構使用的內存
延遲
開始和結束上述任何例程所需的時間
3 Dubbo的時間輪結構
核心接口
TimerTask
在 Dubbo 中，所有定時任務都要實現 TimerTask 接口。只定義了一個 run() 方法，入參是一個 Timeout 接口對象。
Timeout
Timeout 對象與 TimerTask 對象一一對應，類似線程池返回的 Future 對象與提交到線程池中的任務對象之間的關係。
通過 Timeout 對象，不僅可以查看定時任務的狀態，還可以操作定時任務（例如取消關聯的定時任務）。
Timeout 接口中的方法：
Timer 接口定義了定時器的基本行為，核心是 ：提交一個定時任務（TimerTask）並返回關聯的 Timeout 對象，類似於向線程池提交任務。
HashedWheelTimeout
HashedWheelTimeout 是 Timeout 接口的唯一實現，是 HashedWheelTimer 的內部類。HashedWheelTimeout 扮演了兩個角色：
時間輪中雙向鏈表的節點，即定時任務 TimerTask 在 HashedWheelTimer 中的容器
定時任務 TimerTask 提交到 HashedWheelTimer 之後返回的句柄（Handle），用於在時間輪外部查看和控制定時任務
核心字段
prev、next。通過雙向鏈表被用來在HashedWheelTimerBucket鏈timeouts（定時任務），由於只在WorkerThread上行動，沒有必要進行同步/volatile。
task，實際被調度的任務
deadline，定時任務執行的時間。在創建 HashedWheelTimeout 時指定
計算公式：，ns
state，定時任務當前所處狀態
可選狀態：
STATE_UPDATER 用於實現 state 狀態變更的原子性。
remainingRounds，當前任務剩餘的時鐘周期數。時間輪所能表示的時間長度有限，在任務到期時間與當前時刻的時間差，超過時間輪單圈能表示時長，就出現套圈，需要該字段值表示剩餘的時鐘周期。
核心API
isCancelled()
isExpired()
state()
檢查當前 HashedWheelTimeout 狀態
cancel() 方法
expire() 方法
remove()
HashedWheelBucket
時間輪中的一個槽。
時間輪中的槽實際上就是一個用於緩存和管理雙向鏈表的容器，雙向鏈表中的每一個節點就是一個 對象，也就關聯了一個 定時任務。
HashedWheelBucket 持有雙向鏈表的首尾兩個節點 - head 和 tail，再加上每個 HashedWheelTimeout 節點均持有前驅和後繼引用，即可正、逆向遍歷整個鏈表。
核心API
addTimeout()
pollTimeout()
remove()
從雙向鏈表中移除指定的 HashedWheelTimeout 節點。
clearTimeouts()
循環調用 pollTimeout() 方法處理整個雙向鏈表，並返回所有未超時或者未被取消的任務。
expireTimeouts()
遍歷雙向鏈表中的全部 HashedWheelTimeout 節點。在處理到期的定時任務時，會通過 remove() 方法取出，並調用其 expire() 方法執行；對於已取消的任務，通過 remove() 方法取出後直接丟棄；對於未到期的任務，會將 remainingRounds 字段（剩餘時鐘周期數）減一。
HashedWheelTimer
接口的實現，通過時間輪算法實現了一個定時器。
職能
根據當前時間輪指針選定對應 槽，從鏈表頭部開始迭代，計算每個 定時任務：
屬於當前時鐘周期則取出運行
不屬於則將其剩餘的時鐘周期數減一
核心域
workerState
時間輪當前所處狀態，三個可選值，由 實現其原子地修改。
startTime
當前時間輪的啟動時間，提交到該時間輪的定時任務的 deadline 字段值均以該時間戳為起點進行計算。
wheel
時間輪環形隊列，每個元素都是一個槽。當指定時間輪槽數為 n 時，會向上取最靠近 n 的 2 次冪值
timeouts、cancelledTimeouts
HashedWheelTimer 會在處理 HashedWheelBucket 的雙向鏈表前，先處理這倆隊列的數據：
timeouts 隊列
緩衝外部提交時間輪中的定時任務
cancelledTimeouts 隊列
暫存取消的定時任務
tick
位於 ，時間輪的指針，步長為 1 的單調遞增計數器
mask
掩碼， ，執行 便能定位到對應的時鐘槽
ticksDuration
時間指針每次加 1 所代表的實際時間，單位為納秒。
pendingTimeouts
當前時間輪剩餘的定時任務總數。
workerThread
時間輪內部真正執行定時任務的線程。
worker
真正執行定時任務的邏輯封裝這個 Runnable 對象中。
newTimeout()
提交定時任務，在定時任務進入到 timeouts 隊列之前會先調用 start() 方法啟動時間輪，其中會完成下面兩個關鍵步驟：
確定時間輪的 startTime 字段
啟動 workerThread 線程，開始執行 worker 任務。
之後根據 startTime 計算該定時任務的 deadline，最後才能將定時任務封裝成 並添加到 隊列。
4 時間輪指針一次轉動的執行流程
：
時間輪指針轉動，時間輪周期開始
清理用戶主動取消的定時任務，這些定時任務在用戶取消時，記錄到 隊列中。在每次指針轉動的時候，時間輪都會清理該隊列
將緩存在 timeouts 隊列中的定時任務轉移到時間輪中對應的槽中
根據當前指針定位對應槽，處理該槽位的雙向鏈表中的定時任務
檢測時間輪的狀態。如果時間輪處於運行狀態，則循環執行上述步驟，不斷執行定時任務。如果時間輪處於停止狀態，則執行下面的步驟獲取到未被執行的定時任務並加入 隊列：遍歷時間輪中每個槽位，並調用 () 方法；對 timeouts 隊列中未被加入槽中循環調用 poll()
最後再次清理 cancelledTimeouts 隊列中用戶主動取消的定時任務。
5 定時任務應用
並不直接用於周期性操作，而是只向時間輪提交執行單次的定時任務，在上一次任務執行完成的時候，調用 newTimeout() 方法再次提交當前任務，這樣就會在下個周期執行該任務。即使在任務執行過程中出現了 GC、I/O 阻塞等情況，導致任務延遲或卡住，也不會有同樣的任務源源不斷地提交進來，導致任務堆積。
Dubbo 時間輪應用主要在如下方面：
失敗重試， 例如，Provider 向註冊中心進行註冊失敗時的重試操作，或是 Consumer 向註冊中心訂閱時的失敗重試等
周期性定時任務， 例如，定期發送心跳請求，請求超時的處理，或是網絡連接斷開後的重連機制
參考
https://zhuanlan.zhihu.com/p/32906730
