題幹與適用場景
這道題考察你能否為大量近似計時任務選擇合適的資料結構。二元堆依到期時間排序，插入與刪除通常需要維護堆序；時間輪把到期時間映射到桶，適合網路逾時、重試與連線保活等對精確度要求有限的場景。回答必須說明精度、複雜度、取消語意、長延遲與執行緒邊界。
面試官考察什麼
- 能否把 tick、桶數、時間跨度與任務 deadline 建立清楚關係。
- 能否正確處理跨輪任務、目前桶任務、落後 tick 與提前觸發。
- 能否讓取消操作便宜，並避免已取消節點在桶中造成錯誤執行。
- 能否說明執行緒安全、回呼隔離、時鐘選擇與過載時的行為。
回答前需要澄清的問題
先確認任務數量級、允許的最早或最晚誤差、最短延遲、最大延遲、取消比例與回呼耗時。任務是否必須持久化？程序重啟後是否恢復？schedule 與 cancel 是否會被多個執行緒呼叫？回呼是否允許阻塞？如果一次 tick 中到期任務太多，是延遲執行、丟棄低優先級任務，還是施加背壓？這些答案決定單輪時間輪是否足夠，以及是否需要分層時間輪或外部持久化。
30 秒回答框架
我會用單調時間計算相對 deadline，以固定 tick 推進游標。每個任務根據剩餘 tick 數計算桶索引與圈數，放入雙向鏈結串列；tick 到達時只掃描目前桶，圈數大於零的任務減一並留在桶內，圈數為零且 deadline 已到的任務移出並提交執行。cancel 使用控制代號把節點標記為取消並從串列摘除。時間輪只負責排程，不在 tick 執行緒執行使用者回呼；所有誤差、並發與過載策略都用測試與指標驗證。
分步驟深入解答
1. 定義時間輪參數與誤差
設 tick 為 tickDuration，桶數為 wheelSize，一輪覆蓋 tickDuration × wheelSize。deadline 先轉換為相對 tick 數；索引可由 (currentTick + remainingTicks) mod wheelSize 得到。tickDuration 決定最小解析度，輪覆蓋範圍決定單輪能直接容納的延遲。需要更大範圍時，使用分層時間輪或把任務留在目前桶並記錄剩餘圈數。
2. 選擇任務節點與桶結構
每個節點保存 deadline、remainingRounds、callback、cancelled 與前後指標。桶使用雙向鏈結串列，插入和已知節點刪除為常數時間；控制代號直接指向節點，避免 cancel 時重新搜尋。不要用陣列保存所有任務再逐 tick 掃描，否則任務數量會直接放大每次推進的成本。
3. 推進 tick 並處理跨輪任務
每次 tick 先推進單調時鐘與游標，再摘下目前桶的節點。remainingRounds 大於零時減一並重新掛回；為零時比較實際 deadline，尚未到期就按新的剩餘 tick 重新入桶，到期才提交執行。若執行緒長時間暫停導致跳過多個 tick，要限制一次補償掃描量並記錄延遲，避免恢復時阻塞過久。
4. 處理 schedule、cancel 與競態
可以用一個生產者佇列把 schedule 和 cancel 請求交給唯一 tick 執行緒，減少桶鎖競爭。cancel 先設定取消標記，再嘗試摘鏈；tick 執行緒取出節點後再次檢查標記，保證競態下不會執行已取消回呼。schedule 的 deadline 早於目前時間時，應定義為目前 tick 儘快執行，不能把負數取模後放入任意未來桶。
5. 隔離回呼執行與過載
tick 執行緒只負責移動節點與提交任務，把使用者回呼交給受控執行器。執行器滿載時要有明確策略，例如限制佇列、按優先級丟棄可丟任務、延遲非關鍵任務或回傳過載錯誤。記錄到期延遲、桶掃描耗時、取消數、執行佇列長度與回呼失敗，才能判斷時間輪本身或下游執行器成為瓶頸。
6. 用偽代碼固定核心不變量
核心迴圈可以寫成以下形式，具體鎖與執行緒模型依實作語言決定：
schedule(task, deadline):
ticks = ceil((deadline - now) / tickDuration)
ticks = max(ticks, 0)
node.rounds = ticks / wheelSize
node.bucket = (currentTick + ticks) % wheelSize
buckets[node.bucket].append(node)
return node.handle
advance(now):
while currentTick <= floor(now / tickDuration):
bucket = buckets[currentTick % wheelSize]
for node in bucket.detachAll():
if node.cancelled: continue
if node.rounds > 0:
node.rounds -= 1
bucket.append(node)
elif node.deadline <= now:
executor.submit(node.callback)
else:
schedule(node, node.deadline)
currentTick += 1高品質示範回答
我會先確認誤差、延遲範圍、取消比例、持久化與回呼阻塞約束。實作上用單調時鐘與固定 tick 推進游標，桶是雙向鏈結串列，節點保存 deadline、remainingRounds、取消標記與控制代號。schedule 根據剩餘 tick 計算桶索引與圈數，cancel 透過控制代號摘鏈並設定標記；tick 執行緒只處理目前桶，跨輪節點遞減圈數，deadline 到期後提交到受控執行器。對跳過 tick 的恢復限制補償量並記錄延遲；對執行器過載設定佇列上限、優先級與失敗策略。測試涵蓋邊界 deadline、長延遲、重複 cancel、並發 schedule/cancel、時鐘跳躍、回呼例外與數百萬節點的掃描成本。若需要更低誤差或更大時間範圍，再考慮分層時間輪或堆作為補充。
常見錯誤
- 把 wall clock 直接用於相對計時，忽略系統時間調整。
- 忘記保存 remainingRounds，導致跨輪任務提前執行。
- 目前桶任務尚未到期時直接執行或靜默遺失。
- cancel 只設定布林值，卻沒有在取出節點後再次檢查。
- 在 tick 執行緒同步執行使用者回呼，造成整個時間輪停頓。
- 用固定陣列全量掃描任務，失去時間輪的稀疏排程優勢。
- 沒有定義跳 tick、過載、重啟恢復與回呼例外的行為。
追問及應對
為什麼不用最小堆？
最小堆適合任務量較小、需要更精確排序的場景；每次插入或刪除要維護堆序。時間輪犧牲精確度，換取桶內常數時間的掛載與摘除，適合大量、近似到期的任務。應根據誤差預算與操作分布選擇，而不是聲稱時間輪總是更快。
tick 執行緒暫停了幾秒怎麼辦？
用單調時間計算目前應到的 tick，限制一次補償處理的最大桶數或任務數，並把剩餘任務留給後續迴圈。記錄排程延遲；如果業務不能接受突發補償，應配合分批執行與背壓，不能在恢復瞬間同步執行全部回呼。
如何保證 cancel 不會誤執行？
控制代號指向節點，cancel 先原子設定取消標記，再嘗試摘鏈；tick 執行緒從桶取出後必須再次檢查標記。若回呼已提交到執行器，只能定義取消的線性化點，並讓回呼在開始前檢查任務狀態。
什麼時候需要分層時間輪？
當單輪覆蓋範圍不足以容納最大 deadline，或任務跨度跨越多個數量級時，可以增加更粗粒度的上層時間輪，把任務逐層下放。每層仍需明確誤差、降級與遷移成本；若需要持久化與故障恢復，還要把時間輪與可靠儲存或訊息系統分離。