延遲隊(duì)列的需求各位應(yīng)該在日常開發(fā)的場(chǎng)景中經(jīng)常碰到。比如：
用戶登錄之后5分鐘給用戶做分類推送；
用戶多少天未登錄給用戶做召回推送；
定期檢查用戶當(dāng)前退款賬單是否被商家處理等等場(chǎng)景。
一般這種場(chǎng)景和定時(shí)任務(wù)還是有很大的區(qū)別誉察，定時(shí)任務(wù)是你知道任務(wù)多久該跑一次或者什么時(shí)候只跑一次与涡，這個(gè)時(shí)間是確定的。延遲隊(duì)列是當(dāng)某個(gè)事件發(fā)生的時(shí)候需要延遲多久觸發(fā)配套事件持偏，引子事件發(fā)生的時(shí)間不是固定的驼卖。
業(yè)界目前也有很多實(shí)現(xiàn)方案，單機(jī)版的方案就不說了鸿秆，現(xiàn)在也沒有哪個(gè)公司還是單機(jī)版的服務(wù)酌畜，今天我們一一探討各種方案的大致實(shí)現(xiàn)。
1. Redis zset
這個(gè)方案比較常用卿叽，簡(jiǎn)單有效桥胞。利用 Redis 的 sorted set 結(jié)構(gòu)，使用 timeStamp 作為 score考婴，比如你的任務(wù)是要延遲5分鐘贩虾，那么就在當(dāng)前時(shí)間上加5分鐘作為 score ，輪詢?nèi)蝿?wù)每秒只輪詢 score 大于當(dāng)前時(shí)間的 key即可沥阱，如果任務(wù)支持有誤差缎罢，那么當(dāng)沒有掃描到有效數(shù)據(jù)的時(shí)候可以休眠對(duì)應(yīng)時(shí)間再繼續(xù)輪詢。
方案優(yōu)劣：
優(yōu)點(diǎn)：
簡(jiǎn)單實(shí)用考杉，一針見血策精。
缺點(diǎn)：
- 單個(gè) zset 肯定支持不了太大的數(shù)據(jù)量，如果你有幾百萬的延遲任務(wù)需求崇棠，大哥我還是勸你換一個(gè)方案咽袜；
- 定時(shí)器輪詢方案可能會(huì)有異常終止的情況需要自己處理，同時(shí)消息處理失敗的回滾方案枕稀，您也要自己處理酬蹋。
所以及老，sorted set 的方案并不是一個(gè)成熟的方案，他只是一個(gè)快速可供落地的方案范抓。
2. RabbitMQ隊(duì)列
下面說一個(gè)可以落地的方案骄恶，這個(gè)方案也被大多數(shù)目前在架構(gòu)中使用了 RabbitMQ 的項(xiàng)目組使用。不好的一點(diǎn)就是匕垫，捆綁 RabbitMQ僧鲁，當(dāng)你的架構(gòu)方案是要用別的 MQ 替換 RabbitMQ 的時(shí)候，你就蛋疼了（我現(xiàn)在正在經(jīng)歷）象泵。
RabbitMQ 有兩個(gè)特性寞秃，一個(gè)是 Time-To-Live Extensions，另一個(gè)是 Dead Letter Exchanges偶惠。
- Time-To-Live Extensions
RabbitMQ允許我們?yōu)橄⒒蛘哧?duì)列設(shè)置TTL（time to live）春寿，也就是過期時(shí)間。TTL表明了一條消息可在隊(duì)列中存活的最大時(shí)間忽孽，單位為毫秒绑改。也就是說，當(dāng)某條消息被設(shè)置了TTL或者當(dāng)某條消息進(jìn)入了設(shè)置了TTL的隊(duì)列時(shí)兄一，這條消息會(huì)在經(jīng)過TTL秒后 “死亡”厘线，成為Dead Letter。如果既配置了消息的TTL出革，又配置了隊(duì)列的TTL造壮，那么較小的那個(gè)值會(huì)被取用。 - Dead Letter Exchanges
在 RabbitMQ 中骂束，一共有三種消息的 “死亡” 形式：
- 消息被拒絕耳璧。通過調(diào)用
basic.reject或者basic.nack并且設(shè)置的requeue參數(shù)為 false； - 消息因?yàn)樵O(shè)置了TTL而過期展箱；
- 隊(duì)列達(dá)到最大長(zhǎng)度楞抡。
DLX同一般的 Exchange 沒有區(qū)別，它能在任何的隊(duì)列上被指定，實(shí)際上就是設(shè)置某個(gè)隊(duì)列的屬性。當(dāng)隊(duì)列中有 DLX 消息時(shí)句灌，RabbitMQ就會(huì)自動(dòng)的將 DLX 消息重新發(fā)布到設(shè)置的 Exchange 中去，進(jìn)而被路由到另一個(gè)隊(duì)列竞慢，publish 可以監(jiān)聽這個(gè)隊(duì)列中消息做相應(yīng)的處理。
由上簡(jiǎn)介大家可以看出治泥，RabbitMQ本身是不支持延遲隊(duì)列的筹煮，只是他的特性讓勤勞的 中國脫發(fā)群體 急中生智（為了完成任務(wù)）弄出了這么一套可用的方案。
可用的方案就是：
- 如果有事件需要延遲那么將該事件發(fā)送到MQ 隊(duì)列中居夹，為需要延遲的消息設(shè)置一個(gè)TTL败潦；
- TTL到期后就會(huì)自動(dòng)進(jìn)入設(shè)置好的DLX本冲，然后由DLX轉(zhuǎn)發(fā)到配置好的實(shí)際消費(fèi)隊(duì)列；
- 消費(fèi)該隊(duì)列的延遲消息劫扒，處理事件檬洞。
方案優(yōu)劣：
優(yōu)點(diǎn)：
大品牌組件，用的放心沟饥。如果面臨大數(shù)據(jù)量需求可以很容易的橫向擴(kuò)展添怔，同時(shí)消息支持持久化，有問題可回滾贤旷。
缺點(diǎn)：
- 配置麻煩广料，額外增加一個(gè)死信交換機(jī)和一個(gè)死信隊(duì)列的配置；
- RabbitMQ 是一個(gè)消息中間件幼驶，TTL 和 DLX 只是他的一個(gè)特性艾杏，將延遲隊(duì)列綁定在一個(gè)功能軟件的某一個(gè)特性上，可能會(huì)有風(fēng)險(xiǎn)盅藻。不要杠购桑，當(dāng)你們組不用 RabbitMQ 的時(shí)候遷移很痛苦；
- 消息隊(duì)列具有先進(jìn)先出的特點(diǎn)萧求，如果第一個(gè)進(jìn)入隊(duì)列的消息 A 的延遲是10分鐘其兴，第二個(gè)進(jìn)入隊(duì)列的消息B 的延遲是5分鐘顶瞒，期望的是誰先到 TTL誰先出夸政，但是事實(shí)是B已經(jīng)到期了，而還要等到 A 的延遲10分鐘結(jié)束A先出之后榴徐，B 才能出守问。所以在設(shè)計(jì)的時(shí)候需要考慮不同延遲的消息要放到不同的隊(duì)列。另外該問題官方已經(jīng)給出了插件來支持：插件地址坑资。
3. 基于 Netty#HashedWheelTimer類方法的實(shí)現(xiàn)
HashedWheelTimer 是 Netty 中 的一個(gè)基礎(chǔ)工具類耗帕，主要用來高效處理大量定時(shí)任務(wù)，且任務(wù)對(duì)時(shí)間精度要求相對(duì)不高袱贮， 在Netty 中的應(yīng)用場(chǎng)景就是連接超時(shí)或者任務(wù)處理超時(shí)仿便，一般都是操作比較快速的任務(wù)，缺點(diǎn)是內(nèi)存占用相對(duì)較高攒巍。
算法思想
HashedWheelTimer 主要還是一個(gè) DelayQueue 和一個(gè)時(shí)間輪算法組合嗽仪。
Hash Wheel Timer是一個(gè)環(huán)形結(jié)構(gòu)，可以想象成時(shí)鐘柒莉，分為很多格子闻坚，一個(gè)格子代表一段時(shí)間（越短Timer精度越高），并用一個(gè)List保存在該格子上到期的所有任務(wù)兢孝。同時(shí)一個(gè)指針隨著時(shí)間流逝一格一格轉(zhuǎn)動(dòng)窿凤，并執(zhí)行對(duì)應(yīng)List中所有到期的任務(wù)仅偎。
以上圖為例，假設(shè)一個(gè)格子是1s雳殊，則整個(gè)時(shí)間輪能表示的時(shí)間段16s橘沥。當(dāng)前任務(wù)指向格子2，表明在第2s的時(shí)候有任務(wù)需要執(zhí)行相种。任務(wù)列表中有兩個(gè)任務(wù)威恼，每個(gè)任務(wù)前面的數(shù)字表示圈數(shù)。2表示當(dāng)走到第2圈的時(shí)候才會(huì)執(zhí)行寝并，那么整個(gè)任務(wù)的真正執(zhí)行時(shí)間其實(shí)是在12s之后執(zhí)行箫措，即第二圈走到2的時(shí)候。每推進(jìn)一格衬潦，對(duì)應(yīng)的每一個(gè) slot 中的round數(shù)都要減一斤蔓。整體算法就是這么個(gè)邏輯。
時(shí)間輪設(shè)計(jì)要點(diǎn)：
- tick镀岛，一次時(shí)間推進(jìn)弦牡，每次推進(jìn)會(huì)檢查/執(zhí)行超時(shí)任務(wù)；
- tickDuration漂羊，時(shí)間輪推進(jìn)的最小單元驾锰，每隔 tickDuration 會(huì)有一次 tick，它決定了時(shí)間輪的精確程度走越；
- bucket（ticksPerWheel）椭豫，上圖中的每一隔就是一個(gè)bucket，表示一個(gè)時(shí)間輪可以有多少個(gè)tick旨指，它是存儲(chǔ)任務(wù)的最小單元赏酥；
- 上層時(shí)間輪的 tickDuration 是下層時(shí)間輪的表示時(shí)間的最大范圍，即：父 tickDuration = 子 tickDuration * 子 bucket 谆构。
需要注意的是裸扶，這種方式任務(wù)是串行執(zhí)行的。意味著你如果在時(shí)間輪中執(zhí)行任務(wù)且任務(wù)耗時(shí)較長(zhǎng)搬素，將會(huì)出現(xiàn)調(diào)度超時(shí)或者任務(wù)堆積的情況呵晨。所以要將任務(wù)的執(zhí)行異步化。
算法的要點(diǎn)：
- 任務(wù)并不是直接放在格子中的熬尺，而是維護(hù)了一個(gè)雙向鏈表摸屠，這種數(shù)據(jù)結(jié)構(gòu)非常便于插入和移除；
- 新添加的任務(wù)并不直接放入格子猪杭，而是先放入一個(gè)隊(duì)列中餐塘，這是為了避免多線程插入任務(wù)的沖突。在每個(gè)tick運(yùn)行任務(wù)之前由worker線程自動(dòng)對(duì)任務(wù)進(jìn)行歸集和分類皂吮，插入到對(duì)應(yīng)的槽位里面戒傻。
Netty 使用數(shù)組 + 雙向鏈表的方式來組織時(shí)間輪税手，對(duì)于添加/取消操作僅做了記錄，真正的操作實(shí)際發(fā)生在下一個(gè)tick需纳。時(shí)間的推進(jìn)是獨(dú)立的線程在做芦倒，該線程同時(shí)也負(fù)責(zé)過期任務(wù)的執(zhí)行等操作，可簡(jiǎn)單認(rèn)為此步驟操作為O(n)不翩，因?yàn)橥七M(jìn)線程需要完全遍歷timeouts兵扬、cancelledTimeouts與bucket鏈表，在遍歷timeouts時(shí)口蝠，Netty為了避免任務(wù)過多器钟，所以限制每次最多遍歷10萬個(gè)，也就是說妙蔗，一個(gè)tick只能規(guī)劃10萬個(gè)任務(wù)傲霸，當(dāng)任務(wù)量過大時(shí)，會(huì)存在超時(shí)任務(wù)執(zhí)行時(shí)間延遲的現(xiàn)象眉反。
方案優(yōu)劣：
優(yōu)點(diǎn)：
實(shí)現(xiàn)比較優(yōu)雅昙啄。效率高。
缺點(diǎn)：
- 無法實(shí)現(xiàn)HA和橫向擴(kuò)展寸五，要么就使用多個(gè)時(shí)間輪梳凛。
- 最重要的是，實(shí)現(xiàn)也比較復(fù)雜梳杏，開發(fā)者需要考慮所有可能的情況韧拒。
目前我了解到的延遲隊(duì)列在生產(chǎn)環(huán)境下有如上三種實(shí)現(xiàn)方式，每一種都有人在使用秘狞。當(dāng)然沒有最好的只有最適合的叭莫，你覺得 redis 能滿足需求蹈集，就按照最簡(jiǎn)單的來烁试，你要是有充足的開發(fā)周期，你也可以實(shí)現(xiàn)時(shí)間輪展現(xiàn)實(shí)力拢肆。
需求千萬種减响，變化就一種：給時(shí)間都能做。
