ConcurrentDictionary 對決 Dictionary+Locking - gaochundong－IT工程師數位筆記本

文章出處

在 .NET 4.0 之前，如果我們需要在多線程環境下使用 Dictionary 類，除了自己實現線程同步來保證線程安全之外，我們沒有其他選擇。

很多開發人員肯定都實現過類似的線程安全方案，可能是通過創建全新的線程安全的字典類型，或者僅是簡單的用一個類封裝一個 Dictionary 對象，并在所有方法中加上鎖機制，我們稱這種方案叫“Dictionary + Locks”。

但現在，我們有了 ConcurrentDictionary。在 MSDN 中的 Dictionary 類文檔的線程安全的描述中指出，如果你需要用一個線程安全的實現，請使用 ConcurrentDictionary。

所以，既然現在已經有了一個線程安全的字典類，我們再也不需要自己實現了。很棒，不是嗎？

問題起源

事實上我之前只使用過 CocurrentDictionary 一次，就是在我測試其反應速度的測試中。因為在測試中它表現的很好，所以我立即把它替換到我的類中，并做了些測試，然后，居然出了些異常。

那么，到底哪出了問題？不是說線程安全嗎？

經過了更多的測試，我找到了問題的根源。但不知道為什么，MSDN 的 4.0 版本中，關于 GetOrAdd 方法簽名的描述中并沒有包含一個需要傳遞一個委托類型參數的說明。在查看 4.5 版本后，我找到了這段備注：

If you call GetOrAdd simultaneously on different threads, addValueFactory may be called multiple times, but its key/value pair might not be added to the dictionary for every call.

這就是我碰到的問題。因為之前在文檔中并沒有描述，所以我不得不做了更多的測試來確認問題。當然，我碰到的問題與我的使用方法有關，一般來說，我會使用字典類型來緩存一些數據：

這些數據創建起來非常的慢；
這些數據只能創建一次，因為創建第二次會拋出異常，或者多次創建可能會導致資源泄漏等；

我就是在第二個條件上遇到了問題。如果兩個線程同時發現某個數據不存在，都會創建一次該數據，但只有一個結果會被成功的保存。那另一個怎么辦？

如果創建的過程會拋出異常，可以通過 try..catch 來解決（雖不夠優雅，但能解決問題）。但如果某個資源被創建后未被回收該怎么辦？

你可能會說，一個對象被創建后，如果已經對其沒有任何引用，將會被垃圾回收掉。但，請再考慮下，如果下面描述的情形發生了會怎樣：

使用Emit動態生成代碼。我在一個 Remoting 框架中使用了這種方式，并且將所有的實現都放到了一個不能被回收的程序集當中。如果一個類型被創建了兩次，第二個將一直存在，即使其從未被使用過。
直接地或者間接地創建一個線程。比如我們需要構建一個組件，其使用專有線程處理異步消息，并且依賴于消息的接收順序。當實例化該組件時，會創建一個線程。當銷毀這個組件實例時，線程也會被結束。但如果銷毀組件后我們刪除了對該對象的引用，但那個線程因某種原因未結束，并且持有這個對象的引用。那么，如果線程不死亡，這個對象也不會被回收。
進行 P/Invoke 操作。要求對所接收到的句柄的關閉次數必須與打開的次數相同。
可以肯定的是，還可以列舉出很多類似的情形。比如一個字典對象會持有一個遠程服務器上一個服務的連接，該連接只能請求一次，如果請求第二次，對方服務會認為發生了某種錯誤，進而記錄到日志中。（我工作過的一個公司中，這種條件會遭到一些法律上的處罰。）

所以，我們很容易的看到，并不能草率地將 Dictionary + Locks 直接替換成 ConcurrentDictionary，即使文檔上說它是線程安全的。

分析問題

還不明白？

的確，在 Dictionary + Locks 方式下可能不會產生這個問題。因為這依賴于具體的實現，讓我們來看下下面這個簡單的示例：

TValue result;
lock(dictionary)
{
  if (!dictionary.TryGetValue(key, out result))
  {
    result = createValue(key);
    dictionary.Add(key, result);
  }
}
return result;

在上面這段代碼中，在開始查詢鍵值之前，我們持有了對該字典的鎖。如果指定的鍵值對不存在，將會直接創建一個。同時，因為我們已經持有了對該字典的鎖，可以直接將鍵值對添加到字典中。然后釋放字典鎖，并返回結果。如果有兩個線程同時在查詢同一個鍵值，第一個得到字典鎖的線程將會完成對象的創建工作，另一個線程會等待這個創建的完成，并在得到字典鎖之后獲取到已創建的鍵值結果。

這樣挺好的，不是嗎？

真不是！我認為像這種在并行方式下創建對象，最后只有一個被使用的情況不會產生我所描述的問題。

我想闡述的情況和問題可能并不總是能復現，在并行環境中，我們可以簡單的創建兩個對象，然后丟棄一個。那么，到底我們該如何比較 Dictionary + Locks 和 ConcurrentDictionary 呢？

答案是：具體依賴于鎖使用策略和字典的使用方式。

對戰第一局：并行創建同一對象

首先，我們假設某個對象可以被創建兩次，那么如果有兩個線程在同時創建這個對象時，會發生什么？

其次，在類似的創建過程中，我們會消耗多長時間？

我們可以簡單地構建一個例子，比如實例化一個對象需要耗費10秒鐘。當第一個線程創建對象5秒鐘后，第二個實現嘗試調用 GetOrAdd 方法來獲取對象，因為對象仍然不存在所以它也開始創建對象。

在這種條件下，我們有2顆CPU在并行工作5秒鐘，當第一個線程工作結束后，第二個線程仍然需要繼續運行5秒鐘來完成對象的構建。當第二個線程構建對象完畢后，發現已經有一個對象存在了，其選擇使用已經存在的對象，而將剛創建的對象直接丟棄。

假如第二個線程只是簡單等待，而讓第2顆CPU處理些其他工作（運行其他線程或應用程序，節省了些電量消耗），在5秒鐘之后其就可以獲取到所需的對象，而不是10秒鐘。

所以，在這種條件下，Dictionary + Locks 小勝一局。

對戰第二局：并行訪問不同對象

不，你說的情況根本就不成立！

好吧，上面的例子有點特殊，但確實描述了問題，只是這種用法比較極端。那么，考慮下，如果當第一個線程正在創建對象時，第二個線程需要訪問另一個鍵值對象，并且該鍵值對象已經存在了，會發生什么？

在 ConcurrentDictionary 中，由于其沒有對讀操作加鎖，也就是 lock-free 的設計會使讀操作非常迅速。如果是 Dictionary + Locks 方式，會對讀操作進行鎖互斥控制，即使需要讀取的是一個完全不同的鍵值，顯然讀取操作會變慢。

這樣看來，ConcurrentDictionary 扳回一局。

注：這里我考慮你了解字典類中的 Bucket/Node/Entry 等幾種概念，如果不了解，建議看下 Ofir Makmal 的文章 "Understanding Generic Dictionary in-depth"，其中很好地解釋了這些概念。

對戰第三局：多讀單寫

在 Dictionary + Locks 中，如果使用多個讀取方、單一寫入方的方式（Multiple Readers and Single Writer）來取代對字典的完全鎖，情況會如何？

如果一個線程正在創建對象，并且持有了一個可升級的鎖，直到這個對象創建完畢，將該鎖升級為寫操作鎖，那么讀操作就可以在并行的環境下執行。

我們也可以通過讓一個讀操作空閑等待10秒來解決問題。但如果讀操作遠遠多于寫操作，我們會發現 ConcurrentDictionary 的速度仍然很快，因為它實現了 lock-free 模式的讀取。

對 Dictionary 使用 ReaderWriterLockSlim 會使讀操作變得更糟糕，通常更推薦針對 Dictionary 使用完全鎖，而不使用 ReaderWriterLockSlim。

所以，在這種條件下 ConcurrentDictionary 又贏了一局。

注：我在之前的文章中已經介紹了 YieldReaderWriterLock 和 YieldReaderWriterLockSlim 類。通過運用這種讀寫鎖，速度得到了可觀的提升（現在已經演進到了 SpinReaderWriterLockSlim），并且允許多個讀操作并行執行，并幾乎不會受到影響。雖然我還在使用這種方式，但無鎖的 ConcurrentDictionary 顯然會更快。

對戰第四局：添加多個鍵值對

對決還沒有結束。

如果我們有多個鍵值需要添加，并且所有的鍵不會產生碰撞并會被分配在不同的 Bucket 中，情況會如何？

起初，這個問題還是讓我很好奇的，但我做了個不太合適的測試。我使用了 <int, int> 類型的字典，并且對象的構造工廠會直接返回一個負數的結果作為鍵。

我本來期待 ConcurrentDictionary 應該是最快的，但它卻是最慢的。而 Dictionary + Locks 卻表現的更快。這是為什么呢？

這是因為，ConcurrentDictionary 會分配 Node 并將它們放到不同的 Bucket 中，這種優化是為了滿足對于讀操作的 lock-free 的設計。但是，在新增鍵值項時，創建 Node 的過程就會顯得昂貴。

即使在并行的條件下，分配 Node 鎖消耗的時間仍然比使用完全鎖多。

所以，Dictionary + Locks 此局勝利。

對戰第五局：讀操作頻率更高

坦白的說，如果有一個能快速實例化對象的委托，我們就不需要一個 Dictionary 了。我們可以直接調用委托來獲取對象，對吧？

其實，答案也是，要看情況。

想象下，如果鍵類型為 string ，并且包含 Web 服務器中各種頁面的路徑映射，而對應的值為一個對象類型，該類型中包含對該頁當前訪問用戶的記錄和自服務器啟動后所有對該頁訪問的數量。

創建類似這種對象幾乎是瞬間的事。并且在此之后，你不需要再創建新的對象，僅需更改其中保存的值。所以可以允許創建兩次的方式，直到僅有一個實例被使用。然而，因為 ConcurrentDictionary 分配 Node 資源更慢，使用 Dictionary + Locks 將會得到更快的創建時間。

所以，通過這個例子非常特殊，我們也看到了 Dictionary + Locks 在這種條件下表現的更好，花費了更少的時間。

雖然 ConcurrentDictionary 中的 Node 分配要慢些，我也沒有嘗試將 1 億個數據項放入其中來測試時間。因為那顯然很花費時間。

但大部分情況下，一個數據項被創建后，其總是被讀取。而數據項的內容是如何變化的就是另外的事情了。所以說，創建數據項的過程多花銷了多少毫秒并不重要，因為讀取操作更快（也是快了若干毫秒而已），但讀操作發生的頻率更高。

所以，ConcurrentDictionary 贏了這局。

對戰第六局：創建消耗不同時間的對象

針對不同數據項的創建所消耗的時間不同，將會怎樣？

創建多個消耗不同時間的數據項，并且并行的添加至字典中。這是 ConcurrentDictionary 的最強點。

ConcurrentDictionary 使用了多種不同的鎖機制來允許并發地添加數據項，但是諸如決定使用哪個鎖，為改變 Bucket 尺寸而請求鎖等邏輯，并沒有為此帶來幫助。把數據項放入 Bucket 中的速度是機器快速的。真正使 ConcurrentDictionary 勝出的原因是因為它能夠并行的創建對象。

不過，其實我們也可以做同樣的事。如果我們并不關心是否在并行的創建對象，或者其中的一些已經被丟棄，我們可以加鎖，用來檢測該數據項是否已經存在，然后釋放鎖，創建數據項，按后再獲取鎖，再次檢查數據項是否存在，如果不存在，則添加該數據項。代碼可能類似于：

int result;
lock(_dictionary)
  if (_dictionary.TryGetValue(i, out result))
    return result;

int createdResult = _createValue(i);
lock(_dictionary)
{
  if (_dictionary.TryGetValue(i, out result))
    return result;

  _dictionary.Add(i, createdResult);
  return createdResult;
}

* 注意，我使用了一個<int, int>類型的字典。

在上面這個簡單的結構中，當在并行條件下創建并添加數據項時，Dictionary + Locks 的表現幾乎與 ConcurrentDictionary 一樣好。但也有同樣的問題，就是某些值可能被生成來，但從沒被使用過。

結論

那么，有結論了沒？

此時此刻，還是有一些的：

所有的字典類速度都非常快。即便我已經創建了上百萬的數據，速度依然很快。通常情況下，我們只是創建少量的數據項，并且讀取還有一些時間間隔，所以我們一般不會察覺到讀取數據項的時間開銷。
如果相同的對象不能被創建兩次，則不要使用 ConcurrentDictionary。
如果你的確很關注性能，可能 Dictionary + Locks 仍然是一個好的方案。重要的因素是，添加和刪除數據項的數量。但如果是讀操作多，就慢于 ConcurrentDictionary。
雖然我沒有介紹，但其實使用 Dictionary + Locks 方案會有更大的自由性。比如你可以鎖定一次，添加多個數據項，刪除多個數據項，或者查詢多次等，之后再釋放鎖。
一般來說，如果讀操作遠多于寫操作，可避免使用 ReaderWriterLockSlim。字典類型配合完全鎖已經比獲取一個讀寫鎖中的讀鎖快很多了。當然，這也依賴于在一個鎖中創建對象所消耗的時間。

所以，我認為盡管舉的示例有些極端，但卻表明了使用 ConcurrentDictionary 并不總是最好的方案。

感受差異

寫這篇文章的初衷是我想尋求更好的解決方案。

我已經在嘗試深入的理解具體一個字典類是如何工作的（現在看來我感覺我已經非常的明確了）。

可以說，ConcurrentDictionary 中的 Bucket 和 Node 是非常簡單的。當我嘗試創建一個字典類時我也做了類似的事。而常規的 Dictionary 類，可能看起來更簡單，但其實，要復雜些。

在 ConcurrentDictionary 中，每個 Node 都是一個完整的類。而在 Dictionary 類中，Node 使用值類型實現，并且所有 Node 都被保存在一個巨大的數組當中，而 Bucket 則被用于在數組中進行索引。同時，也用于代替 Node 對其下一個 Node 的簡單引用（畢竟，作為結構體類型的 Node，不能包含一個結構體類型的 Node 成員）。

當對字典進行添加和刪除操作時，Dictionary 類不能簡單的創建一個新的 Node，它必須檢查是否有一個索引在標示一個已經被刪除的 Node，進而進行復用。或者會使用 “Count” 來得到新的 Node 在數組中的位置。事實上，當數組已滿時，Dictionary 類會強制改變尺寸。

對于 ConcurrentDictionary ，一個 Node 可以簡單看做一個新對象。移除一個 Node 就是簡單的刪除它的引用。而新增一個 Node 則可簡單的創建一個新的 Node 實例。改變尺寸的操作僅是為了避免沖突，但并不是強制性的。

所以，要是 Dictionary 類有目的性的使用了更加復雜的算法來處理，ConcurrentDictionary 將如何保證在多線程環境下表現的更好呢？

真相是：將所有的 Node 都放到一個數組中，無論分配和讀取都是最快的方法，即使我們需要另外一個數組來記錄在哪里能找到那些數據項。所以看起來因為有相同數量的 Bucket，將會使用更多的內存，但新的數據項并不需要重新分配，不需要新的對象同步，同時也不會導致新的垃圾回收。因為一切都已經就緒了。

但是，替換 Node 中的內容并不是一個原子操作，這也是導致其線程不安全的因素之一。因為 Node 都是對象，一個 Node 被初始化創建，然后一個單獨的引用會被更新用于指向它（此處是原子操作）。所以，讀線程可以讀取字典內容而不需要鎖，而讀到的肯定是舊值和新值中的一個，并沒有機會讀到一個未完成的值。

所以，真相是：如果你不需要鎖得話，Dictionary 類在讀操作上更快，而鎖會導致讀操作變慢。

本文翻譯自 Paulo Zemek 在 CodeProject 上的文章 "Dictionary + Locking versus ConcurrentDictionary"，部分語句由于理解原因會有一些更改。

文章列表