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

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

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

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

第?種，?絡(luò)事件和時(shí)間事件在不同線(xiàn)程當(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í)間事件處理
}

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

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

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

第二種

// 第?種 在其他線(xiàn)程添加定時(shí)任務(wù)
void* thread_timer(void * thread_param) {
 init_timer();
 while (!quit) {
 update_timer(); // 更新檢測(cè)定時(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();
// 更新檢測(cè)定時(shí)器
void update_timer();
// 清除定時(shí)器
// void clear_timer();

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

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

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

三、紅黑樹(shù)

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

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

四、最小堆

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

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

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

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

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

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

五、時(shí)間輪

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

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

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

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

熔斷：每過(guò)五秒查看這五秒有沒(méi)有100次操作

顯而易見(jiàn)的，限流更加準(zhǔn)確，但是很耗費(fèi)時(shí)間，熔斷沒(méi)那么準(zhǔn)確，但是相對(duì)來(lái)說(shuō)沒(méi)那么耗時(shí)間

熔斷的應(yīng)用：

DDos攻擊：

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

解決辦法：

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

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

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

案例：心跳檢測(cè)：

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

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

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

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

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

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

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

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

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

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

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

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

也就是說(shuō)，16大小的時(shí)間輪 對(duì)于5來(lái)說(shuō)，5%16=5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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