面試Java後端卻問我時間輪算法，面試官沒想到我看過Dubbo源碼！（上）

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的時間輪結構

Dubbo 的時間輪實作位于 dubbo-common 子產品的 org.apache.dubbo.common.timer 包中，下面我們就來分析時間輪涉及的核心接口和實作。

核心接口

TimerTask

在 Dubbo 中，所有定時任務都要實作 TimerTask 接口。隻定義了一個 run() 方法，入參是一個 Timeout 接口對象。

Timeout

Timeout 對象與 TimerTask 對象一一對應，類似線程池傳回的 Future 對象與送出到線程池中的任務對象之間的關系。

通過 Timeout 對象，不僅可以檢視定時任務的狀态，還可以操作定時任務（例如取消關聯的定時任務）。

Timeout 接口中的方法：

Timer 接口定義了定時器的基本行為，核心是 

newTimeout()

 ：送出一個定時任務（TimerTask）并傳回關聯的 Timeout 對象，類似于向線程池送出任務。

HashedWheelTimeout

HashedWheelTimeout 是 Timeout 接口的唯一實作，是 HashedWheelTimer 的内部類。HashedWheelTimeout 扮演了兩個角色：

• 時間輪中雙向連結清單的節點，即定時任務 TimerTask 在 HashedWheelTimer 中的容器
• 定時任務 TimerTask 送出到 HashedWheelTimer 之後傳回的句柄（Handle），用于在時間輪外部檢視和控制定時任務