無鎖隊列 Disruptor 原理解析

隊列比較

=======

隊列

隊列比較

總結：

就性能而言，無鎖 (什麼也不加) > CAS > LOCK;

從現實使用中考慮，我們一般選擇有界隊列（避免生產者速度過快，導致內存溢出）；同時，爲了減少 Java 的垃圾回收對系統性能的影響，會盡量選擇 array/heap 格式的數據結構。所以我們實際使用中用 ArrayBlockingQueue 多一些；

注：之後會將 ArrayBlockingQueue 和 Disruptor 做一些對比。

Disruptor 是什麼

Disruptor 是英國外匯交易公司 LMAX 開發的一個高性能隊列，研發的初衷是解決內存隊列的延遲問題（在性能測試中發現竟然與 I/O 操作處於同樣的數量級）。基於 Disruptor 開發的系統單線程能支撐每秒 600 萬訂單，2010 年在 QCon 演講後，獲得了業界關注。2011 年，企業應用軟件專家 Martin Fowler 專門撰寫長文介紹。同年它還獲得了 Oracle 官方的 Duke 大獎。

目前，包括 Apache Storm、Camel、Log4j 2 等在內的很多知名項目都應用了 Disruptor 以獲取高性能。

數據來自：

https://github.com/LMAX-Exchange/disruptor/wiki/Performance-Results

Disruptor 原理解析

CPU 緩存

緩存層級越接近於 CPU core，容量越小，速度越快，當 CPU 執行運算的時候，它先去 L1 查找所需的數據，再去 L2，然後是 L3，最後如果這些緩存中都沒有，所需的數據就要去主內存拿。走得越遠，運算耗費的時間就越長。

緩存行

緩存行 (Cache Line) 是 CPU Cache 中的最小單位，CPU Cache 由若干緩存行組成，一個緩存行的大小通常是 64 字節（這取決於 CPU），並且它有效地引用主內存中的一塊地址。一個 Java 的 long 類型是 8 字節，因此在一個緩存行中可以存 8 個 long 類型的變量。

CPU 每次從主存中拉取數據時，會把相鄰的數據也存入同一個 cache line。

在訪問一個 long 數組的時候，如果數組中的一個值被加載到緩存中，它會自動加載另外 7 個。因此你能非常快的遍歷這個數組。事實上，你可以非常快速的遍歷在連續內存塊中分配的任意數據結構。

利用 CPU 緩存 - 示例

◆ 僞共享

如果多個線程的變量共享了同一個 CacheLine，任意一方的修改操作都會使得整個 CacheLine 失效（因爲 CacheLine 是 CPU 緩存的最小單位），也就意味着，頻繁的多線程操作，CPU 緩存將會徹底失效，降級爲 CPU core 和主內存的直接交互。

如何解決僞共享（字節填充）

◆ RingBuffer

在 Disruptor 中採用了數組的方式保存了我們的數據，上面我們也介紹了採用數組保存我們訪問時很好的利用緩存，但是在 Disruptor 中進一步選擇採用了環形數組進行保存數據，也就是 RingBuffer。在這裏先說明一下環形數組並不是真正的環形數組，在 RingBuffer 中是採用取餘的方式進行訪問的，比如數組大小爲 10，0 訪問的是數組下標爲 0 這個位置，其實 10，20 等訪問的也是數組的下標爲 0 的這個位置。

當然其不僅解決了數組快速訪問的問題，也解決了不需要再次分配內存的問題，減少了垃圾回收，因爲我們 0，10，20 等都是執行的同一片內存區域，這樣就不需要再次分配內存，頻繁的被 JVM 垃圾回收器回收。

實際上，在這些框架中取餘並不是使用 % 運算，都是使用的 & 與運算，這就要求你設置的大小一般是 2 的 N 次方也就是，10,100,1000 等等，這樣減去 1 的話就是，1，11，111，就能很好的使用 index & (size -1), 這樣利用位運算就增加了訪問速度。如果在 Disruptor 中你不用 2 的 N 次方進行大小設置，他會拋出 buffersize 必須爲 2 的 N 次方異常。

Disruptor 生產者和消費者

生產者寫入數據

寫入數據的步驟包括：

  1. 佔位；

  2. 移動遊標並填充數據；

需要考慮的問題：

  1. 如何避免生產者的生產速度過快而造成的新消息覆蓋了未被消費的舊消息的問題；

  2. 如何解決多個生產者搶佔生產位的問題;

  1. 如何避免生產者的生產速度過快而造成的新消息覆蓋了未被消費的舊消息的問題；

答：生產者再獲取佔位之前需要查看當前最慢的消費者位置，如果當前要發佈的位置比消費者大，就等待;

  1. 如何解決多個生產者搶佔生產位的問題;

答：多個生產者通過 CAS 獲取生產位；

消費者讀取數據

說明：

  1. 一個消費者一個線程；

  2. 每個消費者都有一個遊標表示已經消費到哪了（Sequence）；

  3. 消息者會等待 (waitFor) 新數據，直到生產者通知(signal)；

需要考慮的問題：

如何防止讀取的時候，讀到還未寫的元素？

WaitStrategy（等待策略）：

BlockingWaitStrategy：默認策略，沒有獲取到任務的情況下線程會進入等待狀態。cpu 消耗少，但是延遲高。

TimeoutBlockingWaitStrategy：相對於 BlockingWaitStrategy 來說，設置了等待時間，超過後拋異常。

BusySpinWaitStrategy：線程一直自旋等待。cpu 佔用高，延遲低.

YieldingWaitStrategy：嘗試自旋 100 次，然後調用 Thread.yield() 讓出 cpu。cpu 佔用高，延遲低。

SleepingWaitStrategy：嘗試自旋 100 此，然後調用 Thread.yield() 100 次，如果經過這兩百次的操作還未獲取到任務，就會嘗試階段性掛起自身線程。此種方式是對 cpu 佔用和延遲的一種平衡，性能不太穩定。

生產者寫入數據示例 1

◆ 生產者寫入數據示例 2

總結

Disruptor 與 ArrayBlockingQueue 不同的地方：

  1. 增加緩存行補齊， 提升 cache 緩存命中率， 沒有爲僞共享和非預期的競爭；

  2. 可選鎖無關 lock-free, 沒有競爭所以非常快；

  3. 環形數組中的元素不會被刪除；

  4. 支持多個消費者，每個消費者都可以獲得相同的消息（廣播）。而 ArrayBlockingQueue 元素被一個消費者取走後，其它消費者就無法從 Queue 中取到；

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/fJdaMhot0fV7IWJaEr-f4g

猜你喜歡