9

我正在为内部集群实施我自己的 dht。由于它将用于像bittorrent这样的文件共享程序，“Mainline DHT”是我看的第一件事。之后我发现了“纠缠”（python，使用扭曲矩阵的 dht），国会（python，使用 pyev + libev 的 dht），当然还有原始的“kademlia”。

他们在组织 k-buckets 上有不同的方法：

1) 国会，kademlia 使用固定的 160 个桶，范围为 2* i <= (每个 id 与我们的差异) < 2 *(i+1)，对于 0 <= i < 160。

2）主线DHT和纠缠使用动态桶。开始时，他们只有 1 个桶覆盖整个空间。在它被 8 个存活节点填充后，桶将被拆分为 2 个新节点。但前提是我们自己的 id 在那个桶里。如果不是 - 存储桶将永远不会被拆分。因此，很快我们将拥有 160 个离我们最近的存储桶，而其他存储桶则很少。

两种变体都足够好。但是我发现逻辑上的巨大差异检测是否属于某个存储桶的某个 id。这是我的问题。

congress 和 kademlia 将桶边界视为“与我们的最小距离”和“与我们的最大距离”。因此，我们自己的 ID 将始终在 bucket0 中。bucket1 中最多 2 个其他 id（因为它覆盖 2* 1 <= x < 2 *2 距离）总是离我们最近。所以我的大脑没有坏掉，因为一切都好。

但是，如果您查看 Mainline DHT 或 entangled，您会看到哪些桶边界被视为绝对节点 id 边界，而不是异或距离！因此，理论上完整的表 ID 0、1、2、3、4、5、6、7 将在 1 个存储桶中。

所以。为什么有些实现将桶边界视为“与我们的最大/最小距离”，而另一些实现将桶边界视为“最大/最小 160 位整数值”？

4

1 回答 1

10

kademlia 论文实际上提出了随着路由表的增长动态拆分桶的优化。这两种方法在逻辑上没有区别，只是为了节省一些空间而进行的优化。当实现一个固定的全尺寸路由表时，你必须找到 k 个节点来发送请求。如果你的目标落入的桶是空的，或者其中的节点少于 k 个，你必须从相邻的桶中挑选。鉴于此，首先不要拆分离您最近的存储桶，从而使搜索更简单、更快。

至于你的观点（1），我想你可能误解了 kademlia。路由表存储桶边界始终与您自己的节点 ID 相关。对于远离您的每个存储桶，存储桶的 ID 空间跨度加倍。如果没有这个属性（假设每个存储桶覆盖了相同范围的 ID 空间），您将无法正确进行搜索，而且它们肯定不会是 log(n)。

主线 DHT 实现了 kademlia。

于 2011-10-10T05:05:30.440 回答