隊(duì)列比較

隊(duì)列

隊(duì)列比較

總結(jié)：

就性能而言，無(wú)鎖(什么也不加) > CAS > LOCK;

從現(xiàn)實(shí)使用中考慮，我們一般選擇有界隊(duì)列（避免生產(chǎn)者速度過(guò)快，導(dǎo)致內(nèi)存溢出）；同時(shí)，為了減少JAVA的垃圾回收對(duì)系統(tǒng)性能的影響，會(huì)盡量選擇array/heap格式的數(shù)據(jù)結(jié)構(gòu)。所以我們實(shí)際使用中用ArrayBlockingQueue多一些；

注：之后會(huì)將ArrayBlockingQueue和Disruptor做一些對(duì)比。

Disruptor是什么

Disruptor是英國(guó)外匯交易公司LMAX開(kāi)發(fā)的一個(gè)高性能隊(duì)列，研發(fā)的初衷是解決內(nèi)存隊(duì)列的延遲問(wèn)題（在性能測(cè)試中發(fā)現(xiàn)竟然與I/O操作處于同樣的數(shù)量級(jí)）。基于Disruptor開(kāi)發(fā)的系統(tǒng)單線程能支撐每秒600萬(wàn)訂單，2010年在QCon演講后，獲得了業(yè)界關(guān)注。2011年，企業(yè)應(yīng)用軟件專家Martin Fowler專門(mén)撰寫(xiě)長(zhǎng)文介紹。同年它還獲得了Oracle官方的Duke大獎(jiǎng)。

目前，包括Apache Storm、Camel、Log4j 2等在內(nèi)的很多知名項(xiàng)目都應(yīng)用了Disruptor以獲取高性能。

數(shù)據(jù)來(lái)自：

https://github.com/LMAX-Exchange/disruptor/wiki/Performance-Results

Disruptor原理解析

CPU緩存

緩存層級(jí)越接近于 CPU core，容量越小，速度越快，當(dāng) CPU 執(zhí)行運(yùn)算的時(shí)候，它先去 L1 查找所需的數(shù)據(jù)，再去 L2，然后是 L3，最后如果這些緩存中都沒(méi)有，所需的數(shù)據(jù)就要去主內(nèi)存拿。走得越遠(yuǎn)，運(yùn)算耗費(fèi)的時(shí)間就越長(zhǎng)。

緩存行

緩存行 (Cache Line) 是 CPU Cache 中的最小單位，CPU Cache 由若干緩存行組成，一個(gè)緩存行的大小通常是 64 字節(jié)（這取決于 CPU），并且它有效地引用主內(nèi)存中的一塊地址。一個(gè) Java 的 long 類型是 8 字節(jié)，因此在一個(gè)緩存行中可以存 8 個(gè) long 類型的變量。

CPU每次從主存中拉取數(shù)據(jù)時(shí)，會(huì)把相鄰的數(shù)據(jù)也存入同一個(gè)cache line。

在訪問(wèn)一個(gè)long數(shù)組的時(shí)候，如果數(shù)組中的一個(gè)值被加載到緩存中，它會(huì)自動(dòng)加載另外7個(gè)。因此你能非常快的遍歷這個(gè)數(shù)組。事實(shí)上，你可以非常快速的遍歷在連續(xù)內(nèi)存塊中分配的任意數(shù)據(jù)結(jié)構(gòu)。

利用CPU緩存-示例

偽共享

如果多個(gè)線程的變量共享了同一個(gè) CacheLine，任意一方的修改操作都會(huì)使得整個(gè) CacheLine 失效（因?yàn)?CacheLine 是 CPU 緩存的最小單位），也就意味著，頻繁的多線程操作，CPU 緩存將會(huì)徹底失效，降級(jí)為 CPU core 和主內(nèi)存的直接交互。

如何解決偽共享（字節(jié)填充）

RingBuffer

在Disruptor中采用了數(shù)組的方式保存了我們的數(shù)據(jù)，上面我們也介紹了采用數(shù)組保存我們?cè)L問(wèn)時(shí)很好的利用緩存，但是在Disruptor中進(jìn)一步選擇采用了環(huán)形數(shù)組進(jìn)行保存數(shù)據(jù)，也就是RingBuffer。在這里先說(shuō)明一下環(huán)形數(shù)組并不是真正的環(huán)形數(shù)組，在RingBuffer中是采用取余的方式進(jìn)行訪問(wèn)的，比如數(shù)組大小為 10，0訪問(wèn)的是數(shù)組下標(biāo)為0這個(gè)位置，其實(shí)10，20等訪問(wèn)的也是數(shù)組的下標(biāo)為0的這個(gè)位置。

當(dāng)然其不僅解決了數(shù)組快速訪問(wèn)的問(wèn)題，也解決了不需要再次分配內(nèi)存的問(wèn)題，減少了垃圾回收，因?yàn)槲覀?，10，20等都是執(zhí)行的同一片內(nèi)存區(qū)域，這樣就不需要再次分配內(nèi)存，頻繁的被JVM垃圾回收器回收。

實(shí)際上，在這些框架中取余并不是使用%運(yùn)算，都是使用的&與運(yùn)算，這就要求你設(shè)置的大小一般是2的N次方也就是，10,100,1000等等，這樣減去1的話就是，1，11，111，就能很好的使用index & (size -1),這樣利用位運(yùn)算就增加了訪問(wèn)速度。 如果在Disruptor中你不用2的N次方進(jìn)行大小設(shè)置，他會(huì)拋出buffersize必須為2的N次方異常。

Disruptor生產(chǎn)者和消費(fèi)者

生產(chǎn)者寫(xiě)入數(shù)據(jù)

寫(xiě)入數(shù)據(jù)的步驟包括：

1.占位；

2.移動(dòng)游標(biāo)并填充數(shù)據(jù)；

需要考慮的問(wèn)題：

1.如何避免生產(chǎn)者的生產(chǎn)速度過(guò)快而造成的新消息覆蓋了未被消費(fèi)的舊消息的問(wèn)題；

2.如何解決多個(gè)生產(chǎn)者搶占生產(chǎn)位的問(wèn)題;

1.如何避免生產(chǎn)者的生產(chǎn)速度過(guò)快而造成的新消息覆蓋了未被消費(fèi)的舊消息的問(wèn)題；

答：生產(chǎn)者再獲取占位之前需要查看當(dāng)前最慢的消費(fèi)者位置，如果當(dāng)前要發(fā)布的位置比消費(fèi)者大，就等待;

2.如何解決多個(gè)生產(chǎn)者搶占生產(chǎn)位的問(wèn)題;

多個(gè)生產(chǎn)者通過(guò)CAS獲取生產(chǎn)位；

消費(fèi)者讀取數(shù)據(jù)

說(shuō)明：

1.一個(gè)消費(fèi)者一個(gè)線程；

2.每個(gè)消費(fèi)者都有一個(gè)游標(biāo)表示已經(jīng)消費(fèi)到哪了（Sequence）；

3.消息者會(huì)等待(waitFor)新數(shù)據(jù)，直到生產(chǎn)者通知(signal)；

需要考慮的問(wèn)題：

如何防止讀取的時(shí)候，讀到還未寫(xiě)的元素？

WaitStrategy（等待策略）：

BlockingWaitStrategy：默認(rèn)策略，沒(méi)有獲取到任務(wù)的情況下線程會(huì)進(jìn)入等待狀態(tài)。cpu 消耗少，但是延遲高。

TimeoutBlockingWaitStrategy：相對(duì)于BlockingWaitStrategy來(lái)說(shuō)，設(shè)置了等待時(shí)間，超過(guò)后拋異常。

BusySpinWaitStrategy：線程一直自旋等待。cpu 占用高，延遲低.

YieldingWaitStrategy：嘗試自旋 100 次，然后調(diào)用 Thread.yield() 讓出 cpu。cpu 占用高，延遲低。

SleepingWaitStrategy：嘗試自旋 100 此，然后調(diào)用 Thread.yield() 100 次，如果經(jīng)過(guò)這兩百次的操作還未獲取到任務(wù)，就會(huì)嘗試階段性掛起自身線程。此種方式是對(duì)cpu 占用和延遲的一種平衡，性能不太穩(wěn)定。

生產(chǎn)者寫(xiě)入數(shù)據(jù)示例1

生產(chǎn)者寫(xiě)入數(shù)據(jù)示例2

總結(jié)

Disruptor與ArrayBlockingQueue不同的地方：

1.增加緩存行補(bǔ)齊， 提升cache緩存命中率， 沒(méi)有為偽共享和非預(yù)期的競(jìng)爭(zhēng)；

2. 可選鎖無(wú)關(guān)lock-free, 沒(méi)有競(jìng)爭(zhēng)所以非常快；

3. 環(huán)形數(shù)組中的元素不會(huì)被刪除；

4. 支持多個(gè)消費(fèi)者，每個(gè)消費(fèi)者都可以獲得相同的消息（廣播）。 而ArrayBlockingQueue元素被一個(gè)消費(fèi)者取走后，其它消費(fèi)者就無(wú)法從Queue中取到；