工具-時間輪

🎯 什麼情境該想到我

當你「單機要同時管理成千上萬個『N 秒後做一件事』的任務」——連線閒置逾時、心跳偵測、重試退避、單機版延遲佇列——而每個任務各開一個 timer 讓你開始擔心效能時。

⚙️ 怎麼用（步驟 / 公式）

結構：一塊機械秒錶

想像一個有 S 個刻度的錶盤，指針每 T（tick）走一格：

任務延遲 d → 落在第 (cur + d/T) mod S 格
每格掛一條鏈結串列，插入就是 append → O(1)
指針走到某格，就把那格的串列拿出來執行

不排序、不比大小，這是它和最小堆最大的差別。

圈數（circle）：讓小錶盤裝下長延遲

錶盤只有 S 格，最多表示 S × T 的延遲。要掛 30 分鐘、而錶盤只有 60 格 × 1 秒：

steps  = d / T          = 1800 秒 / 1 秒 = 1800 格
slot   = (cur + steps) % S = (cur + 1800) % 60
circle = steps / S      = 1800 / 60 = 30 圈

任務掛上去時記 circle = 30；指針每繞完一圈路過這格就把圈數減 1，減到 0 才真的執行。

type task struct {
    id     int64
    circle int // 還要等幾圈
}
 
// 新增：O(1)
func (w *wheel) add(id int64, d time.Duration) {
    steps := int(d / w.tick)
    slot := (w.cur + steps) % len(w.slots)
    w.slots[slot].PushBack(&task{id: id, circle: steps / len(w.slots)})
}
 
// 每個 tick 推進一格
func (w *wheel) advance() {
    w.cur = (w.cur + 1) % len(w.slots)
    l := w.slots[w.cur]
    for e := l.Front(); e != nil; {
        next := e.Next()
        t := e.Value.(*task)
        t.circle--
        if t.circle == 0 {
            fire(t.id)
            l.Remove(e)
        }
        e = next
    }
}

★「插入和取出都是 O(1)」這句話只對了一半

這是到處被抄、但少有人講清楚的地方。插入確實是 O(1)，但單層＋圈數的版本，每個任務在真正到期前會被「摸」很多次：

每個任務被觸碰次數 = circle = d / (S × T)

也就是說，錶盤一圈的長度 S × T 比延遲 d 小多少倍，任務就被空摸多少次。這是攤還成本不是 O(1)，只是常數很小（動一個 int）。

本機實測（Go 1.26.4 darwin/arm64，2026-09-25），20 萬個 30 分鐘延遲任務、60 格 × 1 秒錶盤：

項目	數值
時間輪插入 20 萬筆	4.6 ms（23 ns/op），heap +12.8 MB
`time.AfterFunc` 插入 20 萬筆	13.9 ms（69 ns/op），heap +31.9 MB
推進 1800 格（模擬 30 分鐘）	觸碰任務 600 萬次 / 到期 20 萬個 = 每任務被摸 30.0 次，純推進耗時 9.6 ms

「每任務被摸 30 次」跟公式 1800 / (60 × 1) = 30 完全吻合。

什麼時候這個常數會咬人：把 tick 降到 1 ms、錶盤 512 格（一圈 0.512 秒），同樣 30 分鐘的延遲 → circle = 1800000/512 ≈ 3516 圈。20 萬個任務平均每格 390 個，指針每毫秒就要空摸 390 次 ≈ 每秒 39 萬次無用的遞減。單層時間輪在「高精度 × 長延遲」的組合下會退化。

解法是階層時間輪（hierarchical timing wheel）：像時鐘的秒針／分針／時針，秒輪轉滿一圈就讓分輪走一格，分輪那一格的任務再「降級」灑回秒輪。任務只在跨層時被搬動，每個任務的總搬動次數 = 層數（常數），這才是真正的攤還 O(1)。Kafka 的 DelayedOperationPurgatory 用階層時間輪；Netty 的 HashedWheelTimer 用的是單層＋圈數（所以 Netty 文件才會建議別拿它掛數量極大又極長的任務）。

★ 在 Go 裡，先別急著自己寫

Java 生態需要 HashedWheelTimer，是因為 java.util.Timer / ScheduledThreadPoolExecutor 用的是最小堆，插入 O(log n) 且每個任務要一個物件。Go runtime 的 timer 是「每個 P 一個最小堆」，插入／刪除也是 O(log n)——但上面的實測告訴我們：20 萬個 timer 也只要 69 ns/op、32 MB。

所以在 Go 的實務判準是：

< 10 萬個 timer：直接 time.AfterFunc / time.After，不要自己造輪子。省下來的心力拿去做別的。
幾十萬～百萬，且任務極輕（純標記逾時）：時間輪的 3 倍插入速度、2.5 倍記憶體優勢才開始有意義。
真的要用：先找現成的（github.com/RussellLuo/timingwheel 這類階層實作），別手寫單層版本。

🧪 我實際套用的紀錄

2026-09-25：在 Go 1.26.4 上把單層時間輪與 time.AfterFunc 對跑 20 萬個 30 分鐘任務，數字如上表。結論是 20 萬這個量級 Go 原生 timer 完全夠用，時間輪的價值在「任務極輕＋量更大」的場景。

⚠️ 注意 / 什麼時候不適用

純記憶體，行程重啟任務全失。要持久性就得每次 add 同步寫一份到 Redis／DB，那你多半該直接用工具-延遲任務方案選型的方案 A。
多實例要自己分片（依 orderId % N 決定歸誰管），時間輪本身沒有任何跨行程協調能力。
執行不能卡住指針。到期任務必須丟給 worker pool，在 advance() 裡同步執行一個慢任務會拖垮整個輪子的精度。
精度上限就是 tick。tick 設 1 秒，就別承諾毫秒級；要毫秒級請上階層時間輪，別把單層 tick 硬壓小（見上面退化分析）。
任務可能被取消時要留得住 handle（slot + list element），否則取消只能靠 tombstone 標記，記憶體會被撐大。

🔗 相關工具

工具-延遲任務方案選型 — 它是三個方案裡的方案 C，什麼時候該選它看那張卡
工具-時間複雜度分析 — 「O(1) 插入」與「攤還成本」不是同一件事
工具-攤還分析 — 每任務被摸 d/(S×T) 次，正是攤還分析要處理的那類成本
工具-資料結構的選擇 — 最小堆 vs 桶＋鏈結串列的取捨範例

Quartz 5

Explorer