并行数据结构设计

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。他们的数据存储针对这些类型的需求进行了优化。