一文讀懂定時器實現技術

1. 定時器介紹

程序里的定時器主要實現的功能是在未來的某個時間點執(zhí)行相應的邏輯。在定時器模型中，一般有如下幾個定義。

interval：間隔時間，即定時器需要在interval時間后執(zhí)行

StartTimer：添加一個定時器任務

StopTimer：結束一個定時器任務

PerTickBookkeeping: 檢查定時器系統(tǒng)中，是否有定時器實例已經到期，相當于定義了最小時間粒度。

常見的實現方法有如下幾種：

鏈表

排序鏈表

最小堆

時間輪

接下來我們一起看下這些方法的具體實現原理。

2. 定時器實現方法

2.1 鏈表實現

鏈表的實現方法比較粗糙。鏈表用于存儲所有的定時器，每個定時器都含有interval 和 elapse 兩個時間參數，elapse表示當前被tickTimer了多少次。當elapse 和interval相等時，表示定時器到期。

在此方案中，添加定時器就是在鏈表的末尾新增一個節(jié)點，時間復雜度是 O(1)。

如果想要刪除一個定時器的話，我們需要遍歷鏈表找到對應的定時器，時間復雜度是O(n)。

此方案下，每隔elapse時間，系統(tǒng)調用信號進行超時檢查，即PerTickBookkeeping。每次PerTickBookkeeping需要對鏈表所有定時器進行 elapse++，因此可以看出PerTickBookkeeping的時間復雜度是O(N)。

可以看出此方案過于粗暴，所以使用場景極少。

2.2 排序雙向鏈表實現

排序雙向鏈表是在鏈表實現上的優(yōu)化。優(yōu)化思路是降低時間復雜度。

首先，每次PerTickBookkeeping需要自增所有定時器的elapse變量，如果我們將interval變?yōu)榻^對時間，那么我們只需要比較當前時間和interval時間是否相等，減少了對每個定時器的操作。

如果不需要對每個定時器進行操作，我們將定時器進行排序，那么每次PerTickBookkeeping都只需要判斷第一個定時器，時間復雜度為O(1)。

相應的，為了維持鏈表順序，每次新增定時器需要進行鏈表排序時間復雜度為 O(N)。

每次刪除定時器時，由于會持有自己節(jié)點的引用，所以不需要查找其在鏈表中所在的位置，所以時間復雜度為O(1)，雙向鏈表的好處。

圖1 雙向鏈表實現示意圖

2.3 時間輪實現

時間輪的數據結構是數組 + 鏈表。

他的時間輪為數組，新增和刪除一個任務，時間復雜度都是O(1)。

PerTickBookkeeping每次轉動一格，時間復雜度也是O(1)。

2.4 最小堆實現

最小堆是堆的一種, (堆是一種二叉樹), 指的是堆中任何一個父節(jié)點都小于子節(jié)點, 子節(jié)點順序不作要求。

二叉排序樹(BST)指的是: 左子樹節(jié)點小于父節(jié)點, 右子樹節(jié)點大于父節(jié)點, 對所有節(jié)點適用

圖3 最小堆

樹的基本操作是插入節(jié)點和刪除節(jié)點。對最小堆而言，為了將一個元素X插入最小堆，我們可以在樹的下一個空閑位置創(chuàng)建一個空穴。如果X可以放在空穴中而不被破壞堆的序，則插入完成。否則就執(zhí)行上濾操作，即交換空穴和它的父節(jié)點上的元素。不斷執(zhí)行上述過程，直到X可以被放入空穴，則插入操作完成。

因此我們可以知道最小堆的插入時間復雜度是O(lgN)。

最小堆的刪除和插入邏輯基本類似，如果不做優(yōu)化，時間復雜度也是O(lgN),但是實際實現方案上，做了延遲刪除操作，時間復雜度為O(1)。

延遲刪除即設置定時器的執(zhí)行回調函數為空，每次最小堆超時，將觸發(fā)pop_heap，pop會重新調整最小堆，最終刪除的定時器將調整到堆頂，但是回調函數不處理。

可以看到PerTickBookkeeping只處理堆頂定時器，時間復雜度O(1)。

最小堆可以使用數組來進行表示，數組中，當前下標n的左子節(jié)點為2N + 1，當前下標n的右子節(jié)點小標為2N + 2。

圖4 最小堆的數組表示

3. 定時器不同實現對比

3.1 時間復雜度對比

圖5 不同實現時間復雜度

從上面的介紹來看，時間輪的時間復雜度最小、性能最好。

3.2 使用場景來看

在任務量小的場景下：最小堆實現，可以根據堆頂設置超時時間，數組存儲結構，節(jié)省內存消耗，使用最小堆可以得到比較好的效果。而時間輪定時器，由于需要維護一個線程用來撥動指針，且需要開辟一個bucket數組，消耗內存大，使用時間輪會較為浪費資源。

在任務量大的場景下：最小堆的插入復雜度是O(lgN), 相比時間輪O(1) 會造成性能下降。更適合使用時間輪實現。

在業(yè)界，服務治理的心跳檢測等功能需要維護大量的鏈接心跳，因此時間輪是首選。