c++ - 并发数据结构设计

Question

我正在尝试提出用于高吞吐量 C++ 服务器的最佳数据结构。该数据结构将用于存储从几到几百万个对象的任何内容，并且不需要排序（尽管可以非常便宜地提供唯一的排序键）。

要求是它可以支持高效的插入，理想情况下为 O(1)，中等效率的移除和高效的遍历。它不需要支持查找操作（除了可能需要删除）。

扭曲是它必须是线程安全的，而其他线程正在枚举数据结构。这意味着简单的红黑树不起作用，因为一个线程无法插入元素（并执行必要的树旋转）而不会弄乱其他线程持有的任何游标。

使用读/写锁并将写操作推迟到所有读者都完成是不可接受的，因为读操作可能会长期存在。有读者时发生的插入是否对该读者可见并不重要。

内存占用也很重要，当然越小越好！

有什么建议？

回复评论：

感谢您的回答。

不，插入不能使现有的迭代器无效。迭代器可能会或可能不会看到新的插入，但他们必须看到如果插入没有发生，他们会看到的所有内容。

需要删除，但是由于更高级别的规则，我可以保证迭代器永远不会在可删除的项目上停止。

为游标锁定每个节点会对性能产生太大影响。可能有多个线程同时读取，并且多个线程在锁中使用的任何类型的内存热点都会杀死内存带宽（正如我们发现的那样困难！）。即使是具有多个调用 InterlockedIncrement 的线程的读取器的简单计数也无法干净地扩展。

我同意链接列表可能是最好的方法。删除很少见，因此为支持 O(1) 删除的反向指针支付内存代价是昂贵的，我们可以根据需要单独计算这些，因为删除往往是批处理操作。

幸运的是，插入到链表中不需要对读取器进行任何锁定，只要在更改头指针之前在插入的节点中更新指针即可。

锁定-复制-解锁的想法很有趣。所涉及的数据量太大，无法将其用作读取器的默认设置，但是当写入器与读取器发生冲突时，它可以用于写入器。读/写锁将保护整个结构，如果与读取器发生冲突，写入将克隆数据结构。写入比读取少得多。

score 12 · Accepted Answer

就个人而言，我非常喜欢在高度并发的情况下持久不变的数据结构。我不知道有什么专门针对 C++ 的，但是 Rich Hickey 在 Java 中为Clojure创建了一些出色的（而且速度极快）不可变数据结构。具体来说：vector、hashtable和hashset。它们并不难移植，因此您可能需要考虑其中之一。

更详细地说，持久的不可变数据结构确实解决了很多与并发相关的问题。因为数据结构本身是不可变的，所以多个线程同时读取/迭代没有问题（只要它是一个 const 迭代器）。“写入”也可以是异步的，因为它并不是真正写入现有结构，而是创建包含新元素的结构的新版本。由于您实际上并没有复制所有内容，因此该操作变得高效（在所有 Hickey 结构中为O(1)）。每个新版本都与旧版本共享大部分结构。这使事情的内存效率更高，并且比简单的写时复制技术显着提高了性能。

对于不可变数据结构，您真正需要同步的唯一时间是实际写入参考单元格。由于内存访问是原子的，即使这样通常也可以是无锁的。唯一需要注意的是，您可能会在线程之间丢失数据（竞争条件）。数据结构永远不会因并发而损坏，但这并不意味着在两个线程基于单个旧线程创建结构的新版本并尝试写入其结果（其中一个线程将“赢”，其他人的更改将丢失）。要解决这个问题，你要么需要一个“写操作”的锁，要么使用某种STM. 我喜欢在低冲突系统中实现易用性和吞吐量的第二种方法（理想情况下，写入是非阻塞的，读取永远不会阻塞），但任何一种都可以。

你问了一个棘手的问题，这个问题并没有很好的答案。并发安全的数据结构很难编写，尤其是当它们需要可变时。在存在共享状态的情况下，完全无锁的架构被证明是不可能的，因此您可能希望放弃该要求。您能做的最好的事情就是尽量减少所需的锁定，从而减少不可变的数据结构。

score 6 · Accepted Answer

链表绝对是这里的答案。O(1) 中的插入和删除，O(1) 中从一个节点到下一个节点的迭代以及跨操作的稳定性。std::list保证所有这些，包括所有迭代器都是有效的，除非从列表中删除元素（这包括指针和对元素的引用）。对于锁定，您可以将列表包装在锁定类中，或者您可以编写自己的列表类（您将无法使用std::list在这种情况下，它支持基于节点的锁定——例如，您可以锁定列表的某些区域以供使用，而其他线程在不同区域执行操作。您使用哪个在很大程度上取决于您期望的并发访问类型 - 如果列表不同部分的多个操作真的很常见，请编写您自己的，但请记住您将在每个节点中放置一个互斥对象，这不是节省空间。

score 4 · Accepted Answer

为双重答案道歉...

由于写入相当罕见，因此您确实应该考虑使用 STM 而不是锁定。STM 是一种乐观锁定形式，这意味着它在性能上严重偏向无冲突系统（也就是更少的写入）。相比之下，悲观锁定（lock-write-unlock）针对冲突严重的系统（也就是大量写入）进行了优化。STM 的唯一问题是它几乎要求您在 TVar 单元中使用不可变的数据结构，否则整个系统就会崩溃。就个人而言，我不认为这是一个问题，因为体面的不可变数据结构将与可变数据结构一样快（请参阅我的另一个答案），但值得考虑。

score 1 · Accepted Answer

我认为链表应该可以满足您的要求。请注意，您只能锁定正在更改（即删除/附加）的节点，因此大部分时间读者将能够与作者完全并行工作。这种方法需要每个链表节点锁定，但这不是必须的。您可以拥有有限数量的锁，然后几个节点将映射到同一个锁。即，拥有 N 个锁和编号为 0..M 的节点的数组，您可以使用锁 (NodeId % N) 来锁定该节点。这些可以是读写锁，通过控制锁的数量，您可以控制并行度。

score 1 · Accepted Answer

如果您不需要排序顺序，请不要使用红/黑树或其他任何固有排序的东西。

你的问题没有很好地说明读写之间的交互。如果通过锁定+复制+解锁实现“读取”然后使用新副本可以吗？

您可能想在http://en.wikipedia.org/wiki/Seqlock中阅读有关 seqlock 的信息，以及一般的“无锁”流程——不过，您可能希望尽可能放宽您的要求——锁-free 哈希表实现是一项重大任务。

score 1 · Accepted Answer

您有 3 种类型的任务：

迭代（慢）
插入（快速）
删除（快速）

如果接近一致性足够好，则跟踪活动迭代任务的数量。

如果迭代任务处于活动状态并且新的插入或删除任务进入队列，这些任务供以后处理（但您可以立即将其返回给调用者）

如果完成进程排队插入和删除，则只要最后一次迭代。

如果在插入或删除待处理时出现迭代请求，则将其排队。

如果一个迭代请求进来，而只有迭代正在运行，那就让它去迭代。

您仍然应该通过制作您正在迭代的数据的副本来尽可能快地编写迭代，然后如果实际数据处理比迭代本身花费更多时间，则在客户端中处理该数据。

我会用哈希表或 stl:map 实现主集合，甚至可能足够快。插入/删除请求可以在列表中排队。

score 1 · Accepted Answer

我认为这是可以实现的唯一方法是通过类似于 oracle/postgresql 等数据库中使用的多版本并发协议的东西。这保证了读者不会阻塞读者，作家不会阻塞读者，但作家只会阻止那些作家更新同一条数据。写入者阻止更新相同数据的写入者的这种属性在并发编程世界中很重要，否则数据/系统不一致是可能的。对于数据结构的每一个写操作，在执行写操作之前，您都会对数据结构进行快照，或者至少将受写操作影响的部分数据结构节点复制到内存中的不同位置。因此，当写入正在进行时，读取器线程请求从写入器部分读取部分数据，您总是参考最新的快照并迭代该快照，从而为所有读者提供一致的数据视图。快照的成本很高，因为它们消耗更多内存，但是对于您的给定要求，这种技术是正确的选择。是的，使用锁（互斥锁/信号量/自旋锁）来保护写操作免受其他需要更新同一条数据的写入器线程/进程的影响。

score 1 · Accepted Answer

我不确定是否有人提到过这一点，但我会从 Java 的 ConcurrentHashMap 中获得灵感。它提供遍历、检索和插入，无需锁定或等待。一旦您找到与哈希键对应的数据桶并且您正在遍历该桶（即您只锁定桶而不是实际的哈希映射），就会发生唯一的锁定。“ConcurrentHashMap 不是使用单个集合锁，而是使用固定的锁池，在桶集合上形成分区。”

您可以在此处找到有关实际实施的更多详细信息。我相信实现中显示的所有内容都可以使用 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，这对任何其他尝试读取该值的线程都是自动可见的。

score 0 · Accepted Answer

好吧，为了线程安全，您将不得不在某个时候锁定某些东西。一个关键的事情是确保您的存储库中的对象可以与存储库结构本身分开锁定：即在您存储的数据中没有_next 链接或任何类似的东西。这种方式读取操作可以锁定对象的内容，而不锁定存储库的结构。

高效的插入很容易：链表、未排序的数组、哈希表都可以正常工作。有效的删除更难，因为这涉及在存储库中查找已删除的内容。然而，为了原始的简单性和速度，链表是一个不错的选择。可以在非忙碌时间和仅标记为“非活动”的项目中推迟删除吗？那么查找/删除的成本就不那么有限了。

但是，您仍然会遇到遍历问题。您所能做的就是锁定并拍摄需要遍历的内容的快照，然后在查看快照后检查是否有任何更改。棘手的问题...

score 0 · Accepted Answer

FWIW，如果您有垃圾收集器，这很容易解决。例如，在 F# 中，您可以只使用对链表或纯函数映射（平衡二叉树）的可变引用，而无需任何锁。这是有效的，因为数据结构是不可变的，并且写入引用（在写入后更新）是原子的，因此并发读者可以保证看到旧的或新的数据结构，但不会损坏。如果您有多个作家，那么您可以将它们序列化。

然而，这在 C++ 中更难解决......

score -1 · Accepted Answer

我参加聚会有点晚了。但是，如果有人仍在寻找解决此问题的实用解决方案，并且他们还没有决定使用服务器，那么我建议使用Google 的 App Engine。他们的数据存储针对这些类型的要求进行了优化。

c++ - 并发数据结构设计

11 回答 11

Related

Reference