java - 高效 Kademlia 桶

Question

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

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

想过用 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

So, what's the most efficient way of implementing k-Buckets?

这要看情况。如果您想要执行带有附加功能的实现(例如存储桶拆分、多归属)，那么您需要一个灵活的列表或树。根据我的经验，写时复制数组 + 二分搜索对于路由表效果很好，因为您很少修改存储桶的总数，而只修改存储桶的内容。

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

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

如果您想要一个简化的近似实现，那么只需使用 160 个元素的固定大小数组，其中数组索引是相对于您的节点 ID。这执行得相当好，但不允许 full kademlia paper 提出的一些优化。 .