高效Kademlia水桶

Question

我正在这里编写一个修改过的Kademlia P2P系统，但是我在这里描述的问题非常类似于原始系统的实现。

那么，实现k桶最有效的方法是什么呢？对我来说，重要的是访问时间、并行性(读和写)和内存配置。

想用一个ConcurrentLinkedQueue和一个ConcurrentHashMap来做它，但是这是相当多余和讨厌的，不是吗？

目前，我只是在同步一个LinkedList。

这是我的代码：

import java.util.LinkedList;

class Bucket {
    private final LinkedList<Neighbour> neighbours;
    private final Object lock;

    Bucket() {
        neighbours = new LinkedList<>();
        lock = new Object();
    }

    void sync(Neighbour n) {
        synchronized(lock) {
            int index = neighbours.indexOf(n);
            if(index == -1) {
                neighbours.add(n);
                n.updateLastSeen();
            } else {
                Neighbour old = neighbours.remove(index);
                neighbours.add(old);
                old.updateLastSeen();
            }
        }
    }

    void remove(Neighbour n) {
        synchronized(lock) {
            neighbours.remove(n);
        }
    }

    Neighbour resolve(Node n) throws ResolveException {
        Neighbour nextHop;
        synchronized(lock) {
            int index = neighbours.indexOf(n);
            if(index == -1) {
                nextHop = neighbours.poll();
                neighbours.add(nextHop);
                return nextHop;
            } else {
                return neighbours.get(index);
            }
        }
    }
}

请不要奇怪，我已经实施了另一个邻居驱逐程序。

Answer 1

那么，实现k桶最有效的方法是什么呢？

这要看情况了。如果你想要用铃铛和口哨来实现(例如桶分裂，多归位)，那么你需要一个灵活的列表或树。在我的经验中，写数组+二进制搜索的副本对于路由表很好，因为很少修改存储桶的总数，只修改存储桶的内容。

使用CoW语义，您需要更少的锁定，因为您只需获取数组的当前副本，检索感兴趣的桶，然后锁定存储桶。或者在每个桶中使用原子数组。当然，只有当您期望获得高吞吐量时，这种优化才是必要的，大多数DHT节点看到的流量很少，最多每秒有几个数据包，也就是说，除非您实现了一个吞吐量非常大的专用节点，需要多个线程来处理数据，否则就不需要涉及多个线程。

CoW对于类似路由表的查找缓存或在查找过程中构建的临时访问的节点/目标节点集不太好，因为这些节点集会被快速修改。如果您期望负载高的话，ConcurrentSkipListMaps可以是一个更好的选择。

如果您想要一个简化的近似实现，那么只需使用由160个元素组成的固定大小的数组，其中数组索引是相对于节点ID的共享前缀位计数。