0

我在这里编写了一个修改后的 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);
            }
        }
    }
}

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

4

1 回答 1

1

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

那要看。如果你想做一个花里胡哨的实现（例如桶拆分、多宿主），那么你需要一个灵活的列表或树。以我的经验，写入数组 + 二进制搜索的副本适用于路由表，因为您很少修改存储桶的总数，只修改存储桶的内容。

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

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

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

于 2014-12-18T16:43:19.553 回答