這一篇文章系統的梳理主流定時器算法實作的差異以及應用地方。
- 定時器介紹
程式裡的定時器主要實作的功能是在未來的某個時間點執行相應的邏輯。在定時器模型中，一般有如下幾個定義。
interval：間隔時間，即定時器需要在interval時間後執行
StartTimer：添加一個定時器任務
StopTimer：結束一個定時器任務
PerTickBookkeeping: 檢查定時器系統中，是否有定時器執行個體已經到期，相當于定義了最小時間粒度。
常見的實作方法有如下幾種：
連結清單
排序連結清單
最小堆
時間輪
接下來我們一起看下這些方法的具體實作原理。
- 定時器實作方法
2.1 連結清單實作
連結清單的實作方法比較粗糙。連結清單用于存儲所有的定時器，每個定時器都含有interval 和 elapse 兩個時間參數，elapse表示目前被tickTimer了多少次。當elapse 和interval相等時，表示定時器到期。
在此方案中，添加定時器就是在連結清單的末尾新增一個節點，時間複雜度是 O(1)。如果想要删除一個定時器的話，我們需要周遊連結清單找到對應的定時器，時間複雜度是O(n)。此方案下，每隔elapse時間，系統調用信号進行逾時檢查，即PerTickBookkeeping。每次PerTickBookkeeping需要對連結清單所有定時器進行 elapse++，是以可以看出PerTickBookkeeping的時間複雜度是O(N)。可以看出此方案過于粗暴，是以使用場景極少
2.2 排序雙向連結清單實作
排序雙向連結清單是在連結清單實作上的優化。優化思路是降低時間複雜度。
首先，每次PerTickBookkeeping需要自增所有定時器的elapse變量，如果我們将interval變為絕對時間，那麼我們隻需要比較目前時間和interval時間是否相等，減少了對每個定時器的操作。如果不需要對每個定時器進行操作，我們将定時器進行排序，那麼每次PerTickBookkeeping都隻需要判斷第一個定時器，時間複雜度為O(1)。相應的，為了維持連結清單順序，每次新增定時器需要進行連結清單排序時間複雜度為 O(N)。每次删除定時器時，由于會持有自己節點的引用，是以不需要查找其在連結清單中所在的位置，是以時間複雜度為O(1)，雙向連結清單的好處。
圖1 雙向連結清單實作示意圖
2.3 時間輪實作
時間輪示意圖如下：
圖2 時間輪
時間輪的資料結構是數組 + 連結清單。 他的時間輪為數組，新增和删除一個任務，時間複雜度都是O(1)。PerTickBookkeeping每次轉動一格，時間複雜度也是O(1)。
2.4 最小堆實作
最小堆是堆的一種, (堆是一種二叉樹), 指的是堆中任何一個父節點都小于子節點, 子節點順序不作要求。
二叉排序樹(BST)指的是: 左子樹節點小于父節點, 右子樹節點大于父節點, 對所有節點适用
圖3 最小堆
樹的基本操作是插入節點和删除節點。對最小堆而言，為了将一個元素X插入最小堆，我們可以在樹的下一個空閑位置建立一個空穴。如果X可以放在空穴中而不被破壞堆的序，則插入完成。否則就執行上濾操作，即交換空穴和它的父節點上的元素。不斷執行上述過程，直到X可以被放入空穴，則插入操作完成。是以我們可以知道最小堆的插入時間複雜度是O(lgN)。最小堆的删除和插入邏輯基本類似，如果不做優化，時間複雜度也是O(lgN),但是實際實作方案上，做了延遲删除操作，時間複雜度為O(1)。
延遲删除即設定定時器的執行回調函數為空，每次最小堆逾時，将觸發pop_heap，pop會重新調整最小堆，最終删除的定時器将調整到堆頂，但是回調函數不處理。
可以看到PerTickBookkeeping隻處理堆頂定時器，時間複雜度O(1)。最小堆可以使用數組來進行表示，數組中，目前下标n的左子節點為2N + 1，目前下标n的右子節點小标為2N + 2。
圖4 最小堆的數組表示
- 定時器不同實作對比
3.1 時間複雜度對比
圖5 不同實作時間複雜度
從上面的介紹來看，時間輪的時間複雜度最小、性能最好。
3.2 使用場景來看
在任務量小的場景下：最小堆實作，可以根據堆頂設定逾時時間，數組存儲結構，節省記憶體消耗，使用最小堆可以得到比較好的效果。而時間輪定時器，由于需要維護一個線程用來撥動指針，且需要開辟一個bucket數組，消耗記憶體大，使用時間輪會較為浪費資源。在任務量大的場景下：最小堆的插入複雜度是O(lgN), 相比時間輪O(1) 會造成性能下降。更适合使用時間輪實作。在業界，服務治理的心跳檢測等功能需要維護大量的連結心跳，是以時間輪是首選。
更多免費技術資料及視訊