Harris’s Linked List

原文地址 作者：Pedro Ramalhete，译者：叶磊，校对：周可人

在学术论文中Harris Linked List是使用最广泛的并发数据结构之一。

Harris Linked List是一个基于linked-list的并发有序set（或者是map），可进行无锁性质的插入，删除和查找操作。

http://research.microsoft.com/pubs/67089/2001-disc.pdf

这篇文章最早在2001年的DISC会议上发表，作者是Tim Harris，目前在Oracle就职。

https://labs.oracle.com/pls/apex/f?p=labs:bio:0:296

除非你阅读并发方面的学术论文，否则你很可能不知道这个数据结构是什么。主要原因是，虽然它是最快，最简单的并发list-based-set，但是在我看来，却是最不切实际的。

链表中的每个节点引用一个键值，节点的相对位置反映出它们所包含的键值在链表中的相对顺序。在链表中，总是有两个特殊的节点（永远不会被删除），一个是列表的开始，head，另一个是列表的表尾，tail。

Harris’s linked list就像一种中国的益智类玩具，即那种你可以玩一会儿，并且凑巧地解决了；但是当你重置它以后，你又需要几个小时来再次解决它。Harris’s linked list并不只包含一个技巧，而是有很多种技巧。

Harris’s linked list的技巧之一是设置指向下个节点的指针中的一位（one bit），将它标记为逻辑删除。这就是问题所在。

自动管理内存的语言（Java, Scala, C#）是不能直接访问一个指针中的一位的，并且很可能永远都不行。

一种可能的实现是使用AtomicMarkableReference或者相近的技术，每当执行一次CAS时创建一个新的对象。新对象包含一个下一个节点的引用，和一个bit标志位，它们都需要被定义为final类型。这样的对象常量创建行为（译者注：严格地来说这样翻译并不对，final类型并不意味着constant variable）意味着在Java中实现这种技术（非常）慢。

在Java中，另一种可能的实现是使用运行时类型信息（RTTI）并创建的一种Harris算法的变体，使用RTTI来确定对象每个节点的类型，如MarkedNode或UnMarkedNode，在运行时，替换对象来表示标记/取消标记。这种技术导致了一个新的问题，因为在现实中，会存在大量的交织的逻辑链表，而解释这样的链表是非常困难的，但它的确比java.util.concurrent中AtomicMarkableReference的处理方式更快。

我们现在有了两种技术实现，接下来将要讨论一下他们的未来发展。

使用非自动管理内存的语言（如C、C++,等等）可以直接访问指针，但是这里有一个问题是在自动内存管的语言中不存在的——内存管理。

在Java中，我们不需要担心内存清理，因为JVM垃圾收集器负责清理未使用的节点，但在C/C++并没有这样的特性。我在这里不是谈论ABA的问题，Harris linked-list算法考虑到了这个问题，其解决方案是：一旦一个节点“标记”为删除，它就永远不可能变成“未标记”，如果相同键值要被插入到链表中，那么必须创建一个新节点。

http://en.wikipedia.org/wiki/ABA_problem

现在有一些语言，比如D，允许在特定的指针上使用GC，但他们不支持在这些指针上的位操作，所以还是有相同的问题。

http://dlang.org/garbage.html

若使用非自动管理内存的语言，能安全实现Harris linked-list的唯一方法是使用lock-free内存管理技术，如”Hazard Pointers”，或 “Pass the Buck”，或”Drop the Anchor”。

http://researchweb.watson.ibm.com/people/m/michael/ieeetpds-2004.pdf
http://secs.ceas.uc.edu/~paw/classes/ece975/sp2010/papers/herlihy-05.pdf
http://www.cs.technion.ac.il/~sakogan/papers/spaa13.pdf

到目前为止的问题是，我还没有看到任何正确使用Hazard Pointers实现的Harris linked-list。即使有人写出了一个较好的实现，它也不会太快，因为做一个简单的遍历列表需要两个全局可见的存储指令和至少每个节点上的屏障释放….是的，它将是缓慢的。也许“Drop the Anchor”技术将提供足够的性能，但我还没有发现任何优秀或差劲的代码，所以目前的实现都是关于Hazard Pointers的。即便如此，如果有人知道使用Hazard Pointers或其他技术较好地实现了Harris linked-list，我想看看，所以请在评论栏中添加链接吧！

总之，如果你想使用自动管理内存的语言实现Harris linked-list，你必须使用怪异的技巧，如AtomicMarkableReference或RTTI，这将极大地影响算法的性能，甚至极大改变算法的工作方式。如果你想使用非自动管理内存的语言实现Harris linked-list，那么你需要一个内存管理技术，这也将影响性能，并且内存管理技术的实现非常重要，而不是说非常困难。

我看过一些研究论文，使用C/C++实现越过了这个障碍，并且简单地跳过了内存管理（译者注：根据本人看过的论文而言，的确是这样，在很多Memory Management Section，通常只是提到了上述的Hazard Pointer技术可以实现，然而就简单跳过）。他们只是有很多的内存，在内存填满之前停止他们的微基准测试。这是种欺骗，但我理解他们，因为最终他们试图将Harris链表与其他算法比较，如Sets和Maps的算法，而不是那些使用内存管理技术的算法，然而有时我真的怀疑这些基准测试的真实性和可用性。

不管怎样，这就是为什么Harris linked-list不那么受软件工程师和研究人员欢迎，以及java.util.concurrent为什么没有实现的原因。