LMAX Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads

《LMAX Disruptor：用于并發(fā)線程間交換數(shù)據(jù)的有界隊(duì)列的高性能替代方案》

作者 Martin Thompson

     Dave Farley

     Michael Barker

     Patricia Gee

     Andrew Stewart

版本 Version 4.0.0-SNAPSHOT,May 2011

摘要

LMAX的成立旨在是要創(chuàng)建一個非常高性能的線上金融交易所。而作為我們實(shí)現(xiàn)這一目標(biāo)的工作的一部分，我們評估了設(shè)計(jì)這樣一個系統(tǒng)的幾種方法，但是當(dāng)我們開始評估和測試這些方法時，我們遇到了一些傳統(tǒng)方法的基本限制和瓶頸。

許多應(yīng)用系統(tǒng)要依賴隊(duì)列在處理階段之間交換數(shù)據(jù)。我們的性能測試表明，以這種方式使用隊(duì)列時，延遲成本與磁盤IO操作（基于RAID或SSD的磁盤系統(tǒng)）的成本基本同一個數(shù)量級——非常慢。如果在一個端到端操作中有多個隊(duì)列，這將使總延遲增加數(shù)百微秒。這顯然是還有優(yōu)化空間的。

進(jìn)一步的研究和對計(jì)算機(jī)科學(xué)原理的關(guān)注使我們認(rèn)識到，傳統(tǒng)方法（如隊(duì)列和處理節(jié)點(diǎn)）中固有的因素的共同作用（ the conflation of concerns inherent in conventional approaches）會導(dǎo)致多線程實(shí)現(xiàn)中的爭用，這表明可能有更好的方法。

考慮到現(xiàn)代cpu是如何工作的，我們喜歡稱之為“機(jī)械共鳴”，軟件與底層硬件的機(jī)制呼應(yīng)上了，使用良好的設(shè)計(jì)實(shí)踐，并將重點(diǎn)放在解決導(dǎo)致多線程爭用的因素上（a strong focus on teasing apart the concerns），我們提出了一種新的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)模式，這就是我們的Disruptor框架。

測試表明，對于一個有3個階段的業(yè)務(wù)處理流程pipeline，使用Disruptor方案的平均延遲比對應(yīng)的基于隊(duì)列的方案低3個數(shù)量級。此外，對于相同的配置，Disruptor處理的吞吐量大約是原來的8倍。

這些性能改進(jìn)代表了并發(fā)編程思想的一個階段性變化。這種新模式是任何需要高吞吐量和低延遲的異步事件處理架構(gòu)的理想基礎(chǔ)。

在LMAX，我們已經(jīng)構(gòu)建了一個訂單匹配引擎、實(shí)時風(fēng)險管理和一個高度可用的內(nèi)存事務(wù)處理系統(tǒng)，所有這些都基于了這種模式并取得了巨大的成功。這些系統(tǒng)中的每一個都制定了新的性能標(biāo)準(zhǔn)，而據(jù)我們所知，這些標(biāo)準(zhǔn)是無與倫比的。

我們的基于Disruptor的方案并不是一個僅與金融行業(yè)相關(guān)的特定專業(yè)領(lǐng)域內(nèi)的解決方案。Disruptor是一種通用機(jī)制，它以一種性能最大化的方式解決并發(fā)編程中的復(fù)雜問題，并且易于實(shí)現(xiàn)。使用的過程中，盡管這個框架的一些個設(shè)計(jì)上的概念、可能一開始理解起來不習(xí)慣，但根據(jù)我們的經(jīng)驗(yàn)，一旦熟悉、按照這種模式構(gòu)建的系統(tǒng)要比類似的機(jī)制簡單得多。

與同類方案相比，Disruptor具有顯著的更少的寫爭用、更低的并發(fā)開銷、對CPU的緩存機(jī)制更友好，所有這些都使得其在更低的延遲下產(chǎn)生更大的吞吐量和更少性能上的抖動。在中等時鐘頻率的處理器上，我們已經(jīng)看到每秒處理超過2500萬條消息，延遲低于50納秒。與我們所看到的任何其他實(shí)現(xiàn)相比，此性能是一個顯著的改進(jìn)。這已經(jīng)非常接近現(xiàn)代處理器在內(nèi)核之間交換數(shù)據(jù)的硬件上的理論極限了。

1. 概述

Disruptor是我們努力在LMAX公司建立世界上性能最高的在線金融交易所這一工作目標(biāo)下的成果。早期的設(shè)計(jì)側(cè)重于從SEDA[1]和Actors[2]派生的架構(gòu)，它們使用pipeline模型來實(shí)現(xiàn)吞吐量。在分析了各種實(shí)現(xiàn)之后，很明顯，pipeline模型中各階段之間的事件排隊(duì)是主要的成本。我們發(fā)現(xiàn)隊(duì)列還引入了延遲和很高的性能抖動（性能很不穩(wěn)定、每次測試結(jié)果差異很大）。我們花了大量精力開發(fā)性能更好的新隊(duì)列實(shí)現(xiàn)。然而，顯而易見的是，隊(duì)列作為一種基本的數(shù)據(jù)結(jié)構(gòu)，由于生產(chǎn)者、消費(fèi)者和他們的數(shù)據(jù)存儲的設(shè)計(jì)關(guān)注點(diǎn)的合并（the conflation of design concerns）而受到限制。Disruptor是我們構(gòu)建一個干凈地分離這些關(guān)注點(diǎn)的并發(fā)數(shù)據(jù)結(jié)構(gòu)的成果。

2. 并發(fā)的復(fù)雜性

在本文以及在一般的計(jì)算機(jī)科學(xué)理論中，并發(fā)不僅意味著兩個以上任務(wù)同時并行發(fā)生，而且意味著它們在訪問資源時相互競爭。爭用的資源可以是數(shù)據(jù)庫、文件、socket，甚至是內(nèi)存中的一個位置。

代碼的并發(fā)執(zhí)行涉及兩件事：互斥和內(nèi)存可見性?；コ馐顷P(guān)于如何管理保證某些資源的獨(dú)占式使用。內(nèi)存可見性是關(guān)于控制內(nèi)存更改何時對其他線程可見。如果你可以避免多線程競爭的去更新共享資源，那么就可以避免互斥。如果您的算法可以保證任何給定的資源只被一個線程修改，那么互斥是不必要的。讀寫操作要求所有更改對其他線程可見。但是，只有爭用的寫操作需要對更改進(jìn)行互斥。

在任何并發(fā)環(huán)境中，最昂貴的操作是爭用寫訪問。要讓多個線程寫入同一資源，需要復(fù)雜而昂貴的協(xié)調(diào)。通常，這是通過采用某種鎖策略來實(shí)現(xiàn)的。

2.1 鎖的開銷

鎖可以提供互斥，并確保以有序的方式發(fā)生更改的可見性。但鎖的開銷是難以置信的昂貴，因?yàn)殒i爭用時需要仲裁。這種仲裁是通過操作系統(tǒng)內(nèi)核的上下文切換來實(shí)現(xiàn)的，這將掛起等待鎖的所有線程，直到鎖被釋放。在這樣的上下文切換期間，以及釋放對操作系統(tǒng)的控制（操作系統(tǒng)可能決定在有控制權(quán)的情況下執(zhí)行其他內(nèi)部管理任務(wù)），執(zhí)行上下文可能會丟失以前緩存的數(shù)據(jù)和指令。這會對現(xiàn)代處理器的性能產(chǎn)生嚴(yán)重影響?？梢允褂每焖俚挠脩魬B(tài)的鎖，但這些鎖只有在不爭用時才有真正的好處。

我們將通過一個簡單的演示來說明鎖的成本。這個實(shí)驗(yàn)的重點(diǎn)是調(diào)用一個函數(shù)，該函數(shù)在一個循環(huán)中使一個64位計(jì)數(shù)器遞增5億次。如果是用Java編寫的，這可以由2.4Ghz Intel Westmere EP上的單個線程在300毫秒內(nèi)執(zhí)行。使用何種語言對于這個實(shí)驗(yàn)來說并不重要，對于所有具有相同基本原語的語言，結(jié)果都是相似的。

一旦引入一個鎖來提供互斥，即使鎖還沒有被爭用，成本也會顯著增加。當(dāng)兩個或多個線程開始爭用時，成本又會增加幾個數(shù)量級。這個簡單實(shí)驗(yàn)的結(jié)果如下表所示：

2.2 CAS的開銷

當(dāng)更新的目標(biāo)是單個內(nèi)存變量時，可以采用比使用鎖更有效的替代方法來更新內(nèi)存。這些替代方案基于現(xiàn)代處理器中實(shí)現(xiàn)的原子指令或互鎖指令。這些操作通常稱為CAS（比較和交換）操作，例如x86上的“l(fā)ock cmpxchg”。CAS操作是一種特殊的機(jī)器代碼指令，它允許將內(nèi)存中的字有條件地設(shè)置為原子操作。比如對于前面的“遞增計(jì)數(shù)器實(shí)驗(yàn)”例子，每個線程都可以在一個循環(huán)中自旋，讀取計(jì)數(shù)器，然后嘗試以原子方式將其設(shè)置為新的遞增值。舊值和新值作為本指令的參數(shù)提供。如果在執(zhí)行操作時，計(jì)數(shù)器的值與提供的預(yù)期值匹配，則計(jì)數(shù)器將用新值更新。另一方面，如果該值不符合預(yù)期，則CAS操作將失敗。然后由嘗試執(zhí)行更改計(jì)數(shù)器的線程重試，重新讀取從該值遞增的計(jì)數(shù)器，依此類推，直到更改成功。這種CAS方法比鎖更有效，因?yàn)樗恍枰舷挛那袚Q到內(nèi)核態(tài)進(jìn)行仲裁。但是CAS操作也并不是完全沒有開銷的。處理器必須鎖定其指令管道以確保原子性，并使用內(nèi)存屏障使更改對其他線程可見。通過使用Java.util.concurrent.Atomic*類，可以在Java中使用CAS操作。

筆者注：CAS無需線程進(jìn)行上下文切換到內(nèi)核態(tài)去執(zhí)行，在用戶態(tài)執(zhí)行了CPU的原語指令cmpxchg，這里可能有疑問，指令分為特權(quán)指令和非特權(quán)指令，用戶態(tài)是可以執(zhí)行非特權(quán)指令的。所以這里糾正一個錯誤理解就是并不是發(fā)生了系統(tǒng)調(diào)用就一定是內(nèi)核態(tài)，內(nèi)核態(tài)和用戶態(tài)是用CPU中的程序狀態(tài)字寄存器PSW，當(dāng)該寄存器值為0時表示CPU處于用戶態(tài)、為1時表示處于核心態(tài)（此刻執(zhí)行的線程處于內(nèi)核態(tài)）。

https://blog.csdn.net/qq_19018277/article/details/98225102 《非特權(quán)指令、特權(quán)指令，用戶態(tài)、核心態(tài)》

如果程序的關(guān)鍵部分比計(jì)數(shù)器的簡單增量更復(fù)雜，則可能需要使用多個CAS操作的復(fù)雜狀態(tài)機(jī)來編排爭用。使用鎖開發(fā)并發(fā)程序是困難的；而使用CAS操作和內(nèi)存屏障開發(fā)無鎖算法要更加復(fù)雜多倍，而且難于測試和證明正確性。

理想的算法是只有一個線程負(fù)責(zé)對單個資源的所有寫入操作，而其他線程則讀取結(jié)果。而說到在多處理器環(huán)境中讀取結(jié)果，需要內(nèi)存屏障，以確保在其他處理器上運(yùn)行的線程可以立即看到更改。

2.3 內(nèi)存屏障

出于提升性能的原因，現(xiàn)代處理器執(zhí)行指令、以及內(nèi)存和執(zhí)行單元之間數(shù)據(jù)的加載和存儲都是不保證順序的。不管實(shí)際的執(zhí)行順序如何，處理器只需保證與程序邏輯的順序產(chǎn)生相同的結(jié)果即可。這在單線程的程序中不是一個問題。但是，當(dāng)線程共享狀態(tài)時，為了確保數(shù)據(jù)交換的成功與正確，在需要的時候、內(nèi)存的改變能夠以正確的順序顯式是非常重要的。處理器使用內(nèi)存屏障來指示內(nèi)存更新順序很重要的代碼部分。它們是在線程之間實(shí)現(xiàn)硬件排序和更改可見性的方法。編譯器可以設(shè)置免費(fèi)的軟件屏障，以確保編譯代碼的順序，也就是除了處理器本身使用的硬件屏障之外，還存在這樣的軟件內(nèi)存屏障。

現(xiàn)代的CPU現(xiàn)在比當(dāng)前一代的內(nèi)存系統(tǒng)快得多。為了彌合這一鴻溝，CPU使用復(fù)雜的高速緩存系統(tǒng)，這些系統(tǒng)是有效的快速硬件哈希表，無需鏈接。這些緩存通過消息傳遞協(xié)議與其他處理器緩存系統(tǒng)保持一致。此外，處理器還具有“存儲緩沖區(qū)”（store buffer/load buffer，比L1緩存更靠近CPU，跟寄存器同一個級別，用來當(dāng)作CPU與高速緩存之間的緩沖。畢竟高速緩存由于一致性的問題也會阻塞）來緩沖對這些緩存的寫入，以及作為“失效隊(duì)列”，以便緩存一致性協(xié)議能夠在即將發(fā)生寫入時快速確認(rèn)失效消息，以提高效率。

這對數(shù)據(jù)意味著，任何值的最新版本在被寫入后的任何階段都可以位于寄存器、存儲緩沖區(qū)、L1/L2/L3緩存之一或主內(nèi)存中。如果線程要共享此值，則需要以有序的方式使其可見，這是通過協(xié)調(diào)緩存一致性消息的交換來實(shí)現(xiàn)的。這些信息的及時產(chǎn)生可以通過內(nèi)存屏障來控制。

• A read memory barrier orders load instructions on the CPU that executes it by marking a point in the invalidate queue for changes coming into its cache. This gives it a consistent view of the world for write operations ordered before the read barrier.

• A write barrier orders store instructions on the CPU that executes it by marking a point in the store buffer, thus flushing writes out via its cache. This barrier gives an ordered view to the world of what store operations happen before the write barrier.

• A full memory barrier orders both loads and stores but only on the CPU that executes it.

除了這三個原語之外，有些CPU還有更多的變體，但這三個原語足以理解所涉及內(nèi)容的復(fù)雜性。在Java內(nèi)存模型中，volatile字段的讀寫分別實(shí)現(xiàn)了讀寫屏障。這在Java內(nèi)存模型中是明確的[3]正如Java5發(fā)行版所定義的那樣。

理解這節(jié)需要了解內(nèi)存屏障的底層實(shí)現(xiàn)原理和CPU緩存一致性協(xié)議相關(guān)的知識。https://blog.csdn.net/m0_37561834/article/details/78457078

2.4 緩存行

高速緩存在現(xiàn)代處理器中的使用方式對于成功的高性能操作具有極其重要的意義。這樣的處理器在處理高速緩存中的數(shù)據(jù)和指令時非常高效，但在發(fā)生高速緩存丟失時，效率相對非常低。

我們的硬件不會以byte或word(字，1字=2byte)的形式移動內(nèi)存。為了提高效率，緩存被組織成大小通常為32-256字節(jié)的緩存行cacheline，最常見的cacheline是64字節(jié)。這是緩存一致性協(xié)議MESI操作的粒度級別。這意味著，如果兩個變量位于同一個cacheline中，并且它們是由不同的線程寫入的，那么它們將出現(xiàn)與單個變量相同的寫爭用問題。這是一個被稱為“偽共享”的概念。為了獲得高性能、盡量最小化爭用，確保獨(dú)立但同時寫入的變量不共享同一cacheline是非常重要的。

當(dāng)以可預(yù)測的方式訪問內(nèi)存時，cpu能夠通過預(yù)測下一個可能訪問的內(nèi)存并在后臺將其預(yù)取到緩存中來減少下一次訪問主內(nèi)存的延遲成本。只有當(dāng)處理器能夠預(yù)測一個固定內(nèi)存訪問的模式、比如以可預(yù)測的“步幅”遍歷一塊內(nèi)存，這種方法才有效。當(dāng)?shù)鷶?shù)組的內(nèi)容時，步長是可預(yù)測的，因此內(nèi)存將被預(yù)讀到cacheline，從而最大限度地提高訪問效率。步長通常必須小于2048字節(jié)，處理器才能注意到。然而，像鏈表和樹這樣的數(shù)據(jù)結(jié)構(gòu)往往有節(jié)點(diǎn)，這些節(jié)點(diǎn)在內(nèi)存中分布更廣，沒有可預(yù)測的訪問步長。內(nèi)存中缺少一致的模式限制了系統(tǒng)預(yù)取cacheline的能力，從而導(dǎo)致只能直接訪問主存——其性能較高速緩存要降低2個數(shù)量級以上。

筆者注：其實(shí)第2節(jié)都是在講理論儲備，2.4概括來說就是一句話，為了有效利用CPU的高速緩存機(jī)制，我們應(yīng)該盡量用順序存儲結(jié)構(gòu)，比如數(shù)組

2.5 隊(duì)列帶來的問題

隊(duì)列通常使用鏈表或數(shù)組作為元素的底層存儲。如果允許內(nèi)存中的隊(duì)列是無界的，那么對于許多類的問題，它可以不受約束地增長，直到耗盡內(nèi)存而達(dá)到災(zāi)難性的后果，當(dāng)生產(chǎn)者超過消費(fèi)者時就會發(fā)生這種情況。無界隊(duì)列在可以在生產(chǎn)者可以保證不超過消費(fèi)者的系統(tǒng)中使用，因?yàn)閮?nèi)存是一種寶貴的資源，但是如果這種假設(shè)不成立，而隊(duì)列增長沒有限制，那么總是有風(fēng)險的。為了避免這種災(zāi)難性的結(jié)果，隊(duì)列的大小通常要受到限制（有界）。要使隊(duì)列保持有界，就需要對其底層選擇數(shù)組結(jié)構(gòu)或主動跟蹤其大小。

隊(duì)列的實(shí)現(xiàn)往往要在head、tail和size變量上有寫爭用。在使用時，由于消費(fèi)者和生產(chǎn)者之間的速度差異，隊(duì)列通?？偸墙咏跐M或接近于空。它們很少在生產(chǎn)和消費(fèi)速率均衡的中間地帶運(yùn)作。這種總是滿的或總是空的傾向會導(dǎo)致高級別的爭用、和/或昂貴的緩存一致性。問題在于，即使head和tail使用不同的并發(fā)對象（如鎖或CAS變量）來進(jìn)行讀寫鎖分離，它們通常也占用相同的cacheline。

管理生產(chǎn)者申請隊(duì)列的head，消費(fèi)者申請隊(duì)列的tail，以及中間節(jié)點(diǎn)的存儲，這些問題使得并發(fā)實(shí)現(xiàn)的設(shè)計(jì)非常復(fù)雜，除了在隊(duì)列上使用一個粗粒度的鎖之外，還難以管理。對于put和take操作，使用整個隊(duì)列上的粗粒度鎖實(shí)現(xiàn)起來很簡單，但對吞吐量來說是一個很大的瓶頸。如果并發(fā)關(guān)注點(diǎn)在隊(duì)列的語義中被分離開來，那么對于除單個生產(chǎn)者-單個消費(fèi)者之外的任何場景，實(shí)現(xiàn)都變得非常復(fù)雜。

在Java中，隊(duì)列的使用還有一個問題，因?yàn)樗鼈儠a(chǎn)生較多的垃圾對象。因?yàn)?，必須在?duì)列中分配和放置對象。其次，如果支持鏈表，則必須分配表示鏈表節(jié)點(diǎn)的對象。當(dāng)不再被引用時，需要重新聲明為支持隊(duì)列實(shí)現(xiàn)而分配的所有的這些對象。

筆者注：這節(jié)大意是推薦使用有界隊(duì)列以避免內(nèi)存耗盡問題，隊(duì)列的head、tail、size等變量通常會占用相同的cacheline從而引發(fā)偽共享問題，這樣即便是嘗試使用讀寫鎖分離的策略，由于無法有效利用高速緩存機(jī)制，性能也很難達(dá)到最優(yōu)。隊(duì)列中鎖的粒度比較粗，帶來吞吐量上的性能影響。Java實(shí)現(xiàn)的隊(duì)列容易產(chǎn)生較多垃圾對象。

2.6 Pipelines and Graphs

對于許多類型的問題，都可以將幾個處理階段連接到一個管道pipeline中。有時候幾個這樣的管道又具有并行路徑，可以被組織成圖形拓?fù)錉畹膱?zhí)行流程。而每個階段之間的連接通常由隊(duì)列實(shí)現(xiàn)，每個階段都有自己的處理線程。

上述所說的這種方案的開銷并不小——在每一個階段，我們都必須承擔(dān)工作單元入隊(duì)和出隊(duì)的成本。當(dāng)路徑必須分叉fork時，目標(biāo)的數(shù)量將此成本相乘，當(dāng)路徑必須在分叉之后重新連接時，將不可避免地產(chǎn)生爭用成本。

如果我們的流程模型可以即表示stage之間的依賴關(guān)系圖，而不需要在階段之間放置隊(duì)列，這將是非常理想的方案。

3. LMAX Disruptor的設(shè)計(jì)

在試圖解決上述問題的同時，通過嚴(yán)格分離在隊(duì)列中被合并的關(guān)注點(diǎn)，出現(xiàn)了一種設(shè)計(jì)。這種方法結(jié)合了一個重點(diǎn)，即確保任何數(shù)據(jù)只能由一個線程擁有以進(jìn)行寫訪問，從而消除寫爭用。這種設(shè)計(jì)被稱為“Disruptor”。它之所以這樣命名，是因?yàn)樗谔幚砼cJava7中的“Phasers”[4]概念的圖狀依賴關(guān)系時具有相似的點(diǎn)，而Java7是為了支持Fork-Join而引入的。

LMAX Disruptor旨在解決上述所有問題，試圖最大限度地提高內(nèi)存分配效率，并以緩存友好的方式運(yùn)行，以便在現(xiàn)代硬件上以最佳方式運(yùn)行。Disruptor機(jī)制的核心是一個以環(huán)形緩沖區(qū)的形式預(yù)先分配的有界數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)通過一個或多個生產(chǎn)者添加到環(huán)形緩沖區(qū)，并由一個或多個消費(fèi)者進(jìn)行處理。

3.1 內(nèi)存分配

啟動時，將預(yù)先分配環(huán)形緩沖區(qū)的所有內(nèi)存。環(huán)形緩沖區(qū)可以存儲指向entry的指針數(shù)組，也可以存儲表示entry的結(jié)構(gòu)數(shù)組。Java語言的局限性意味著entry作為指向?qū)ο蟮闹羔樑c環(huán)形緩沖區(qū)相關(guān)聯(lián)。這些entry中的每一個通常不是傳遞的數(shù)據(jù)本身，而是它的容器。這種entry的預(yù)分配消除了支持垃圾回收的語言中的問題，因?yàn)閑ntry將被重用，并在整個Disruptor實(shí)例存活期間都有效。這些entry的內(nèi)存是同時分配的，很可能會在主內(nèi)存中連續(xù)布局，因此支持高速緩存預(yù)讀。John Rose提議在Java語言中引入“值類型”[5]，這將允許元組數(shù)組，就像C等其他語言一樣，從而確保連續(xù)分配內(nèi)存并避免指針間接尋址。

在像Java這樣的托管運(yùn)行時環(huán)境中開發(fā)低延遲系統(tǒng)時，垃圾收集機(jī)制可能會帶來問題。分配的內(nèi)存越多，給垃圾收集器帶來的負(fù)擔(dān)就越大。當(dāng)對象的壽命很短或?qū)嶋H上是常駐的時候，垃圾收集器工作得最好。在環(huán)形緩沖區(qū)中預(yù)先分配entry意味著它對于垃圾收集器來說是常駐內(nèi)存的，因此帶來很少的負(fù)擔(dān)。

在重負(fù)載情況下，基于隊(duì)列的系統(tǒng)會發(fā)生堵塞，這會導(dǎo)致處理速度的降低，并導(dǎo)致分配的對象比原本正常情況下存活的時間更長，因此會被通過分代垃圾收集器提升到年輕一代之外。這有兩個含義：第一，對象必須在幾代之間復(fù)制，這會導(dǎo)致延遲抖動；第二，這些對象必須從老年代收集，這通常是一個更昂貴的操作，并且增加了“STW”暫停的可能性，當(dāng)碎片化的內(nèi)存空間需要壓縮時，就會出現(xiàn)這種暫停。在大內(nèi)存堆中，這可能會導(dǎo)致每GB的暫停時間長達(dá)數(shù)秒。

3.2 Teasing Apart the Concerns

我們看到，在所有隊(duì)列實(shí)現(xiàn)中，以下問題被合并在一起，以至于這些不同行為的集合傾向于定義隊(duì)列實(shí)現(xiàn)的接口：

1. 隊(duì)列中用于交換的元素的存儲

2. 協(xié)調(diào)生產(chǎn)者獲得下一個序列號用于入隊(duì)

3. 協(xié)調(diào)通知消費(fèi)者有新元素可用

當(dāng)用使用Java這種帶垃圾收集機(jī)制的語言開發(fā)在線金融交易所系統(tǒng)時，過多的內(nèi)存分配可能是有問題的。因此，正如我們所描述的，用基于鏈表的隊(duì)列做數(shù)據(jù)結(jié)構(gòu)不是一個好方法。如果可以預(yù)先分配用于各個處理階段stage之間做數(shù)據(jù)交換的整個存儲，則可以最小化垃圾收集的開銷。此外，如果這個分配可以在一個統(tǒng)一的內(nèi)存塊中執(zhí)行，那么數(shù)據(jù)的遍歷將以一種對現(xiàn)代處理器所采用的高速緩存策略非常友好的方式來完成。滿足此要求的數(shù)據(jù)結(jié)構(gòu)是一個預(yù)先填充了所有slot的數(shù)組。在創(chuàng)建RingBuffer時，Disruptor使用抽象工廠模式來預(yù)分配entry。這樣生產(chǎn)者在數(shù)據(jù)入隊(duì)而索要entry時，可以將其數(shù)據(jù)復(fù)制到預(yù)先分配的結(jié)構(gòu)中。

在大多數(shù)處理器上，序列號的余數(shù)計(jì)算成本非常高，而序列號%ringBufferSize得到的余數(shù)=元素在環(huán)中的插槽的下標(biāo)。通過使環(huán)的大小為2的冪，可以大大降低成本?？梢允褂么笮樨?fù)1的位掩碼來有效地執(zhí)行余數(shù)運(yùn)算。

正如我們前面所描述的，有界隊(duì)列在隊(duì)列的head和tail都會發(fā)生爭用。而環(huán)形緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)不受這種爭用和并發(fā)原語的影響，因?yàn)檫@些問題已經(jīng)被梳理成生產(chǎn)者和消費(fèi)者的屏障barrier，必須通過這些barrier來訪問環(huán)形緩沖區(qū)。這些barrier的邏輯如下所述。

在Disruptor最常見的用法中，通常只有一個生產(chǎn)者。典型的生產(chǎn)者是file reader或網(wǎng)絡(luò)listener。在只有一個生產(chǎn)者的情況下，equence/entry的分配沒有爭用。在有多個生產(chǎn)者的更不尋常的用法中，生產(chǎn)者將互相競爭以獲得環(huán)形緩沖區(qū)中的下一個entry。索要下一個可用entry的爭用可以通過對該slot的sequence number執(zhí)行簡單的CAS操作來管理。

一旦生產(chǎn)者將相關(guān)數(shù)據(jù)復(fù)制到申請到的entry中，它就可以通過提交序列將其公開給消費(fèi)者。這可以在沒有CAS的情況下通過一個簡單的忙旋轉(zhuǎn)來完成，直到其他生產(chǎn)者在他們自己的提交中達(dá)到這個序列。然后，該生產(chǎn)者可以前進(jìn)光標(biāo)，指示下一個可用的消費(fèi)條目。生產(chǎn)者可以通過跟蹤消費(fèi)者序列來避免覆蓋環(huán)(避免覆蓋了還未讀取的slot)，這是在其寫入環(huán)緩沖區(qū)之前的要做的一個簡單的讀取操作。

消費(fèi)者在讀取entry之前，等待entry的序列在環(huán)形緩沖區(qū)中變?yōu)榭捎?。等待時可以采用各種策略。如果CPU資源非常寶貴，那么它們可以在等待一個鎖中的Condition.awaite()，等待由生產(chǎn)者對Condition.signal()。這顯然是一個爭用點(diǎn)，僅在CPU資源比延遲或吞吐量更重要時使用。消費(fèi)者還可以循環(huán)的檢查環(huán)形緩沖區(qū)中代表當(dāng)前可用序列號的游標(biāo)。這可以在有或沒有線程yield的情況下完成，以CPU資源換取低延遲。如果不使用lock和condition變量，這將有很好的伸縮性，因?yàn)槲覀円呀?jīng)打破了生產(chǎn)者和消費(fèi)者之間的競爭依賴關(guān)系。無鎖多生產(chǎn)者-多消費(fèi)者隊(duì)列確實(shí)存在，但它們需要在head、tail、size等計(jì)數(shù)器上執(zhí)行多個CAS操作。Disruptor避免了這種CAS爭用。

這節(jié)介紹了大量的使用RingBuffer這個環(huán)形數(shù)組實(shí)現(xiàn)無鎖隊(duì)列的精巧算法和設(shè)計(jì)，由于翻譯過程中的信息不對稱和表達(dá)不到位，還是要配合源碼才能理解很多細(xì)節(jié)。此外，這篇論文是按照當(dāng)時早期的Disruptor版本寫的，跟最新的Disruptor會有一些不同，比如RingBuffer的ReadBarrier和WriteBarrier我記得后來的版本中好像就去掉了，我們注意理解論文中的思想就好。 可以參考美團(tuán)技術(shù)團(tuán)隊(duì)的blog，https://tech.meituan.com/2016/11/18/disruptor.html

3.3 Sequencing

順序序列是Disruptor中如何管理并發(fā)的核心概念。每個生產(chǎn)者和消費(fèi)者都有一個嚴(yán)格的序列概念，用于如何與RingBuffer交互。生產(chǎn)者在環(huán)中申請entry時，按順序申請下一個slot。在只有一個生產(chǎn)者的情況下、下一個可用slot的序列下標(biāo)可以是一個簡單計(jì)數(shù)器，或者在多個生產(chǎn)者的情況下，可以是使用CAS操作更新的原子計(jì)數(shù)器。一旦序列值被申請了，環(huán)形緩沖區(qū)中的這個entry現(xiàn)在就可以被申請它的生產(chǎn)者寫入。當(dāng)生產(chǎn)者完成更新entry時，它可以通過更新一個單獨(dú)的計(jì)數(shù)器來提交更改，該計(jì)數(shù)器表示環(huán)形緩沖區(qū)上的游標(biāo)，以獲取消費(fèi)者可用的最新entry。環(huán)形緩沖區(qū)游標(biāo)可以由生產(chǎn)者使用內(nèi)存屏障在繁忙的旋轉(zhuǎn)中讀寫，而不需要CAS操作。

long expectedSequence = claimedSequence – 1;
while (cursor != expectedSequence)
{
  // busy spin
}

cursor = claimedSequence;

消費(fèi)者通過使用內(nèi)存屏障來讀取游標(biāo)，等待給定的序列下標(biāo)對應(yīng)的entry變?yōu)榭捎?。一旦游?biāo)被更新，內(nèi)存屏障確保等待游標(biāo)前進(jìn)的消費(fèi)者可以立刻看到環(huán)形緩沖區(qū)中entry的變化。

每個消費(fèi)者都包含自己的序列sequence，在處理來自環(huán)形緩沖區(qū)的entry時更新這些序列。這些消費(fèi)者序列允許生產(chǎn)者跟蹤消費(fèi)者，以防止消費(fèi)者在環(huán)形緩沖上被生產(chǎn)者套圈、這樣生產(chǎn)者寫入就覆蓋了還未被消費(fèi)者讀取的數(shù)據(jù)了。消費(fèi)者序列還允許消費(fèi)者以有序的方式協(xié)調(diào)同一entry上的工作

在只有一個生產(chǎn)者的情況下，不管消費(fèi)者的復(fù)雜性如何，都不需要鎖或CAS操作。在所討論的序列上，只需設(shè)置內(nèi)存障礙，就可以實(shí)現(xiàn)整個并發(fā)協(xié)調(diào)。

3.4 Batching Effect

當(dāng)消費(fèi)者在環(huán)形緩沖區(qū)中等待前進(jìn)的游標(biāo)序列時，一個在隊(duì)列中不可能出現(xiàn)有趣的現(xiàn)象出現(xiàn)了。如果消費(fèi)者發(fā)現(xiàn)環(huán)形緩沖區(qū)游標(biāo)自上次檢查以來已前進(jìn)了許多步，則它可以處理該序列，而無需涉及并發(fā)機(jī)制。這導(dǎo)致落后的消費(fèi)者很快就追趕上了生產(chǎn)者的步伐，從而平衡系統(tǒng)。這種類型的批處理可以提高吞吐量，同時減少和平滑延遲。根據(jù)我們的觀察，這種效應(yīng)可使得延遲時間在任何負(fù)載下接近恒定，直到內(nèi)存子系統(tǒng)飽和，延遲曲線是線性的，遵循利特爾定律[6]。這與我們以往觀察到的隊(duì)列在負(fù)載增加時的延遲的“J”形曲線效果非常不同。

環(huán)形數(shù)組中生產(chǎn)者指針如果已經(jīng)領(lǐng)先很多，消費(fèi)者是可以不用任何鎖等并發(fā)機(jī)制直接把自己指針與生產(chǎn)者指針之間的數(shù)據(jù)都拿出來的，與之相對的是隊(duì)列則是要一個一個的從head里取出數(shù)據(jù)、且這中間還要用到鎖、產(chǎn)生了延遲，很容易想到當(dāng)負(fù)載增加、隊(duì)列中出現(xiàn)了堆積，這種延遲會成倍的增加。從由數(shù)據(jù)結(jié)構(gòu)本身產(chǎn)生的延遲的角度來看，無疑是RingBuffer要比一般的隊(duì)列要少的多。

3.5. Dependency Graphs

隊(duì)列表示生產(chǎn)者和消費(fèi)者之間簡單的一步管道依賴關(guān)系。如果消費(fèi)者形成了一個鏈?zhǔn)交蝾愃朴趫D的依賴結(jié)構(gòu)，那么在圖的每個階段之間都需要隊(duì)列。在相依階段圖中，這會導(dǎo)致多次隊(duì)列的固定成本。在設(shè)計(jì)lmax在線金融交易所系統(tǒng)時，我們的觀測與分析表明，如采用基于隊(duì)列的方案，在最終總的整體的事務(wù)處理執(zhí)行的成本中，隊(duì)列成本占比最高。

因?yàn)樯a(chǎn)者和消費(fèi)者的關(guān)注點(diǎn)（concerns）是用Disruptor模型分開的，所以可以表示消費(fèi)者之間的復(fù)雜依賴關(guān)系圖，而只需在核心部分使用一個環(huán)形緩沖區(qū)。這將大大降低執(zhí)行的固定成本，從而在減少延遲的同時提高吞吐量。

可以使用單個環(huán)形緩沖區(qū)來存儲具有復(fù)雜結(jié)構(gòu)的entry，在一個內(nèi)聚的地方的表示整個工作流。在設(shè)計(jì)這種結(jié)構(gòu)時必須小心，要確保彼此獨(dú)立的幾個消費(fèi)者寫狀態(tài)不會導(dǎo)致cacheline的偽共享。

3.6. Disruptor的類結(jié)構(gòu)圖

classdiagram.png

Disruptor框架中的核心類如圖。此圖省略了可用于簡化編程模型的工具類。在建立了依賴圖之后，編程模型變得簡單。生產(chǎn)者通過ProducerBarrier按順序申請entry，將其更改寫入申請到的entry，然后通過ProducerBarrier提交該entry，使其可供消費(fèi)。作為消費(fèi)者，我們所需要做的就是提供一個BatchHandler實(shí)現(xiàn)，當(dāng)一個新entry可用時接收回調(diào)。整個編程模型是基于事件驅(qū)動的，與Actor模型有很多相似之處。

分離通常在隊(duì)列實(shí)現(xiàn)中合并的關(guān)注點(diǎn)可以實(shí)現(xiàn)更靈活的設(shè)計(jì)。Disruptor框架的核心是一個RingBuffer，它為數(shù)據(jù)交換提供存儲，而不存在爭用。對于與RingBuffer交互的生產(chǎn)者和消費(fèi)者，并發(fā)關(guān)注點(diǎn)被分離出來。ProducerBarrier管理與在環(huán)緩沖區(qū)中索要slot相關(guān)的任何并發(fā)問題，同時跟蹤相關(guān)的消費(fèi)者以防止覆蓋未讀的slot。當(dāng)新entry可用時，ConsumerBarrier通知消費(fèi)者，消費(fèi)者可以被構(gòu)造成表示處理管道中多個階段的依賴關(guān)系圖狀流程。

3.7. 代碼例子

下面的代碼是單個生產(chǎn)者、以及單個的使用convenience接口BatchHandler實(shí)現(xiàn)的消費(fèi)者的示例。消費(fèi)者在一個單獨(dú)的線程上運(yùn)行，接收可用的entry。

// Callback handler which can be implemented by consumers
final BatchHandler<ValueEntry> batchHandler = new BatchHandler<ValueEntry>()
{
public void onAvailable(final ValueEntry entry) throws Exception
{
// process a new entry as it becomes available.
}

    public void onEndOfBatch() throws Exception
    {
        // useful for flushing results to an IO device if necessary.
    }

    public void onCompletion()
    {
        // do any necessary clean up before shutdown
    }
};

RingBuffer<ValueEntry> ringBuffer =
    new RingBuffer<ValueEntry>(ValueEntry.ENTRY_FACTORY, SIZE,
                               ClaimStrategy.Option.SINGLE_THREADED,
                               WaitStrategy.Option.YIELDING);
ConsumerBarrier<ValueEntry> consumerBarrier = ringBuffer.createConsumerBarrier();
BatchConsumer<ValueEntry> batchConsumer =
    new BatchConsumer<ValueEntry>(consumerBarrier, batchHandler);
ProducerBarrier<ValueEntry> producerBarrier = ringBuffer.createProducerBarrier(batchConsumer);

// Each consumer can run on a separate thread
EXECUTOR.submit(batchConsumer);

// Producers claim entries in sequence
ValueEntry entry = producerBarrier.nextEntry();

// copy data into the entry container

// make the entry available to consumers
producerBarrier.commit(entry);

4. Throughput Performance Testing

5. Latency Performance Testing

6. 總結(jié)

在提高吞吐量、減少并發(fā)執(zhí)行上下文之間的延遲和確?？深A(yù)測的延遲方面，Disruptor是向前邁出的重要一步，這在許多應(yīng)用程序中是一個重要的考慮因素。我們的測試表明，它在線程間交換數(shù)據(jù)方面的性能超過了類似的方案。我們相信這是這種數(shù)據(jù)交換的最高性能機(jī)制。通過將跨線程數(shù)據(jù)交換中涉及的關(guān)注點(diǎn)完全分離，消除寫爭用，最小化讀爭用，并確保代碼與現(xiàn)代處理器使用的Cache特性良好配合，我們創(chuàng)建了一種高效的機(jī)制，可用于在任何應(yīng)用中的線程之間交換數(shù)據(jù)。

批處理效應(yīng)允許消費(fèi)者在沒有任何爭用的情況下處理高達(dá)給定閾值的entry，這在高性能系統(tǒng)中引入了一個新特性。對于大多數(shù)系統(tǒng)，隨著負(fù)載和爭用的增加，延遲呈指數(shù)增長，即特征“J”曲線。而當(dāng)Disruptor上的負(fù)載增加時，在內(nèi)存子系統(tǒng)達(dá)到飽和之前，延遲幾乎保持不變。

我們相信Disruptor為高性能計(jì)算建立了一個新的基準(zhǔn)，并且它的設(shè)計(jì)非常能夠繼續(xù)利用當(dāng)前趨勢下處理器和計(jì)算機(jī)設(shè)計(jì)的優(yōu)勢。

后記

查看百度空間殘留的個人日記得知，筆者早在2012年2月1日就動了研究Disruptor原理的念頭，并打算在后端開發(fā)中使用它，前后花了1個月左右時間嘗試翻譯和理解它的官方論文和指南、以及開發(fā)者的各篇blog，到當(dāng)年3月20日認(rèn)識到自己知識儲備不足功力不夠，遂暫時放棄。2016年差不多到了能夠基本的簡單進(jìn)行使用的程度。2020年疫情期間，著手把Disruptor應(yīng)用在了筆者負(fù)責(zé)的一個實(shí)時競價系統(tǒng)上去，用來取代隊(duì)列。只可惜公司拉跨，沒有機(jī)會把這個成果推到線上并在高負(fù)載場景下進(jìn)行驗(yàn)證。2021年的今天，念念不忘，再次翻譯理解Disruptor的官方論文，經(jīng)過了將近十年的理論認(rèn)知與實(shí)踐經(jīng)驗(yàn)的逐漸提高，理解起來變得容易了許多。筆者愚鈍，且又經(jīng)歷種種生活不易，光陰十載、仍未成神。但古人云，朝聞道、夕死可矣。每個人都有著他自己的朝圣路，不是么。