为可索引并发跳过列表实现交换方法(Implementing a swap method for an indexable concurrent skip list)

 我正在实现一个基于Java的ConcurrentSkipListMap的并发跳过列表映射，区别在于我希望列表允许重复，并且我也希望列表是可索引的 （这样查找列表的第N个元素需要O（lg（ n））时间，而不是像标准跳过列表那样的O（n）时间）。 这些修改不会产生问题。 
 
 另外，跳过列表的键是可变的。 例如，如果列表元素是整数{0,4,7}，那么中间元素的键可以更改为[0，7]中的任何值，而不会提示更改列表结构; 如果密钥更改为（-inf，-1]或[8，+ inf），则删除该元素并重新添加以维护列表顺序。 除了在O（lg（n））插入后执行此操作外，我将其实现为一个删除，然后进行线性遍历，后跟一个O（1）插入（预期运行时间为O（1） - 99该节点将与相邻节点交换的时间百分比）。 
 
 插入一个全新的节点很少（在启动后），并且删除一个节点（不需要立即重新添加它）永远不会发生; 几乎所有的操作都是elementAt（i）来检索第i个索引处的元素，或者在键被修改后交换节点的操作。 
 
 我遇到的问题是如何实现关键修改类（es）。 从概念上讲，我想要做类似的事情 
 
public class Node implements Runnable {
    private int key;
    private Node prev, next;
    private BlockingQueue<Integer> queue;

    public void update(int i) {
        queue.offer(i);
    }

    public void run() {
        while(true) {
            int temp = queue.take();
            temp += key;
            if(prev.getKey() > temp) {
                // remove node, update key to temp, perform backward linear traversal, and insert
            } else if(next.getKey() < temp) {
                // remove node, update key to temp, perform forward linear traveral, and insert
            } else {
                key = temp; // node doesn't change position
            }
        }
    }
}
 
 （从run调用的insert子方法使用CAS来处理两个节点试图同时插入同一位置的问题（类似于ConcurrentSkipListMap处理冲突插入的方式） - 概念上，这与第一个节点锁定与插入点相邻的节点，除非在没有冲突的情况下减少开销。） 
 
 通过这种方式，我可以确保列表总是按顺序进行的（如果密钥更新稍微延迟，可以确定更新最终会发生;但是，如果列表变得无序，那么事情可能会失灵）。 问题是用这种方式实现列表会产生很多线程，每个Node有一个线程（列表中有几千个节点） - 大多数线程在任何给定的时间点都会被阻塞，但是我担心有几个线程千个阻塞线程仍然会导致开销过高。 
 
 另一种选择是使update方法同步并从Node移除Runnable接口，这样就不会让两个线程在Node排队更新，然后在其单独的线程上处理这些更新，这两个线程将轮流执行Node#update方法。 问题是这可能会造成瓶颈; 如果八个不同的线程都决定一次更新同一个节点，那么队列实现可以很好地扩展，但同步实现会阻塞八个线程中的七个（然后阻塞六个线程，然后是五个等）。 
 
 所以我的问题是，除了线程数量减少之外，我将如何实现队列实现之类的东西，否则除非没有潜在的瓶颈问题，否则我将如何实现类似于同步实现的东西。 

I'm implementing a concurrent skip list map based on Java's ConcurrentSkipListMap, the differences being that I want the list to allow duplicates, and I also want the list to be indexable (so that finding the Nth element of the list takes O(lg(n)) time, instead of O(n) time as with a standard skip list). These modifications aren't presenting a problem.
 
In addition, the skip list's keys are mutable. For example, if the list elements are the integers {0, 4, 7}, then the middle element's key can be changed to any value in [0, 7] without prompting a change to the list structure; if the key changes to (-inf, -1] or [8, +inf) then the element is removed and re-added to maintain the list order. Rather than implementing this as a removal followed by a O(lg(n)) insert, I implement this as a removal followed by a linear traversal followed by an O(1) insert (with an expected runtime of O(1) - 99% of the time the node will be swapped with an adjacent node).
 
Inserting a completely new node is rare (after startup), and deleting a node (without immediately re-adding it) never occurs; almost all of the operations are elementAt(i) to retrieve the element at the ith index, or operations to swap nodes after a key is modified.
 
The problem I'm running into is in how to implement the key modification class(es). Conceptually, I'd like to do something like
 
public class Node implements Runnable {
    private int key;
    private Node prev, next;
    private BlockingQueue<Integer> queue;

    public void update(int i) {
        queue.offer(i);
    }

    public void run() {
        while(true) {
            int temp = queue.take();
            temp += key;
            if(prev.getKey() > temp) {
                // remove node, update key to temp, perform backward linear traversal, and insert
            } else if(next.getKey() < temp) {
                // remove node, update key to temp, perform forward linear traveral, and insert
            } else {
                key = temp; // node doesn't change position
            }
        }
    }
}
 
(The insert sub-method being called from run uses CAS in order to handle the problem of two nodes attempting to simultaneously insert at the same location (similar to how the ConcurrentSkipListMap handles conflicting inserts) - conceptually this is the same as if the first node locked the nodes adjacent to the insertion point, except that the overhead is reduced for the case where there's no conflict.)
 
This way I can ensure that the list is always in order (it's okay if a key update is a bit delayed, because I can be certain that the update will eventually happen; however, if the list becomes unordered then things might go haywire). The problem being that implementing the list this way will generate an awful lot of threads, one per Node (with several thousand nodes in the list) - most of them will be blocking at any given point in time, but I'm concerned that several thousand blocking threads will still result in too high of an overhead.
 
Another option is to make the update method synchronized and remove the Runnable interface from Node, so that rather than having two threads enqueuing updates in the Node which then takes care of processing these updates on its separate thread, the two threads would instead take turns executing the Node#update method. The problem is that this could potentially create a bottleneck; if eight different threads all decided to update the same node at once then the queue implementation would scale just fine, but the synchronized implementation would block seven out of the eight threads (and would then block six threads, then five, etc).
 
So my question is, how would I implement something like the queue implementation except with a reduced number of threads, or else how would I implement something like the synchronized implementation except without the potential bottleneck problem.

原文：https://stackoverflow.com/questions/16529799