Disruptor (無鎖并發(fā)框架)-發(fā)布

原文：http://blog.codeaholics.org/2011/the-disruptor-lock-free-publishing/

譯者：羅立樹

假如你生活在另外一個星球，我們最近開源了一套高性能的基于消息傳遞的開源框架。

下面我給大家介紹一下如何將消息通過 Ring buffer 在無鎖的情況下進行處理。

在深入介紹之前，可以先快速閱讀一下 Trish 發(fā)表的文章，該文章介紹了 ring buffer 和其工作原理。

這篇文章的要點如下：

1.ring buffer 是由一個大數(shù)組組成的。

2.所有 ring buffer 的“指針”（也稱為序列或游標）是 java long 類型的（64位有符號數(shù)），指針采用往上計數(shù)自增的方式。（不用擔心越界，即使每秒 1,000,000 條消息，也要消耗 300,000 年才可以用完）。

3.對 ring buffer 中的指針進行按 ring buffer 的 size 取模找出數(shù)組的下標來定位入口（類似于 HashMap 的 entry）。為了提高性能，我們通常將 ring buffe r的 size 大小設置成實際使用的2倍。

這樣我們可以通過位運算(bit-mask )的方式計算出數(shù)組的下標。

Ring buffer 的基礎結構

注意：和代碼中的實際實現(xiàn)，我這里描述的內(nèi)容是進行了簡化和抽象的。從概念上講，我認為更加方面理解。

ring buffer維護兩個指針，“next”和“cursor”。

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/9-1.jpg" alt="" />

在上面的圖示里，是一個 size 為 7 的 ring buffer（你應該知道這個手工繪制的圖示的原理），從 0-2 的坐標位置是填充了數(shù)據(jù)的。

“next”指針指向第一個未填充數(shù)據(jù)的區(qū)塊?！癱ursor”指針指向最后一個填充了數(shù)據(jù)的區(qū)塊。在一個空閑的 ring bufer 中，它們是彼此緊鄰的，如上圖所示。

填充數(shù)據(jù)（Claiming a slot，獲取區(qū)塊）

Disruptor API 提供了事務操作的支持。當從 ring buffe r獲取到區(qū)塊，先是往區(qū)塊中寫入數(shù)據(jù)，然后再進行提交的操作。

假設有一個線程負責將字母“D”寫進ring buffer中。將會從 ring buffer中獲取一個區(qū)塊（slot）,這個操作是一個基于CAS的“get-and-increment”操作，將“next”指針進行自增。這樣，當前線程（我們可以叫做線程D）進行了 get-and-increment 操作后，

指向了位置 4，然后返回 3。這樣，線程 D 就獲得了位置3的操作權限。

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/9-2.jpg" alt="" />

接著，另一個線程E做類似以上的操作。

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/9-3.jpg" alt="" />

提交寫入

以上，線程 D 和線程 E 都可以同時線程安全的往各自負責的區(qū)塊（或位置，slots）寫入數(shù)據(jù)。但是，我們可以討論一下線程 E 先完成任務的場景…

線程E嘗試提交寫入數(shù)據(jù)。在一個繁忙的循環(huán)中有若干的 CAS 提交操作。線程E持有位置 4，它將會做一個 CAS 的 waiting 操作，直到 “cursor”變成 3，然后將“cursor”變成 4。

再次強調(diào)，這是一個原子性的操作。因此，現(xiàn)在的 ring buffer中，“cursor”現(xiàn)在是 2，線程E將會進入長期等待并重試操作，直到 “cursor”變成 3。

然后，線程 D 開始提交。線程 E 用 CAS 操作將“cursor”設置為 3（線程E持有的區(qū)塊位置）當且僅當“cursor”位置是2.“cursor”當前是 2，所以 CAS 操作成功和提交也成功了。

這時候，“cursor”已經(jīng)更新成 3，然后所有和3相關的數(shù)據(jù)變成可讀。

這是一個關鍵點。知道 ring buffer 填充了多少 – 即寫了多少數(shù)據(jù)，那一個序列數(shù)寫入最高等等，是游標的一些簡單的功能。“next”指針是為了保證寫入的事務特性。

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/9-4.jpg" alt="" />

最后的疑惑是線程E的寫入可見，線程E一直重試，嘗試將“cursor”從 3 更新成 4，經(jīng)過線程 D操作后已經(jīng)更新成 3，那么下一次重試就可以成功了。

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/9-5.jpg" alt="" />

總結

寫入數(shù)據(jù)可見的先后順序是由線程所搶占的位置的先后順序決定的，而不是由它的提交先后決定的。但你可以想象這些線程從網(wǎng)絡層中獲取消息，這是和消息按照時間到達的先后順序是沒什么不同的，而兩個線程競爭獲取一個不同循序的位置。

因此，這是一個簡單而優(yōu)雅的算法，寫操作是原子的，事務性和無鎖，即使有多個寫入線程。

原創(chuàng)文章，轉(zhuǎn)載請注明： 轉(zhuǎn)載自并發(fā)編程網(wǎng) – ifeve.com

本文鏈接地址: Disruptor(無鎖并發(fā)框架)-發(fā)布