定时器的实现原理
文章目錄
- 1.定時器的作用?
- 2.數據結構要求
- 3.時間輪
- 4.分級時間輪
- 5.業界實現方案
- 參考文獻
1.定時器的作用?
定時器的主要用途是執行定時任務。
定時任務在很多場景都需要用到，比如游戲的 Buff 實現，Redis 中的過期任務，Linux 中的定時任務，電商未支付訂單的關閉等等。
2.數據結構要求
定時器需要支持如下幾個操作：
- 創建定時器
- 添加定時任務
- 取消定時任務
- 執行到期任務（查找）
以下為常見實現定時器數據結構的時間復雜度：
- 有序鏈表：插入O(n)，刪除 O(1)，過期 expire 執行 O(1)
- 最小堆：插入O(logn)，刪除 O(logn)，過期 expire 執行 O(1)
- 紅黑樹：插入O(logn)，刪除 O(logn)，過期 expire 執行 O(logn)
- 哈希表+鏈表（時間輪）：插入 O(1)，刪除 O(1)，過期 expire 平均執行 O(1)（最壞為O(n)）
不同開源框架定時器實現方式不一，如 libuv 采用最小堆，nginx 采用紅黑樹，linux 內核和 skynet 采用時間輪算法等等。
3.時間輪
一個時間輪是一個環形結構，可以想象成時鐘，分為很多格子，一個格子代表一段時間（越短 Timer 精度越高），并用一個 List 保存在該格子上到期要執行的所有任務。同時一個指針隨著時間流逝一格一格移動，并執行對應 List 中所有到期的任務。任務通過取模決定應該放入哪個格子。
以上圖為例，假設一個格子是1秒，則整個 wheel 能表示的時間段為 8s。
假如當前指針指向 0。
此時需要調度一個 3s 后執行的任務，顯然應該加入到(0+3=3)的方格中，指針再走3次就可以執行了。
如果任務要在10s后執行，應該等指針走完一個 round 零 2 格再執行，因此應放入2并將 round 標記為 2 表示第二輪時執行。
4.分級時間輪
如果任務的時間跨度很大，數量也多，傳統的時間輪會造成任務的 round 很大，單個格子的任務 List 很長，并會維持很長一段時間。
這時可將 Wheel 按時間粒度分級：
這種方式的優點在于能夠保證任務鏈表的長度一直在比較短的狀態，但缺點是需要更多的空間。
5.業界實現方案
業界對于定時器/延遲隊列的工程實踐，則通常使用以下幾種方案。
- 基于 Redis ZSet 實現。
- 采用某些自帶延遲選項的隊列實現，如 RabbitMQ、Beanstalkd、騰訊 TDMQ 等。
- 基于 Timing-Wheel 時間輪算法實現。
參考文獻
如何快速實現一個定時器？- InfoQ
總結
