Disruptor是LMAX公司開源的一個高效的記憶體無鎖隊列。這兩天看了一下相關的設計文檔和部落格，下面嘗試進行一下總結。
第一部分。引子 談到并發程式設計，有幾個概念是避免不了的。
1.鎖 ：鎖是用來做并發最簡單的方式，當然其代價也是最高的。核心态的鎖的時候需要作業系統進行一次上下文切換，等待鎖的線程會被挂起直至鎖釋放。在上下文切換的時候，cpu之前緩存的指令和資料都将失效，對性能有很大的損失。使用者态的鎖雖然避免了這些問題，但是其實它們隻是在沒有真實的競争時才有效。下面是一個計數實驗中不加鎖、使用鎖、使用CAS及定義volatile變量之間的性能對比。
- CAS ： CAS的涵義不多介紹了。使用CAS時不像上鎖那樣需要一次上下文切換，但是也需要處理器鎖住它的指令流水線來保證原子性，并且還要加上Memory Barrier來保證其結果可見。
- Memory Barrier : 大家都知道現代CPU是亂序執行的，也就是程式順序與實際的執行順序很可能是不一緻的。在單線程執行時這不是個問題，但是在多線程環境下這種亂序就可能會對執行結果産生很大的影響了。memory barrier提供了一種控制程式執行順序的手段, 關于其更多介紹，可以參考 http://en.wikipedia.org/wiki/Memory_barrier
- Cache Line ：cache line解釋起來其實很簡單，就是CPU在做緩存的時候有個最小緩存單元，在同一個單元内的資料被同時被加載到緩存中，充分利用 cache line可以大大降低資料讀寫的延遲，錯誤利用cache line也會導緻緩存不同替換，反複失效。
好，接下來談一談設計并發記憶體隊列時需要考慮的問題。一就是資料結構的問題，是選用定長的數組還是可變的連結清單，二是并發控問題，是使用鎖還是CAS 操作，是使用粗粒度的一把鎖還是将隊列的頭、尾、和容量三個變量分開控制，即使分開，能不能避免它們落入同一個Cache line中呢。 我們再回過頭來思考一下隊列的使用場景。通常我們的處理會形成一條流水線或者圖結構，隊列被用來作為這些流程中間的銜接表示它們之間的依賴關系，同時起到一個緩沖的作用。但是使用隊列并不是沒有代價的，實際上資料的入隊和出隊都是很耗時的，尤其在性能要求極高的場景中，這種消耗更顯得奢侈。如果這種依賴能夠不通過在各個流程之間放一個隊列來表示那就好啦！
第二部分 正文 現在開始來介紹我們的Disruptor啦，有了前面這麼多的鋪墊，我想可以直入主題了。接下來我們就從隊列的三種基本問題來細細分析下disruptor吧。
1.列隊中的元素如何存儲？ Disruptor的中心資料結構是一個基于定長數組的環形隊列，如圖1。 在數組建立時可以預先配置設定好空間，插入新元素時隻要将新元素資料拷貝到已經配置設定好的記憶體中即可。對數組的元素通路對CPU cache 是非常友好的。關于數組的大小選擇有一個講究，大家都知道環形隊列中會用到取餘操作， 在大部分處理器上，取餘操作并不高效。是以可以将數組大小設定為2的指數倍，這樣計算餘數隻需要通過位操作 index & ( size -1 )就能夠得到實際的index。 Disruptor對外隻有一個變量，那就是隊尾元素的下标：cursor，這也避免了對head/tail這兩個變量的操作和協同。生産者和消費者對 disruptor的通路分别需要通過producer barrier和consumer barrier來協調。關于這兩個barrier是啥，後面會介紹。
圖1. RingBuffer,目前的隊尾元素位置為18
2.生産者如何向隊列中插入元素？ 生産者插入元素分為兩個步驟，第一步申請一個空的slot, 每個slot隻會被一個生産者占用，申請到空的slot的生産者将新元素的資料拷貝到該slot；第二步是釋出，釋出之後，新元素才能為消費者所見。如果隻有一個生産者，第一步申請操作無需同步即可完成。如果有多個生産者，那麼會有一個變量：claimSequence來記錄申請位置，申請操作需要通過 CAS來同步，例如圖二中，如果兩個生産者都想申請第19号slot, 則它們會同時執行CAS(&claimSequence, 18, 19)，執行成功的人得到該slot，另一個則需要繼續申請下一個可用的slot。在disruptor中，釋出成功的順序與申請的順序是嚴格保持一緻的，在實作上，釋出事件實際上就是修改cursor的值，操作等價于CAS(&cursor, myslot-1, myslot)，從此操作也可以看出，釋出執行成功的順序必定是slot, slot 1, slot 2 ….嚴格有序的。另外，為了防止生産者生産過快，在環形隊列中覆寫消費者的資料，生産者要對消費者的消費情況進行跟蹤，實作上就是去讀取一下每個消費者目前的消費位置。例如一個環形隊列的大小是8，有兩個消費者的分别消費到第13和14号元素，那麼生産者生産的新元素是不能超過20的。插入元素的過程圖示如下：
圖2. RingBuffer目前的隊尾位置序号為18.生産者提出申請。
圖3. 生産者申請得到第19号位置，并且19号位置是獨占的，可以寫入生産元素。此時19号元素對消費者是不可見的。
圖4，生産者成功寫入19号位置後，将cursor修改為19，進而完成釋出，之後消費者可以消費19号元素。
3.消費者如何獲知有新的元素進來了？ 消費者需要等待有新元素進入方能繼續消費，也就是說cursor大于自己目前的消費位置。等待政策有多種。可以選擇sleep wait, busy spin等等，在使用disruptor時，可以根據場景選擇不同的等待政策。
4.批量 如果消費者發現cursor相比其最後的一次消費位置前進了不止一個位置，它就可以選擇批量消費這區段的元素，而不是一次一個的向前推進。這種做法在提高吞吐量的同時還可以使系統的延遲更加平滑。
5.依賴圖 前面也提過，在傳統的系統中，通常使用隊列來表示多個處理流程之間的依賴，并且一步依賴就需要多添加一個隊列。在Disruptor中，由于生産者和消費者是分開考慮和控制的，是以有可能能夠通過一個核心的環形隊列來表示全部的依賴關系，可以大大提高吞吐，降低延遲。當然，要達到這個目的，還需要使用者細心地去設計。下面舉一個簡單的例子來說明如何使用disruptor來表示依賴關系。
| |
第三部分 結束語 disruptor本身是用java寫的，但是筆者認為在c 中更能展現其優點，自己也山寨了一個c 版本。在一個生産者和一個消費者的場景中測試表明，無鎖隊列相比有鎖隊列，qps有大約10倍的提升，latency更是有幾百倍的提升。不管怎麼樣，現在大家都漸漸都這麼一個意識了：鎖是性能殺手。是以這些無鎖的資料結構和算法，可以嘗試借鑒來使用在合适的場景中。
http://liuxun.org/blog/disruptor-yi-ge-kai-yuan-de-gao-xiao-nei-cun-wu-suo-dui-lie/點選打開連結