本系列轉(zhuǎn)載自 【架構(gòu)師之路】公眾號 By 58沈劍。

沈老師擅長用簡單的文字把常見原理講的很透徹窜司，推薦。

一、緣起

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

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

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

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

• “輪詢掃描法”

1）用一個(gè)Map來記錄每一個(gè)uid最近一次請求時(shí)間last_packet_time

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

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

• “多timer觸發(fā)法”

1）用一個(gè)Map來記錄每一個(gè)uid最近一次請求時(shí)間last_packet_time

2）當(dāng)某個(gè)用戶uid有請求包來到，實(shí)時(shí)更新這個(gè)Map喉钢，并同時(shí)對這個(gè)uid請求包啟動一個(gè)timer姆打，30s之后觸發(fā)

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

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

方案二：不需要輪詢闲延，但每個(gè)請求包要啟動一個(gè)timer，比較耗資源, 特別在同時(shí)在線量很大時(shí)韩玩，很容易CPU100%垒玲，如何高效維護(hù)和觸發(fā)大量的定時(shí)/超時(shí)任務(wù)，是本文要討論的問題啸如。

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

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

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

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

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

image

同時(shí)：

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

2）有一個(gè)Current Index指針來標(biāo)識剛檢測過的slot

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

1）從Map結(jié)構(gòu)中，查找出這個(gè)uid存儲在哪一個(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會被timer在30s之后掃描到

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

哪些元素會被超時(shí)掉呢慈参？

Current Index每秒種移動一個(gè)slot，這個(gè)slot對應(yīng)的Set中所有uid都應(yīng)該被集體超時(shí)刮萌！如果最近30s有請求包來到驮配，一定被放到Current Index的前一個(gè)slot了，Current Index所在的slot對應(yīng)Set中所有元素着茸， 都是最近30s沒有請求包來到的壮锻。

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

優(yōu)勢：

（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è)最簡單的舉例义图。

HashedWheelTimer（[https://segmentfault.com/a/1190000010987765](https://segmentfault.com/a/1190000010987765)）也是類似的原理减俏，有興趣的同學(xué)可以百度一下這個(gè)數(shù)據(jù)結(jié)構(gòu)，Netty中的一個(gè)工具類碱工，希望大家有收獲娃承，幫忙轉(zhuǎn)發(fā)一下哈。 

補(bǔ)：

Netty中增加了要給round的概念怕篷，這樣可以實(shí)現(xiàn)任意時(shí)間之后開始历筝。

image

以上圖為例，假設(shè)一個(gè)格子是1秒廊谓，則整個(gè)wheel能表示的時(shí)間段為8s梳猪，假如當(dāng)前指針指向2，此時(shí)需要調(diào)度一個(gè)3s后執(zhí)行的任務(wù)蒸痹，顯然應(yīng)該加入到(2+3=5)的方格中春弥，指針再走3次就可以執(zhí)行了呛哟；如果任務(wù)要在10s后執(zhí)行，應(yīng)該等指針走完一個(gè)round零2格再執(zhí)行匿沛，因此應(yīng)放入4扫责，同時(shí)將round（1）保存到任務(wù)中。檢查到期任務(wù)時(shí)應(yīng)當(dāng)只執(zhí)行round為0的逃呼。每次執(zhí)行之后鳖孤，格子上其他任務(wù)的round應(yīng)減1。

效率

• 添加任務(wù)：O(1)
• 刪除/取消任務(wù)：O(1)
• 過期/執(zhí)行任務(wù)：最差情況為O(n)->也就是當(dāng)HashMap里面的元素全部hash沖突抡笼，退化為一條鏈表的情況苏揣。平均O(1)