轉(zhuǎn)自架構(gòu)師之路
一馒稍、緣起
很多時(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連接，用來實(shí)時(shí)收發(fā)消息不见，對(duì)這個(gè)TCP連接澳化，有這樣一個(gè)需求：“如果連續(xù)30s沒有請(qǐng)求包（例如登錄，消息稳吮，keepalive包）缎谷，服務(wù)端就要將這個(gè)用戶的狀態(tài)置為離線”。
其中灶似，單機(jī)TCP同時(shí)在線量約在10w級(jí)別列林，keepalive請(qǐng)求包大概30s一次，吞吐量約在3000qps酪惭。
一般來說怎么實(shí)現(xiàn)這類需求呢希痴？
“輪詢掃描法”
1）用一個(gè)Map<uid, last_packet_time>來記錄每一個(gè)uid最近一次請(qǐng)求時(shí)間last_packet_time
2）當(dāng)某個(gè)用戶uid有請(qǐng)求包來到，實(shí)時(shí)更新這個(gè)Map
3）啟動(dòng)一個(gè)timer春感，當(dāng)Map中不為空時(shí)砌创，輪詢掃描這個(gè)Map虏缸，看每個(gè)uid的last_packet_time是否超過30s，如果超過則進(jìn)行超時(shí)處理“多timer觸發(fā)法”
1）用一個(gè)Map<uid, last_packet_time>來記錄每一個(gè)uid最近一次請(qǐng)求時(shí)間last_packet_time
2）當(dāng)某個(gè)用戶uid有請(qǐng)求包來到嫩实，實(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是否超過30s，如果超過則進(jìn)行超時(shí)處理
方案一：只啟動(dòng)一個(gè)timer竟纳，但需要輪詢撵溃，效率較低
方案二：不需要輪詢，但每個(gè)請(qǐng)求包要啟動(dòng)一個(gè)timer锥累，比較耗資源
特別在同時(shí)在線量很大時(shí)缘挑，很容易CPU100%，如何高效維護(hù)和觸發(fā)大量的定時(shí)/超時(shí)任務(wù)桶略，是本文要討論的問題语淘。
二、環(huán)形隊(duì)列法
廢話不多說际歼，三個(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指針來標(biāo)識(shí)剛檢測(cè)過的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)求包來到池充，一定被放到Current Index的前一個(gè)slot了，Current Index所在的slot對(duì)應(yīng)Set中所有元素缎讼，都是最近30s沒有請(qǐng)求包來到的矮燎。
所以飞几，當(dāng)沒有超時(shí)時(shí)吭服，Current Index掃到的每一個(gè)slot的Set中應(yīng)該都沒有元素。
優(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è)工具類奋姿。
