并行数据结构设计

就我个人而言,我非常喜欢在高度并发的情况下使用持久的不可变数据结构。我不知道有什么是专门针对C++的,但Rich Hickey在Java中为 Clojure 具体来说:向量、哈希表和哈希集。它们不太难移植,所以你可能想考虑其中之一。

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

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

你问了一个很难回答的问题。并发安全数据结构很难编写,特别是当它们需要可变时。在共享状态存在的情况下,完全无锁的架构是不可能的,所以你可能想放弃这一要求。你能做的最好的事情就是尽量减少所需的锁定,从而减少不可变的数据结构。

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

对于双重回答,我深表歉意。..

由于写作相当罕见,你 真正地 应该考虑使用STM而不是锁定。STM是一种乐观锁定形式,这意味着它在性能上严重偏向于无冲突系统(即更少的写入)。相比之下,悲观锁定(锁-写-解锁)针对冲突严重的系统(即大量写入)进行了优化。STM的唯一问题是,它几乎要求你在TVar单元中使用不可变的数据结构,否则整个系统就会崩溃。就我个人而言,我不认为这是一个问题,因为一个体面的不可变数据结构和可变数据结构一样快(见我的另一个答案),但值得考虑。

我认为链表应该能满足你的要求。请注意,您只能锁定正在更改(即删除/附加)的节点,这样读取器在大多数情况下都能与写入器完全并行工作。 这种方法要求每个链表节点都有一个锁,但这不是必须的。您可以使用有限数量的锁,然后几个节点将映射到同一个锁。即,拥有N个锁和编号为0..M的节点数组,您可以使用锁(NodeId%N)锁定此节点。这些锁可以是读写锁,通过控制锁的数量,可以控制并行度。

如果你不需要排序顺序,不要使用红/黑树或其他任何固有的排序方式。

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

你可能想在 http://en.wikipedia.org/wiki/Seqlock ,在一般的“无锁”进程中——不过,您可能希望尽可能放宽要求——实现无锁哈希表是一项艰巨的任务。

您有三种类型的任务:

1. 迭代(缓慢)
2. 插入(快速)
3. 删除(快速)

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

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

一旦最后一次迭代完成,进程就会排队插入和删除。

如果在插入或删除等待处理时收到迭代请求,则将其排队。

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

如果实际的数据处理比迭代本身花费更多的时间,你仍然应该通过复制你正在迭代的数据来尽可能快地编写迭代,然后在客户端处理这些数据。

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

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

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

您可以找到有关实际实施的更多详细信息 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,这对任何其他试图读取该值的线程都是自动可见的。

好吧,为了线程安全,你必须在某个时候锁定一些东西。一个关键是要确保存储库中的对象可以与存储库结构本身分开锁定:即,在您存储的数据中没有_next链接或任何类似的东西。这样,读取操作可以锁定对象的内容,而不会锁定存储库的结构。

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

不过,遍历仍然会有问题。你所能做的就是锁定并拍摄需要遍历的内容的快照,然后在查看快照后检查是否有任何更改。这是一个棘手的问题。..

FWW,如果你有一个垃圾收集器,解决这个问题很简单。例如,在F#中,你可以只使用对链表或纯函数映射(平衡二叉树)的可变引用,而不使用任何锁。这是有效的,因为数据结构是不可变的,写入引用(在写入后更新)是原子性的,因此并发读取器可以保证看到旧的或新的数据结构,但永远不会损坏。如果你有多个作者,那么你可以对它们进行序列化。

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

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