[[346568]]

1 定時任務(wù)

 Netty、Quartz、Kafka 以及 Linux 都有定時任務(wù)功能。

JDK 自帶的 java.util.Timer 和 DelayedQueue 可實(shí)現(xiàn)簡單的定時任務(wù)，底層用的是堆，存取復(fù)雜度都是 O(nlog(n))，但無法支撐海量定時任務(wù)。

在任務(wù)量大、性能要求高的場景，為了將任務(wù)存取及取消操作時間復(fù)雜度降為 O(1)，會采用時間輪算法。

2 時間輪模型及其應(yīng)用

一種高效批量管理定時任務(wù)的調(diào)度模型。一般會實(shí)現(xiàn)成一個環(huán)形結(jié)構(gòu)，類似一個時鐘，分為很多槽，一個槽代表一個時間間隔，每個槽使用雙向鏈表存儲定時任務(wù)。

指針周期性跳動，跳動到一個槽位，就執(zhí)行該槽位的定時任務(wù)。

Hashed Timing Wheel 結(jié)構(gòu)示意圖

• 故障恢復(fù)
• 流量控制
• 調(diào)度算法
• 控制網(wǎng)絡(luò)中的數(shù)據(jù)包生命周期

計(jì)時器維護(hù)代價高，如果

• 處理器在每個時鐘滴答聲中都會中斷
• 使用精細(xì)粒度計(jì)時器
• 未完成的計(jì)時器很多

需要高效的定時器算法以減少總體中斷的開銷。

單層時間輪的容量和精度都是有限的，對于精度要求特別高、時間跨度特別大或是海量定時任務(wù)需要調(diào)度的場景，通常會使用多級時間輪以及持久化存儲與時間輪結(jié)合的方案。

模型和性能指標(biāo)

模型中的規(guī)則

客戶端調(diào)用：

• START_TIMER（時間間隔，Request_ID，Expiry_Action）
• STOP_TIMER（Request_ID）

計(jì)時器tick調(diào)用：

• PER_TICK_BOOKKEEPING
• EXPIRY_PROCESSING

性能指標(biāo)

• 空間

           數(shù)據(jù)結(jié)構(gòu)使用的內(nèi)存

• 延遲

           開始和結(jié)束上述任何例程所需的時間

3 Dubbo的時間輪結(jié)構(gòu)

Dubbo 時間輪實(shí)現(xiàn)位于 dubbo-common 模塊的 org.apache.dubbo.common.timer 包，下面我們就來分析時間輪涉及的核心接口和實(shí)現(xiàn)。

核心接口

TimerTask

 在 Dubbo 中，所有定時任務(wù)都要實(shí)現(xiàn) TimerTask 接口。只定義了一個 run() 方法，入?yún)⑹且粋€ Timeout 接口對象。

 Timeout

Timeout 對象與 TimerTask 對象一一對應(yīng)，類似線程池返回的 Future 對象與提交到線程池中的任務(wù)對象之間的關(guān)系。
通過 Timeout 對象，不僅可以查看定時任務(wù)的狀態(tài)，還可以操作定時任務(wù)（例如取消關(guān)聯(lián)的定時任務(wù)）。

Timeout 接口中的方法：

Timer 接口定義了定時器的基本行為，核心是 newTimeout() ：提交一個定時任務(wù)（TimerTask）并返回關(guān)聯(lián)的 Timeout 對象，類似于向線程池提交任務(wù)。

 HashedWheelTimeout

 HashedWheelTimeout 是 Timeout 接口的唯一實(shí)現(xiàn)，是 HashedWheelTimer 的內(nèi)部類。HashedWheelTimeout 扮演了兩個角色：

時間輪中雙向鏈表的節(jié)點(diǎn)，即定時任務(wù) TimerTask 在 HashedWheelTimer 中的容器

定時任務(wù) TimerTask 提交到 HashedWheelTimer 之后返回的句柄（Handle），用于在時間輪外部查看和控制定時任務(wù)

核心字段

prev、next。通過雙向鏈表被用來在HashedWheelTimerBucket鏈timeouts（定時任務(wù)），由于只在WorkerThread上行動，沒有必要進(jìn)行同步/volatile。

task，實(shí)際被調(diào)度的任務(wù)

deadline，定時任務(wù)執(zhí)行的時間。在創(chuàng)建 HashedWheelTimeout 時指定
計(jì)算公式：currentTime（創(chuàng)建 HashedWheelTimeout 的時間） + delay（任務(wù)延遲時間） - startTime（HashedWheelTimer 的啟動時間），ns

state，定時任務(wù)當(dāng)前所處狀態(tài)

可選狀態(tài)：

STATE_UPDATER 用于實(shí)現(xiàn) state 狀態(tài)變更的原子性。

remainingRounds，當(dāng)前任務(wù)剩余的時鐘周期數(shù)。時間輪所能表示的時間長度有限，在任務(wù)到期時間與當(dāng)前時刻的時間差，超過時間輪單圈能表示時長，就出現(xiàn)套圈，需要該字段值表示剩余的時鐘周期。

核心API

isCancelled()

isExpired()

state()
檢查當(dāng)前 HashedWheelTimeout 狀態(tài)

cancel() 方法

expire() 方法

remove()

 HashedWheelBucket

 時間輪中的一個槽。
時間輪中的槽實(shí)際上就是一個用于緩存和管理雙向鏈表的容器，雙向鏈表中的每一個節(jié)點(diǎn)就是一個 HashedWheelTimeout 對象，也就關(guān)聯(lián)了一個 TimerTask 定時任務(wù)。

HashedWheelBucket 持有雙向鏈表的首尾兩個節(jié)點(diǎn) - head 和 tail，再加上每個 HashedWheelTimeout 節(jié)點(diǎn)均持有前驅(qū)和后繼引用，即可正、逆向遍歷整個鏈表。

核心API

addTimeout()

pollTimeout()

remove()
從雙向鏈表中移除指定的 HashedWheelTimeout 節(jié)點(diǎn)。

clearTimeouts()
循環(huán)調(diào)用 pollTimeout() 方法處理整個雙向鏈表，并返回所有未超時或者未被取消的任務(wù)。

expireTimeouts()
遍歷雙向鏈表中的全部 HashedWheelTimeout 節(jié)點(diǎn)。在處理到期的定時任務(wù)時，會通過 remove() 方法取出，并調(diào)用其 expire() 方法執(zhí)行；對于已取消的任務(wù)，通過 remove() 方法取出后直接丟棄；對于未到期的任務(wù)，會將 remainingRounds 字段（剩余時鐘周期數(shù)）減一。

 HashedWheelTimer

Timer 接口的實(shí)現(xiàn)，通過時間輪算法實(shí)現(xiàn)了一個定時器。

職能

根據(jù)當(dāng)前時間輪指針選定對應(yīng) HashedWheelBucket 槽，從鏈表頭部開始迭代，計(jì)算每個 HashedWheelTimeout 定時任務(wù)：

• 屬于當(dāng)前時鐘周期則取出運(yùn)行
• 不屬于則將其剩余的時鐘周期數(shù)減一

核心域

 workerState
時間輪當(dāng)前所處狀態(tài)，三個可選值，由 AtomicIntegerFieldUpdater 實(shí)現(xiàn)其原子地修改。

startTime
當(dāng)前時間輪的啟動時間，提交到該時間輪的定時任務(wù)的 deadline 字段值均以該時間戳為起點(diǎn)進(jìn)行計(jì)算。

wheel
時間輪環(huán)形隊(duì)列，每個元素都是一個槽。當(dāng)指定時間輪槽數(shù)為 n 時，會向上取最靠近 n 的 2 次冪值

timeouts、cancelledTimeouts
HashedWheelTimer 會在處理 HashedWheelBucket 的雙向鏈表前，先處理這倆隊(duì)列的數(shù)據(jù)：

timeouts 隊(duì)列
緩沖外部提交時間輪中的定時任務(wù)

cancelledTimeouts 隊(duì)列
暫存取消的定時任務(wù)

tick
位于 HashedWheelTimer$Worker ，時間輪的指針，步長為 1 的單調(diào)遞增計(jì)數(shù)器

mask
掩碼， mask = wheel.length - 1，執(zhí)行 ticks & mask 便能定位到對應(yīng)的時鐘槽

ticksDuration
時間指針每次加 1 所代表的實(shí)際時間，單位為納秒。

pendingTimeouts
當(dāng)前時間輪剩余的定時任務(wù)總數(shù)。

workerThread
時間輪內(nèi)部真正執(zhí)行定時任務(wù)的線程。

worker
真正執(zhí)行定時任務(wù)的邏輯封裝這個 Runnable 對象中。

newTimeout()

 提交定時任務(wù)，在定時任務(wù)進(jìn)入到 timeouts 隊(duì)列之前會先調(diào)用 start() 方法啟動時間輪，其中會完成下面兩個關(guān)鍵步驟：

1. 確定時間輪的 startTime 字段
2. 啟動 workerThread 線程，開始執(zhí)行 worker 任務(wù)。

之后根據(jù) startTime 計(jì)算該定時任務(wù)的 deadline，最后才能將定時任務(wù)封裝成 HashedWheelTimeout 并添加到 timeouts 隊(duì)列。

4 時間輪指針一次轉(zhuǎn)動的執(zhí)行流程

 HashedWheelTimer$Worker.run()：

1. 時間輪指針轉(zhuǎn)動，時間輪周期開始
2. 清理用戶主動取消的定時任務(wù)，這些定時任務(wù)在用戶取消時，記錄到 cancelledTimeouts 隊(duì)列中。在每次指針轉(zhuǎn)動的時候，時間輪都會清理該隊(duì)列
3. 將緩存在 timeouts 隊(duì)列中的定時任務(wù)轉(zhuǎn)移到時間輪中對應(yīng)的槽中
4. 根據(jù)當(dāng)前指針定位對應(yīng)槽，處理該槽位的雙向鏈表中的定時任務(wù)
5. 檢測時間輪的狀態(tài)。如果時間輪處于運(yùn)行狀態(tài)，則循環(huán)執(zhí)行上述步驟，不斷執(zhí)行定時任務(wù)。如果時間輪處于停止?fàn)顟B(tài)，則執(zhí)行下面的步驟獲取到未被執(zhí)行的定時任務(wù)并加入 unprocessedTimeouts 隊(duì)列：遍歷時間輪中每個槽位，并調(diào)用 clearTimeouts() 方法；對 timeouts 隊(duì)列中未被加入槽中循環(huán)調(diào)用 poll()
6. 最后再次清理 cancelledTimeouts 隊(duì)列中用戶主動取消的定時任務(wù)。

5 定時任務(wù)應(yīng)用

 并不直接用于周期性操作，而是只向時間輪提交執(zhí)行單次的定時任務(wù)，在上一次任務(wù)執(zhí)行完成的時候，調(diào)用 newTimeout() 方法再次提交當(dāng)前任務(wù)，這樣就會在下個周期執(zhí)行該任務(wù)。即使在任務(wù)執(zhí)行過程中出現(xiàn)了 GC、I/O 阻塞等情況，導(dǎo)致任務(wù)延遲或卡住，也不會有同樣的任務(wù)源源不斷地提交進(jìn)來，導(dǎo)致任務(wù)堆積。

Dubbo 時間輪應(yīng)用主要在如下方面：

1. 失敗重試， 例如，Provider 向注冊中心進(jìn)行注冊失敗時的重試操作，或是 Consumer 向注冊中心訂閱時的失敗重試等
2. 周期性定時任務(wù)， 例如，定期發(fā)送心跳請求，請求超時的處理，或是網(wǎng)絡(luò)連接斷開后的重連機(jī)制

參考

https://zhuanlan.zhihu.com/p/32906730