個人專題目錄
背景
Disruptor是英國外匯交易公司LMAX開發(fā)的一個高性能隊列，研發(fā)的初衷是解決內(nèi)存隊列的延遲問題（在性能測試中發(fā)現(xiàn)竟然與I/O操作處于同樣的數(shù)量級）疙渣。基于Disruptor開發(fā)的系統(tǒng)單線程能支撐每秒600萬訂單俗冻，2010年在QCon演講后礁叔，獲得了業(yè)界關注。2011年迄薄，企業(yè)應用軟件專家Martin Fowler專門撰寫長文介紹琅关。同年它還獲得了Oracle官方的Duke大獎。
目前讥蔽，包括Apache Storm涣易、Camel、Log4j 2在內(nèi)的很多知名項目都應用了Disruptor以獲取高性能冶伞。在美團點評技術團隊它也有不少應用新症，有的項目架構(gòu)借鑒了它的設計機制。本文從實戰(zhàn)角度剖析了Disruptor的實現(xiàn)原理碰缔。
需要特別指出的是账劲，這里所說的隊列是系統(tǒng)內(nèi)部的內(nèi)存隊列，而不是Kafka這樣的分布式隊列金抡。另外，本文所描述的Disruptor特性限于3.3.4腌且。
Java內(nèi)置隊列
介紹Disruptor之前梗肝，我們先來看一看常用的線程安全的內(nèi)置隊列有什么問題。Java的內(nèi)置隊列如下表所示铺董。
| 隊列 | 有界性 | 鎖 | 數(shù)據(jù)結(jié)構(gòu) |
|---|---|---|---|
| ArrayBlockingQueue | bounded | 加鎖 | arraylist |
| LinkedBlockingQueue | optionally-bounded | 加鎖 | linkedlist |
| ConcurrentLinkedQueue | unbounded | 無鎖 | linkedlist |
| LinkedTransferQueue | unbounded | 無鎖 | linkedlist |
| PriorityBlockingQueue | unbounded | 加鎖 | heap |
| DelayQueue | unbounded | 加鎖 | heap |
隊列的底層一般分成三種：數(shù)組巫击、鏈表和堆。其中精续，堆一般情況下是為了實現(xiàn)帶有優(yōu)先級特性的隊列坝锰，暫且不考慮。
我們就從數(shù)組和鏈表兩種數(shù)據(jù)結(jié)構(gòu)來看重付，基于數(shù)組線程安全的隊列顷级，比較典型的是ArrayBlockingQueue，它主要通過加鎖的方式來保證線程安全确垫；基于鏈表的線程安全隊列分成LinkedBlockingQueue和ConcurrentLinkedQueue兩大類弓颈，前者也通過鎖的方式來實現(xiàn)線程安全，而后者以及上面表格中的LinkedTransferQueue都是通過原子變量compare and swap（以下簡稱“CAS”）這種不加鎖的方式來實現(xiàn)的删掀。
通過不加鎖的方式實現(xiàn)的隊列都是無界的（無法保證隊列的長度在確定的范圍內(nèi)）翔冀；而加鎖的方式，可以實現(xiàn)有界隊列披泪。在穩(wěn)定性要求特別高的系統(tǒng)中纤子，為了防止生產(chǎn)者速度過快，導致內(nèi)存溢出，只能選擇有界隊列控硼；同時泽论，為了減少Java的垃圾回收對系統(tǒng)性能的影響，會盡量選擇array/heap格式的數(shù)據(jù)結(jié)構(gòu)象颖。這樣篩選下來佩厚，符合條件的隊列就只有ArrayBlockingQueue。
ArrayBlockingQueue的問題
ArrayBlockingQueue在實際使用過程中说订，會因為加鎖和偽共享等出現(xiàn)嚴重的性能問題抄瓦，我們下面來分析一下。
加鎖
現(xiàn)實編程過程中陶冷，加鎖通常會嚴重地影響性能钙姊。線程會因為競爭不到鎖而被掛起，等鎖被釋放的時候埂伦，線程又會被恢復煞额，這個過程中存在著很大的開銷，并且通常會有較長時間的中斷沾谜，因為當一個線程正在等待鎖時膊毁，它不能做任何其他事情。如果一個線程在持有鎖的情況下被延遲執(zhí)行基跑，例如發(fā)生了缺頁錯誤婚温、調(diào)度延遲或者其它類似情況，那么所有需要這個鎖的線程都無法執(zhí)行下去媳否。如果被阻塞線程的優(yōu)先級較高栅螟，而持有鎖的線程優(yōu)先級較低，就會發(fā)生優(yōu)先級反轉(zhuǎn)篱竭。
Disruptor論文中講述了一個實驗：
- 這個測試程序調(diào)用了一個函數(shù)力图，該函數(shù)會對一個64位的計數(shù)器循環(huán)自增5億次。
- 機器環(huán)境：2.4G 6核
- 運算： 64位的計數(shù)器累加5億次
| Method | Time (ms) |
|---|---|
| Single thread | 300 |
| Single thread with CAS | 5,700 |
| Single thread with lock | 10,000 |
| Single thread with volatile write | 4,700 |
| Two threads with CAS | 30,000 |
| Two threads with lock | 224,000 |
CAS操作比單線程無鎖慢了1個數(shù)量級掺逼；有鎖且多線程并發(fā)的情況下吃媒，速度比單線程無鎖慢3個數(shù)量級∑夯可見無鎖速度最快晓折。
單線程情況下，不加鎖的性能 > CAS操作的性能 > 加鎖的性能兽泄。
在多線程情況下漓概，為了保證線程安全，必須使用CAS或鎖病梢，這種情況下胃珍，CAS的性能超過鎖的性能梁肿，前者大約是后者的8倍。
綜上可知觅彰，加鎖的性能是最差的吩蔑。
關于鎖和CAS
保證線程安全一般分成兩種方式：鎖和原子變量。
鎖
圖1 通過加鎖的方式實現(xiàn)線程安全
采取加鎖的方式填抬，默認線程會沖突烛芬，訪問數(shù)據(jù)時，先加上鎖再訪問飒责，訪問之后再解鎖赘娄。通過鎖界定一個臨界區(qū)，同時只有一個線程進入宏蛉。如上圖所示遣臼，Thread2訪問Entry的時候，加了鎖拾并，Thread1就不能再執(zhí)行訪問Entry的代碼揍堰，從而保證線程安全。
下面是ArrayBlockingQueue通過加鎖的方式實現(xiàn)的offer方法嗅义，保證線程安全屏歹。
public boolean offer(E e) {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
if (count == items.length)
return false;
else {
insert(e);
return true;
}
} finally {
lock.unlock();
}
}
原子變量
原子變量能夠保證原子性的操作，意思是某個任務在執(zhí)行過程中之碗，要么全部成功西采，要么全部失敗回滾，恢復到執(zhí)行之前的初態(tài)继控，不存在初態(tài)和成功之間的中間狀態(tài)。例如CAS操作胖眷，要么比較并交換成功武通，要么比較并交換失敗。由CPU保證原子性珊搀。
通過原子變量可以實現(xiàn)線程安全冶忱。執(zhí)行某個任務的時候，先假定不會有沖突境析，若不發(fā)生沖突囚枪，則直接執(zhí)行成功；當發(fā)生沖突的時候劳淆，則執(zhí)行失敗链沼，回滾再重新操作，直到不發(fā)生沖突沛鸵。
圖2 通過原子變量CAS實現(xiàn)線程安全
如圖所示括勺，Thread1和Thread2都要把Entry加1缆八。若不加鎖，也不使用CAS疾捍，有可能Thread1取到了myValue=1奈辰，Thread2也取到了myValue=1，然后相加乱豆，Entry中的value值為2奖恰。這與預期不相符，我們預期的是Entry的值經(jīng)過兩次相加后等于3宛裕。
CAS會先把Entry現(xiàn)在的value跟線程當初讀出的值相比較瑟啃，若相同，則賦值续滋；若不相同翰守，則賦值執(zhí)行失敗。一般會通過while/for循環(huán)來重新執(zhí)行疲酌，直到賦值成功蜡峰。
代碼示例是AtomicInteger的getAndAdd方法。CAS是CPU的一個指令朗恳，由CPU保證原子性湿颅。
/**
* Atomically adds the given value to the current value.
*
* @param delta the value to add
* @return the previous value
*/
public final int getAndAdd(int delta) {
for (;;) {
int current = get();
int next = current + delta;
if (compareAndSet(current, next))
return current;
}
}
/**
* Atomically sets the value to the given updated value
* if the current value {@code ==} the expected value.
*
* @param expect the expected value
* @param update the new value
* @return true if successful. False return indicates that
* the actual value was not equal to the expected value.
*/
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
在高度競爭的情況下，鎖的性能將超過原子變量的性能粥诫，但是更真實的競爭情況下油航，原子變量的性能將超過鎖的性能。同時原子變量不會有死鎖等活躍性問題怀浆。
偽共享
什么是共享
下圖是計算的基本結(jié)構(gòu)谊囚。L1、L2执赡、L3分別表示一級緩存镰踏、二級緩存、三級緩存沙合，越靠近CPU的緩存奠伪，速度越快，容量也越小首懈。所以L1緩存很小但很快绊率，并且緊靠著在使用它的CPU內(nèi)核；L2大一些究履，也慢一些滤否，并且仍然只能被一個單獨的CPU核使用；L3更大挎袜、更慢顽聂，并且被單個插槽上的所有CPU核共享肥惭；最后是主存，由全部插槽上的所有CPU核共享紊搪。
圖3 計算機CPU與緩存示意圖
當CPU執(zhí)行運算的時候蜜葱，它先去L1查找所需的數(shù)據(jù)、再去L2耀石、然后是L3牵囤，如果最后這些緩存中都沒有，所需的數(shù)據(jù)就要去主內(nèi)存拿滞伟。走得越遠揭鳞，運算耗費的時間就越長。所以如果你在做一些很頻繁的事梆奈，你要盡量確保數(shù)據(jù)在L1緩存中野崇。
另外，線程之間共享一份數(shù)據(jù)的時候亩钟，需要一個線程把數(shù)據(jù)寫回主存乓梨，而另一個線程訪問主存中相應的數(shù)據(jù)。
