并发数据结构设计

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

要求是它能够支持高效的插入（最好是 O(1)）、中等效率的删除和高效的遍历。它不需要支持查找操作（删除可能需要的除外）。

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

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

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

有哪些建议？

对评论的回应：

感谢您的回答。

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

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

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

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

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

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

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

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

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

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