隊列比較
隊列
隊列比較
總結(jié)：
就性能而言，無鎖(什么也不加) > CAS > LOCK;
從現(xiàn)實使用中考慮，我們一般選擇有界隊列（避免生產(chǎn)者速度過快，導(dǎo)致內(nèi)存溢出）；同時，為了減少JAVA的垃圾回收對系統(tǒng)性能的影響，會盡量選擇array/heap格式的數(shù)據(jù)結(jié)構(gòu)。所以我們實際使用中用ArrayBlockingQueue多一些；
注：之后會將ArrayBlockingQueue和Disruptor做一些對比。
Disruptor是什么
Disruptor是英國外匯交易公司LMAX開發(fā)的一個高性能隊列，研發(fā)的初衷是解決內(nèi)存隊列的延遲問題（在性能測試中發(fā)現(xiàn)竟然與I/O操作處于同樣的數(shù)量級）。基于Disruptor開發(fā)的系統(tǒng)單線程能支撐每秒600萬訂單，2010年在QCon演講后，獲得了業(yè)界關(guān)注。2011年，企業(yè)應(yīng)用軟件專家Martin Fowler專門撰寫長文介紹。同年它還獲得了Oracle官方的Duke大獎。
目前，包括Apache Storm、Camel、Log4j 2等在內(nèi)的很多知名項目都應(yīng)用了Disruptor以獲取高性能。
數(shù)據(jù)來自：
https://github.com/LMAX-Exchange/disruptor/wiki/Performance-Results
Disruptor原理解析
CPU緩存
緩存層級越接近于 CPU core，容量越小，速度越快，當(dāng) CPU 執(zhí)行運算的時候，它先去 L1 查找所需的數(shù)據(jù)，再去 L2，然后是 L3，最后如果這些緩存中都沒有，所需的數(shù)據(jù)就要去主內(nèi)存拿。走得越遠(yuǎn)，運算耗費的時間就越長。
緩存行
緩存行 (Cache Line) 是 CPU Cache 中的最小單位，CPU Cache 由若干緩存行組成，一個緩存行的大小通常是 64 字節(jié)（這取決于 CPU），并且它有效地引用主內(nèi)存中的一塊地址。一個 Java 的 long 類型是 8 字節(jié)，因此在一個緩存行中可以存 8 個 long 類型的變量。
CPU每次從主存中拉取數(shù)據(jù)時，會把相鄰的數(shù)據(jù)也存入同一個cache line。
在訪問一個long數(shù)組的時候，如果數(shù)組中的一個值被加載到緩存中，它會自動加載另外7個。因此你能非常快的遍歷這個數(shù)組。事實上，你可以非常快速的遍歷在連續(xù)內(nèi)存塊中分配的任意數(shù)據(jù)結(jié)構(gòu)。
利用CPU緩存-示例
偽共享
如果多個線程的變量共享了同一個 CacheLine，任意一方的修改操作都會使得整個 CacheLine 失效（因為 CacheLine 是 CPU 緩存的最小單位），也就意味著，頻繁的多線程操作，CPU 緩存將會徹底失效，降級為 CPU core 和主內(nèi)存的直接交互。
如何解決偽共享（字節(jié)填充）
RingBuffer
在Disruptor中采用了數(shù)組的方式保存了我們的數(shù)據(jù)，上面我們也介紹了采用數(shù)組保存我們訪問時很好的利用緩存，但是在Disruptor中進(jìn)一步選擇采用了環(huán)形數(shù)組進(jìn)行保存數(shù)據(jù)，也就是RingBuffer。在這里先說明一下環(huán)形數(shù)組并不是真正的環(huán)形數(shù)組，在RingBuffer中是采用取余的方式進(jìn)行訪問的，比如數(shù)組大小為 10，0訪問的是數(shù)組下標(biāo)為0這個位置，其實10，20等訪問的也是數(shù)組的下標(biāo)為0的這個位置。
當(dāng)然其不僅解決了數(shù)組快速訪問的問題，也解決了不需要再次分配內(nèi)存的問題，減少了垃圾回收，因為我們0，10，20等都是執(zhí)行的同一片內(nèi)存區(qū)域，這樣就不需要再次分配內(nèi)存，頻繁的被JVM垃圾回收器回收。
實際上，在這些框架中取余并不是使用%運算，都是使用的&與運算，這就要求你設(shè)置的大小一般是2的N次方也就是，10,100,1000等等，這樣減去1的話就是，1，11，111，就能很好的使用index & (size -1),這樣利用位運算就增加了訪問速度。 如果在Disruptor中你不用2的N次方進(jìn)行大小設(shè)置，他會拋出buffersize必須為2的N次方異常。
Disruptor生產(chǎn)者和消費者
生產(chǎn)者寫入數(shù)據(jù)
寫入數(shù)據(jù)的步驟包括：
1.占位；
2.移動游標(biāo)并填充數(shù)據(jù)；
需要考慮的問題：
1.如何避免生產(chǎn)者的生產(chǎn)速度過快而造成的新消息覆蓋了未被消費的舊消息的問題；
2.如何解決多個生產(chǎn)者搶占生產(chǎn)位的問題;
1.如何避免生產(chǎn)者的生產(chǎn)速度過快而造成的新消息覆蓋了未被消費的舊消息的問題；
答：生產(chǎn)者再獲取占位之前需要查看當(dāng)前最慢的消費者位置，如果當(dāng)前要發(fā)布的位置比消費者大，就等待;
2.如何解決多個生產(chǎn)者搶占生產(chǎn)位的問題;
多個生產(chǎn)者通過CAS獲取生產(chǎn)位；
消費者讀取數(shù)據(jù)
說明：
1.一個消費者一個線程；
2.每個消費者都有一個游標(biāo)表示已經(jīng)消費到哪了（Sequence）；
3.消息者會等待(waitFor)新數(shù)據(jù)，直到生產(chǎn)者通知(signal)；
需要考慮的問題：
如何防止讀取的時候，讀到還未寫的元素？
WaitStrategy（等待策略）：
BlockingWaitStrategy：默認(rèn)策略，沒有獲取到任務(wù)的情況下線程會進(jìn)入等待狀態(tài)。cpu 消耗少，但是延遲高。
TimeoutBlockingWaitStrategy：相對于BlockingWaitStrategy來說，設(shè)置了等待時間，超過后拋異常。
BusySpinWaitStrategy：線程一直自旋等待。cpu 占用高，延遲低.
YieldingWaitStrategy：嘗試自旋 100 次，然后調(diào)用 Thread.yield() 讓出 cpu。cpu 占用高，延遲低。
SleepingWaitStrategy：嘗試自旋 100 此，然后調(diào)用 Thread.yield() 100 次，如果經(jīng)過這兩百次的操作還未獲取到任務(wù)，就會嘗試階段性掛起自身線程。此種方式是對cpu 占用和延遲的一種平衡，性能不太穩(wěn)定。
生產(chǎn)者寫入數(shù)據(jù)示例1
生產(chǎn)者寫入數(shù)據(jù)示例2
總結(jié)
Disruptor與ArrayBlockingQueue不同的地方：
1.增加緩存行補齊， 提升cache緩存命中率， 沒有為偽共享和非預(yù)期的競爭；
2. 可選鎖無關(guān)lock-free, 沒有競爭所以非常快；
3. 環(huán)形數(shù)組中的元素不會被刪除；
4. 支持多個消費者，每個消費者都可以獲得相同的消息（廣播）。 而ArrayBlockingQueue元素被一個消費者取走后，其它消費者就無法從Queue中取到；
