并发数据结构-1.7 查找树

原文链接，译文链接，译者：iDestiny，校对：周可人

任何查找树的并发实现都可以通过用一个独占锁保护来完成。通过使用读写锁对并发性能有一定提升，读写锁允许所有只读（查找）操作并发地执行，因为读操作是以共享模式持有锁，然而更新（插入或删除）操作持有独占模式的锁，从而排斥其他所有操作。如果更新操作比较少，这还能接受，但是只要有适量的更新操作，那么更新操作所持有的独占锁将产生线性的瓶颈，从而大大降低性能。通过使用细粒度的锁策略——比如每个节点一个锁，而不是整棵树使用同一个锁——这样我们进一步地提升了并发性能。

Kung和Lehman介绍了一种并发二分查找树的实现：更新操作每次只拥有固定数量的节点锁，并且这些锁只排斥其他的更新操作，查询操作从不会被阻塞。但是这种实现并没有试图保持查找树平衡。在本节的其他部分，我们会关注平衡的查找树，这将更具有挑战性。

作为迈向实现更细粒度的同步平衡查找树的第一步，我们可以注意到，让一个引起任何修改的操作持有子树的独占锁是可行的。这样一来，修改操作可以并行地在不相交的子树上被执行。在B+树的背景下，我们简要描述一些技术。回想B+树，所有的关键字和数据被存储在叶子节点；内部节点只维护路由信息，从而将更新操作引导至对应的叶子节点，而且，插入到叶子可能需要拆分叶子，反过来一个新的条目需要被添加到叶子节点的父亲节点中，它(父亲节点)自己可能也需要被拆分来适应新的条目。因此，一个插入操作可能导致修改从根到叶子的所有节点。然而这种行为是很少见的，所以使用完全独占锁住整个路径来防止这种情况，是没有意义的。

作为避免那种传统的锁策略的第一步，我们可以注意到，如果一个插入操作经过了一个不完全的内部B+树节点，然后修改它，那么其后的调整超越将不会越过这个节点（译者注：即不会调整这个节点之上的节点）。在这种情况下，我们就说该节点的插入操作是安全的。当一个更新操作在树中自上而下遍历每个节点并锁住每一个遍历过的节点时遇到一个安全节点，它能够安全地释放所有该节点的祖先上的锁，因此，通过允许其他操作遍历那些节点来提高了并发性。由于查找操作不会修改树，能够沿着树向下用lock coupling的策略（交接锁），只要在子节点的锁已经被获取到，在其父亲上的锁就能够被释放。因此，查找操作在任何时候最多持有2个锁（共享模式下）， 因而很少阻碍其他操作的执行。

这种方式仍然要求每个更新操作要获取根节点的独占锁，且在读取子节点时要持有锁，子节点可能从磁盘读取，所以根仍然是一个瓶颈。通过注意到大多数更新操作不将需要拆分或合并他们访问过的节点，因此最终将释放到叶子节点路径上遍历的所有节点上的独占锁。这个现象启示了一个“乐观的”方法，我们可以在共享模式下沿着树向下获取到那些锁，仅独占叶子节点锁。如果叶子节点没有必要拆分或合并，更新操作可以立即完成；在很少情况下，调整需要沿着树向上传播，我们可以释放所有的锁，然后重新尝试上面描述的更悲观的做法。作为其中一种选择，我们可以用读写锁来允许共享模式持有的锁被”升级”到独占模式。这种方式，如果更新操作发现确实需要修改叶子节点以外的节点，它就可以将共享模式占有的锁升级为独占模式，并且避免完全从树根重新开始操作。上面的技术的各种组合都是可用的，因为树根附近的节点更有可能和其他操作产生但更少可能被修改，而叶子附近的节点则相反。

当我们使用上面描述的更复杂的技术时，算法也会变得更复杂，并且很难避免死锁，导致进一步复杂化。虽然如此，所有这些技术保持了操作独占锁他们修改的子树的不变性，所以操作不会碰到他们在顺序执行中没有碰到的状态。通过放宽这一要求，并发性和性能会得到显著改善，代价是使得推论算法正确性会更困难。

当我们尝试放宽严格的子树锁定方案时，我们遇到的关键难点是当一个操作跟随指向子节点的指针沿着树向下，该子节点由于并发操作的修改不再是正确子节点了。很多现在的技术已经允许操作从这种”混乱”中恢复，而不是完全避免它。

在B+树背景下的一个重要的例子是Lehman和Yao，他们定义了B(link)树:：即B+树中每个节点都带有指向同一级别上的右邻居的链接。这些链接让我们将对一个节点的分裂和对其父亲节点做调整来分裂分离开来。具体的，为了拆分一个节点n，我们可以创建一个新的节点n’到它的右边，并且加上一个n到n’的链接。如果一个操作由于查找关键字位置，沿着树向下到达节点n，现在关键字位置由于拆分而被节点n’覆盖，操作可以简单地从n到n‘的链接中恢复。这允许一个节点被拆分时，不会阻止并发操作访问节点的父亲节点。因此，更新操作不必在修改时锁住整个子树。实际上，在Lehman-Yao算法中，更新操作和查找操作使用交接锁技术以便于没有操作可以一次持有2个以上的锁，这极大提高了并发性。该技术已经被进一步提炼，以至没有操作可以一次可以持有1个以上的锁。

Lehman和Yao没有解决如何合并节点，而是允许删除操作时节点数未满(译者注：在传统的B+树中，删除操作需要合并条目数未达到要求的节点)。他们提出在多数情况下删除操作很少见，并且如果空间利用率成为问题，树可以偶尔在“批处理”模式下，通过独占锁锁住整个树而被重组。Lanin和Shasha将合并操作并入删除操作，类似于之前实现中，插入操作拆分溢出的节点的方式。类似于Lehman-Yao的链接技术，这些实现用链接让由于节点合并而到达一个空节点的错误操作得以恢复。

在所有上面讨论的算法中，维护操作如节点拆分和合并都作为执行常规更新操作的一部分。没有维护操作和常规操作之间的紧耦合，我们就不能保证严格的平衡属性。然而，如果我们放宽平衡需求，我们可以将树的维护操作从更新操作中分离出来，这样带来很多优势，比需要保持查找树严格平衡更有价值。比如说，B-link树在实现压缩过程中和常规操作并发执行来合并不足的节点。通过从常规操作中分离这些工作，它可以在不同处理器或在后台的线程并发执行。

从常规的树操作中分离再平衡的想法首先被建议使用在红黑树上，并且首先在AVL树中实现来支持插入和查询操作。这些实现通过将平衡分解得更小，局部的树调整可以独立完成来改善并发性。分析表明通过做一些调整，该方案保证对于一棵N个节点的树，每一个更新操作最多引起O(llogN)次再平衡操作。类似的结论对于B-trees和红黑树也是这样。

唯一的非阻塞的平衡查找树实现已经用动态软件事务内存机制完成（译者注：最近有了新的实现技术，见PODC2014和PPOPP2014）。这些实现使用那些将平衡操作作为常规操作一部分的顺序代码转换而来的事务来完成。

上面简短的调研只涉及到有关实现并发查找树的基本问题和技术。再提一些很多改进和扩展的知识中的一小部分，[105]提出了在数据库产品中用B+树解决实际问题，比如失败后恢复；[75]提出用广义搜索树(GiSTs)的并发实现来方便实现没有精巧的并发控制的查找树的设计，并提出几种支持高效插入和删除一组值的树。Pugh提出了它的skiplist随机查找结构的一个并发版本。在skiplist中的期望查找时间与其元素个数是对数关系。skiplists主要的优势时它们不要求再平衡：插入操作在一个随机并且可保持查找树平衡的方式中被完成。

并发查找树和其他数据结构的实验和分析的评估在[41, 67]中可以找到。