10w定時(shí)任務(wù)，如何高效觸發(fā)超時(shí)

一、緣起

---

很多時(shí)候，業(yè)務(wù)有定時(shí)任務(wù)或者定時(shí)超時(shí)的需求，當(dāng)任務(wù)量很大時(shí)，可能需要維護(hù)大量的timer，或者進(jìn)行低效的掃描。

例如：58到家APP實(shí)時(shí)消息通道系統(tǒng)，對(duì)每個(gè)用戶會(huì)維護(hù)一個(gè)APP到服務(wù)器的TCP連接，用來(lái)實(shí)時(shí)收發(fā)消息，對(duì)這個(gè)TCP連接，有這樣一個(gè)需求：“如果連續(xù)30s沒(méi)有請(qǐng)求包（例如登錄，消息，keepalive包），服務(wù)端就要將這個(gè)用戶的狀態(tài)置為離線”。

其中，單機(jī)TCP同時(shí)在線量約在10w級(jí)別，keepalive請(qǐng)求包大概30s一次，吞吐量約在3000qps。

一般來(lái)說(shuō)怎么實(shí)現(xiàn)這類需求呢？

“輪詢掃描法”

1）用一個(gè)Map<uid, last_packet_time>來(lái)記錄每一個(gè)uid最近一次請(qǐng)求時(shí)間last_packet_time

2）當(dāng)某個(gè)用戶uid有請(qǐng)求包來(lái)到，實(shí)時(shí)更新這個(gè)Map

3）啟動(dòng)一個(gè)timer，當(dāng)Map中不為空時(shí)，輪詢掃描這個(gè)Map，看每個(gè)uid的last_packet_time是否超過(guò)30s，如果超過(guò)則進(jìn)行超時(shí)處理

“多timer觸發(fā)法”

1）用一個(gè)Map<uid, last_packet_time>來(lái)記錄每一個(gè)uid最近一次請(qǐng)求時(shí)間last_packet_time

2）當(dāng)某個(gè)用戶uid有請(qǐng)求包來(lái)到，實(shí)時(shí)更新這個(gè)Map，并同時(shí)對(duì)這個(gè)uid請(qǐng)求包啟動(dòng)一個(gè)timer，30s之后觸發(fā)

3）每個(gè)uid請(qǐng)求包對(duì)應(yīng)的timer觸發(fā)后，看Map中，查看這個(gè)uid的last_packet_time是否超過(guò)30s，如果超過(guò)則進(jìn)行超時(shí)處理

方案一：只啟動(dòng)一個(gè)timer，但需要輪詢，效率較低

方案二：不需要輪詢，但每個(gè)請(qǐng)求包要啟動(dòng)一個(gè)timer，比較耗資源

特別在同時(shí)在線量很大時(shí)，很容易CPU100%，如何高效維護(hù)和觸發(fā)大量的定時(shí)/超時(shí)任務(wù)，是本文要討論的問(wèn)題。

二、環(huán)形隊(duì)列法

---

廢話不多說(shuō)，三個(gè)重要的數(shù)據(jù)結(jié)構(gòu)：

1）30s超時(shí)，就創(chuàng)建一個(gè)index從0到30的環(huán)形隊(duì)列（本質(zhì)是個(gè)數(shù)組）

2）環(huán)上每一個(gè)slot是一個(gè)Set<uid>，任務(wù)集合

3）同時(shí)還有一個(gè)Map<uid, index>，記錄uid落在環(huán)上的哪個(gè)slot里 

同時(shí)：

1）啟動(dòng)一個(gè)timer，每隔1s，在上述環(huán)形隊(duì)列中移動(dòng)一格，0->1->2->3…->29->30->0…

2）有一個(gè)Current Index指針來(lái)標(biāo)識(shí)剛檢測(cè)過(guò)的slot

當(dāng)有某用戶uid有請(qǐng)求包到達(dá)時(shí)：

1）從Map結(jié)構(gòu)中，查找出這個(gè)uid存儲(chǔ)在哪一個(gè)slot里

2）從這個(gè)slot的Set結(jié)構(gòu)中，刪除這個(gè)uid

3）將uid重新加入到新的slot中，具體是哪一個(gè)slot呢 => Current Index指針?biāo)赶虻纳弦粋€(gè)slot，因?yàn)檫@個(gè)slot，會(huì)被timer在30s之后掃描到

4）更新Map，這個(gè)uid對(duì)應(yīng)slot的index值

哪些元素會(huì)被超時(shí)掉呢？

Current Index每秒種移動(dòng)一個(gè)slot，這個(gè)slot對(duì)應(yīng)的Set<uid>中所有uid都應(yīng)該被集體超時(shí)！如果最近30s有請(qǐng)求包來(lái)到，一定被放到Current Index的前一個(gè)slot了，Current Index所在的slot對(duì)應(yīng)Set中所有元素，都是最近30s沒(méi)有請(qǐng)求包來(lái)到的。 

所以，當(dāng)沒(méi)有超時(shí)時(shí)，Current Index掃到的每一個(gè)slot的Set中應(yīng)該都沒(méi)有元素。 

優(yōu)勢(shì)：

（1）只需要1個(gè)timer

（2）timer每1s只需要一次觸發(fā)，消耗CPU很低

（3）批量超時(shí)，Current Index掃到的slot，Set中所有元素都應(yīng)該被超時(shí)掉

三、總結(jié)

---

這個(gè)環(huán)形隊(duì)列法是一個(gè)通用的方法，Set和Map中可以是任何task，本文的uid是一個(gè)最簡(jiǎn)單的舉例。

HashedWheelTimer也是類似的原理，有興趣的同學(xué)可以百度一下這個(gè)數(shù)據(jù)結(jié)構(gòu)，Netty中的一個(gè)工具類，希望大家有收獲，幫忙轉(zhuǎn)發(fā)一下哈。