并发数据结构设计

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

要求是它可以支持有效的插入,理想的是O(1),适度有效的移除和有效的遍历.它不需要支持查找操作(除了可能需要删除).

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

这是不接受使用读/写锁和推迟写操作,直到所有的读者已经完成,因为读操作可以长期居住.如果有读取器发生的插入对于该读取器是否可见则无关紧要.

内存占用也非常重要,小的显然更好!

有什么建议吗？

回复评论:

谢谢你的回答.

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

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

锁定游标的每个节点会对性能产生太大影响.可能有多个线程同时读取,并且多个线程在锁中使用的任何类型的内存热点都会占用内存带宽(因为我们发现了很难的方法!).即使是一个简单的多线程调用InterlockedIncrement的读者也无法完全扩展.

我同意链表可能是最好的方法.删除是罕见的,因此支持后向指针支持O(1)删除的内存代价是昂贵的,我们可以根据需要单独计算它们,因为删除往往是批处理操作.

幸运的是,只要在更改头指针之前在插入的节点中更新指针,插入到链表中就不需要对读者进行任何锁定.

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

就个人而言,我非常喜欢在高度并发的情况下持久不可变的数据结构.我不知道C++的具体内容,但Rich Hickey已经用Java为Clojure创建了一些优秀的(并且速度极快)不可变的数据结构.具体来说:vector,hashtable和hashset.它们不太难移植,因此您可能需要考虑其中之一.

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

使用不可变数据结构,实际需要同步的唯一时间是实际写入引用单元.由于内存访问是原子的,即使这通常也是无锁的.这里唯一需要注意的是你可能会丢失线程之间的数据(竞争条件).由于并发性,数据结构永远不会被破坏,但这并不意味着在两个线程基于一个旧版本创建结构的新版本并尝试编写其结果的情况下,不可能出现不一致的结果(其中一个将会"胜利",其他的变化将会丢失).要解决此问题,您需要锁定"写入操作",或使用某种STM.我喜欢低冲突系统中易用性和吞吐量的第二种方法(写入理想情况下是非阻塞的,读取永远不会阻塞),但任何一种都可以工作.

你问过一个棘手的问题,其中一个问题并不是很好.并发安全的数据结构很难编写,特别是当它们需要是可变的时.在共享状态存在的情况下,完全无锁的架构是不可能的,因此您可能希望放弃该要求.您可以做的最好是最小化所需的锁定,因此不可变的数据结构.

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