锁定自由双链跳跃列表
关于无锁双链表有大量的研究。同样，对于无锁跳过列表也有大量的研究。然而，据我所知，没有人管理过无锁的双向链接跳跃列表。有谁知道有任何相反的研究，或者这种情况的原因吗？
编辑： 具体场景是构建快速分位数（50%、75% 等）累加器。样本会在 O(log n) 时间内插入到跳跃列表中。通过维护一个到当前分位数的迭代器，我们可以在 O(1) 时间内将插入的值与当前分位数进行比较，并且可以轻松判断插入的值是在分位数的左边还是右边，以及与分位数相差多少结果需要移动。这是需要前一个指针的左移动。
据我了解，任何困难都来自于在多个线程同时插入和删除时保持先前的指针一致。我想解决方案几乎肯定会涉及到指针标记的巧妙使用。
There exists tons of research on lock-free doubly linked list. Likewise, there is tons of reserach on lock-free skip lists. As best I can tell, however, nobody has managed a lock free doubly linked skip list. Does anybody know of any research to the contrary, or a reason why this is the case?
Edit:
The specific scenario is for building a fast quantile (50%, 75%, etc) accumulator. Samples are inserted into the skip list in O(log n) time. By maintaining an iterator to the current quantile, we can compare the inserted value to the current quantile in O(1) time, and can easily determine whether the inserted value is to the left or right of the quantile, and by how much the quantile needs to move as a result. It's the left move that requires a previous pointer.
As I understand it, any difficulty will come from keeping the previous pointers consistent in the face of multiple threads inserting and removing at once. I imagine the solution will almost certainly involve a clever use of pointer marking.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
但你为什么要做这样的事呢？我实际上还没有坐下来弄清楚跳过列表的工作原理，但从我模糊的理解来看，你永远不会使用以前的指针。那么为什么要承担维护它们的开销呢？
但如果你愿意，我不明白为什么你不能。只需将单链表替换为双向链表即可。双向链表逻辑上是连贯的，所以都是一样的。
But why would you do such a thing? I've not actually sat down and worked out exacty how skip lists work, but from my vague understanding, you'd never use the previous pointers. So why have the overhead of maintaining them?
But if you wanted to, I don't see why you cannot. Just replace the singly linked list with a doubly linked list. The doubly linked list is logically coherent, so it's all the same.
我有一个主意给你。我们使用“光标”来查找跳跃列表中的项目。光标还保留到达该项目的轨迹。我们使用此跟踪进行删除和插入 - 它避免了第二次搜索来执行这些操作，并且它嵌入了遍历时看到的列表的版本号。我想知道您是否可以使用光标更快地找到上一项。
您必须将光标向上移动一个级别，然后搜索仅比您的项目少一点的项目。或者，如果搜索到达了链表的最低级别，则只需在遍历时保存上一个 ptr 即可。最低级别可能有 50% 的时间用于查找您的项目，因此性能会不错。
嗯...现在想想，好像光标有50%的时间有prev ptr，25%的时间需要从1级向上重新搜索，12.%2级向上，等等。所以在在极少数情况下，您几乎必须重新进行搜索。
我认为这样做的好处是，您不必弄清楚如何“无锁”维护双链接的跳过列表，并且在大多数情况下，您可以大大降低定位前一项的成本。
I have an idea for you. We use a "cursor" to find the item in a skiplist. The cursor also maintains the trail that was taken to get to the item. We use this trail for delete and insert - it avoids a second search to perform those operations, and it embeds the version # of the list that was seen when the traversal was made. I am wondering if you could use the cursor to more quickly find the previous item.
You would have to go up a level on the cursor and then search for the item that is just barely less than your item. Alternatively, if the search made it to the lowest level of the linked list, just save the prev ptr as you traverse. The lowest level is probably used 50% of the time to find your item, so performance would be decent.
Hmm... thinking about it now, it seems that the cursor would 50% of the time have the prev ptr, 25% of the time need to search again from 1 level up, 12.% 2 levels up, etc. So in infrequent cases, you have to almost do the search entirely again.
I think the advantage to this would be that you don't have to figure out how to "lock free" maintain a double linked skip list, and for the majority of cases you dramatically decrease the cost of locating the previous item.
作为维护反向链接的替代方法，当需要更新分位数时，您可以进行另一次搜索以查找键小于当前键的节点。正如我刚刚在 johnnycrash 的评论中提到的，可以构建在每个级别找到的最右边节点的数组 - 并由此可以加速第二次搜索。 （福米切夫的论文提到这是一种可能的优化。）
As an alternative to maintaining backlinks, when a quantile needs to be updated, you could do another search to find the node whose key is less than the current one. As I also just mentioned in a comment to johnnycrash, it's possible to build an array of the rightmost node found at each level -- and from that it would be possible to accelerate the second search. (Fomitchev's thesis mentions this as a possible optimization.)