1. 定時(shí)器介紹

程序里的定時(shí)器主要實(shí)現(xiàn)的功能是在未來的某個(gè)時(shí)間點(diǎn)執(zhí)行相應(yīng)的邏輯。在定時(shí)器模型中，一般有如下幾個(gè)定義。

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

StartTimer：添加一個(gè)定時(shí)器任務(wù)

StopTimer：結(jié)束一個(gè)定時(shí)器任務(wù)

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

常見的實(shí)現(xiàn)方法有如下幾種：

鏈表

排序鏈表

最小堆

時(shí)間輪

接下來我們一起看下這些方法的具體實(shí)現(xiàn)原理。

2. 定時(shí)器實(shí)現(xiàn)方法

2.1 鏈表實(shí)現(xiàn)

鏈表的實(shí)現(xiàn)方法比較粗糙。鏈表用于存儲所有的定時(shí)器，每個(gè)定時(shí)器都含有interval 和 elapse 兩個(gè)時(shí)間參數(shù)，elapse表示當(dāng)前被tickTimer了多少次。當(dāng)elapse 和interval相等時(shí)，表示定時(shí)器到期。

在此方案中，添加定時(shí)器就是在鏈表的末尾新增一個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度是 O(1)。

如果想要刪除一個(gè)定時(shí)器的話，我們需要遍歷鏈表找到對應(yīng)的定時(shí)器，時(shí)間復(fù)雜度是O(n)。

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

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

2.2 排序雙向鏈表實(shí)現(xiàn)

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

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

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

相應(yīng)的，為了維持鏈表順序，每次新增定時(shí)器需要進(jìn)行鏈表排序時(shí)間復(fù)雜度為 O(N)。

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

圖1 雙向鏈表實(shí)現(xiàn)示意圖

2.3 時(shí)間輪實(shí)現(xiàn)

時(shí)間輪的數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 鏈表。

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

PerTickBookkeeping每次轉(zhuǎn)動一格，時(shí)間復(fù)雜度也是O(1)。

2.4 最小堆實(shí)現(xiàn)

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

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

圖3 最小堆

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

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

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

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

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

最小堆可以使用數(shù)組來進(jìn)行表示，數(shù)組中，當(dāng)前下標(biāo)n的左子節(jié)點(diǎn)為2N + 1，當(dāng)前下標(biāo)n的右子節(jié)點(diǎn)小標(biāo)為2N + 2。

圖4 最小堆的數(shù)組表示

3. 定時(shí)器不同實(shí)現(xiàn)對比

3.1 時(shí)間復(fù)雜度對比

圖5 不同實(shí)現(xiàn)時(shí)間復(fù)雜度

從上面的介紹來看，時(shí)間輪的時(shí)間復(fù)雜度最小、性能最好。

3.2 使用場景來看

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

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

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