Java內(nèi)置隊(duì)列 和 高性能隊(duì)列Disruptor
1 隊(duì)列簡(jiǎn)介
隊(duì)列是一種特殊的線性表，遵循先入先出歌殃、后入后出（FIFO）的基本原則，一般來說外莲，它只允許在表的前端進(jìn)行刪除操作不狮，而在表的后端進(jìn)行插入操作降铸，但是java的某些隊(duì)列運(yùn)行在任何地方插入刪除；比如我們常用的 LinkedList 集合摇零，它實(shí)現(xiàn)了Queue 接口推掸，因此，我們可以理解為 LinkedList 就是一個(gè)隊(duì)列驻仅；
2 Java隊(duì)列分類
Java中隊(duì)列主要分為阻塞和非阻塞谅畅，有界和無界、單向鏈表和雙向鏈表之分噪服；
2.1 阻塞和非阻塞
-
阻塞隊(duì)列
入列(添加元素)時(shí)毡泻，如果元素?cái)?shù)量超過隊(duì)列總數(shù)，會(huì)進(jìn)行等待（阻塞）粘优，待隊(duì)列的中的元素出列后仇味，元素?cái)?shù)量未超過隊(duì)列總數(shù)時(shí)，就會(huì)解除阻塞狀態(tài)雹顺，進(jìn)而可以繼續(xù)入列邪铲；
出列(刪除元素)時(shí)，如果隊(duì)列為空的情況下无拗，也會(huì)進(jìn)行等待（阻塞），待隊(duì)列有值的時(shí)候即會(huì)解除阻塞狀態(tài)昧碉，進(jìn)而繼續(xù)出列英染；
阻塞隊(duì)列的好處是可以防止隊(duì)列容器溢出；只要滿了就會(huì)進(jìn)行阻塞等待被饿；也就不存在溢出的情況四康；
只要是阻塞隊(duì)列，都是線程安全的狭握；闪金；
-
非阻塞隊(duì)列
不管出列還是入列，都不會(huì)進(jìn)行阻塞
入列時(shí)论颅，如果元素?cái)?shù)量超過隊(duì)列總數(shù)哎垦，則會(huì)拋出異常，
出列時(shí)恃疯，如果隊(duì)列為空漏设，則取出空值；
一般情況下今妄，非阻塞式隊(duì)列使用的比較少郑口，一般都用阻塞式的對(duì)象比較多鸳碧；阻塞和非阻塞隊(duì)列在使用上的最大區(qū)別就是阻塞隊(duì)列提供了以下2個(gè)方法：
出隊(duì)阻塞方法 ： take()
入隊(duì)阻塞方法 ： put()
2.12 有界和無界
有界：有界限，大小長(zhǎng)度受限制
無界：無限大小犬性，其實(shí)說是無限大小瞻离，其實(shí)是有界限的，只不過超過界限時(shí)就會(huì)進(jìn)行擴(kuò)容乒裆，就行ArrayList 一樣套利，在內(nèi)部動(dòng)態(tài)擴(kuò)容
2.13 單向鏈表和雙向鏈表
單向鏈表 ： 每個(gè)元素中除了元素本身之外，還存儲(chǔ)一個(gè)指針缸兔，這個(gè)指針指向下一個(gè)元素日裙；
雙向鏈表 ：除了元素本身之外，還有兩個(gè)指針惰蜜，一個(gè)指針指向前一個(gè)元素的地址昂拂，另一個(gè)指針指向后一個(gè)元素的地址；
3 Java內(nèi)置隊(duì)列
3.1 Java 隊(duì)列接口繼承圖
3.2 常見的Java線程安全的內(nèi)置隊(duì)列
| 隊(duì)列 | 有界性 | 鎖 | 數(shù)據(jù)結(jié)構(gòu) | 隊(duì)列類型 |
|---|---|---|---|---|
| ArrayBlockingQueue | 有界 | 加鎖（ReentrantLock抛猖，讀寫同一把鎖） | arraylist（數(shù)組） | 阻塞 |
| LinkedBlockingQueue | 可選 | 加鎖（ReentrantLock格侯，讀寫各自一把鎖） | linkedlist（鏈表） | 阻塞 |
| ConcurrentLinkedQueue | 無界 | 無鎖（CAS） | linkedlist（鏈表） | 非阻塞 |
| LinkedTransferQueue | 無界 | 無鎖（CAS） | linkedlist（鏈表） | 阻塞 |
| PriorityBlockingQueue | 無界 | 加鎖（ReentrantLock，讀寫同一把鎖） | heap（堆） | 阻塞 |
| DelayQueue | 無界 | 加鎖（ReentrantLock财著，讀寫同一把鎖） | heap（堆） | 阻塞 |
-
ArrayBlockingQueue
一個(gè)用數(shù)組實(shí)現(xiàn)的有界阻塞隊(duì)列联四，初始化時(shí)必須指定隊(duì)列大小。此隊(duì)列按照先進(jìn)先出（FIFO）的原則對(duì)元素進(jìn)行排序撑教。默認(rèn)情況下采用非公平鎖的方式實(shí)現(xiàn)朝墩，可以通過構(gòu)造器傳參控制是采用公平鎖還是非公平鎖實(shí)現(xiàn)
-
LinkedBlockingQueue
一個(gè)由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列,此隊(duì)列按照先進(jìn)先出（FIFO）的原則對(duì)元素進(jìn)行排序
LinkedTransferQueue
一個(gè)由鏈表結(jié)構(gòu)組成的無界阻塞隊(duì)列-
ConcurrentLinkedQueue
一個(gè)通過CAS實(shí)現(xiàn)的線程安全的無界非阻塞隊(duì)列
PriorityBlockingQueue
一個(gè)帶優(yōu)先級(jí)的無界隊(duì)列，而不是先進(jìn)先出隊(duì)列伟姐。元素按優(yōu)先級(jí)順序被移除收苏，而且它也是無界的，也就是沒有容量上限愤兵，雖然此隊(duì)列邏輯上是無界的鹿霸，但是由于資源被耗盡，所以試圖執(zhí)行添加操作可能會(huì)導(dǎo)致 OutOfMemoryError 錯(cuò)誤秆乳；DelayQueue
一個(gè)通過PriorityBlockingQueue實(shí)現(xiàn)延遲獲取元素的無界隊(duì)列無界阻塞隊(duì)列懦鼠，其中添加進(jìn)該隊(duì)列的元素必須實(shí)現(xiàn)Delayed接口（指定延遲時(shí)間），而且只有在延遲期滿后才能從中提取元素屹堰。
如果要 實(shí)現(xiàn) 一個(gè) 線程安全的隊(duì)列肛冶，有兩種方式：一種是使用阻塞算法，另一種是使用非阻塞算法扯键。
使用阻塞算法的隊(duì)列可以用一個(gè) 鎖 （入隊(duì)和出隊(duì)用同一把鎖淑趾，ArrayBlockingQueue ）或兩個(gè)鎖 （入隊(duì)和出隊(duì) 用不同的鎖 ，LinkedBlockingQueue）等方式來 實(shí)現(xiàn) 忧陪。
非阻塞的實(shí)現(xiàn) 方式則 可以使用循環(huán)CAS 的方式來實(shí)現(xiàn)（ConcurrentLinkedQueue 扣泊。
3.3 隊(duì)列常用方法
add：增加一個(gè)元索 如果隊(duì)列已滿近范，則拋出一個(gè)IIIegaISlabEepeplian異常
remove：移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常
element：返回隊(duì)列頭部的元素 如果隊(duì)列為空延蟹，則拋出一個(gè)NoSuchElementException異常
offer：添加一個(gè)元素并返回true 如果隊(duì)列已滿评矩，則返回false
poll：移除并返問隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
peek：返回隊(duì)列頭部的元素 如果隊(duì)列為空阱飘，則返回null
put：添加一個(gè)元素 如果隊(duì)列滿斥杜，則阻塞
take：移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則阻塞
drainTo(list)：一次性取出隊(duì)列所有元素
知識(shí)點(diǎn)： remove沥匈、element蔗喂、offer 、poll高帖、peek 其實(shí)是屬于Queue接口缰儿。
4 高性能隊(duì)列Disruptor
4.1 Disruptor簡(jiǎn)介
Disruptor是英國(guó)外匯交易公司LMAX開發(fā)的一個(gè)高性能隊(duì)列，研發(fā)的初衷是解決內(nèi)存隊(duì)列的延遲問題散址。與Kafka乖阵、RabbitMQ用于服務(wù)間的消息隊(duì)列不同，disruptor一般用于線程間消息的傳遞预麸〉山基于Disruptor開發(fā)的系統(tǒng)單線程能支撐每秒600萬訂單。 disruptor適用于多個(gè)線程之間的消息隊(duì)列吏祸，作用與ArrayBlockingQueue有相似之處对蒲，但是disruptor從功能、性能都遠(yuǎn)好于ArrayBlockingQueue贡翘，當(dāng)多個(gè)線程之間傳遞大量數(shù)據(jù)或?qū)π阅芤筝^高時(shí)蹈矮，可以考慮使用disruptor作為ArrayBlockingQueue的替代者。 官方也對(duì)disruptor和ArrayBlockingQueue的性能在不同的應(yīng)用場(chǎng)景下做了對(duì)比床估，目測(cè)性能只有有5~10倍左右的提升。
目前诱渤，包括Apache Storm丐巫、Camel、Log4j2等等知名的框架都在內(nèi)部集成了Disruptor用來替代jdk的隊(duì)列勺美，以此來獲得高性能递胧。
Disruptor使用觀察者模式, 主動(dòng)將消息發(fā)送給消費(fèi)者, 而不是等消費(fèi)者從隊(duì)列中取; 在無鎖的情況下, 實(shí)現(xiàn)queue(環(huán)形, RingBuffer)的并發(fā)操作, 性能遠(yuǎn)高于BlockingQueue。
4.2 高性能原理
Disruptor為什么性能這么好呢赡茸，主要依賴于以下四個(gè)特性
無鎖設(shè)計(jì)：CAS
采用CAS無鎖方式缎脾，保證線程的安全性。多線程環(huán)境下占卧，多個(gè)生產(chǎn)者通過do/while循環(huán)的條件CAS遗菠，來判斷每次申請(qǐng)的空間是否已經(jīng)被其他生產(chǎn)者占據(jù)联喘。假如已經(jīng)被占據(jù)，該函數(shù)會(huì)返回失敗辙纬，While循環(huán)重新執(zhí)行豁遭，申請(qǐng)寫入空間。如果申請(qǐng)到之后贺拣，直接在該位置寫入或者讀取數(shù)據(jù)蓖谢。
ArrayBlockingQueue用了重量級(jí)lock鎖，在我們加鎖過程中我們會(huì)把鎖掛起譬涡，解鎖后闪幽，又會(huì)把線程恢復(fù)，這一過程會(huì)有一定的開銷涡匀，并且我們一旦沒有獲取鎖盯腌，這個(gè)線程就只能一直等待，這個(gè)線程什么事也不能做渊跋。
CAS 更多知識(shí)見 Java 鎖
RingBuffer : 環(huán)形數(shù)組
引入環(huán)形的數(shù)組結(jié)構(gòu)：這種固定大小的環(huán)形隊(duì)列的另外一個(gè)好處就是可以做到完全的內(nèi)存復(fù)用腊嗡。在系統(tǒng)的運(yùn)行過程中，不會(huì)有新的空間需要分配或者老的空間需要回收拾酝，大大減少系統(tǒng)分配空間及回收空間的額外開銷燕少，避免頻繁的GC；同時(shí)蒿囤，數(shù)組對(duì)處理器的緩存機(jī)制更加友好客们。
[圖片上傳失敗...(image-1650c4-1677132259413)]
-
元素位置的定位：
數(shù)組長(zhǎng)度強(qiáng)制要求一定是 2^n ，這樣可以通過位運(yùn)算材诽，加快定位的速度底挫。通過sequence ＆(queueSize-1)就能立即定位到實(shí)際的元素位置index，這比取余（%）操作快得多（hashMap定位也是采用這種方式）脸侥。
下標(biāo)采取遞增的形式建邓，不用擔(dān)心index溢出的問題，index是long類型睁枕，即使100萬QPS的處理速度官边，也需要30萬年才能用完。
-
消除偽共享 : 通過添加額外的無用信息外遇，避免偽共享問題
當(dāng)CPU訪問某一個(gè)變量時(shí)候注簿，首先會(huì)去看CPU Cache內(nèi)是否有該變量，如果有則直接從中獲取跳仿，否者就去主內(nèi)存里面獲取該變量诡渴，然后把該變量所在內(nèi)存區(qū)域的一個(gè)Cache行大小的內(nèi)存拷貝到Cache（cache行是Cache與主內(nèi)存進(jìn)行數(shù)據(jù)交換的單位）。
由于存放到Cache行的的是內(nèi)存塊而不是單個(gè)變量菲语，所以可能會(huì)把多個(gè)變量存放到了一個(gè)cache行妄辩。當(dāng)多個(gè)線程同時(shí)修改一個(gè)緩存行里面的多個(gè)變量時(shí)候惑灵，由于同時(shí)只能有一個(gè)線程操作緩存行，所以相比每個(gè)變量放到一個(gè)緩存行性能會(huì)有所下降恩袱，這就是偽共享泣棋。
總之偽共享的產(chǎn)生是因?yàn)槎鄠€(gè)變量被放入了一個(gè)緩存行，并且多個(gè)線程同時(shí)去寫入緩存行中不同變量畔塔，解決偽共享最直接的方法就是填充潭辈，通過添加額外的無用信息，避免偽共享問題澈吨。
如上圖變量x,y同時(shí)被放到了CPU的一級(jí)和二級(jí)緩存把敢，當(dāng)線程1使用CPU1對(duì)變量x進(jìn)行更新時(shí)候，首先會(huì)修改cpu1的一級(jí)緩存變量x所在緩存行谅辣，這時(shí)候緩存一致性協(xié)議會(huì)導(dǎo)致cpu2中變量x對(duì)應(yīng)的緩存行失效修赞，那么線程2寫入變量x的時(shí)候就只能去二級(jí)緩存去查找，這就破壞了一級(jí)緩存桑阶，而一級(jí)緩存比二級(jí)緩存更快柏副。更壞的情況下如果cpu只有一級(jí)緩存，那么會(huì)導(dǎo)致頻繁的直接訪問主內(nèi)存蚣录。我們的緩存都是以緩存行作為一個(gè)單位來處理的割择，所以失效x的緩存的同時(shí)，也會(huì)把y失效萎河，反之亦然荔泳。
4.3 Disruptor應(yīng)用場(chǎng)景
參考使用到disruptor的一些框架.
- log4j2
Log4j 2相對(duì)于Log4j 1最大的優(yōu)勢(shì)在于多線程并發(fā)場(chǎng)景下性能更優(yōu)。該特性源自于Log4j 2的異步模式采用了Disruptor來處理虐杯。
Jstorm 在流處理中不同線程中數(shù)據(jù)交換玛歌，數(shù)據(jù)計(jì)算可能蠻多內(nèi)存中計(jì)算， 流計(jì)算快進(jìn)快出擎椰，disruptor應(yīng)該不錯(cuò)的選擇支子。
百度uid-generator 部分使用ring buffer和去偽共享等思路緩存已生成的uid，也部分參考了disruptor
經(jīng)過測(cè)試达舒，Disruptor的速度比LinkedBlockingQueue提高了七倍值朋。所以，當(dāng)你在使用LinkedBlockingQueue出現(xiàn)性能瓶頸的時(shí)候休弃，你就可以考慮采用Disruptor的代替吞歼。
