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

杜老師說 2022-01-07 16:37:46 阅读数:701

disruptor 框架

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

譯者:羅立樹

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

下面我給大家介紹一下如何將消息通過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”。

basic-structure1

在上面的圖示裏,是一個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的操作權限。

after-d-claim2

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

after-e-claim3

提交寫入

以上,線程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”指針是為了保證寫入的事務特性。

after-d-commits4

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

after-e-commits5

總結

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

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

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: Disruptor(無鎖並發框架)-發布

FavoriteLoading添加本文到我的收藏
版权声明:本文为[杜老師說]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071637459918.html