在任務(wù)調(diào)度的場(chǎng)景中，經(jīng)常遇到以下需求：
1、某個(gè)操作失敗后，每隔1、2、5、10、20秒去重試
2、一篇公眾號(hào)文章發(fā)布之后，要在5分鐘之后推送到粉絲終端
這種場(chǎng)景當(dāng)然可以通過(guò) RocketMQ 這類(lèi)支持延遲消息的中間件來(lái)做，如果從任務(wù)調(diào)度的角度該怎么做，任務(wù)隊(duì)列怎么選擇呢？從題干可知以下三要素：觸發(fā)條件，延遲任務(wù)存儲(chǔ)，時(shí)間到達(dá)之后的操作。這是一個(gè)非常典型的生產(chǎn)者消費(fèi)者模型，生產(chǎn)者往任務(wù)隊(duì)列放任務(wù)，消費(fèi)者從隊(duì)列中消費(fèi)任務(wù)。先拋開(kāi)生產(chǎn)者、消費(fèi)者不講，以下只討論任務(wù)隊(duì)列的選擇。
JAVA DelayQueue、redis Sorted Set 都是延遲任務(wù)很好的選擇，除此之外時(shí)間輪隊(duì)列也是一種非常好，也非常適合的設(shè)計(jì)。本文對(duì) DelayQueue 和 時(shí)間輪做特點(diǎn)分析和對(duì)比。
01. DelayQueue 延時(shí)隊(duì)列
DelayQueue 本質(zhì)是一個(gè)無(wú)界的優(yōu)先級(jí)阻塞隊(duì)列，內(nèi)部封裝了 PriorityQueue，提供了 put 接口放入任務(wù)，take 接口獲取任務(wù)。添加元素時(shí)需要設(shè)置一個(gè)延遲時(shí)間，在有任務(wù)到達(dá)執(zhí)行時(shí)間前，take 接口是阻塞的。所以 DelayQueue 實(shí)現(xiàn)延時(shí)，核心功能有：
1. 有序性，延時(shí)短的先出列2. put、take 后依然有序
3. 沒(méi)有元素到達(dá)時(shí)間，take被阻塞
4. 線程安全
第1、2點(diǎn)是 PriorityQueue 實(shí)現(xiàn)的，第 3、4 點(diǎn)是 DelayQueue 自己實(shí)現(xiàn)的。
- 有序性
PriorityQueue 內(nèi)部使用小頂堆來(lái)維持順序，最小堆并沒(méi)有通過(guò)二叉樹(shù)實(shí)現(xiàn)，而是使用了數(shù)組存儲(chǔ) Object[] queue。每次取出最小元素的時(shí)間復(fù)雜度是 O(1)，使用數(shù)組尋址非?？?，但是增刪元素時(shí)需要重排序，時(shí)間復(fù)雜度是O(logN)，最終其每次存取時(shí)間復(fù)雜度是 O(logN)。
take 元素取第 0 個(gè)
每次 put 時(shí)，需要排序達(dá)到新平衡。比較下標(biāo)通過(guò) int parent = (k - 1) >>> 1; 計(jì)算，take 也是類(lèi)似的計(jì)算。
- 阻塞 && 線程安全
OK，明白了，當(dāng)隊(duì)列為空或者到達(dá)時(shí)間之前，通過(guò) ReentrantLock + condition 配合使用實(shí)現(xiàn) take 時(shí)線程安全和阻塞，put 時(shí)同樣使用同一把 ReentrantLock，進(jìn)而 condition signal 緩存等待的線程，和AQS基本類(lèi)似。
- 存在的問(wèn)題
DelayQueue 是一個(gè)很優(yōu)秀的設(shè)計(jì)，精巧、漂亮，使用小頂堆 O(logN) 時(shí)間復(fù)雜度維持隊(duì)列有序，ReentrantLock + condition 組合保證線程安全、阻塞，高效而也沒(méi)有隊(duì)列空輪詢。這樣優(yōu)秀的設(shè)計(jì)存在什么問(wèn)題？小任務(wù)量是沒(méi)有問(wèn)題，當(dāng)任務(wù)非常多，且高頻時(shí)就不太好了，為什么？
i. 鎖
put、take 共用一把鎖，在 take lock 生效時(shí)，是不能 put 的。什么是take lock 生效呢？在 take 過(guò)程中，有幾處 await ，一旦調(diào)用了 condition.await() 即便沒(méi)有調(diào)用 lock.unlock()，也會(huì)暫時(shí)釋放鎖，等待喚醒。此時(shí)是不會(huì)阻塞put操作的，但是，當(dāng)有需要出列的元素時(shí)，put、take就會(huì)產(chǎn)生互斥，任務(wù)量大時(shí)，這倆就會(huì)產(chǎn)生性能問(wèn)題。
ii. 數(shù)據(jù)結(jié)構(gòu)
PriorityQueue 使用數(shù)組來(lái)存儲(chǔ)元素，這是一種高效的結(jié)構(gòu)，但是要求連續(xù)空間，任務(wù)量很大時(shí)是否一定有足夠大的連續(xù)空間？如果沒(méi)有就需要 GC，或者進(jìn)入老年代了。
iii. 不支持去重
同一個(gè)時(shí)間點(diǎn)的同一個(gè)任務(wù)，不應(yīng)該在隊(duì)列出現(xiàn)兩次。
微信平臺(tái)上有多少公眾號(hào)不清楚，應(yīng)該是一個(gè)很大的數(shù)字，每天早上和晚上都會(huì)產(chǎn)生大量的公眾號(hào)推送，如果使用 DelayQueue 能否滿足需要呢？恐怕很難。
02. TimeWheel 時(shí)間輪
時(shí)間輪也被廣泛用于延時(shí)任務(wù)調(diào)度，比如Kafka、Netty，同樣 XXL-JOB 也使用時(shí)間輪做任務(wù)調(diào)度。時(shí)間輪是一種非常巧妙的思想，沒(méi)有查到其出處，個(gè)人感覺(jué)應(yīng)該跟「CPU 時(shí)間片輪轉(zhuǎn)調(diào)度算法」有關(guān)?；窘Y(jié)構(gòu)如下
時(shí)間輪基本結(jié)構(gòu)
Kafka 為了實(shí)現(xiàn)多時(shí)間跨度調(diào)度，實(shí)現(xiàn)了多級(jí)時(shí)間輪
Kafka 時(shí)間輪
時(shí)間輪類(lèi)似于鐘表，上面有時(shí)分秒的刻度，秒針一秒一秒的跳，對(duì)應(yīng)到秒級(jí)任務(wù)，如果刻度跨度為毫秒則可以實(shí)現(xiàn)毫秒調(diào)度。每一個(gè)刻度后面都連接著當(dāng)前秒應(yīng)該執(zhí)行的任務(wù)，系統(tǒng)每次都調(diào)度當(dāng)前時(shí)間指針下的任務(wù)。其數(shù)據(jù)結(jié)構(gòu)就可以看成「數(shù)組+鏈表」的實(shí)現(xiàn)，時(shí)間輪是一種算法思想，在各開(kāi)發(fā)語(yǔ)言中沒(méi)有對(duì)應(yīng)的實(shí)現(xiàn)，HashMap、Dict 也可以滿足要求。XXL-JOB 就是使用的 ConcurrentHashMap<Integer,List<Integer>>。時(shí)間輪相比于 DelayQueue 怎么樣呢，又存在哪些問(wèn)題，該怎么解決呢？
- 有序性
時(shí)間輪靠時(shí)間指針調(diào)度，不存在任務(wù)排序，每次都是取出當(dāng)前刻度下的任務(wù)。每次都是O(1)，假如當(dāng)前時(shí)刻下有多個(gè)任務(wù)，當(dāng)前隊(duì)列需要全部彈出。
- 線程安全
與 DelayQueue 不同，時(shí)間輪每個(gè)刻度下都是一個(gè)獨(dú)立的隊(duì)列，各隊(duì)列的存取互不影響，可以通過(guò)線程安全的隊(duì)列來(lái)實(shí)現(xiàn)，所以存取的并發(fā)性能比 DelayQueue 高很多。
- 避免空輪詢
時(shí)間輪的本質(zhì)是隨著時(shí)間的推移，不斷的輪詢當(dāng)前時(shí)間刻度下的任務(wù)，與 DelayQueue 不同，即使時(shí)間輪為空時(shí)，依然輪詢，會(huì)產(chǎn)生空輪詢。在 XXL-JOB 里就存在這種問(wèn)題，幸好一般情況下，都是秒級(jí)調(diào)度，空輪詢也沒(méi)有大影響。但如果是毫秒級(jí)調(diào)度，空輪詢是會(huì)影響系統(tǒng)性能的，比如 epoll CPU100% 的bug 和 Netty 空輪詢bug。
- 任務(wù)去重
需要保證在一個(gè)時(shí)間刻度下，一個(gè)任務(wù)不能出現(xiàn)兩次，不然可能會(huì)多次調(diào)度。
- 時(shí)間輪實(shí)現(xiàn)
理想中的時(shí)間輪是能夠滿足以上 4 點(diǎn)要求，revolver 通過(guò)跳躍表數(shù)組實(shí)現(xiàn)基本結(jié)構(gòu)ConcurrentSkipListSet<Integer>[]，ConcurrentSkipListSet 是一個(gè)基于跳躍表實(shí)現(xiàn)的無(wú)鎖的線程安全的、有序列、去重的列表表，向列表put元素并排序的時(shí)間復(fù)雜度是O(logN)，ReentrantLock + condition + AtomicInteger 計(jì)數(shù)器避免空輪詢。
當(dāng)任務(wù)數(shù)=0 時(shí)，調(diào)用 condition.await() take 被阻塞，當(dāng)元素個(gè)數(shù)從無(wú)變成有的時(shí)候，調(diào)用 condition.signal()，也是一個(gè)典型的生產(chǎn)者消費(fèi)者模型。
某資料上就用這種設(shè)計(jì)做出了監(jiān)控10億級(jí)定時(shí)任務(wù)檢測(cè)系統(tǒng)，時(shí)間輪是一種設(shè)計(jì)方式，非特定的數(shù)據(jù)結(jié)構(gòu)，除了性能好之外其擴(kuò)展性也是非常好的。
歡迎關(guān)注公眾號(hào)：看起來(lái)很美（kanqilaihenmei_）
-- 完 --
