Choose Concurrency-Friendly Data Structures(翻译)

为什么想翻译这篇文章,最近在看disque的代码,里面queue在存储job时用的是skiplist,插入和删除时间复杂度O(lgn),获取job是O(1)。最初的想法是红黑树在插入和删除的情况下也可以达到同样水准,只是弹出job的时候需要维护指向最前面节点的指针。并没有想到什么特殊的理由,用一个全新的数据结构,看了下面的文章,才知道并发性也是选择数据结构的一个考量,特别是在高性能场景。

Choose Concurrency-Friendly Data Structures

链表和平衡搜索树是相似的数据结构,但是它们是否能在并发环境下实现实现性能的飞跃?

什么是高性能的数据结构?为了回答这个问题,我们通常会考虑以下因素:时间复杂度,内存占用情况,局部性,以及遍历顺序。以上的因素在顺序和并发软件中同样使用。

但是在并发代码中,我们需要考虑余外的两个情况,用来帮助我们判定一个数据结构是否是并发友好的:

  • 在并发代码中,性能的提升要求数据结构允许多线程的同时操作。如果你的数据结构应用在一个竞争比较激烈的场景,它是否允许读和写操作不同的部分?如果你的回答是,“不”,那么你可能给你的系统引入了一个瓶颈,需要锁保护的资源会引起线程的等待,同一时间只有一个线程可以使用资源。
  • 在并发硬件之上,你也许还会考虑使内存的同步动作尽量的小。当一个线程更新数据结构的一部分时,为了使更改对于其他线程可见,你需要移动的内存有多少?如果你的回答是“比数据结构表面上的改变要多”那么你又引入了一个潜在的性能杀手,这次是由于内存的复制-数据从发起改变的内核移动到其他读取这个改变的内核。

数据结构是否允许真正意义上的局部更新直接影响以上问题的答案。如果数据结构中的小改变导致了数据结构中其他部分的改变,我们就失去了局部性;其他部分需要被锁定,并且所有改变的内存都需要同步。

为了证明以上观点,让我们考虑两种普遍的数据结构:链表和平衡树。

链表

链表是并发友好的数据结构,因为它支持高度的局部更新。例如图1,像双向链表中插入一个新节点,只需要使用2个已经存在的节点;在这两个节点相邻之处,将新节点拼接进去。删除一个节点,你只需要触摸3个节点:被删除节点和相邻的两个节点。

局部性让我们可以使用适当力度锁:我们可以允许大量的线程操作同一个链表,只要他们操作不同的部分就不会产生冲突。每一个操作只需要锁住自己需要的节点即可。

举个例子,图2说明了hand-over-hand锁。基本的想法是:列表的每个节点都有自己的锁。每个线程都可能从获取第一个节点的锁来开始添加或删除节点,保持第一个锁不变,获取第二个节点的锁,然后释放第一个节点的锁,重复上面的步骤。(当你删除节点的时候,需要同时有3个节点的锁)当遍历链表时,每个线程至少拿着2把锁-并且都是以同样的顺序获取锁。

上面的技术有以下好处:

  • 多个读和写线程可以在同一个列表上工作。
  • 读者和写者以同样的顺序遍历列表,不会超越彼此。 在并发模式下,这样的策略会达到确定的结构。特别是,如果每个线程要求完全的互斥并且在隔离的情况下操作列表。
  • 对于部分列表锁的竞争不会导致死锁,因为锁的获取是相同顺序的。
  • 我们可以容易的调整锁的力度来达到更好的并发性能:一个列表锁(无并发),每个节点一个锁(最大的并发性),或者块锁。

此外:如果我们一直以同样的顺序遍历链表,为什么途中展示的是双向链表?因为不是所有的操作都需要拿多个锁;那些只需要获取一个单位锁的操作可以以任意的顺序竞争锁资源,并且不会引起死锁。

除了并发情况下的遍历和更新之外,链表在并发硬件之上也有较好的缓存友好特性。例如,当一个线程移除一个节点,为了应对其他内核接下来的度操作,只需要传输2个相邻节点即可。如果链表的剩余部分没有改变,多个内核会非常开心的存储列表到他们的缓存中,这样不用就去除掉了大量的内存获取与同步。(记住,写总是比读更加的昂贵,因为写需要被广播。当然,“大量的写”总是比“有限的写”昂贵)

比较明确的是,链表享有的一个好处是-它是节点的容器:没有元素存储在它自己的节点中。不像是数组或向量。当你插入或删除元素时会导致大量节点的移动。我们也许预测所有的节点容器都有良好的并发性。不幸的是,这是错的。

平衡搜索树

这个比较流行的数据结构在并发上的表现并不好。(重要提示:这个部分说的仅是平衡树,非平衡树因为支持局部更新,所以并不会有下面说到的问题)

考虑红黑树:通过标记节点为“红”或者“黑”来保持平衡,并且在每次插入或删除操作之后可以进行平衡操作,用来防止分支之间不平衡。尤其是,平衡操作通过旋转子树来达到目的,主要参与的节点可能包括插入或者删除节点的父亲或者叔叔节点甚至直到根节点。

例如,考虑图3。树包含3个节点值分别是1、2、3。插入值4,作为3的孩子,并没有打破结构上的平衡,但是我们仍旧需要把3和1标记为黑色。这个会损失并发性;例如插入4会与插入1.5冲突,因为都需要修改节点1和3。

下一个,插入值5,我们需要操作除了1之外的所有节点:首先插入4的右孩子,然后修改4和3的颜色,然后因为树失去了平衡我们需要旋转3-4-5,把4作为根节点,这也意味着需要用到2,把4作为其右孩子。

所以红黑树在导致并发代码有一些问题:

  • 更新操作很难达到真正的并发,因为更新任意离得远的节点可能需要操作相同的节点-尤其是根节点,其他的高level节点也右可能。所以我们会失去只进行局部操作的特性。
  • 树会发起内部的一些小操作-为了维护平衡。这会增加写和同步的次数。

“但是等等,”我听到有些人说,“为什么我们不能给每个节点分配锁,并按照同样的方向去竞争锁?这样做会至少给树带来并发的能力吗?”简短的回答:容易做,但是做对很难。不像是链表:你可能需要竞争特别多的锁,甚至是通向根节点的所有路径;结果高level的节点会变成竞争激烈的资源,成为瓶颈所在。而且,实现这件事的代码非常复杂。像Fraser在2004年提到:”一个比较有吸引力的做法是向下遍历申请读锁,返回时用写锁,只要需要rebalancing。这个策略可以在最小数量的节点上得到互斥操作,但是会导致死锁“。他也提供了一个锁的粒度比较好的技术,允许树提供一定程度的并发,但是注意”会非常复杂“。其实有容易解决办法,但是几乎没有容易且正确的答案。

为了避开这些限制,研究人员开发出了一个替代的数据结构-skiplist,作为红黑树的变体更加适用于并发场景,不需要像红黑树每次更新完有可能需要理解rebalancing。可以在认为需要的时候做这个操作。一些实现很复杂,导致性能损失,并且可维护性差。想要获取更多的信息和对比测试结果,查看文档The Performance of Concurrent Red-Black Tree Algorithms

结论

并发友好不能独立于其他性能指标。当我们写算法时不能只因为它并发友好就采用它;你需要选择适应你所有性能需求的那一个。链表也许比平衡树在并发情况下更好,但是树的搜索速度更快。

记住:

  • 并发代码,性能的提升可能需要允许多线程同时访问同样的数据。
  • 并发硬件,需要考虑尽量减少内存的同步。

在上面的情况,我们可能需要采用并发友好的数据结构。一个容器越能支持局部性,并发性就会越好,同时也会避免更多的内不能复制。

Choose Concurrency-Friendly Data Structures(翻译)
Share this