Disruptor測試結果運算1億次,耗時5503ms,吞吐量18171000/s,於是我扒開了Disruptor高效能的外衣

語言: CN / TW / HK

hello 小夥伴兒們,昨天搞了一篇Disruptor的入門文章,看大家反饋不錯,在大家一再催更下,昨天熬夜至下班,終於續寫了第二篇Disruptor的高效能原理剖析的文章,為大家揭開Disruptor高效能的神祕外衣。 如果小夥伴,錯過了入門Disruptor的入門篇的文章,在這裡自行檢視:

如此狂妄,自稱高效能佇列的 Disruptor 有啥來頭?

能對比測試

為了直觀地感受 Disruptor **有多快,設計了一個性能對比測試:Producer 釋出 1 億次事件,從釋出第一個事件開始計時,捕捉 Consumer 處理完所有事件的耗時。

測試用例在 Producer 如何將事件通知到 Consumer 的實現方式上,設計了兩種不同的實現:

  1. Producer 的事件釋出和 Consumer 的事件處理在不同的執行緒,通過 ArrayBlockingQueue 傳遞給 Consumer 進行處理;
  2. Producer 的事件釋出和 Consumer 的事件處理在不同的執行緒,通過 Disruptor 傳遞給 Consumer 進行處理;

3.1 程式碼實現

3.1.1 計算程式碼

進行CAS累加運算

public class CommonUtils {
    private static AtomicLong count = new AtomicLong(0);

    public static void calculation() {
        count.incrementAndGet();
    }

    public static long get() {
        return count.get();
    }
}
3.1.2 抽象類

進行一億次 CAS運算計算耗時

/**
 * 抽象類
 *
 * @param <T>
 */
public abstract class AbstractTask<T> {
    private static final Logger logger = LoggerFactory.getLogger(AbstractTask.class);
    //執行緒池
    private static final ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors() + 1);
    private static final CountDownLatch countDownLatch = new CountDownLatch(1);
    //一億次測試
    public static long tasksize = 100000000;


    /**
     * 開始呼叫測試
     */
    public void invok() {
        //計算當前事件
        long currentTime = System.currentTimeMillis();
        //獲取到監聽器
        Runnable monitor = monitor();
        if (null != monitor) {
            executor.execute(monitor);
        }
        //啟動
        start();

        //執行任務釋出
        Runnable runnable = getTask();
        for (long i = 0; i < tasksize; i++) {
            runnable.run();
        }

        //停止任務
        stop();
        //等待任務釋出完成
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        executor.shutdown();
        //獲取處理結果
        T result = getResult();
        //計算耗時
        long duration = System.currentTimeMillis() - currentTime;
        //計算吞吐量
        long throughput = (tasksize / duration) * 1000;
        logger.info("每秒吞吐量:[{}];({}/{})", throughput, result, duration);
    }


    /**
     * 獲取監聽器
     *
     * @return
     */
    public Runnable monitor() {
        return null;
    }

    /**
     * 啟動任務
     */
    public void start() {

    }

    /**
     * 完成任務
     */
    public void complete() {
        countDownLatch.countDown();
    }

    /**
     * 停止任務
     */
    public void stop() {

    }

    /**
     * 獲取需要執行的任務
     *
     * @return
     */
    public abstract Runnable getTask();

    /**
     * 獲取執行結果
     *
     * @return
     */
    public abstract T getResult();
}

3.1.3 Disruptor效能測試程式碼
public class DisruptorTest extends AbstractTask<Long> {
    //定義隨機數生成器
    private static final Random r = new Random();
    //定義Disruptor物件
    private Disruptor disruptor = null;
    //定義Disruptor事件釋出物件
    private LongEventProducerWithTranslator translator = null;

    /**
     * 啟動
     */
    @Override
    public void start() {
        //定義事件工廠
        EventFactory<LongEvent> eventFactory = new LongEventFactory();
        // RingBuffer 大小,必須是 2 的 N 次方;
        int ringBufferSize = 1024 * 1024;
        //構建disruptor物件
        disruptor = new Disruptor<LongEvent>(eventFactory,
                ringBufferSize, Executors.defaultThreadFactory(), ProducerType.SINGLE,
                new YieldingWaitStrategy());
        //定義事件處理類
        EventHandler<LongEvent> eventHandler = new LongEventHandler();
        //配置事件處理類
        disruptor.handleEventsWith(eventHandler);
        //啟動disruptor
        disruptor.start();
        //建立事件釋出物件
        translator = new LongEventProducerWithTranslator(disruptor.getRingBuffer());
    }

    /**
     * 停止任務
     */
    @Override
    public void stop() {
        disruptor.shutdown();
        System.out.println("運算結果:" + CommonUtils.get());
        //完成任務
        complete();
    }

    /**
     * 獲取需要執行的任務
     *
     * @return
     */
    @Override
    public Runnable getTask() {
        return () -> {
            publishEvent();
        };
    }

    /**
     * 獲取執行結果
     *
     * @return
     */
    @Override
    public Long getResult() {
        return CommonUtils.get();
    }


    /**
     * 釋出物件
     */
    private void publishEvent() {
        //獲取要通過事件傳遞的業務資料
        Long data = r.nextLong();
        // 釋出事件
        translator.onData(data);
    }


    public static void main(String[] args) {
        DisruptorTest disruptorTest = new DisruptorTest();
        disruptorTest.invok();
    }

}

輸出結果

10:45:22.941 [main] INFO com.heima.task.AbstractTask - 每秒吞吐量:[18171000];(100000000/5503)
ArrayBlockingQueue效能測試程式碼
public class ArrayBlockingQueueTest extends AbstractTask {
    private static final Random r = new Random();
    private static final ArrayBlockingQueue<Long> queue = new ArrayBlockingQueue(10000000);


    @Override
    public Runnable monitor() {
        return () -> {
            try {
                for (int i = 0; i < tasksize; i++) {
                    //獲取一個元素
                    queue.take();
                    //執行計算
                    CommonUtils.calculation();
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            complete();
        };
    }

    public static void main(String[] args) {
        ArrayBlockingQueueTest test = new ArrayBlockingQueueTest();
        test.invok();
    }

    @Override
    public Runnable getTask() {
        return () -> {
            publish();
        };
    }

    @Override
    public Object getResult() {
        return CommonUtils.get();
    }

    public void publish() {
        Long data = r.nextLong();
        try {
            queue.put(data);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

輸出結果

10:45:46.379 [main] INFO com.heima.task.AbstractTask - 每秒吞吐量:[6192000];(100000000/16148)

3.2 測試對比

測試類 運算次數 耗時(ms) 吞吐量/s
ArrayBlockingQueue 1億次 16148 6192000
Disruptor 1億次 5503 18171000

3.3 Disruptor官方效能測試

Disruptor論文中講述了一個實驗:

  • 這個測試程式呼叫了一個函式,該函式會對一個64位的計數器迴圈自增5億次。
  • 機器環境:2.4G 6核
  • 運算: 64位的計數器累加5億次
Method Time (ms)
單執行緒 300
單執行緒使用 CAS 5,700
單執行緒使用鎖 10,000
單執行緒使用volatile 4,700
多執行緒使用 CAS 30,000
多執行緒使用鎖 224,000

4. 高效能原理

  • 引入環形的陣列結構:陣列元素不會被回收,避免頻繁的GC,
  • 無鎖的設計:採用CAS無鎖方式,保證執行緒的安全性
  • 屬性填充:通過新增額外的無用資訊,避免偽共享問題
  • 元素位置的定位:採用跟一致性雜湊一樣的方式,一個索引,進行自增

4.1 偽共享概念

4.1.1 計算機快取構成

​ 下圖是計算的基本結構。L1、L2、L3分別表示一級快取、二級快取、三級快取,越靠近CPU的快取,速度越快,容量也越小,所以L1快取很小但很快,並且緊靠著在使用它的CPU核心;L2大一些,也慢一些,並且仍然只能被一個單獨的CPU核使用;L3更大、更慢,並且被單個插槽上的所有CPU核共享;最後是主存,由全部插槽上的所有CPU核共享。

file

​ 當CPU要讀取一個數據時,首先從一級快取中查詢,如果沒有找到再從二級快取中查詢,如果還是沒有就從三級快取或記憶體中查詢。一般來說,每級快取的命中率大概都在80%左右,也就是說全部資料量的80%都可以在一級快取中找到,只剩下20%的總資料量才需要從二級快取、三級快取或記憶體中讀取,由此可見一級快取是整個CPU快取架構中最為重要的部分。

file

下表是一些快取未命中的消耗資料:

從CPU到 大約需要的CPU週期 大約需要的時間
主存 約60-80ns
QPI匯流排 約20ns
L3 cache 約40-45cycles 約15ns
L2 cache 約10cycles 約3ns
L1 cache 約3-4cycles 約1ns
暫存器 1cycle

可見CPU讀取主存中的資料會比從L1中讀取慢了近2個數量級。

4.1.2 什麼是快取行

​ 為了解決計算機系統中主記憶體與 CPU 之間執行速度差問題,會在 CPU 與主記憶體之間 新增一級或者多級高速緩衝儲存器( Cache)。這個 Cache 一般是被整合到 CPU 內部的, 所以也叫 CPU Cache,如圖所示是兩級 Cache 結構。

file

​ Cache內部是按行儲存的,其中每一行稱為一個cache line,由很多個 Cache line 組成的,Cache line 是 cache 和 RAM 交換資料的最小單位,cache行的大小一般為2的冪次數字節,通常為 64 Byte。Cache line是Cache與主記憶體進行資料交換的單位。

file

​ 當 CPU 把記憶體的資料載入 cache 時,會把臨近的共 64 Byte 的資料一同放入同一個Cache line,因為空間區域性性:臨近的資料在將來被訪問的可能性大。

linux 檢視快取行大小

more /sys/devices/system/cpu/cpu1/cache/index0/coherency_line_size
64
4.1.3 什麼是共享

​ CPU快取是以快取行(cache line)為單位儲存的。快取行通常是 64 位元組,並且它有效地引用主記憶體中的一塊地址。一個 Java 的 long 型別是 8 位元組,因此在一個快取行中可以存 8 個 long 型別的變數。所以,如果你訪問一個 long 陣列,當陣列中的一個值被載入到快取中,它會額外載入另外 7 個,以致你能非常快地遍歷這個陣列。事實上,你可以非常快速的遍歷在連續的記憶體塊中分配的任意資料結構。而如果你在資料結構中的項在記憶體中不是彼此相鄰的(如連結串列),你將得不到免費快取載入所帶來的優勢,並且在這些資料結構中的每一個項都可能會出現快取未命中。下圖是一個CPU快取行的示意圖:

file

​ 表面上 X 和 Y 都是被獨立執行緒操作的,而且兩操作之間也沒有任何關係。只不過它們共享了一個快取行,但所有競爭衝突都是來源於共享。

4.1.4 什麼是偽共享

​ 當CPU訪問某一個變數時候,首先會去看CPU Cache內是否有該變數,如果有則直接從中獲取,否者就去主記憶體裡面獲取該變數,然後把該變數所在記憶體區域的一個Cache行大小的記憶體拷貝到Cache(cache行是Cache與主記憶體進行資料交換的單位)。

​ 由於存放到Cache行的的是記憶體塊而不是單個變數,所以可能會把多個變數存放到了一個cache行。當多個執行緒同時修改一個快取行裡面的多個變數時候,由於同時只能有一個執行緒操作快取行,所以相比每個變數放到一個快取行效能會有所下降,這就是偽共享。

file

​ 如上圖變數x,y同時被放到了CPU的一級和二級快取,當執行緒1使用CPU1對變數x進行更新時候,首先會修改cpu1的一級快取變數x所在快取行,這時候快取一致性協議會導致cpu2中變數x對應的快取行失效,那麼執行緒2寫入變數x的時候就只能去二級快取去查詢,這就破壞了一級快取,而一級快取比二級快取更快。更壞的情況下如果cpu只有一級快取,那麼會導致頻繁的直接訪問主記憶體。

​ 我們的快取都是以快取行作為一個單位來處理的,所以失效x的快取的同時,也會把y失效,反之亦然。

4.1.5 為何會出現偽共享

​ 偽共享的產生是因為多個變數被放入了一個快取行,並且多個執行緒同時去寫入快取行中不同變數。那麼為何多個變數會被放入一個快取行那。其實是因為Cache與記憶體交換資料的單位就是Cache line,當CPU要訪問的變數沒有在Cache命中時候,根據程式執行的區域性性原理會把該變數在記憶體中大小為Cache行的記憶體放如快取行。

long a;
long b;
long c;
long d;

​ 如上程式碼,聲明瞭四個long變數,假設cache line的大小為32個位元組,那麼當cpu訪問變數a時候發現該變數沒有在cache命中,那麼就會去主記憶體把變數a以及記憶體地址附近的b,c,d放入快取行。也就是地址連續的多個變數才有可能會被放到一個快取行中,當建立陣列時候,數組裡面的多個元素就會被放入到同一個快取行。那麼單執行緒下多個變數放入快取行對效能有影響?其實正常情況下單執行緒訪問時候由於陣列元素被放入到了一個或者多個cache行對程式碼執行是有利的,因為資料都在快取中,程式碼執行會更快。

4.1.6 如何解偽共享

​ 解決偽共享最直接的方法就是填充(padding),例如下面的VolatileLong,一個long佔8個位元組,Java的物件頭佔用8個位元組(32位系統)或者12位元組(64位系統,預設開啟物件頭壓縮,不開啟佔16位元組)。一個快取行64位元組,那麼我們可以填充6個long(6 * 8 = 48 個位元組)。

4.1.6.1 不使用欄位填充
public class VolatileData {
    // 佔用 8個位元組 +48 + 物件頭 = 64位元組

    //需要操作的資料
    volatile long value;

    public VolatileData() {
    }

    public VolatileData(long defValue) {
        value = defValue;
    }

    public long accumulationAdd() {
        //因為單執行緒操作不需要加鎖
        value++;
        return value;
    }

    public long getValue() {
        return value;
    }
}

記憶體佈局

file

4.6.1.2 填充欄位

因為JDK1.7以後就自動優化程式碼會刪除無用的程式碼,在JDK1.7以後的版本這些不生效了。

/**
 * 快取行填充父類
 */
public class DataPadding {
    //填充 5個long型別欄位 8*5 = 40 個位元組
    private long p1, p2, p3, p4, p5; //jvm 優化 刪除無用程式碼
    //需要操作的資料
    volatile long value;
}

記憶體佈局

file

4.1.6.3 繼承的方式
/**
 * 快取行填充父類
 */
public class DataPadding {
    //填充 5個long型別欄位 8*5 = 40 個位元組
    private long p1, p2, p3, p4, p5;
}

繼承快取填充類

/**
 * 繼承DataPadding
 */
public class VolatileData extends DataPadding {
    // 佔用 8個位元組 +48 + 物件頭 = 64位元組

    public VolatileData() {
    }

    public VolatileData(long defValue) {
        value = defValue;
    }

    public long accumulationAdd() {
        //因為單執行緒操作不需要加鎖
        value++;
        return value;
    }

    public long getValue() {
        return value;
    }
}

記憶體佈局

file

4.1.6.4 Disruptor填充方式
class LhsPadding {
    protected long p1, p2, p3, p4, p5, p6, p7;
}

class Value extends LhsPadding {
    protected volatile long value;
}

class RhsPadding extends Value {
    protected long p9, p10, p11, p12, p13, p14, p15;
}

繼承填充類

public class VolatileData extends RhsPadding {
    // 佔用 8個位元組 +48 + 物件頭 = 64位元組

    //需要操作的資料
    volatile long value;

    public VolatileData() {
    }

    public VolatileData(long defValue) {
        value = defValue;
    }

    public long accumulationAdd() {
        //因為單執行緒操作不需要加鎖
        value++;
        return value;
    }

    public long getValue() {
        return value;
    }
}

記憶體佈局

file

4.1.6.5 @Contended註解
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.FIELD, ElementType.TYPE})
public @interface Contended {
    String value() default "";
}

註解填充類

@Contended
public class VolatileData  {
    // 佔用 8個位元組 +48 + 物件頭 = 64位元組

    //需要操作的資料
    volatile long value;
    
    public VolatileData() {
    }

    public VolatileData(long defValue) {
        value = defValue;
    }

    public long accumulationAdd() {
        //因為單執行緒操作不需要加鎖
        value++;
        return value;
    }

    public long getValue() {
        return value;
    }
}

記憶體佈局

file

注意事項

在Java8中提供了**@sun.misc.Contended來避免偽共享時,在執行時需要設定JVM啟動引數-XX:-RestrictContended**否則可能不生效。

4.1.7 效能對比
4.1.7.1 測試程式碼

使用和不使用快取行填充的對比

/**
 * 快取行測試
 */
public class CacheLineTest {
    /**
     * 通過快取行填充的變數
     */
    private VolatileData volatileData1 = new VolatileData(0);
    private VolatileData volatileData2 = new VolatileData(0);
    private VolatileData volatileData3 = new VolatileData(0);
    private VolatileData volatileData4 = new VolatileData(0);
    private VolatileData volatileData5 = new VolatileData(0);
    private VolatileData volatileData6 = new VolatileData(0);
    private VolatileData volatileData7 = new VolatileData(0);

    /**
     * 迴圈次數
     */
    private final long size = 100000000;

    /**
     * 進行累加操作
     */
    public void accumulationX(VolatileData volatileData) {
        //計算耗時
        long currentTime = System.currentTimeMillis();
        long value = 0;
        //迴圈累加
        for (int i = 0; i < size; i++) {
            //使用快取行填充的方式
            value = volatileData.accumulationAdd();


        }
        //列印
        System.out.println(value);
        //列印耗時
        System.out.println("耗時:" + (System.currentTimeMillis() - currentTime));
    }


    public static void main(String[] args) {
        //建立物件
        CacheLineTest cacheRowTest = new CacheLineTest();
        //建立執行緒池
        ExecutorService executorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        //啟動三個執行緒個呼叫他們各自的方法
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData1));
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData2));
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData3));
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData4));
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData5));
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData6));
        executorService.execute(() -> cacheRowTest.accumulationX(cacheRowTest.volatileData7));
        executorService.shutdown();
    }
}
4.1.7.2 測試資料

同樣的結構他們之間差了 將近 50倍的速度差距

物件 NoPadding(MS) DataPadding(MS) RhsPadding(MS) Contended(MS)
volatileData1 3751 1323 1307 1291
volatileData2 3790 1383 1311 1314
volatileData3 7551 1400 1311 1333
volatileData4 7669 1407 1317 1356
volatileData5 8577 1447 1327 1361
volatileData6 8705 1479 1339 1375
volatileData6 8741 1512 1368 1389
4.1.8 Disruptor解決偽共享

​ 在Disruptor中有一個重要的類Sequence,該類包裝了一個volatile修飾的long型別資料value,無論是Disruptor中的基於陣列實現的緩衝區RingBuffer,還是生產者,消費者,都有各自獨立的Sequence,RingBuffer緩衝區中,Sequence標示著寫入進度,例如每次生產者要寫入資料進緩衝區時,都要呼叫RingBuffer.next()來獲得下一個可使用的相對位置。對於生產者和消費者來說,Sequence標示著它們的事件序號,來看看Sequence類的原始碼:

class LhsPadding {
	protected long p1, p2, p3, p4, p5, p6, p7;
}

class Value extends LhsPadding {
	protected volatile long value;
}

class RhsPadding extends Value {
	protected long p9, p10, p11, p12, p13, p14, p15;
}

public class Sequence extends RhsPadding {
	static final long INITIAL_VALUE = -1L;
	private static final Unsafe UNSAFE;
	private static final long VALUE_OFFSET;
	static {
		UNSAFE = Util.getUnsafe();
		try {
			VALUE_OFFSET = UNSAFE.objectFieldOffset(Value.class.getDeclaredField("value"));
		} catch(final Exception e) {
			 throw new RuntimeException(e);
		}
	}
	


    public Sequence() {
        this(INITIAL_VALUE);
    }

    public Sequence(final long initialValue) {
        UNSAFE.putOrderedLong(this, VALUE_OFFSET, initialValue);
    }

}

​ 從第1到11行可以看到,真正使用到的變數value,它的前後空間都由8個long型的變數填補了,對於一個大小為64位元組的快取行,它剛好被填補滿(一個long型變數value,8個位元組加上前/後個7long型變數填補,7*8=56,56+8=64位元組)。這樣做每次把變數value讀進快取記憶體中時,都能把快取行填充滿(對於大小為64個位元組的快取行來說,如果快取行大小大於64個位元組,那麼還是會出現偽共享問題),保證每次處理資料時都不會與其他變數發生衝突。

4.2 無鎖的設計

4.2.1 鎖機制存在的問題
  • 在多執行緒競爭下,加鎖、釋放鎖會導致比較多的上下文切換和排程延時,引起效能問題,而且在上下文切換的時候,cpu之前快取的指令和資料都將失效,對效能有很大的損失,使用者態的鎖雖然避免了這些問題,但是其實它們只是在沒有真實的競爭時才有效。

  • 一個執行緒持有鎖會導致其它所有需要此鎖的執行緒掛起直至該鎖釋放。

  • 如果一個優先順序高的執行緒等待一個優先順序低的執行緒釋放鎖會導致導致優先順序反轉(Priority Inversion),引起效能風險。

4.2.2 CAS無鎖演算法

​ 實現無鎖(lock-free)的非阻塞演算法有多種實現方法,其中 CAS(比較與交換,Compare and swap) 是一種有名的無鎖演算法。CAS的語義是“我認為V的值應該為A,如果是,那麼將V的值更新為B,否則不修改並告訴V的值實際為多少”,CAS是一種 樂觀鎖 技術,當多個執行緒嘗試使用CAS同時更新同一個變數時,只有其中一個執行緒能更新變數的值,而其它執行緒都失敗,失敗的執行緒並不會被掛起,而是被告知這次競爭中失敗,並可以再次嘗試。CAS有3個運算元,記憶體值V,舊的預期值A,要修改的新值B。當且僅當預期值A和記憶體值V相同時,將記憶體值V修改為B,否則什麼都不做。

​ 這是一個CPU級別的指令,在我的意識中,它的工作方式有點像樂觀鎖——CPU去更新一個值,但如果想改的值不再是原來的值,操作就失敗,因為很明顯,有其它操作先改變了這個值。

file

注意,這可以是CPU的兩個不同的核心,但不會是兩個獨立的CPU。

​ CAS操作比鎖消耗資源少的多,因為它們不牽涉作業系統,它們直接在CPU上操作。但它們並非沒有代價——在上面的試驗中,單執行緒無鎖耗時300ms,單執行緒有鎖耗時10000ms,單執行緒使用CAS耗時5700ms。所以它比使用鎖耗時少,但比不需要考慮競爭的單執行緒耗時多。

4.2.3 傳統佇列問題

佇列的底層資料結構一般分成三種:陣列、連結串列和堆。其中,堆這裡是為了實現帶有優先順序特性的佇列,暫且不考慮。

佇列 有界性 資料結構
ArrayBlockingQueue bounded 加鎖 arraylist
LinkedBlockingQueue optionally-bounded 加鎖 linkedlist
ConcurrentLinkedQueue unbounded 無鎖 linkedlist
LinkedTransferQueue unbounded 無鎖 linkedlist
PriorityBlockingQueue unbounded 加鎖 heap
DelayQueue unbounded 加鎖 heap

​ 在穩定性和效能要求特別高的系統中,為了防止生產者速度過快,導致記憶體溢位,只能選擇有界佇列;

​ 同時,為了減少Java的垃圾回收對系統性能的影響,會盡量選擇array/heap格式的資料結構。這樣篩選下來,符合條件的佇列就只有ArrayBlockingQueue,但是ArrayBlockingQueue是通過加鎖的方式保證執行緒安全,而且ArrayBlockingQueue還存在偽共享問題,這兩個問題嚴重影響了效能。

4.2.3.1 Disruptor的無鎖設計

​ 多執行緒環境下,多個生產者通過do/while迴圈的條件CAS,來判斷每次申請的空間是否已經被其他生產者佔據。假如已經被佔據,該函式會返回失敗,While迴圈重新執行,申請寫入空間。

do
{
    current = cursor.get();
    next = current + n;

    if (!hasAvailableCapacity(gatingSequences, n, current))
    {
        throw InsufficientCapacityException.INSTANCE;
    }
}
while (!cursor.compareAndSet(current, next));
//next 類比於ArrayBlockQueue的陣列索引index
return next;

4.3 環形陣列結構

環形陣列結構是整個Disruptor的核心所在。

4.3.1 什麼是環形陣列

​ RingBuffer 是一個環(首尾相連的環),用做在不同上下文(執行緒)間傳遞資料的buffer,RingBuffer 擁有一個序號,這個序號指向陣列中下一個可用元素。

file

4.3.2 為什麼使用環形陣列

為了避免垃圾回收,採用陣列而非連結串列。同時,陣列對處理器的快取機制更加友好

​ 首先因為是陣列,所以要比連結串列快,而且根據我們對上面快取行的解釋知道,陣列中的一個元素載入,相鄰的陣列元素也是會被預載入的,因此在這樣的結構中,cpu無需時不時去主存載入陣列中的下一個元素。

​ 而且,你可以為陣列預先分配記憶體,使得陣列物件一直存在(除非程式終止)。這就意味著不需要花大量的時間用於垃圾回收。

​ 此外,不像連結串列那樣,需要為每一個新增到其上面的物件創造節點物件—對應的,當刪除節點時,需要執行相應的記憶體清理操作。環形陣列中的元素採用覆蓋方式,避免了jvm的GC。

​ 其次結構作為環形,陣列的大小為2的n次方,這樣元素定位可以通過位運算效率會更高,這個跟一致性雜湊中的環形策略有點像。在disruptor中,這個牛逼的環形結構就是RingBuffer,既然是陣列,那麼就有大小,而且這個大小必須是2的n次方,結構如下:

file

​ 其實質只是一個普通的陣列,只是當放置資料填充滿佇列(即到達2^n-1位置)之後,再填充資料,就會從0開始,覆蓋之前的資料,於是就相當於一個環。

4.4 元素位置定位

​ 陣列長度2^n,通過位運算,加快定位的速度。下標採取遞增的形式。不用擔心index溢位的問題。index是long型別,即使100萬QPS的處理速度,也需要30萬年才能用完。

4.5 等待策略

​ 定義 Consumer 如何進行等待下一個事件的策略。 (注:Disruptor 定義了多種不同的策略,針對不同的場景,提供了不一樣的效能表現)根據實際執行環境的 CPU 的硬體特點選擇恰當的策略,並配合特定的 JVM 的配置引數,能夠實現不同的效能提升。

4.5.1 BlockingWaitStrategy

​ Disruptor的預設策略是BlockingWaitStrategy,在BlockingWaitStrategy內部是使用鎖和condition來控制執行緒的喚醒

​ BlockingWaitStrategy是最低效的策略,但其對CPU的消耗最小並且在各種不同部署環境中能提供更加一致的效能表現。

4.5.2 SleepingWaitStrategy

​ SleepingWaitStrategy 的效能表現跟 BlockingWaitStrategy 差不多,對 CPU 的消耗也類似,但其對生產者執行緒的影響最小,通過使用LockSupport.parkNanos(1)來實現迴圈等待,適合用於非同步日誌類似的場景;

4.5.3 YieldingWaitStrategy

​ YieldingWaitStrategy是可以使用在低延遲系統的策略之一,YieldingWaitStrategy將自旋以等待序列增加到適當的值。在迴圈體內,將呼叫Thread.yield()以允許其他排隊的執行緒執行。在要求極高效能且事件處理線數小於 CPU 邏輯核心數的場景中,推薦使用此策略;

4.5.4 BusySpinWaitStrategy

​ 效能最好,適合用於低延遲的系統。在要求極高效能且事件處理執行緒數小於CPU邏輯核心數的場景中,推薦使用此策略;

4.5.5 PhasedBackoffWaitStrategy

​ 自旋 + yield + 自定義策略,CPU資源緊缺,吞吐量和延遲並不 的場景。

本文由傳智教育博學谷教研團隊釋出。

如果本文對您有幫助,歡迎關注點贊;如果您有任何建議也可留言評論私信,您的支援是我堅持創作的動力。

轉載請註明出處!