並行數據結構設計

Question

我正想要在高吞吐量C++服務器中使用最佳數據結構。數據結構將被用來存儲從幾個到幾百萬個對象的任何東西，並且不需要排序（儘管可以非常便宜地提供獨特的排序鍵）。要求是它可以支持高效的插入，理想情況下是O（1），中等效率的移除和高效的遍歷。它不需要支持查找操作（除了可能需要刪除）。

扭曲的是它在修改時必須是線程安全的，而其他線程正在枚舉數據結構。這意味着一個簡單的紅黑樹不起作用，因爲一個線程不能插入一個元素（並執行必要的樹旋轉），而不會搞亂其他線程持有的任何光標。

它是而不是可接受的使用讀/寫鎖，並推遲寫操作，直到所有的讀取器完成，因爲讀操作可能會很長壽。讀者是否可以看到插入是否可見，這並不重要。

內存佔用也很重要，而小顯然更好！

有什麼建議？

迴應評論：

感謝您的答案。

不，插入無法使現有的迭代器無效。迭代器可能會或可能不會看到新插入，但是他們必須看到插入沒有發生時他們會看到的所有內容。

需要刪除，但是由於更高級別的規則，我可以保證迭代器永遠不會停止在可刪除的項目上。

爲每個節點鎖定遊標會對性能產生太大的影響。一次可能有多個線程讀取，多個線程在鎖中使用的任何類型的內存熱點都會導致內存帶寬（正如我們發現的難題！）。即使是多線程調用InterlockedIncrement的讀者的簡單計數也無法順利進行擴展。

我同意鏈接列表可能是最好的方法。刪除是很少見的，因此爲支持O（1）刪除而支付內存處罰是很昂貴的，我們可以根據需要分別計算這些值，因爲刪除往往是批處理操作。

幸運的是，只要在改變頭指針之前在插入的節點中更新指針，插入到鏈表中並不需要對讀取器進行任何鎖定。

鎖複製解鎖的想法很有趣。所涉及的數據量太大，無法用作讀者的默認設置，但它可能會在作家與讀者碰撞時使用。讀/寫鎖可以保護整個結構，如果數據結構與讀卡器發生衝突，寫入操作會克隆數據結構。寫入比讀取要少得多。

Answer 1

個人而言，我非常喜歡在高度併發的情況下持久不變的數據結構我不知道任何專門針對C++，但Rich Hickey已經在Java中爲Clojure創建了一些優秀（且快速）的不可變數據結構。具體來說：vector，h ashtable和hashset。它們不太難以移植，因此您可能需要考慮其中之一。

爲了闡述更多，持久不變的數據結構確實解決了許多與併發有關的問題。因爲數據結構本身是不可變的，所以多線程讀取/併發迭代（只要它是一個常量迭代器）就沒有問題。 「寫作」也可以是異步的，因爲它不是真的寫入現有結構，而是創建包含新元素的新結構。這個操作是有效的（O（1）在所有Hickey的結構中），因爲您實際上並未複製所有內容。每個新版本都與舊版本共享其大部分結構。這使得內存效率更高，並且通過簡單的寫入時複製技術顯着提高了性能。

對於不可變的數據結構，實際需要同步的唯一時間實際上是寫入參考單元。由於內存訪問是原子的，即使這樣也可以無鎖。唯一需要注意的是你可能會在線程之間丟失數據（競爭條件）。數據結構永遠不會因併發而受到破壞，但這並不意味着在兩個線程基於單箇舊版本創建新版本結構並嘗試寫入其結果的情況下不可能產生不一致的結果（其中一個將會「贏」，其他的變化將會失去）。要解決此問題，您需要鎖定「寫入操作」，或使用某種STM。我喜歡在低碰撞系統中使用易用性和吞吐量的第二種方法（寫入理想情況下是非阻塞的並且讀取從未塊），但是其中任何一個都可以工作。

你已經提出了一個棘手的問題，其中沒有一個很好的答案。併發安全的數據結構很難編寫，特別是當它們需要可變時。在共享狀態下，完全無鎖的體系結構是不可能的，因此您可能要放棄這一要求。你可以做的最好的事情是儘量減少所需的鎖定，因此不可變的數據結構。

Answer 2

我認爲鏈表應該回答你的要求。請注意，您只能鎖定正在更改（即已刪除/附加）的節點，以便讀者大部分時間都能夠與作者完全並行工作。 此方法需要每個鏈接列表節點鎖定，但它不是必須的。您可以擁有有限數量的鎖，然後將多個節點映射到同一個鎖。也就是說，有N個鎖和數組編號爲0..M的數組，你可以使用lock（NodeId％N）來鎖定這個節點。這些可以是讀寫鎖，並通過控制鎖的數量來控制並行度。

Answer 3

那麼，爲了線程安全，你將不得不鎖定某些點。一個關鍵的問題是要確保您的存儲庫中的對象可以與存儲庫結構本身分開鎖定：即，在您要存儲的數據中沒有_next鏈接或類別。這樣讀取操作可以鎖定對象的內容而不鎖定存儲庫的結構。

高效插入很簡單：鏈表，未排序數組，哈希表都可以正常工作。有效的刪除比較困難，因爲這涉及到在存儲庫中查找已刪除的東西。 Howerver爲了簡單和快速，鏈接列表是一個不錯的選擇。非繁忙時間和剛標記爲「非活動」的項目可以刪除嗎？那麼查找/刪除的代價並不是如此限制。

儘管你仍然會遇到遍歷問題。大家可以做的就是鎖定並拍攝需要遍歷的內容的快照，然後在查看快照後檢查是否有任何更改。嚴重的問題...

Answer 4

如果你不需要排序順序，不要使用紅/黑樹或任何其他內在排序。

你的問題沒有很好地指定w.r.t讀寫之間的交互。 如果通過鎖定+複製+解鎖實現「讀取」，然後使用新的副本，它會好嗎？

您可能想要閱讀關於http://en.wikipedia.org/wiki/Seqlock中的seqlocks和通常的「無鎖」進程 - 儘管您可能想盡可能放寬您的需求 - 無鎖哈希表實現是一項主要承諾。

Answer 5

鏈接列表絕對是答案。 O（1）中的插入和刪除，O（1）中從一個節點到下一個節點的迭代以及跨操作的穩定性。 std::list保證所有這些，包括所有迭代器都是有效的，除非該元素從列表中移除（這包括指針和對元素的引用）。對於鎖定，您可以將列表包裝在一個鎖定類中，或者您可以編寫自己的列表類（在這種情況下，您將無法使用std::list，它支持基於節點的鎖定 - 例如，您可以鎖定某些區域在其他線程在不同區域執行操作時使用的列表，您使用的主要取決於您期望的併發訪問類型 - 如果列表的不同部分上的多個操作將非常常見，請自行編寫，但請記住在每個節點上放置一個互斥對象，這是不節約空間的

Answer 6

道歉雙答案...

由於寫操作是相當罕見的，你真的應該考慮使用STM，而不是鎖定。 STM是樂觀鎖定的一種形式，這意味着它嚴重偏向於無碰撞系統（也就是更少的寫入）。相比之下，悲觀鎖定（鎖 - 寫 - 解鎖）針對碰撞繁重的系統（又名大量寫入）進行了優化。 STM的唯一問題是它幾乎要求你在TVar單元內使用不可變的數據結構，否則整個系統就會崩潰。就我個人而言，我不認爲這是一個問題，因爲體面的不可變數據結構將會像變化的數據結構一樣快（請參閱我的其他答案），但值得考慮。

Answer 7

你有3種類型的任務：

1. 迭代（慢）
2. 插入（快速）
3. 刪除（快）

如果附近的一致性不夠好，然後跟蹤有效迭代任務的數量。

如果迭代任務活動和新的插入或刪除任務來在隊列中用於以後處理這些任務（但你可以返回到呼叫方馬上）一旦

爲最後一次迭代如果完成過程排隊刀片並刪除。

如果在插入或刪除操作掛起時出現迭代請求，則將其排隊。

如果有一個迭代請求進來，而只有迭代運行，只是讓它進行迭代。

如果實際數據處理比迭代本身需要更多時間，您仍然應該通過複製正在迭代的數據並在客戶端處理該數據來儘可能快地編寫迭代。

我會用hashtable或stl：map實現主集合，甚至可能足夠快。插入/刪除請求可以在列表中排隊。

Answer 8

我認爲這是可以實現的唯一方法是通過類似於Oracle/postgresql等數據庫中使用的多版本併發協議。這保證讀者不會阻止讀者，作者不會阻止讀者，但作家阻止只有那些更新相同數據的作者。編寫者阻止更新相同數據片段的寫入器的這種屬性在併發編程領域中是重要的，否則數據/系統不一致是可能的。對於數據結構的每一次寫入操作，您都要在寫入數據結構之前拍攝數據結構的快照，或至少將受寫入操作影響的數據結構節點的一部分寫入內存中的其他位置。因此，在寫入過程中，讀取器線程會請求從寫入器部分讀取部分數據，您始終會參考最新快照&迭代該快照，從而爲所有讀取器提供一致的數據視圖。快照是昂貴的，因爲它們消耗更多的內存，但是對於您的要求，這種技術是正確的。是的，使用鎖（互斥/信號/螺旋鎖）來保護寫操作免受需要更新同一段數據的其他寫入器線程/進程的影響。

Answer 9

FWIW，如果你有一個垃圾收集器，這是微不足道的。例如，在F＃中，您可以只使用鏈接列表的可變引用或純功能映射（平衡二叉樹），而不使用任何鎖定。這是可行的，因爲數據結構是不可變的，並且寫入引用（在寫入後更新）是原子的，所以併發的讀者可以保證看到舊的或新的數據結構，但永遠不會損壞。如果你有多個作家，那麼你可以序列化他們。

然而，這是更難在C++解決......

Answer 10

我不知道是否有人已經提到這一點，但我會採取從Java的ConcurrentHashMap的靈感。它提供了無需鎖定或等待的遍歷，檢索和插入。一旦你發現了一個對應於散列鍵的數據桶並且你正在遍歷該桶（即你只鎖定了桶而不是實際的散列圖），就會發生唯一的鎖定。 「ConcurrentHashMap不是使用單個集合鎖，而是使用一個固定的鎖池來形成一個分區來存儲分區集合。」

您可以在實際實施here上找到更多細節。我相信實現中顯示的所有內容都可以用C++輕鬆完成。

所以，讓我們通過你的要求清單：

1. High throughput. CHECK 
2. Thread safe. CHECK 
3. Efficient inserts happen in O(1). CHECK 
4. Efficient removal (with no data races or locks). CHECK 
5. VERY efficient traversal. CHECK 
6. Does not lock or wait. CHECK 
7. Easy on the memory. CHECK 
8. It is scalable (just increase the lock pool). CHECK 

這裏是一個映射條目的例子：

protected static class Entry implements Map.Entry { 
    protected final Object key; 
    protected volatile Object value; 
    protected final int hash; 
    protected final Entry next; 
    ... 
} 

注意，該值是揮發性的，所以當我們移除條目我們將該值設置爲NULL，對於嘗試讀取該值的任何其他線程，該值自動可見。

Answer 11

我對晚會有點遲。但是如果有人仍然在尋找解決這個問題的實際解決方案，並且他們還沒有決定在服務器上，請讓我建議Google's App Engine。他們的數據存儲針對這些類型的需求進行了優化。