一、網絡事件和時間事件

對于服務端來說，驅動服務端邏輯的事件主要有兩個，?個是?絡事件，另?個是時間事件；

在不同框架中，這兩種事件有不同的實現?式；

第?種，?絡事件和時間事件在?個線程當中配合使?；例如nginx、redis；

第?種，?絡事件和時間事件在不同線程當中處理；例如skynet；

第一種

// 第?種
while (!quit) {
	 int now = get_now_time();// 單位：ms
	 int timeout = get_nearest_timer() - now;
	 if (timeout < 0) timeout = 0;
	 int nevent = epoll_wait(epfd, ev, nev, timeout);
	 for (int i=0; i< nevent; i++) {
	 //... ?絡事件處理
	 }
	 update_timer(); // 時間事件處理
}

通過epoll_wait中的timeout進行定時操作。但是由于可能會受到網絡事件處理中網絡影響，導致后面update_timer()時間事件處理出現比較大的誤差（沒有那么準時）。

受到網絡影響，定時器的誤差較大，如何解決？

通過定時信號，發送信號的方式提前打斷epoll_wait，然后盡快執行我們的定時器事件update_timer()(nginx就是采用這種方法)

第二種

// 第?種 在其他線程添加定時任務
void* thread_timer(void * thread_param) {
 init_timer();
 while (!quit) {
 update_timer(); // 更新檢測定時器，并把定時事件發送到消息隊列中
 sleep(t); // 這?的 t 要?于 時間精度
 }
 clear_timer();
 return NULL;
}
pthread_create(&pid, NULL, thread_timer, &thread_param);

二、接口設計

// 初始化定時器
void init_timer();
// 添加定時器
Node* add_timer(int expire, callback cb);
// 刪除定時器
bool del_timer(Node* node);
// 找到最近要發?的定時任務
Node* find_nearest_timer();
// 更新檢測定時器
void update_timer();
// 清除定時器
// void clear_timer();

大量定時任務怎么處理？

通過一個數據結構組織定時任務，讓時間越近的定時任務先觸發（它的優先級高）

可以采用數據結構如：紅黑樹（nginx）、最小堆(libevent、go、libev等大部分)、時間輪（netty、kafka、skynet）

三、紅黑樹

在紅黑樹中，怎么解決相同的時間的key？

比如插入時間為7，那么就可以插入右側(也就是說，如果定時器的時間相等的話，定時事件后加入的就后觸發)（nignx中定時器就是這樣實現的）

四、最小堆

最小堆也可以用一個數組來表示，數組的第一個數永遠是最小的。

它的效率要比紅黑樹高，最小堆不一定要保證是一個有序的結構，只需要父節點小于子節點就好了。

紅黑樹的增加和刪除的節點的 時間復雜度為O(logN)，查找最小的節點時間為O(H),其中H為紅黑樹高度

最小堆的增加和刪除節點的 時間復雜度也為O(logN)，查找最小的節點時間為O(1)

最小堆的是一種AVL樹，左右子樹高度差不超過1，因此增加和刪除節點的 時間更具有穩定性，而紅黑樹沒有最小堆這么穩定。并且最小堆的查找最小節點的時候復雜度僅有O(1)。因此大部分定時器，都用最小堆來做。

最小堆和紅黑樹通常用在單線程，時間輪用在多線程(原因在本文最后)

五、時間輪

1、單層級時間輪

用于實現時間窗口（如tcp滑動窗口）的限流與熔斷

假設檢測5秒內是否有100次操作

限流： 每秒都查看最近五秒是否有100次操作

熔斷：每過五秒查看這五秒有沒有100次操作

顯而易見的，限流更加準確，但是很耗費時間，熔斷沒那么準確，但是相對來說沒那么耗時間

熔斷的應用：

DDos攻擊：

客戶端不斷發送大量數據給服務器的過程為DDos攻擊

解決辦法：

在網絡底層用DPDK判斷

在應用層用熔斷機制判斷規定時間內客戶端發送的數據包是否大于最大上限

為什么要使用時間輪？

案例：心跳檢測：

客戶端每 5 秒鐘發送心跳包；服務端若 10 秒內沒收到心跳數據，則清除連接；

實際在開發過程中，若收到除了心跳包的其他數據，心跳檢測也算通過，在這是為了簡化流程，只判斷心跳包；作為對?：我們假設使? map 來存儲所有連接數；每秒檢測 map 結構，那么每秒需要遍歷所有的連接，如果這個map結構包含?萬條連接，那么我們做了很多?效檢測；考慮極端情況，剛添加進來的連接，下?秒就需要去檢測，實際上只需要10秒后檢測就?了；那么我們考慮使?時間輪來檢測

上圖的時間輪大小為8，時間精度為秒

定時事件什么時候要觸發？

時間輪數組每個索引對應一串鏈表，每個節點就是要觸發的定時時間，當時間輪指針指到該索引時，該鏈表下的時間都要觸發。

將定時事件插入到時間輪中哪個位置呢？

假設時間輪的長度為8(也就是數組的長度)

在時間輪指針為5的時候加入了一個新的連接，那么它下次的檢測的時間為 (5+10)%8=7，在時間輪數組索引為7的時候，進行檢測。

這樣就不需要每秒遍歷所有的連接了，可以減少運算量。但是這樣子仍然存在問題，因為10s檢測一次，索引為5的時候加入的，可是過了2秒又要檢測，因此依舊會檢測到未超時的任務，浪費計算量。因此要求時間的長度要大于 檢測時間間隔(在這里，也就是10秒)

時間輪大小應該取 2 的n次方 > 檢測時間間隔

時間輪（數組）長度為什么要 2 的n次方 呢？

這就涉及取余操作原理的實現了，有除法還有下取整，如果是 2 的n次方,可以直接替換成位運算，來提高運算速度

也就是說，16大小的時間輪 對于5來說，5%16=5

可以寫成5&(16-1)=5

16寫成2進制為1111,五寫為二進制為0101，也就是說大于等于16的數，都會被控制在0~15內，實現取余的效果。

時間輪設置太大有什么后果？

會出現踏空(空推進)的情況，在時間輪中，事件會變得很稀疏，很多對應索引下，沒有定時器事件。精度由1s設置成1ms也會造成空推進現象。

如何解決空推進問題？

(空推進是分布式定時器必須要解決的問題，可以通過 最小堆+時間輪 解決,通過最小堆 讓時間輪的指針直接跳到下一個要觸發定時器事件的索引處，避免出現空推進的現象（或者使用多層級時間輪）

如果定時任務，時間跨度特別大，幾毫秒的，幾個小時的，幾天的定時任務，該怎么處理呢？

單層級時間輪沒法解決，會出現很多空推進的問題。因此要使用多層級時間輪,比如將最近幾秒要觸發的放在第一層，幾分鐘的放在第二層，幾小時的放在第三層…

2、多層級時間輪

比如當前秒針的指針在2處,分針的指針在0處，下一個時間定時器在61秒后觸發，由于61》=60，因此floor((2+61)/60)=1,

于是放在分針的索引為1處的地方。（同時鏈表中的節點還記錄著時間，2+61=63）

當秒針指針經過58秒后，秒針指向0，分針向前移動一格，為1。這時候，將分針指向的定時器事件，映射到第一級時間輪(秒)里面，還有3秒，因此放到秒針索引為(63-60=3)處。當再經過3秒，秒針指針指向3，該定時事件觸發

(綠色箭頭指的是，該索引處 用鏈表存放的定時器，時間范圍)

由于將最近要處理的事件放入第一級時間輪中，由于事件密集，可以避免空推進的現象。

在實際的代碼中，不需要記錄，分針的指針和時針的指針，只有一個tick，范圍是0~43200。

因為都可以通過tick進行算出來。

按上面的例子，可以知道，除了第一級時間輪，0號位置是有數據的，但是第二級，第三級通常是沒有數據的，為什么那些開源框架中，0號位置都有數據呢？

什么情況下，最后一層的0號索引有數據呢？

tick的范圍是(0~43199 因為 (606012=43200)）

因為tick不能一直加到無窮大（如果能加到無窮大，在0號位置就不會有值）

比如剛開始秒針指向2，其他指針都指向0。要經過43199秒，那么(2+43199)%43200=1

因此，此時數據放在，第三層的索引0號處。(時針的位置為 時針當前的位置+floor(x/3600)%12)

多線程環境為什么使用時間輪？

涉及鎖的力度，紅黑樹和最小堆都是O(logN),要對整個結構進行加鎖，鎖的力度比較大，會鎖太久。

因為增加定時器和檢測定時器都是O(1)，不管定時任務有多少。