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