在任務調(diào)度的場景中，經(jīng)常遇到以下需求：

1、某個操作失敗后，每隔1、2、5、10、20秒去重試

2、一篇公眾號文章發(fā)布之后，要在5分鐘之后推送到粉絲終端

這種場景當然可以通過 RocketMQ 這類支持延遲消息的中間件來做，如果從任務調(diào)度的角度該怎么做，任務隊列怎么選擇呢？從題干可知以下三要素：觸發(fā)條件，延遲任務存儲，時間到達之后的操作。這是一個非常典型的生產(chǎn)者消費者模型，生產(chǎn)者往任務隊列放任務，消費者從隊列中消費任務。先拋開生產(chǎn)者、消費者不講，以下只討論任務隊列的選擇。

JAVA DelayQueue、redis Sorted Set 都是延遲任務很好的選擇，除此之外時間輪隊列也是一種非常好，也非常適合的設計。本文對 DelayQueue 和時間輪做特點分析和對比。

01. DelayQueue 延時隊列

DelayQueue 本質(zhì)是一個無界的優(yōu)先級阻塞隊列，內(nèi)部封裝了 PriorityQueue，提供了 put 接口放入任務，take 接口獲取任務。添加元素時需要設置一個延遲時間，在有任務到達執(zhí)行時間前，take 接口是阻塞的。所以 DelayQueue 實現(xiàn)延時，核心功能有：

1. 有序性，延時短的先出列2. put、take 后依然有序
3. 沒有元素到達時間，take被阻塞
4. 線程安全

第1、2點是 PriorityQueue 實現(xiàn)的，第 3、4 點是 DelayQueue 自己實現(xiàn)的。

有序性

PriorityQueue 內(nèi)部使用小頂堆來維持順序，最小堆并沒有通過二叉樹實現(xiàn)，而是使用了數(shù)組存儲 Object[] queue。每次取出最小元素的時間復雜度是 O(1)，使用數(shù)組尋址非常快，但是增刪元素時需要重排序，時間復雜度是O(logN)，最終其每次存取時間復雜度是 O(logN)。

take 元素取第 0 個

每次 put 時，需要排序達到新平衡。比較下標通過 int parent = (k - 1) >>> 1; 計算，take 也是類似的計算。

阻塞 && 線程安全

OK，明白了，當隊列為空或者到達時間之前，通過 ReentrantLock + condition 配合使用實現(xiàn) take 時線程安全和阻塞，put 時同樣使用同一把 ReentrantLock，進而 condition signal 緩存等待的線程，和AQS基本類似。

存在的問題

DelayQueue 是一個很優(yōu)秀的設計，精巧、漂亮，使用小頂堆 O(logN) 時間復雜度維持隊列有序，ReentrantLock + condition 組合保證線程安全、阻塞，高效而也沒有隊列空輪詢。這樣優(yōu)秀的設計存在什么問題？小任務量是沒有問題，當任務非常多，且高頻時就不太好了，為什么？

i. 鎖

put、take 共用一把鎖，在 take lock 生效時，是不能 put 的。什么是take lock 生效呢？在 take 過程中，有幾處 await ，一旦調(diào)用了 condition.await() 即便沒有調(diào)用 lock.unlock()，也會暫時釋放鎖，等待喚醒。此時是不會阻塞put操作的，但是，當有需要出列的元素時，put、take就會產(chǎn)生互斥，任務量大時，這倆就會產(chǎn)生性能問題。

ii. 數(shù)據(jù)結(jié)構(gòu)

PriorityQueue 使用數(shù)組來存儲元素，這是一種高效的結(jié)構(gòu)，但是要求連續(xù)空間，任務量很大時是否一定有足夠大的連續(xù)空間？如果沒有就需要 GC，或者進入老年代了。

iii. 不支持去重

同一個時間點的同一個任務，不應該在隊列出現(xiàn)兩次。

微信平臺上有多少公眾號不清楚，應該是一個很大的數(shù)字，每天早上和晚上都會產(chǎn)生大量的公眾號推送，如果使用 DelayQueue 能否滿足需要呢？恐怕很難。

02. TimeWheel 時間輪

時間輪也被廣泛用于延時任務調(diào)度，比如Kafka、Netty，同樣 XXL-JOB 也使用時間輪做任務調(diào)度。時間輪是一種非常巧妙的思想，沒有查到其出處，個人感覺應該跟「CPU 時間片輪轉(zhuǎn)調(diào)度算法」有關。基本結(jié)構(gòu)如下

時間輪基本結(jié)構(gòu)

Kafka 為了實現(xiàn)多時間跨度調(diào)度，實現(xiàn)了多級時間輪

Kafka 時間輪

時間輪類似于鐘表，上面有時分秒的刻度，秒針一秒一秒的跳，對應到秒級任務，如果刻度跨度為毫秒則可以實現(xiàn)毫秒調(diào)度。每一個刻度后面都連接著當前秒應該執(zhí)行的任務，系統(tǒng)每次都調(diào)度當前時間指針下的任務。其數(shù)據(jù)結(jié)構(gòu)就可以看成「數(shù)組+鏈表」的實現(xiàn)，時間輪是一種算法思想，在各開發(fā)語言中沒有對應的實現(xiàn)，HashMap、Dict 也可以滿足要求。XXL-JOB 就是使用的 ConcurrentHashMap<Integer,List<Integer>>。時間輪相比于 DelayQueue 怎么樣呢，又存在哪些問題，該怎么解決呢？

有序性

時間輪靠時間指針調(diào)度，不存在任務排序，每次都是取出當前刻度下的任務。每次都是O(1)，假如當前時刻下有多個任務，當前隊列需要全部彈出。

線程安全

與 DelayQueue 不同，時間輪每個刻度下都是一個獨立的隊列，各隊列的存取互不影響，可以通過線程安全的隊列來實現(xiàn)，所以存取的并發(fā)性能比 DelayQueue 高很多。

避免空輪詢

時間輪的本質(zhì)是隨著時間的推移，不斷的輪詢當前時間刻度下的任務，與 DelayQueue 不同，即使時間輪為空時，依然輪詢，會產(chǎn)生空輪詢。在 XXL-JOB 里就存在這種問題，幸好一般情況下，都是秒級調(diào)度，空輪詢也沒有大影響。但如果是毫秒級調(diào)度，空輪詢是會影響系統(tǒng)性能的，比如 epoll CPU100% 的bug 和 Netty 空輪詢bug。

任務去重

需要保證在一個時間刻度下，一個任務不能出現(xiàn)兩次，不然可能會多次調(diào)度。

時間輪實現(xiàn)

理想中的時間輪是能夠滿足以上 4 點要求，revolver 通過跳躍表數(shù)組實現(xiàn)基本結(jié)構(gòu)ConcurrentSkipListSet<Integer>[]，ConcurrentSkipListSet 是一個基于跳躍表實現(xiàn)的無鎖的線程安全的、有序列、去重的列表表，向列表put元素并排序的時間復雜度是O(logN)，ReentrantLock + condition + AtomicInteger 計數(shù)器避免空輪詢。

當任務數(shù)=0 時，調(diào)用 condition.await() take 被阻塞，當元素個數(shù)從無變成有的時候，調(diào)用 condition.signal()，也是一個典型的生產(chǎn)者消費者模型。