Disruptor是英國外彙交易公司LMAX開發的一個高性能隊列，研發的初衷是解決記憶體隊列的延遲問題（在性能測試中發現竟然與I/O操作處于同樣的數量級）。基于Disruptor開發的系統單線程能支撐每秒600萬訂單，2010年在QCon演講後，獲得了業界關注。2011年，企業應用軟體專家Martin Fowler專門撰寫長文介紹。同年它還獲得了Oracle官方的Duke大獎。
目前，包括Apache Storm、Camel、Log4j 2在内的很多知名項目都應用了Disruptor以擷取高性能。在美團技術團隊它也有不少應用，有的項目架構借鑒了它的設計機制。本文從實戰角度剖析了Disruptor的實作原理。
需要特别指出的是，這裡所說的隊列是系統内部的記憶體隊列，而不是Kafka這樣的分布式隊列。另外，本文所描述的Disruptor特性限于3.3.4。
介紹Disruptor之前，我們先來看一看常用的線程安全的内置隊列有什麼問題。Java的内置隊列如下表所示。
隊列
有界性
鎖
資料結構
ArrayBlockingQueue
bounded
加鎖
arraylist
LinkedBlockingQueue
optionally-bounded
linkedlist
ConcurrentLinkedQueue
unbounded
無鎖
LinkedTransferQueue
PriorityBlockingQueue
heap
DelayQueue
隊列的底層一般分成三種：數組、連結清單和堆。其中，堆一般情況下是為了實作帶有優先級特性的隊列，暫且不考慮。
我們就從數組和連結清單兩種資料結構來看，基于數組線程安全的隊列，比較典型的是ArrayBlockingQueue，它主要通過加鎖的方式來保證線程安全；基于連結清單的線程安全隊列分成LinkedBlockingQueue和ConcurrentLinkedQueue兩大類，前者也通過鎖的方式來實作線程安全，而後者以及上面表格中的LinkedTransferQueue都是通過原子變量compare and swap（以下簡稱“CAS”）這種不加鎖的方式來實作的。
通過不加鎖的方式實作的隊列都是無界的（無法保證隊列的長度在确定的範圍内）；而加鎖的方式，可以實作有界隊列。在穩定性要求特别高的系統中，為了防止生産者速度過快，導緻記憶體溢出，隻能選擇有界隊列；同時，為了減少Java的垃圾回收對系統性能的影響，會盡量選擇array/heap格式的資料結構。這樣篩選下來，符合條件的隊列就隻有ArrayBlockingQueue。
ArrayBlockingQueue在實際使用過程中，會因為加鎖和僞共享等出現嚴重的性能問題，我們下面來分析一下。
現實程式設計過程中，加鎖通常會嚴重地影響性能。線程會因為競争不到鎖而被挂起，等鎖被釋放的時候，線程又會被恢複，這個過程中存在着很大的開銷，并且通常會有較長時間的中斷，因為當一個線程正在等待鎖時，它不能做任何其他事情。如果一個線程在持有鎖的情況下被延遲執行，例如發生了缺頁錯誤、排程延遲或者其它類似情況，那麼所有需要這個鎖的線程都無法執行下去。如果被阻塞線程的優先級較高，而持有鎖的線程優先級較低，就會發生優先級反轉。
Disruptor論文中講述了一個實驗：
這個測試程式調用了一個函數，該函數會對一個64位的計數器循環自增5億次。
機器環境：2.4G 6核
運算： 64位的計數器累加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個數量級；有鎖且多線程并發的情況下，速度比單線程無鎖慢3個數量級。可見無鎖速度最快。
單線程情況下，不加鎖的性能 > CAS操作的性能 > 加鎖的性能。
在多線程情況下，為了保證線程安全，必須使用CAS或鎖，這種情況下，CAS的性能超過鎖的性能，前者大約是後者的8倍。
綜上可知，加鎖的性能是最差的。
保證線程安全一般分成兩種方式：鎖和原子變量。
圖1 通過加鎖的方式實作線程安全
采取加鎖的方式，預設線程會沖突，通路資料時，先加上鎖再通路，通路之後再解鎖。通過鎖界定一個臨界區，同時隻有一個線程進入。如上圖所示，Thread2通路Entry的時候，加了鎖，Thread1就不能再執行通路Entry的代碼，進而保證線程安全。
下面是ArrayBlockingQueue通過加鎖的方式實作的offer方法，保證線程安全。
原子變量能夠保證原子性的操作，意思是某個任務在執行過程中，要麼全部成功，要麼全部失敗復原，恢複到執行之前的初态，不存在初态和成功之間的中間狀态。例如CAS操作，要麼比較并交換成功，要麼比較并交換失敗。由CPU保證原子性。
通過原子變量可以實作線程安全。執行某個任務的時候，先假定不會有沖突，若不發生沖突，則直接執行成功；當發生沖突的時候，則執行失敗，復原再重新操作，直到不發生沖突。
圖2 通過原子變量CAS實作線程安全
如圖所示，Thread1和Thread2都要把Entry加1。若不加鎖，也不使用CAS，有可能Thread1取到了myValue=1，Thread2也取到了myValue=1，然後相加，Entry中的value值為2。這與預期不相符，我們預期的是Entry的值經過兩次相加後等于3。
CAS會先把Entry現在的value跟線程當初讀出的值相比較，若相同，則指派；若不相同，則指派執行失敗。一般會通過while/for循環來重新執行，直到指派成功。
代碼示例是AtomicInteger的getAndAdd方法。CAS是CPU的一個指令，由CPU保證原子性。
在高度競争的情況下，鎖的性能将超過原子變量的性能，但是更真實的競争情況下，原子變量的性能将超過鎖的性能。同時原子變量不會有死鎖等活躍性問題。
下圖是計算的基本結構。L1、L2、L3分别表示一級緩存、二級緩存、三級緩存，越靠近CPU的緩存，速度越快，容量也越小。是以L1緩存很小但很快，并且緊靠着在使用它的CPU核心；L2大一些，也慢一些，并且仍然隻能被一個單獨的CPU核使用；L3更大、更慢，并且被單個插槽上的所有CPU核共享；最後是主存，由全部插槽上的所有CPU核共享。
圖3 計算機CPU與緩存示意圖
當CPU執行運算的時候，它先去L1查找所需的資料、再去L2、然後是L3，如果最後這些緩存中都沒有，所需的資料就要去主記憶體拿。走得越遠，運算耗費的時間就越長。是以如果你在做一些很頻繁的事，你要盡量確定資料在L1緩存中。
另外，線程之間共享一份資料的時候，需要一個線程把資料寫回主存，而另一個線程通路主存中相應的資料。
下面是從CPU通路不同層級資料的時間概念:
從CPU到
大約需要的CPU周期
大約需要的時間
主存
-
約60-80ns
QPI 總線傳輸(between sockets, not drawn)
約20ns
L3 cache
約40-45 cycles
約15ns
L2 cache
約10 cycles
約3ns
L1 cache
約3-4 cycles
約1ns
寄存器
1 cycle
可見CPU讀取主存中的資料會比從L1中讀取慢了近2個數量級。
Cache是由很多個cache line組成的。每個cache line通常是64位元組，并且它有效地引用主記憶體中的一塊兒位址。一個Java的long類型變量是8位元組，是以在一個緩存行中可以存8個long類型的變量。
CPU每次從主存中拉取資料時，會把相鄰的資料也存入同一個cache line。
在通路一個long數組的時候，如果數組中的一個值被加載到緩存中，它會自動加載另外7個。是以你能非常快的周遊這個數組。事實上，你可以非常快速的周遊在連續記憶體塊中配置設定的任意資料結構。
下面的例子是測試利用cache line的特性和不利用cache line的特性的效果對比。
在2G Hz、2核、8G記憶體的運作環境中測試，速度差一倍。
結果：
Loop times:30ms Loop times:65ms
ArrayBlockingQueue有三個成員變量： - takeIndex：需要被取走的元素下标 - putIndex：可被元素插入的位置的下标 - count：隊列中元素的數量
這三個變量很容易放到一個緩存行中，但是之間修改沒有太多的關聯。是以每次修改，都會使之前緩存的資料失效，進而不能完全達到共享的效果。
圖4 ArrayBlockingQueue僞共享示意圖
如上圖所示，當生産者線程put一個元素到ArrayBlockingQueue時，putIndex會修改，進而導緻消費者線程的緩存中的緩存行無效，需要從主存中重新讀取。
這種無法充分使用緩存行特性的現象，稱為僞共享。
對于僞共享，一般的解決方案是，增大數組元素的間隔使得由不同線程存取的元素位于不同的緩存行上，以空間換時間。
在2G Hz，2核，8G記憶體, jdk 1.7.0_45 的運作環境下，使用了共享機制比沒有使用共享機制，速度快了4倍左右。
Thread num 1 duration = 447
Thread num 2 duration = 463
Thread num 3 duration = 454
Thread num 4 duration = 464
Thread num 5 duration = 561
Thread num 6 duration = 606
Thread num 7 duration = 684
Thread num 8 duration = 870
Thread num 9 duration = 823
把代碼中ValuePadding都替換為ValueNoPadding後的結果：
Thread num 1 duration = 446
Thread num 2 duration = 2549
Thread num 3 duration = 2898
Thread num 4 duration = 3931
Thread num 5 duration = 4716
Thread num 6 duration = 5424
Thread num 7 duration = 4868
Thread num 8 duration = 4595
Thread num 9 duration = 4540
備注：在jdk1.8中，有專門的注解@Contended來避免僞共享，更優雅地解決問題。
Disruptor通過以下設計來解決隊列速度慢的問題：
環形數組結構
為了避免垃圾回收，采用數組而非連結清單。同時，數組對處理器的緩存機制更加友好。
元素位置定位
數組長度2^n，通過位運算，加快定位的速度。下标采取遞增的形式。不用擔心index溢出的問題。index是long類型，即使100萬QPS的處理速度，也需要30萬年才能用完。
無鎖設計
每個生産者或者消費者線程，會先申請可以操作的元素在數組中的位置，申請到之後，直接在該位置寫入或者讀取資料。
下面忽略數組的環形結構，介紹一下如何實作無鎖設計。整個過程通過原子變量CAS，保證操作的線程安全。
寫資料
生産者單線程寫資料的流程比較簡單：
申請寫入m個元素；
若是有m個元素可以入，則傳回最大的序列号。這兒主要判斷是否會覆寫未讀的元素；
若是傳回的正确，則生産者開始寫入元素。
圖5 單個生産者生産過程示意圖
多個生産者的情況下，會遇到“如何防止多個線程重複寫同一個元素”的問題。Disruptor的解決方法是，每個線程擷取不同的一段數組空間進行操作。這個通過CAS很容易達到。隻需要在配置設定元素的時候，通過CAS判斷一下這段空間是否已經配置設定出去即可。
但是會遇到一個新問題：如何防止讀取的時候，讀到還未寫的元素。Disruptor在多個生産者的情況下，引入了一個與Ring Buffer大小相同的buffer：available Buffer。當某個位置寫入成功的時候，便把availble Buffer相應的位置置位，标記為寫入成功。讀取的時候，會周遊available Buffer，來判斷元素是否已經就緒。
下面分讀資料和寫資料兩種情況介紹。
生産者多線程寫入的情況會複雜很多：
申請讀取到序号n；
若writer cursor >= n，這時仍然無法确定連續可讀的最大下标。從reader cursor開始讀取available Buffer，一直查到第一個不可用的元素，然後傳回最大連續可讀元素的位置；
消費者讀取元素。
如下圖所示，讀線程讀到下标為2的元素，三個線程Writer1/Writer2/Writer3正在向RingBuffer相應位置寫資料，寫線程被配置設定到的最大元素下标是11。
讀線程申請讀取到下标從3到11的元素，判斷writer cursor>=11。然後開始讀取availableBuffer，從3開始，往後讀取，發現下标為7的元素沒有生産成功，于是WaitFor(11)傳回6。
然後，消費者讀取下标從3到6共計4個元素。
圖6 多個生産者情況下，消費者消費過程示意圖
多個生産者寫入的時候：
若是有m個元素可以寫入，則傳回最大的序列号。每個生産者會被配置設定一段獨享的空間；
生産者寫入元素，寫入元素的同時設定available Buffer裡面相應的位置，以标記自己哪些位置是已經寫入成功的。
如下圖所示，Writer1和Writer2兩個線程寫入數組，都申請可寫的數組空間。Writer1被配置設定了下标3到下表5的空間，Writer2被配置設定了下标6到下标9的空間。
Writer1寫入下标3位置的元素，同時把available Buffer相應位置置位，标記已經寫入成功，往後移一位，開始寫下标4位置的元素。Writer2同樣的方式。最終都寫入完成。
圖7 多個生産者情況下，生産者生産過程示意圖
防止不同生産者對同一段空間寫入的代碼，如下所示：
通過do/while循環的條件cursor.compareAndSet(current, next)，來判斷每次申請的空間是否已經被其他生産者占據。假如已經被占據，該函數會傳回失敗，While循環重新執行，申請寫入空間。
消費者的流程與生産者非常類似，這兒就不多描述了。
Disruptor通過精巧的無鎖設計實作了在高并發情形下的高性能。
在美團内部，很多高并發場景借鑒了Disruptor的設計，減少競争的強度。其設計思想可以擴充到分布式場景，通過無鎖設計，來提升服務性能。
使用Disruptor比使用ArrayBlockingQueue略微複雜，為友善讀者上手，增加代碼樣例。
代碼實作的功能：每10ms向disruptor中插入一個元素，消費者讀取資料，并列印到終端。詳細邏輯請細讀代碼。
以下代碼基于3.3.4版本的Disruptor包。
以下面這些模式測試性能:
吞吐量測試資料（每秒的數量）如下。
環境： - CPU:Intel Core i7 860 @ 2.8 GHz without HT - JVM:Java 1.6.0_25 64-bit - OS:Windows 7
ABQ
Disruptor
Unicast: 1P – 1C
5,339,256
25,998,336
Pipeline: 1P – 3C
2,128,918
16,806,157
Sequencer: 3P – 1C
5,539,531
13,403,268
Multicast: 1P – 3C
1,077,384
9,377,871
Diamond: 1P – 3C
2,113,941
16,143,613
環境：
CPU:Intel Core i7-2720QM
JVM:Java 1.6.0_25 64-bit
OS:Ubuntu 11.04
4,057,453
22,381,378
2,006,903
15,857,913
2,056,118
14,540,519
260,733
10,860,121
2,082,725
15,295,197
依據并發競争的激烈程度的不同，Disruptor比ArrayBlockingQueue吞吐量快4~7倍。
按照Pipeline: 1P – 3C的連接配接模式測試延遲，生産者兩次寫入之間的延遲為1ms。
運作環境：
CPU:2.2GHz Core i7-2720QM
Java: 1.6.0_25 64-bit
OS:Ubuntu 11.04.
Array Blocking Queue (ns)
Disruptor (ns)
99% observations less than
2,097,152
128
99.99% observations less than
4,194,304
8,192
Max Latency
5,069,086
175,567
Mean Latency
32,757
52
Min Latency
145
29
可見，平均延遲差了3個數量級。
暫時隻有休眠1ns。
名稱
措施
适用場景
BlockingWaitStrategy
CPU資源緊缺，吞吐量和延遲并不重要的場景
BusySpinWaitStrategy
自旋
通過不斷重試，減少切換線程導緻的系統調用，而降低延遲。推薦線上程綁定到固定的CPU的場景下使用
PhasedBackoffWaitStrategy
自旋 + yield + 自定義政策
SleepingWaitStrategy
自旋 + yield + sleep
性能和CPU資源之間有很好的折中。延遲不均勻
TimeoutBlockingWaitStrategy
加鎖，有逾時限制
YieldingWaitStrategy
自旋 + yield + 自旋
性能和CPU資源之間有很好的折中。延遲比較均勻
Log4j 2相對于Log4j 1最大的優勢在于多線程并發場景下性能更優。該特性源自于Log4j 2的異步模式采用了Disruptor來處理。 在Log4j 2的配置檔案中可以配置WaitStrategy，預設是Timeout政策。下面是Log4j 2中對WaitStrategy的配置官方文檔：
System Property
Default Value
Description
AsyncLogger.WaitStrategy
Timeout
Valid values: Block, Timeout, Sleep, Yield. Block is a strategy that uses a lock and condition variable for the I/O thread waiting for log events. Block can be used when throughput and low-latency are not as important as CPU resource. Recommended for resource constrained/virtualised environments. Timeout is a variation of the Block strategy that will periodically wake up from the lock condition await() call. This ensures that if a notification is missed somehow the consumer thread is not stuck but will recover with a small latency delay (default 10ms). Sleep is a strategy that initially spins, then uses a Thread.yield(), and eventually parks for the minimum number of nanos the OS and JVM will allow while the I/O thread is waiting for log events. Sleep is a good compromise between performance and CPU resource. This strategy has very low impact on the application thread, in exchange for some additional latency for actually getting the message logged. Yield is a strategy that uses a Thread.yield() for waiting for log events after an initially spinning. Yield is a good compromise between performance and CPU resource, but may use more CPU than Sleep in order to get the message logged to disk sooner.
loggers all async采用的是Disruptor，而Async Appender采用的是ArrayBlockingQueue隊列。
由圖可見，單線程情況下，loggers all async與Async Appender吞吐量相差不大，但是在64個線程的時候，loggers all async的吞吐量比Async Appender增加了12倍，是Sync模式的68倍。
圖8 Log4j 2各個模式性能比較
美團在公司内部統一推行日志接入規範，要求必須使用Log4j 2，使普通單機QPS的上限不再隻停留在幾千，極高地提升了服務性能。
http://brokendreams.iteye.com/blog/2255720
http://ifeve.com/dissecting-disruptor-whats-so-special/
https://github.com/LMAX-Exchange/disruptor/wiki/Performance-Results
https://lmax-exchange.github.io/disruptor/
https://logging.apache.org/log4j/2.x/manual/async.html
https://tech.meituan.com/2016/11/18/disruptor.html