鎖的缺點

原文：http://ifeve.com/disruptor-locks-are-bad/

作者：Trisha’s 譯者：張文灼，潘曦
整理和校對：方騰飛，丁一

Martin Fowler 寫了一篇非常好的文章，里面不僅提到了 Disruptor,而且還解釋了 Disruptor 如何應(yīng)用在 LMAX 的架構(gòu)里。里面有提及了一些目前沒有涉及的概念，但最經(jīng)常問到的問題是 “Disruptor 究竟是什么?＂。

目前我正準備在回答這個問題，但首先回答＂為什么它會這么快?＂

這些問題持續(xù)出現(xiàn)，但是我不能沒有說它是干什么的就說它為什么會這么快，不能沒有說它為什么這樣做就說它是什么東西。

所以我陷入了一個僵局，一個如何寫博客的僵局。

要打破這個僵局，我準備以最簡單方式回答第一個問題，如果幸運的話，在以后博文里，如果需要解釋的話我會重新提回：Disruptor 提供了一種線程之間信息交換的方式。

作為一個開發(fā)者,因為＂線程＂一詞的出現(xiàn)，我的警鐘已經(jīng)敲響，它意味著并發(fā)，而并發(fā)是困難的。

并發(fā) 01

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-1.png" alt="并發(fā)01" />

想象有兩個線程嘗試修改同一個變量 value：

情況一：線程 1 先到達

變量 value 的值變?yōu)?“blah” 。 然后當(dāng)線程 ２ 到達時，變量 value 的值變?yōu)?“blahy”。

情況二：線程 2 先到達

變量 value 的值變?yōu)?“fluffy” 。 然后當(dāng)線程 1 到達時，值變?yōu)?“blah” 。

情況三：線程 1 與線程 ２ 交互

線程 2 得到值 “fluff” 然后賦給本地變量 myValue 。

線程 1 改變 value 的值為 ”blah”。

然后線程 2 醒來并把變量 value 的值改為 ”fluffy”

情況三顯然是唯一一個是錯誤的，除非除非你認為 Wiki 編輯的幼稚做法是正確的（Google Code Wiki，我一直在關(guān)注你）。其他兩種情況主要是看你的意圖和想要達到的效果。線程 2 可能不會關(guān)心變量 value 的值是什么，主要的意圖就是在后面加上字符 ‘y＇而不管它原來的值是什么，在這種前提下，情況一和情況二都是正確的。

但是如果線程 ２ 只是想把＂fluff＂改為 ”fluffy”，那么情況二和三都不正確。假定線程 2 想把值設(shè)為 ”fluffy”,有幾種辦法可以解決這個問題：

辦法一：悲觀鎖

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-2.png" alt="悲觀鎖" />

(“No Entry” 的標志對于在沒有在英國開車的人看得明白不？)

悲觀鎖和樂觀鎖這兩個詞通常在我們談?wù)摂?shù)據(jù)庫讀寫時經(jīng)常會用到，但原理可以應(yīng)用到在獲得一個對象的鎖的情況。

只要線程 2 一獲得 Entry 的互斥鎖，它就會阻擊其它線程去改變它，然后它就可以隨意做它要做的事情，設(shè)置值，然后做其它事情。

你可以想象這里非常耗性能的，因為其它線程在系統(tǒng)各處徘徊著準備要獲得鎖然后又阻塞。線程越多，系統(tǒng)的響應(yīng)性就會越慢．

辦法二：樂觀鎖

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-3.png" alt="樂觀鎖" />

在這種情況，當(dāng)線程 ２ 需要去寫 Entry 時才會去鎖定它。它需要檢查 Entry 自從上次讀過后是否已經(jīng)被改過了。如果線程 １ 在線程 ２ 讀完后到達并把值改為”blah”,線程 ２ 讀到了這個新值，線程 ２ 不會把＂fluffy＂寫到 Entry 里并把線程 １ 所寫的數(shù)據(jù)覆蓋．線程 ２ 會重試（重新讀新的值，與舊值比較，如果相等則在變量的值后面附上’y’）,這里在線程 ２ 不會關(guān)心新的值是什么的情況．或者線程 ２ 會拋出一個異常，或者會返回一個某些字段已更新的標志，這是在期望把”fluff”改為”fluffy”的情況．舉一個第二種情況的例子，如果你和另外一個用戶同時更新一個 Ｗiki 的頁面，你會告訴另外一個用戶的線程 Thread 2，它們需要重新加載從 Thread 1 來新的變化，然后再提交它們的內(nèi)容。

潛在的問題：死鎖

鎖定會帶來各種各樣的問題，比如死鎖，想象有２個線程需要訪問兩個資源

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-4.png" alt="死鎖" />

如果你濫用鎖技術(shù)，兩個鎖都在獲得鎖的情況下嘗試去獲得另外一個鎖，那就是你應(yīng)該重啟你的電腦的時候了。（校注：作者還挺幽默）

很明確的一個問題：鎖技術(shù)是慢的．．

關(guān)于鎖就是它們需要操作系統(tǒng)去做裁定。線程就像兩姐妹在為一個玩具在爭吵，然后操作系統(tǒng)就是能決定他們誰能拿到玩具的父母，就像當(dāng)你跑向你父親告訴他你的姐姐在你玩著的時候搶走了你的變形金剛－他還有比你們爭吵更大的事情去擔(dān)心，他或許在解決你們爭吵之前要啟動洗碗機并把它擺在洗衣房里。如果你把你的注意力放在鎖上，不僅要花時間來讓操作系統(tǒng)來裁定。Disruptor 論文中講述了我們所做的一個實驗。這個測試程序調(diào)用了一個函數(shù)，該函數(shù)會對一個 64 位的計數(shù)器循環(huán)自增 5 億次。當(dāng)單線程無鎖時，程序耗時 300 ms。如果增加一個鎖（仍是單線程、沒有競爭、僅僅增加鎖），程序需要耗時 10000 ms，慢了兩個數(shù)量級。更令人吃驚的是，如果增加一個線程（簡單從邏輯上想，應(yīng)該比單線程加鎖快一倍），耗時 224000 ms。使用兩個線程對計數(shù)器自增 5 億次比使用無鎖單線程慢 1000 倍。并發(fā)很難而鎖的性能糟糕。我僅僅是揭示了問題的表面，而且，這個例子很簡單。但重點是，如果代碼在多線程環(huán)境中執(zhí)行，作為開發(fā)者將會遇到更多的困難：

• 代碼沒有按設(shè)想的順序執(zhí)行。上面的場景 3 表明，如果沒有注意到多線程訪問和寫入相同的數(shù)據(jù)，事情可能會很糟糕。
• 減慢系統(tǒng)的速度。場景3中，使用鎖保護代碼可能導(dǎo)致諸如死鎖或者效率問題。

這就是為什么許多公司在面試時會多少問些并發(fā)問題（當(dāng)然針對 Java 面試）。不幸的是，即使未能理解問題的本質(zhì)或沒有問題的解決方案，也很容易學(xué)會如何回答這些問題。

Disruptor如何解決這些問題。

首先，Disruptor 根本就不用鎖。

取而代之的是，在需要確保操作是線程安全的（特別是，在多生產(chǎn)者的環(huán)境下，更新下一個可用的序列號）地方，我們使用 CAS（Compare And Swap/Set）操作。這是一個 CPU 級別的指令，在我的意識中，它的工作方式有點像樂觀鎖—— CPU 去更新一個值，但如果想改的值不再是原來的值，操作就失敗，因為很明顯，有其它操作先改變了這個值。

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-5.png" alt="CAS" />

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

CAS 操作比鎖消耗資源少的多，因為它們不牽涉操作系統(tǒng)，它們直接在 CPU 上操作。但它們并非沒有代價——在上面的試驗中，單線程無鎖耗時 300 ms，單線程有鎖耗時 10000 ms，單線程使用 CAS 耗時 5700 ms。所以它比使用鎖耗時少，但比不需要考慮競爭的單線程耗時多。

回到 Disruptor，在我講生產(chǎn)者時講過 ClaimStrategy。在這些代碼中，你可以看見兩個策略，一個是SingleThreadedStrategy（單線程策略）另一個是 MultiThreadedStrategy（多線程策略）。你可能會有疑問，為什么在只有單個生產(chǎn)者時不用多線程的那個策略？它是否能夠處理這種場景？當(dāng)然可以。但多線程的那個使用了 AtomicLong（Java 提供的 CAS 操作），而單線程的使用 long，沒有鎖也沒有 CAS。這意味著單線程版本會非常快，因為它只有一個生產(chǎn)者，不會產(chǎn)生序號上的沖突。

我知道，你可能在想：把一個數(shù)字轉(zhuǎn)成 AtomicLong 不可能是 Disruptor 速度快的唯一秘密。當(dāng)然，它不是，否則它不可能稱為“為什么這么快（第一部分）”。

但這是非常重要的一點——在整個復(fù)雜的框架中，只有這一個地方出現(xiàn)多線程競爭修改同一個變量值。這就是秘密。還記得所有的訪問對象都擁有序號嗎？如果只有一個生產(chǎn)者，那么系統(tǒng)中的每一個序列號只會由一個線程寫入。這意味著沒有競爭、不需要鎖、甚至不需要 CAS。在 ClaimStrategy 中，如果存在多個生產(chǎn)者，唯一會被多線程競爭寫入的序號就是 ClaimStrategy 對象里的那個。

這也是為什么 Entry 中的每一個變量都只能被一個消費者寫。它確保了沒有寫競爭，因此不需要鎖或者 CAS。

回到為什么隊列不能勝任這個工作

因此你可能會有疑問，為什么隊列底層用 RingBuffer 來實現(xiàn)，仍然在性能上無法與 Disruptor 相比。隊列和最簡單的 ring buffer 只有兩個指針——一個指向隊列的頭，一個指向隊尾：

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-6.png" alt="range" />

如果有超過一個生產(chǎn)者想要往隊列里放東西，尾指針就將成為一個沖突點，因為有多個線程要更新它。如果有多個消費者，那么頭指針就會產(chǎn)生競爭，因為元素被消費之后，需要更新指針，所以不僅有讀操作還有寫操作了。

等等，我聽到你喊冤了！因為我們已經(jīng)知道這些了，所以隊列常常是單生產(chǎn)者和單消費者（或者至少在我們的測試里是）。 隊列的目的就是為生產(chǎn)者和消費者提供一個地方存放要交互的數(shù)據(jù)，幫助緩沖它們之間傳遞的消息。這意味著緩沖常常是滿的（生產(chǎn)者比消費者快）或者空的（消費者比生產(chǎn)者快）。生產(chǎn)者和消費者能夠步調(diào)一致的情況非常少見。

所以，這就是事情的真面目。一個空的隊列：

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-7.png" alt="empty" /> …

一個滿的隊列：

http://wiki.jikexueyuan.com/project/disruptor-getting-started/images/1-8.png" alt="fill" />

(校對注：這應(yīng)該是一個雙向隊列) 隊列需要保存一個關(guān)于大小的變量，以便區(qū)分隊列是空還是滿。否則，它需要根據(jù)隊列中的元素的內(nèi)容來判斷，這樣的話，消費一個節(jié)點（Entry）后需要做一次寫入來清除標記，或者標記節(jié)點已經(jīng)被消費過了。無論采用何種方式實現(xiàn)，在頭、尾和大小變量上總是會有很多競爭，或者如果消費操作移除元素時需要使用一個寫操作，那元素本身也包含競爭。

基于以上，這三個變量常常在一個 cache line里面，有可能導(dǎo)致 false sharing。因此，不僅要擔(dān)心生產(chǎn)者和消費者同時寫 size 變量（或者元素），還要注意由于頭指針尾指針在同一位置，當(dāng)頭指針更新時，更新尾指針會導(dǎo)致緩存不命中。這篇文章已經(jīng)很長了，所以我就不再詳述細節(jié)了。

這就是我們所說的“分離競爭點問題”或者隊列的“合并競爭點問題”。通過將所有的東西都賦予私有的序列號，并且只允許一個消費者寫 Entry 對象中的變量來消除競爭，Disruptor 唯一需要處理訪問沖突的地方，是多個生產(chǎn)者寫入 Ring Buffer 的場景。

總結(jié)

Disruptor 相對于傳統(tǒng)方式的優(yōu)點：

1. 沒有競爭=沒有鎖=非?？?。
2. 所有訪問者都記錄自己的序號的實現(xiàn)方式，允許多個生產(chǎn)者與多個消費者共享相同的數(shù)據(jù)結(jié)構(gòu)。
3. 在每個對象中都能跟蹤序列號（ring buffer，claim Strategy，生產(chǎn)者和消費者），加上神奇的 cache line padding，就意味著沒有為偽共享和非預(yù)期的競爭。

校訂：需要注意 Disruptor2.0 使用了與本文中不一樣的名字。如果對類名感到困惑，請參考我的變更匯總。

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

本文鏈接地址: 剖析 Disruptor:為什么會這么快？(一)鎖的缺點