java - 高效Kademlia桶

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

那么，实现k-Bucket的最有效方法是什么？对我来说重要的是访问时间，并行性（读和写）和内存消耗。

想过用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);
            }
        }
    }
}

请不要怀疑，我已经实施了另一个邻居驱逐过程。

最佳答案

那么，实现k-Bucket的最有效方法是什么？


那要看。如果您想用铃铛来实现（例如桶拆分，多宿主），则需要一个灵活的列表或一棵树。
以我的经验，写阵列+二进制搜索的副本非常适合路由表，因为您很少修改存储桶的总数，而只是修改存储桶的内容。

使用CoW语义，您只需减少数组的当前副本，检索感兴趣的存储区，然后锁定该存储区，因此无需太多锁定。或者在每个存储桶中使用一个原子数组。
但是当然，只有在期望高吞吐量的情况下才需要进行此类优化，大多数DHT节点的流量很少，最多每秒只有几个数据包，也就是说，除非您实现具有如此高吞吐量的专用节点，否则无需涉及多个线程。需要多个线程来处理数据。

CoW对于类似路由表的查找缓存或在查找过程中建立的临时访问节点/目标节点集的效果较差，因为它们被快速修改了。如果期望高负载，则ConcurrentSkipListMaps可能是更好的选择。

如果您想要简化的近似实现，则只需使用一个固定大小的数组，该数组包含160个元素，其中数组索引是相对于您的节点ID的共享前缀位数。这执行得很好，但是不允许full kademlia paper提出的某些优化。

关于java - 高效Kademlia桶，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26564506/