676      阿裏雲  技術社區[雲棲]

Disruptor(無鎖並發框架)-發布

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

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

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

這篇文章的要點如下：

1.ring buffer是由一個大數組組成的。

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

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

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

Ring buffer的基礎結構

注意：和代碼中的實際實現，我這裏描述的內容是進行了簡化和抽象的。從概念上講，我認為更加方麵理解。

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

在上麵的圖示裏，是一個size為7的ring buffer（你應該知道這個手工繪製的圖示的原理），從0-2的坐標位置是填充了數據的。

“next”指針指向第一個未填充數據的區塊。“cursor”指針指向最後一個填充了數據的區塊。在一個空閑的ring bufer中，它們是彼此緊鄰的，如上圖所示。

填充數據（Claiming a slot，獲取區塊）

Disruptor API 提供了事務操作的支持。當從ring buffer獲取到區塊，先是往區塊中寫入數據，然後再進行提交的操作。

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

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

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

提交寫入

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

線程E嚐試提交寫入數據。在一個繁忙的循環中有若幹的CAS提交操作。線程E持有位置4，它將會做一個CAS的waiting操作，直到  “cursor”變成3，然後將“cursor”變成4。

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

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

這時候，“cursor”已經更新成3，然後所有和3相關的數據變成可讀。

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

最後的疑惑是線程E的寫入可見，線程E一直重試，嚐試將“cursor”從3更新成4，經過線程D操作後已經更新成3，那麼下一次重試就可以成功了。

總結

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

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

文章轉自 並發編程網-ifeve.com

最後更新：2017-05-23 10:02:45

  上一篇：  如何使用Disruptor（二）如何從Ringbuffer讀取

  下一篇：  The j.u.c Synchronizer Framework翻譯(三)使用、性能與總結