Disruptor 高性能隊列原理淺析
你知道的越多，不知道的就越多，業(yè)余的像一棵小草！
你來，我們一起精進！你不來，我和你的競爭對手一起精進！
編輯：業(yè)余草
來源：https://qin.news/
推薦：https://www.xttblog.com/?p=5367
自律才 能自由
介紹
Disruptor 是英國外匯交易公司 LMAX 開發(fā)的一個高性能隊列，研發(fā)的初衷是解決內(nèi)存隊列的延遲問題（在性能測試中發(fā)現(xiàn)竟然與 I/O 操作處于同樣的數(shù)量級）?；贒isruptor 開發(fā)的系統(tǒng)單線程能支撐每秒 600 萬訂單，2010 年在 QCon 演講后，獲得了業(yè)界關(guān)注。2011 年，企業(yè)應(yīng)用軟件專家 Martin Fowler 專門撰寫長文介紹。同年它還獲得了 Oracle 官方的 Duke 大獎。
本文主要參考它 2011 年的論文 《LMAX Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads》https://t.zsxq.com/108BSDZ4D 還結(jié)合了美團技術(shù)團隊對它分析的文章。論文中文翻譯參考了肥兔子愛豆畜子翻譯的中文版。
這里所說的隊列是系統(tǒng)內(nèi)部的內(nèi)存隊列，而不是Kafka這樣的分布式隊列。
許多應(yīng)用程序依靠隊列在處理階段之間交換數(shù)據(jù)。我們的性能測試表明，當以這種方式使用隊列時，其延遲成本與磁盤（基于RAID或SSD的磁盤系統(tǒng)）的IO操作成本處于同一數(shù)量級都很慢。如果在一個端到端的操作中有多個隊列，這將使整個延遲增加數(shù)百微秒。
測試表明，使用 Disruptor 的三階段流水線的平均延遲比基于隊列的同等方法低 3 個數(shù)量級。此外，在相同的配置下，Disruptor 處理的吞吐量約為 8 倍。
并發(fā)問題
在本文以及在一般的計算機科學理論中，并發(fā)不僅意味著兩個以上任務(wù)同時并行發(fā)生，而且意味著它們在訪問資源時相互競爭。爭用的資源可以是數(shù)據(jù)庫、文件、socket，甚至是內(nèi)存中的一個位置。
代碼的并發(fā)執(zhí)行涉及兩件事：互斥和內(nèi)存可見性?；コ馐顷P(guān)于如何管理保證某些資源的獨占式使用。內(nèi)存可見性是關(guān)于控制內(nèi)存更改何時對其他線程可見。如果你可以避免多線程競爭的去更新共享資源，那么就可以避免互斥。如果您的算法可以保證任何給定的資源只被一個線程修改，那么互斥是不必要的。讀寫操作要求所有更改對其他線程可見。但是，只有爭用的寫操作需要對更改進行互斥。
在任何并發(fā)環(huán)境中，最昂貴的操作是爭用寫訪問。要讓多個線程寫入同一資源，需要復雜而昂貴的協(xié)調(diào)。通常，這是通過采用某種鎖策略來實現(xiàn)的。
但是鎖的開銷是非常大的，在論文中設(shè)計了一個實驗：
- 這個測試程序調(diào)用了一個函數(shù)，該函數(shù)會對一個 64 位的計數(shù)器循環(huán)自增 5 億次。
- 機器環(huán)境：2.4G 6 核
- 運算：64 位的計數(shù)器累加 5 億次
單線程情況下，不加鎖的性能 > CAS 操作的性能 > 加鎖的性能。
在多線程情況下，為了保證線程安全，必須使用 CAS 或鎖，這種情況下，CAS 的性能超過鎖的性能，前者大約是后者的 8 倍。
保證線程安全一般使用鎖或者原子變量。
采取加鎖的方式，默認線程會沖突，訪問數(shù)據(jù)時，先加上鎖再訪問，訪問之后再解鎖。通過鎖界定一個臨界區(qū)，同時只有一個線程進入。
原子變量能夠保證原子性的操作，意思是某個任務(wù)在執(zhí)行過程中，要么全部成功，要么全部失敗回滾，恢復到執(zhí)行之前的初態(tài)，不存在初態(tài)和成功之間的中間狀態(tài)。例如 CAS 操作，要么比較并交換成功，要么比較并交換失敗。由 CPU 保證原子性。
通過原子變量可以實現(xiàn)線程安全。執(zhí)行某個任務(wù)的時候，先假定不會有沖突，若不發(fā)生沖突，則直接執(zhí)行成功；當發(fā)生沖突的時候，則執(zhí)行失敗，回滾再重新操作，直到不發(fā)生沖突。
CAS 操作是一種特殊的機器代碼指令，它允許將內(nèi)存中的字有條件地設(shè)置為原子操作。比如對于前面的“遞增計數(shù)器實驗”例子，每個線程都可以在一個循環(huán)中自旋，讀取計數(shù)器，然后嘗試以原子方式將其設(shè)置為新的遞增值。
如圖所示，Thread1 和 Thread2 都要把 Entry 加 1。若不加鎖，也不使用 CAS，有可能 Thread1 取到了myValue=1，Thread2 也取到了 myValue=1，然后相加，Entry 中的 value 值為 2。這與預(yù)期不相符，我們預(yù)期的是 Entry 的值經(jīng)過兩次相加后等于3。
CAS 會先把 Entry 現(xiàn)在的 value 跟線程當初讀出的值相比較，若相同，則賦值；若不相同，則賦值執(zhí)行失敗。一般會通過 while/for 循環(huán)來重新執(zhí)行，直到賦值成功。CAS無需線程進行上下文切換到內(nèi)核態(tài)去執(zhí)行，在用戶態(tài)執(zhí)行了 CPU 的原語指令 cmpxchg，CAS 相當于在用戶態(tài)代碼里邊插入了一個 cmpxchg 指令，這樣 CPU 一直在用戶態(tài)執(zhí)行，執(zhí)行到 cmpxchg 指令就開始執(zhí)行內(nèi)核態(tài)內(nèi)存空間的操作系統(tǒng)的代碼。執(zhí)行指令要比上下文切換的開銷要小，所以 CAS 要比重量級互斥鎖性能要高。（用戶態(tài)和內(nèi)核態(tài)沒有切換）
如果程序的關(guān)鍵部分比計數(shù)器的簡單增量更復雜，則可能需要使用多個CAS操作的復雜狀態(tài)機來編排爭用。使用鎖開發(fā)并發(fā)程序是困難的；而使用 CAS 操作和內(nèi)存屏障開發(fā)無鎖算法要更加復雜多倍，而且難于測試和證明正確性。
內(nèi)存屏障和緩存問題
出于提升性能的原因，現(xiàn)代處理器執(zhí)行指令、以及內(nèi)存和執(zhí)行單元之間數(shù)據(jù)的加載和存儲都是不保證順序的。不管實際的執(zhí)行順序如何，處理器只需保證與程序邏輯的順序產(chǎn)生相同的結(jié)果即可。這在單線程的程序中不是一個問題。但是，當線程共享狀態(tài)時，為了確保數(shù)據(jù)交換的成功與正確，在需要的時候、內(nèi)存的改變能夠以正確的順序顯式是非常重要的。處理器使用內(nèi)存屏障來指示內(nèi)存更新順序很重要的代碼部分。它們是在線程之間實現(xiàn)硬件排序和更改可見性的方法。
內(nèi)存屏障（英語：Memory barrier），也稱內(nèi)存柵欄，內(nèi)存柵障，屏障指令等，是一類同步屏障指令，它使得 CPU 或編譯器在對內(nèi)存進行操作的時候, 嚴格按照一定的順序來執(zhí)行, 也就是說在內(nèi)存屏障之前的指令和之后的指令不會由于系統(tǒng)優(yōu)化等原因而導致亂序。
大多數(shù)處理器提供了內(nèi)存屏障指令:
- 完全內(nèi)存屏障(full memory barrier)保障了早于屏障的內(nèi)存讀寫操作的結(jié)果提交到內(nèi)存之后，再執(zhí)行晚于屏障的讀寫操作。
- 內(nèi)存讀屏障(read memory barrier)僅確保了內(nèi)存讀操作；
- 內(nèi)存寫屏障(write memory barrier)僅保證了內(nèi)存寫操作。
現(xiàn)代的 CPU 現(xiàn)在比當前一代的內(nèi)存系統(tǒng)快得多。為了彌合這一鴻溝，CPU 使用復雜的高速緩存系統(tǒng)，這些系統(tǒng)是有效的快速硬件哈希表，無需鏈接。這些緩存通過消息傳遞協(xié)議與其他處理器緩存系統(tǒng)保持一致。此外，處理器還具有“存儲緩沖區(qū)”（store buffer/load buffer，比 L1 緩存更靠近 CPU，跟寄存器同一個級別，用來當作 CPU 與高速緩存之間的緩沖。畢竟高速緩存由于一致性的問題也會阻塞）來緩沖對這些緩存的寫入，以及作為“失效隊列”，以便緩存一致性協(xié)議能夠在即將發(fā)生寫入時快速確認失效消息，以提高效率。
這對數(shù)據(jù)意味著，任何值的最新版本在被寫入后的任何階段都可以位于寄存器、存儲緩沖區(qū)、L1/L2/L3 緩存之一或主內(nèi)存中。如果線程要共享此值，則需要以有序的方式使其可見，這是通過協(xié)調(diào)緩存一致性消息的交換來實現(xiàn)的。這些信息的及時產(chǎn)生可以通過內(nèi)存屏障來控制。
L1、L2、L3 分別表示一級緩存、二級緩存、三級緩存，越靠近 CPU 的緩存，速度越快，容量也越小。所以 L1 緩存很小但很快，并且緊靠著在使用它的 CPU 內(nèi)核；L2 大一些，也慢一些，并且仍然只能被一個單獨的 CPU 核使用；L3 更大、更慢，并且被單個插槽上的所有 CPU 核共享；最后是主存，由全部插槽上的所有 CPU 核共享。
當 CPU 執(zhí)行運算的時候，它先去 L1 查找所需的數(shù)據(jù)、再去 L2、然后是 L3，如果最后這些緩存中都沒有，所需的數(shù)據(jù)就要去主內(nèi)存拿。走得越遠，運算耗費的時間就越長。所以如果你在做一些很頻繁的事，你要盡量確保數(shù)據(jù)在 L1 緩存中。
另外，線程之間共享一份數(shù)據(jù)的時候，需要一個線程把數(shù)據(jù)寫回內(nèi)存，而另一個線程訪問內(nèi)存中相應(yīng)的數(shù)據(jù)。
如果你用一種能被預(yù)測的方式訪問內(nèi)存的話，CPU 可以預(yù)測下個可能訪問的值從內(nèi)存先緩存到緩存中，來降低下次訪問的延遲。但是如果是一些非順序的、步長無法預(yù)測的結(jié)構(gòu)，讓 CPU 只能訪問內(nèi)存，性能上與訪問緩存差很多。所以為了有效利用 CPU 高速緩存的特性，我們應(yīng)當盡量使用順序存儲結(jié)構(gòu)。
隊列的問題
隊列通常使用鏈表或數(shù)組作為元素的底層存儲。如果允許內(nèi)存中的隊列是無界的，那么對于許多類的問題，它可以不受約束地增長，直到耗盡內(nèi)存而達到災(zāi)難性的后果，當生產(chǎn)者超過消費者時就會發(fā)生這種情況。無界隊列在可以在生產(chǎn)者可以保證不超過消費者的系統(tǒng)中使用，因為內(nèi)存是一種寶貴的資源，但是如果這種假設(shè)不成立，而隊列增長沒有限制，那么總是有風險的。為了避免這種災(zāi)難性的結(jié)果，隊列的大小通常要受到限制（有界）。要使隊列保持有界，就需要對其底層選擇數(shù)組結(jié)構(gòu)或主動跟蹤其大小。
隊列的實現(xiàn)往往要在 head、tail 和 size 變量上有寫爭用。在使用時，由于消費者和生產(chǎn)者之間的速度差異，隊列通?？偸墙咏跐M或接近于空。它們很少在生產(chǎn)和消費速率均衡的中間地帶運作。這種總是滿的或總是空的傾向會導致高級別的爭用、和/或昂貴的緩存一致性。問題在于，即使 head 和 tail 使用不同的并發(fā)對象（如鎖或CAS變量）來進行讀寫鎖分離，它們通常也占用相同的 cacheline。
管理生產(chǎn)者申請隊列的 head，消費者申請隊列的 tail，以及中間節(jié)點的存儲，這些問題使得并發(fā)實現(xiàn)的設(shè)計非常復雜，除了在隊列上使用一個粗粒度的鎖之外，還難以管理。對于 put 和 take 操作，使用整個隊列上的粗粒度鎖實現(xiàn)起來很簡單，但對吞吐量來說是一個很大的瓶頸。如果并發(fā)關(guān)注點在隊列的語義中被分離開來，那么對于除單個生產(chǎn)者-單個消費者之外的任何場景，實現(xiàn)都變得非常復雜。
而使用相同的 cacheline 會產(chǎn)生偽共享問題。比如 ArrayBlockingQueue 有三個成員變量：
- takeIndex：需要被取走的元素下標；
- putIndex：可被元素插入的位置的下標；
- count：隊列中元素的數(shù)量；
這三個變量很容易放到一個緩存行中，但是之間修改沒有太多的關(guān)聯(lián)。所以每次修改，都會使之前緩存的數(shù)據(jù)失效，從而不能完全達到共享的效果。
如上圖所示，當生產(chǎn)者線程 put 一個元素到 ArrayBlockingQueue 時，putIndex 會修改，從而導致消費者線程的緩存中的緩存行無效，需要從主存中重新讀取。一般的解決方案是，增大數(shù)組元素的間隔使得由不同線程存取的元素位于不同的緩存行上，以空間換時間。
Disruptor 解決思路
啟動時，將預(yù)先分配環(huán)形緩沖區(qū)的所有內(nèi)存。環(huán)形緩沖區(qū)可以存儲指向 entry 的指針數(shù)組，也可以存儲表示 entry 的結(jié)構(gòu)數(shù)組。這些 entry 中的每一個通常不是傳遞的數(shù)據(jù)本身，類似對象池機制，而是它的容器。這種 entry 的預(yù)分配消除了支持垃圾回收的語言中的問題，因為 entry 將被重用，并在整個 Disruptor 實例存活期間都有效。這些 entry 的內(nèi)存是同時分配的。
一般的數(shù)據(jù)結(jié)構(gòu)是像下面這樣的：
我們可以使用一個環(huán)狀的數(shù)組結(jié)構(gòu)改進成下面這樣：
數(shù)組的連續(xù)多個元素會一并加載到 CPU Cache 里面來，所以訪問遍歷的速度會更快。而鏈表里面各個節(jié)點的數(shù)據(jù)，多半不會出現(xiàn)在相鄰的內(nèi)存空間，自然也就享受不到整個 Cache Line 加載后數(shù)據(jù)連續(xù)從高速緩存里面被訪問到的優(yōu)勢。遍歷訪問時 CPU 層面的分支預(yù)測會很準確。這可以使得我們更有效地利用了 CPU 里面的多級流水線，我們的程序就會跑得更快。
在像 Java 這樣的托管運行時環(huán)境中開發(fā)低延遲系統(tǒng)時，垃圾收集機制可能會帶來問題。分配的內(nèi)存越多，給垃圾收集器帶來的負擔就越大。當對象的壽命很短或?qū)嶋H上是常駐的時候，垃圾收集器工作得最好。在環(huán)形緩沖區(qū)中預(yù)先分配 entry 意味著它對于垃圾收集器來說是常駐內(nèi)存的，垃圾回收的負擔就很輕。同時，數(shù)組結(jié)構(gòu)對處理器的緩存機制更加友好。數(shù)組長度 2^n，通過位運算，加快定位的速度。下標采取遞增的形式。不用擔心 index 溢出的問題。index 是 long 類型，即使 100 萬 QPS 的處理速度，也需要 30 萬年才能用完。
一般的 Cache Line 大小在 64 字節(jié)左右，然后 Disruptor 在非常重要的字段前后加了很多額外的無用字段。可以讓這一個字段占滿一整個緩存行，這樣就可以避免未共享導致的誤殺。
每個生產(chǎn)者或者消費者線程，會先申請可以操作的元素在數(shù)組中的位置，申請到之后，直接在該位置寫入或者讀取數(shù)據(jù)。
下面用非環(huán)形的結(jié)構(gòu)模擬無鎖讀寫。
一個生產(chǎn)者的流程
- 申請寫入m個元素；
- 若是有m個元素可以入，則返回最大的序列號。這兒主要判斷是否會覆蓋未讀的元素；
- 若是返回的正確，則生產(chǎn)者開始寫入元素。
多個生產(chǎn)者流程
多個生產(chǎn)者的情況下，會遇到“如何防止多個線程重復寫同一個元素”的問題。Disruptor 的解決方法是，每個線程獲取不同的一段數(shù)組空間進行操作。這個通過 CAS 很容易達到。只需要在分配元素的時候，通過 CAS 判斷一下這段空間是否已經(jīng)分配出去即可。
但如何防止讀取的時候，讀到還未寫的元素。Disruptor 在多個生產(chǎn)者的情況下，引入了一個與 Ring Buffer 大小相同的 buffer，Available Buffer。當某個位置寫入成功的時候，便把 Availble Buffer 相應(yīng)的位置置位，標記為寫入成功。讀取的時候，會遍歷 Available Buffer，來判斷元素是否已經(jīng)就緒。
讀數(shù)據(jù)流程
生產(chǎn)者多線程寫入的情況會復雜很多：
- 申請讀取到序號n；
- 若 writer cursor >= n，這時仍然無法確定連續(xù)可讀的最大下標。從 reader cursor 開始讀取 available Buffer，一直查到第一個不可用的元素，然后返回最大連續(xù)可讀元素的位置；
- 消費者讀取元素。
如下圖所示，讀線程讀到下標為 2 的元素，三個線程 Writer1/Writer2/Writer3 正在向 RingBuffer 相應(yīng)位置寫數(shù)據(jù)，寫線程被分配到的最大元素下標是 11。
讀線程申請讀取到下標從3到11的元素，判斷 writer cursor>=11。然后開始讀取 availableBuffer，從 3 開始，往后讀取，發(fā)現(xiàn)下標為7的元素沒有生產(chǎn)成功，于是WaitFor(11)返回6。
然后，消費者讀取下標從 3 到 6 共計 4 個元素（多個生產(chǎn)者情況下，消費者消費過程示意圖）。
寫數(shù)據(jù)流程
多個生產(chǎn)者寫入的時候：
- 申請寫入 m 個元素；
- 若是有 m 個元素可以寫入，則返回最大的序列號。每個生產(chǎn)者會被分配一段獨享的空間；
- 生產(chǎn)者寫入元素，寫入元素的同時設(shè)置 available Buffer 里面相應(yīng)的位置，以標記自己哪些位置是已經(jīng)寫入成功的。
如下圖所示，Writer1 和 Writer2 兩個線程寫入數(shù)組，都申請可寫的數(shù)組空間。Writer1 被分配了下標 3 到下表 5 的空間，Writer2 被分配了下標 6 到下標 9 的空間。
Writer1 寫入下標 3 位置的元素，同時把 available Buffer 相應(yīng)位置置位，標記已經(jīng)寫入成功，往后移一位，開始寫下標 4 位置的元素。Writer2 同樣的方式。最終都寫入完成。
總結(jié)
整體上來看 Disruptor 在提高吞吐量、減少并發(fā)執(zhí)行損耗上做出了很大貢獻，通過貼合硬件機制的方式進行設(shè)計，消除寫爭用，最小化讀爭用，并確保代碼與現(xiàn)代處理器使用的 Cache 特性良好配合。我們可以看下 Log4j 2 的性能數(shù)據(jù)，Log4j 2 的 Loggers all async 就是基于 Disruptor 的。
總結(jié)來說 Disruptor 是性能極高的無鎖隊列，提供了一種很好的利用硬件特性實現(xiàn)盡可能從緩存讀取來加速訪問的無鎖方案。