一、網(wǎng)絡事件和時間事件

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

在不同框架中，這兩種事件有不同的實現(xiàn)?式；

第?種，?絡事件和時間事件在?個線程當中配合使?；例如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進行定時操作。但是由于可能會受到網(wǎng)絡事件處理中網(wǎng)絡影響，導致后面update_timer()時間事件處理出現(xiàn)比較大的誤差（沒有那么準時）。

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

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

第二種

// 第?種 在其他線程添加定時任務
void* thread_timer(void * thread_param) {
 init_timer();
 while (!quit) {
 update_timer(); // 更新檢測定時器，并把定時事件發(fā)送到消息隊列中
 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);
// 找到最近要發(fā)?的定時任務
Node* find_nearest_timer();
// 更新檢測定時器
void update_timer();
// 清除定時器
// void clear_timer();

大量定時任務怎么處理？

通過一個數(shù)據(jù)結構組織定時任務，讓時間越近的定時任務先觸發(fā)（它的優(yōu)先級高）

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

三、紅黑樹

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

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

四、最小堆

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

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

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

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

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

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

五、時間輪

1、單層級時間輪

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

假設檢測5秒內(nèi)是否有100次操作

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

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

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

熔斷的應用：

DDos攻擊：

客戶端不斷發(fā)送大量數(shù)據(jù)給服務器的過程為DDos攻擊

解決辦法：

在網(wǎng)絡底層用DPDK判斷

在應用層用熔斷機制判斷規(guī)定時間內(nèi)客戶端發(fā)送的數(shù)據(jù)包是否大于最大上限

為什么要使用時間輪？

案例：心跳檢測：

客戶端每 5 秒鐘發(fā)送心跳包；服務端若 10 秒內(nèi)沒收到心跳數(shù)據(jù)，則清除連接；

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

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

定時事件什么時候要觸發(fā)？

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

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

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

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

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

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

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

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

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

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

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

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

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

如何解決空推進問題？

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

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

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

2、多層級時間輪

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

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

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

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

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

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

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

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

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

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

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

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

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

多線程環(huán)境為什么使用時間輪？

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

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