一、網(wǎng)絡(luò)事件和時(shí)間事件

對于服務(wù)端來說，驅(qū)動服務(wù)端邏輯的事件主要有兩個(gè)，?個(gè)是?絡(luò)事件，另?個(gè)是時(shí)間事件；

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

第?種，?絡(luò)事件和時(shí)間事件在?個(gè)線程當(dāng)中配合使?；例如nginx、redis；

第?種，?絡(luò)事件和時(shí)間事件在不同線程當(dāng)中處理；例如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++) {
	 //... ?絡(luò)事件處理
	 }
	 update_timer(); // 時(shí)間事件處理
}

通過epoll_wait中的timeout進(jìn)行定時(shí)操作。但是由于可能會受到網(wǎng)絡(luò)事件處理中網(wǎng)絡(luò)影響，導(dǎo)致后面update_timer()時(shí)間事件處理出現(xiàn)比較大的誤差（沒有那么準(zhǔn)時(shí)）。

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

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

第二種

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

二、接口設(shè)計(jì)

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

大量定時(shí)任務(wù)怎么處理？

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

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

三、紅黑樹

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

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

四、最小堆

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

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

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

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

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

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

五、時(shí)間輪

1、單層級時(shí)間輪

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

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

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

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

顯而易見的，限流更加準(zhǔn)確，但是很耗費(fèi)時(shí)間，熔斷沒那么準(zhǔn)確，但是相對來說沒那么耗時(shí)間

熔斷的應(yīng)用：

DDos攻擊：

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

解決辦法：

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

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

為什么要使用時(shí)間輪？

案例：心跳檢測：

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

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

上圖的時(shí)間輪大小為8，時(shí)間精度為秒

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

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

將定時(shí)事件插入到時(shí)間輪中哪個(gè)位置呢？

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

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

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

時(shí)間輪大小應(yīng)該取 2 的n次方 > 檢測時(shí)間間隔

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

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

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

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

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

時(shí)間輪設(shè)置太大有什么后果？

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

如何解決空推進(jìn)問題？

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

如果定時(shí)任務(wù)，時(shí)間跨度特別大，幾毫秒的，幾個(gè)小時(shí)的，幾天的定時(shí)任務(wù)，該怎么處理呢？

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

2、多層級時(shí)間輪

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

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

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

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

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

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

因?yàn)槎伎梢酝ㄟ^tick進(jìn)行算出來。

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

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

tick的范圍是(0~43199 因?yàn)?(606012=43200)）

因?yàn)閠ick不能一直加到無窮大（如果能加到無窮大，在0號位置就不會有值）

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

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

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

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

因?yàn)樵黾佣〞r(shí)器和檢測定時(shí)器都是O(1)，不管定時(shí)任務(wù)有多少。