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

Question

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

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

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

不可以使用读/写锁并将写操作推迟到所有读者都完成后，因为读操作可能会持续很长时间。有读者时发生的插入是否对该读者可见并不重要。

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

有什么建议？

对评论的回应:

感谢您的回答。

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

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

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

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

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

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

Answer 1

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

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

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

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