前言

延遲隊(duì)列是我們?nèi)粘ｉ_發(fā)過程中，經(jīng)常接觸并需要使用到的一種技術(shù)方案。前些時(shí)間在開發(fā)業(yè)務(wù)需求時(shí)，我也遇到了一個(gè)需要使用到延遲消息隊(duì)列的需求場景，因此我也在網(wǎng)上調(diào)研了一系列不同的延遲隊(duì)列的實(shí)現(xiàn)方案，在此進(jìn)行了一個(gè)總結(jié)并且給大家進(jìn)行分享。

 

 

延遲隊(duì)列定義

首先，隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)相信大家都不陌生，它是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。普通隊(duì)列中的元素是有序的，先進(jìn)入隊(duì)列中的元素會(huì)被優(yōu)先取出進(jìn)行消費(fèi)；

延時(shí)隊(duì)列相比于普通隊(duì)列最大的區(qū)別就體現(xiàn)在其延時(shí)的屬性上，普通隊(duì)列的元素是先進(jìn)先出，按入隊(duì)順序進(jìn)行處理，而延時(shí)隊(duì)列中的元素在入隊(duì)時(shí)會(huì)指定一個(gè)延遲時(shí)間，表示其希望能夠在經(jīng)過該指定時(shí)間后處理。從某種意義上來講，延遲隊(duì)列的結(jié)構(gòu)并不像一個(gè)隊(duì)列，而更像是一種以時(shí)間為權(quán)重的有序堆結(jié)構(gòu)。

應(yīng)用場景

我在開發(fā)業(yè)務(wù)需求時(shí)遇到的使用場景是這樣的，用戶可以在小程序中訂閱不同的微信或者 QQ 的模板消息，產(chǎn)品同學(xué)可以在小程序的管理端新建消息推送計(jì)劃，當(dāng)?shù)竭_(dá)指定的時(shí)間節(jié)點(diǎn)的時(shí)候給所有訂閱模板消息的用戶進(jìn)行消息推送。

如果僅僅是服務(wù)單一的小程序，那也許起個(gè)定時(shí)任務(wù)，或者甚至人工的定時(shí)去執(zhí)行能夠最便捷最快速的去完成這項(xiàng)需求，但我們希望能夠抽象出一個(gè)消息訂閱的模塊服務(wù)出來給所有業(yè)務(wù)使用，這時(shí)候就需要一種通用的系統(tǒng)的解決方案，這時(shí)候便需要使用到延遲隊(duì)列了。

除了上述我所遇到的這樣的典型的需求以外，延遲隊(duì)列的應(yīng)用場景其實(shí)也非常的廣泛，比如說以下的場景：

1. 新建的訂單，如果用戶在 15 分鐘內(nèi)未支付，則自動(dòng)取消。
2. 公司的會(huì)議預(yù)定系統(tǒng)，在會(huì)議預(yù)定成功后，會(huì)在會(huì)議開始前半小時(shí)通知所有預(yù)定該會(huì)議的用戶。
3. 安全工單超過 24 小時(shí)未處理，則自動(dòng)拉企業(yè)微信群提醒相關(guān)責(zé)任人。
4. 用戶下單外賣以后，距離超時(shí)時(shí)間還有 10 分鐘時(shí)提醒外賣小哥即將超時(shí)。

對于數(shù)據(jù)量比較少并且時(shí)效性要求不那么高的場景，一種比較簡單的方式是輪詢數(shù)據(jù)庫，比如每秒輪詢一下數(shù)據(jù)庫中所有數(shù)據(jù)，處理所有到期的數(shù)據(jù)，比如如果我是公司內(nèi)部的會(huì)議預(yù)定系統(tǒng)的開發(fā)者，我可能就會(huì)采用這種方案，因?yàn)檎麄€(gè)系統(tǒng)的數(shù)據(jù)量必然不會(huì)很大并且會(huì)議開始前提前 30 分鐘提醒與提前 29 分鐘提醒的差別并不大。

但是如果需要處理的數(shù)據(jù)量比較大實(shí)時(shí)性要求比較高，比如淘寶每天的所有新建訂單 15 分鐘內(nèi)未支付的自動(dòng)超時(shí)，數(shù)量級高達(dá)百萬甚至千萬，這時(shí)候如果你還敢輪詢數(shù)據(jù)庫怕是要被你老板打死，不被老板打死估計(jì)也要被運(yùn)維同學(xué)打死。

這種場景下，就需要使用到我們今天的主角 —— 延遲隊(duì)列了。延遲隊(duì)列為我們提供了一種高效的處理大量需要延遲消費(fèi)消息的解決方案。那么話不多說，下面我們就來看一下幾種常見的延遲隊(duì)列的解決方案以及他們各自的優(yōu)缺點(diǎn)。

實(shí)現(xiàn)方案

Redis ZSet

我們知道 Redis 有一個(gè)有序集合的數(shù)據(jù)結(jié)構(gòu) ZSet，ZSet 中每個(gè)元素都有一個(gè)對應(yīng) Score，ZSet 中所有元素是按照其 Score 進(jìn)行排序的。

那么我們可以通過以下這幾個(gè)操作使用 Redis 的 ZSet 來實(shí)現(xiàn)一個(gè)延遲隊(duì)列：

1. 入隊(duì)操作： ZADD KEY timestamp task , 我們將需要處理的任務(wù)，按其需要延遲處理時(shí)間作為 Score 加入到 ZSet 中。Redis 的 ZAdd 的時(shí)間復(fù)雜度是 O(logN) ， N 是 ZSet 中元素個(gè)數(shù)，因此我們能相對比較高效的進(jìn)行入隊(duì)操作。
2. 起一個(gè)進(jìn)程定時(shí)（比如每隔一秒）通過 ZREANGEBYSCORE 方法查詢 ZSet 中 Score 最小的元素，具體操作為： ZRANGEBYSCORE KEY -inf +inf limit 0 1 WITHSCORES 。查詢結(jié)果有兩種情況： 
   a. 查詢出的分?jǐn)?shù)小于等于當(dāng)前時(shí)間戳，說明到這個(gè)任務(wù)需要執(zhí)行的時(shí)間了，則去異步處理該任務(wù)； 
   b. 查詢出的分?jǐn)?shù)大于當(dāng)前時(shí)間戳，由于剛剛的查詢操作取出來的是分?jǐn)?shù)最小的元素，所以說明 ZSet 中所有的任務(wù)都還沒有到需要執(zhí)行的時(shí)間，則休眠一秒后繼續(xù)查詢； 
   同樣的， ZRANGEBYSCORE 操作的時(shí)間復(fù)雜度為 O(logN + M) ，其中 N 為 ZSet 中元素個(gè)數(shù)， M 為查詢的元素個(gè)數(shù)，因此我們定時(shí)查詢操作也是比較高效的。

這里從網(wǎng)上搬運(yùn)了一套 Redis 實(shí)現(xiàn)延遲隊(duì)列的后端架構(gòu)，其在原來 Redis 的 ZSet 實(shí)現(xiàn)上進(jìn)行了一系列的優(yōu)化，使得整個(gè)系統(tǒng)更穩(wěn)定、更健壯，能夠應(yīng)對高并發(fā)場景，并且具有更好的可擴(kuò)展性，是一個(gè)挺不錯(cuò)的架構(gòu)設(shè)計(jì)，其整體架構(gòu)圖如下：

 

 

其核心設(shè)計(jì)思路：

1. 將延遲的消息任務(wù)通過 hash 算法路由至不同的 Redis Key 上，這樣做有兩大好處： 
   a. 避免了當(dāng)一個(gè) KEY 在存儲(chǔ)了較多的延時(shí)消息后，入隊(duì)操作以及查詢操作速度變慢的問題（兩個(gè)操作的時(shí)間復(fù)雜度均為 O(logN) ）。 
   b. 系統(tǒng)具有了更好的橫向可擴(kuò)展性，當(dāng)數(shù)據(jù)量激增時(shí)，我們可以通過增加 Redis Key 的數(shù)量來快速的擴(kuò)展整個(gè)系統(tǒng)，來抗住數(shù)據(jù)量的增長。
2. 每個(gè) Redis Key 都對應(yīng)建立一個(gè)處理進(jìn)程，稱為 Event 進(jìn)程，通過上述步驟 2 中所述的 ZRANGEBYSCORE 方法輪詢 Key，查詢是否有待處理的延遲消息。
3. 所有的 Event 進(jìn)程只負(fù)責(zé)分發(fā)消息，具體的業(yè)務(wù)邏輯通過一個(gè)額外的消息隊(duì)列異步處理，這么做的好處也是顯而易見的： 
   a. 一方面，Event 進(jìn)程只負(fù)責(zé)分發(fā)消息，那么其處理消息的速度就會(huì)非常快，就不太會(huì)出現(xiàn)因?yàn)闃I(yè)務(wù)邏輯復(fù)雜而導(dǎo)致消息堆積的情況。 
   b. 另一方面，采用一個(gè)額外的消息隊(duì)列后，消息處理的可擴(kuò)展性也會(huì)更好，我們可以通過增加消費(fèi)者進(jìn)程數(shù)量來擴(kuò)展整個(gè)系統(tǒng)的消息處理能力。
4. Event 進(jìn)程采用 Zookeeper 選主單進(jìn)程部署的方式，避免 Event 進(jìn)程宕機(jī)后，Redis Key 中消息堆積的情況。一旦 Zookeeper 的 leader 主機(jī)宕機(jī)，Zookeeper 會(huì)自動(dòng)選擇新的 leader 主機(jī)來處理 Redis Key 中的消息。

從上述的討論中我們可以看到，通過 Redis Zset 實(shí)現(xiàn)延遲隊(duì)列是一種理解起來較為直觀，可以快速落地的方案。并且我們可以依賴 Redis 自身的持久化來實(shí)現(xiàn)持久化，使用 Redis 集群來支持高并發(fā)和高可用，是一種不錯(cuò)的延遲隊(duì)列的實(shí)現(xiàn)方案。

RabbitMQ

RabbitMQ 本身并不直接提供對延遲隊(duì)列的支持，我們依靠 RabbitMQ 的 TTL 以及 死信隊(duì)列功能，來實(shí)現(xiàn)延遲隊(duì)列的效果。那就讓我們首先來了解一下，RabbitMQ 的死信隊(duì)列以及 TTL 功能。

死信隊(duì)列

死信隊(duì)列實(shí)際上是一種 RabbitMQ 的消息處理機(jī)制，當(dāng) RabbmitMQ 在生產(chǎn)和消費(fèi)消息的時(shí)候，消息遇到如下的情況，就會(huì)變成“死信”：

1. 消息被拒絕 basic.reject/ basic.nack 并且不再重新投遞 requeue=false
2. 消息超時(shí)未消費(fèi)，也就是 TTL 過期了
3. 消息隊(duì)列到達(dá)最大長度

消息一旦變成一條死信，便會(huì)被重新投遞到死信交換機(jī)（Dead-Letter-Exchange），然后死信交換機(jī)根據(jù)綁定規(guī)則轉(zhuǎn)發(fā)到對應(yīng)的死信隊(duì)列上，監(jiān)聽該隊(duì)列就可以讓消息被重新消費(fèi)。

消息生存時(shí)間 TTL

TTL（Time-To-Live）是 RabbitMQ 的一種高級特性，表示了一條消息的最大生存時(shí)間，單位為毫秒。如果一條消息在 TTL 設(shè)置的時(shí)間內(nèi)沒有被消費(fèi)，那么它就會(huì)變成一條死信，進(jìn)入我們上面所說的死信隊(duì)列。

有兩種不同的方式可以設(shè)置消息的 TTL 屬性，一種方式是直接在創(chuàng)建隊(duì)列的時(shí)候設(shè)置整個(gè)隊(duì)列的 TTL 過期時(shí)間，所有進(jìn)入隊(duì)列的消息，都被設(shè)置成了統(tǒng)一的過期時(shí)間，一旦消息過期，馬上就會(huì)被丟棄，進(jìn)入死信隊(duì)列，參考代碼如下：

Map<String, Object> args = new HashMap<String, Object>(); 
args.put("x-message-ttl", 6000); 
channel.queueDeclare(queueName, durable, exclusive, autoDelete, args); 

在延遲隊(duì)列的延遲時(shí)間為固定值的時(shí)候，比較適合使用這種方式。

另一種方式是針對單條消息設(shè)置，參考代碼如下，該消息被設(shè)置了 6 秒的過期時(shí)間：

AMQP.BasicProperties.Builder builder = new AMQP.BasicProperties.Builder(); 
builder.expiration("6000"); 
AMQP.BasicProperties properties = builder.build(); 
channel.basicPublish(exchangeName, routingKey, mandatory, properties, "msg content".getBytes()); 

如果需要不同的消息設(shè)置不同的延遲時(shí)間，上面針對隊(duì)列的 TTL 設(shè)置便無法滿足我們的需求，需要使用這種針對單個(gè)消息的 TTL 設(shè)置。

不過需要注意的是，使用這種方式設(shè)置的 TTL，消息可能不會(huì)按時(shí)死亡，因?yàn)?RabbitMQ 只會(huì)檢查第一個(gè)消息是否過期。比如這種情況，第一個(gè)消息設(shè)置了 20s 的 TTL，第二個(gè)消息設(shè)置了 10s 的 TTL，那么 RabbitMQ 會(huì)等到第一個(gè)消息過期之后，才會(huì)讓第二個(gè)消息過期。

解決這個(gè)問題的方法也很簡單，只需要安裝 RabbitMQ 的一個(gè)插件即可：

https://www.rabbitmq.com/community-plugins.html

安裝好這個(gè)插件后，所有的消息就都能按照被設(shè)置的 TTL 過期了。

RabbitMQ 實(shí)現(xiàn)延遲隊(duì)列

好了，介紹完 RabbitMQ 的死信隊(duì)列以及 TTL 這兩種特性之后，我們離實(shí)現(xiàn)延遲隊(duì)列就只差一步之遙了。

聰明的讀者可能已經(jīng)發(fā)現(xiàn)了，TTL 不就是延遲隊(duì)列中消息要延遲的時(shí)間么？如果我們把需要延遲的消息，將 TTL 設(shè)置為其延遲時(shí)間，投遞到 RabbitMQ 的普通隊(duì)列中，一直不去消費(fèi)它，那么經(jīng)過 TTL 的時(shí)間后，消息就會(huì)自動(dòng)被投遞到死信隊(duì)列，這時(shí)候我們使用消費(fèi)者進(jìn)程實(shí)時(shí)地去消費(fèi)死信隊(duì)列中的消息，不就實(shí)現(xiàn)了延遲隊(duì)列的效果。

從下圖可以直觀的看出使用 RabbitMQ 實(shí)現(xiàn)延遲隊(duì)列的整體流程：

 

 

使用 RabbitMQ 來實(shí)現(xiàn)延遲隊(duì)列，我們可以很好的利用一些 RabbitMQ 的特性，比如消息可靠發(fā)送、消息可靠投遞、死信隊(duì)列來保障消息至少被消費(fèi)一次以及未被正確處理的消息不會(huì)被丟棄。另外，通過 RabbitMQ 集群的特性，可以很好的解決單點(diǎn)故障問題，不會(huì)因?yàn)閱蝹€(gè)節(jié)點(diǎn)掛掉導(dǎo)致延遲隊(duì)列不可用或者消息丟失。

TimeWheel

TimeWheel 時(shí)間輪算法，是一種實(shí)現(xiàn)延遲隊(duì)列的巧妙且高效的算法，被應(yīng)用在 Netty，Zookeeper，Kafka 等各種框架中。

時(shí)間輪

 

 

如上圖所示，時(shí)間輪是一個(gè)存儲(chǔ)延遲消息的環(huán)形隊(duì)列，其底層采用數(shù)組實(shí)現(xiàn)，可以高效循環(huán)遍歷。這個(gè)環(huán)形隊(duì)列中的每個(gè)元素對應(yīng)一個(gè)延遲任務(wù)列表，這個(gè)列表是一個(gè)雙向環(huán)形鏈表，鏈表中每一項(xiàng)都代表一個(gè)需要執(zhí)行的延遲任務(wù)。

時(shí)間輪會(huì)有表盤指針，表示時(shí)間輪當(dāng)前所指時(shí)間，隨著時(shí)間推移，該指針會(huì)不斷前進(jìn)，并處理對應(yīng)位置上的延遲任務(wù)列表。

添加延遲任務(wù)

由于時(shí)間輪的大小固定，并且時(shí)間輪中每個(gè)元素都是一個(gè)雙向環(huán)形鏈表，我們可以在 O(1) 的時(shí)間復(fù)雜度下向時(shí)間輪中添加延遲任務(wù)。

如下圖，例如我們有一個(gè)這樣的時(shí)間輪，在表盤指針指向當(dāng)前時(shí)間為 2 時(shí)，我們需要新添加一個(gè)延遲 3 秒的任務(wù)，我們可以快速計(jì)算出延遲任務(wù)在時(shí)間輪中所對應(yīng)的位置為 5，并添加到位置 5 上任務(wù)列表尾部。

 

 

多層時(shí)間輪

到現(xiàn)在為止一切都非常棒，但是細(xì)心的同學(xué)可能發(fā)現(xiàn)了，上面的時(shí)間輪的大小是固定的，只有 12 秒。如果此時(shí)我們有一個(gè)需要延遲 200 秒的任務(wù)，我們應(yīng)該怎么處理呢？直接擴(kuò)充整個(gè)時(shí)間輪的大小嗎？這顯然不可取，因?yàn)檫@樣做的話我們就需要維護(hù)一個(gè)非常非常大的時(shí)間輪，內(nèi)存是不可接受的，而且底層數(shù)組大了之后尋址效率也會(huì)降低，影響性能。

為此，Kafka 引入了多層時(shí)間輪的概念。其實(shí)多層時(shí)間輪的概念和我們的機(jī)械表上時(shí)針、分針、秒針的概念非常類似，當(dāng)僅使用秒針無法表示當(dāng)前時(shí)間時(shí)，就使用分針結(jié)合秒針一起表示。同樣的，當(dāng)任務(wù)的到期時(shí)間超過了當(dāng)前時(shí)間輪所表示的時(shí)間范圍時(shí)，就會(huì)嘗試添加到上層時(shí)間輪中，如下圖所示：

 

 

第一層時(shí)間輪整個(gè)時(shí)間輪所表示時(shí)間范圍是 0-12 秒，第二層時(shí)間輪每格能表示的時(shí)間范圍是整個(gè)第一層時(shí)間輪所表示的范圍也就是 12 秒，所以整個(gè)第二層時(shí)間輪能表示的時(shí)間范圍即 12*12=144 秒，依次類推第三層時(shí)間輪能表示的范圍是 1728 秒，第四層為 20736 秒等等。

比如現(xiàn)在我們需要添加一個(gè)延時(shí)為 200 秒的延遲消息，我們發(fā)現(xiàn)其已經(jīng)超過了第一層時(shí)間輪能表示的時(shí)間范圍，我們就需要繼續(xù)往上層時(shí)間輪看，將其添加在第二層時(shí)間輪 200/12 = 17 的位置，然后我們發(fā)現(xiàn) 17 也超過了第二次時(shí)間輪的表示范圍，那么我們就需要繼續(xù)往上層看，將其添加在第三層時(shí)間輪的 17/12 = 2 的位置。

Kafka 中時(shí)間輪算法添加延遲任務(wù)以及推動(dòng)時(shí)間輪滾動(dòng)的核心流程如下，其中 Bucket 即時(shí)間輪中的延遲任務(wù)隊(duì)列，并且 Kafka 引入的 DelayQueue 解決了多數(shù) Bucket 為空導(dǎo)致的時(shí)間輪滾動(dòng)效率低下的問題：

 

 

使用時(shí)間輪實(shí)現(xiàn)的延遲隊(duì)列，能夠支持大量任務(wù)的高效觸發(fā)。并且在 Kafka 的時(shí)間輪算法的實(shí)現(xiàn)方案中，還引入了 DelayQueue，使用 DelayQueue 來推送時(shí)間輪滾動(dòng)，而延遲任務(wù)的添加與刪除操作都放在時(shí)間輪中，這樣的設(shè)計(jì)大幅提升了整個(gè)延遲隊(duì)列的執(zhí)行效率。

總結(jié)

延遲隊(duì)列在我們?nèi)粘ｉ_發(fā)中應(yīng)用非常廣泛，本文介紹了三種不同的實(shí)現(xiàn)延遲隊(duì)列的方案，三種方案各自有各自的特點(diǎn)，例如 Redis 的實(shí)現(xiàn)方案理解起來最為簡單，能夠快速落地，但 Redis 畢竟是基于內(nèi)存的，雖然有數(shù)據(jù)持久化方案，但還是有數(shù)據(jù)丟失的可能性。而 RabbitMQ 的實(shí)現(xiàn)方案，由于 RabbitMQ 本身的消息可靠發(fā)送、消息可靠投遞、死信隊(duì)列等特性，可以保障消息至少被消費(fèi)一次以及未被正確處理的消息不會(huì)被丟棄，讓消息的可靠性有了保障。最后 Kafka 的時(shí)間輪算法，個(gè)人覺得是三種實(shí)現(xiàn)方案中最難理解但也不失為一種非常巧妙實(shí)現(xiàn)方案。 最后， 希望以上這些內(nèi)容，能幫助大家在實(shí)現(xiàn)自己的延遲隊(duì)列時(shí)提供一點(diǎn)思路。