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