DHT: BitTorrent对kademlia对克隆(python)

Question

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

他们在组织k桶方面有不同的方法：

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

2)主线DHT和纠缠使用动态水桶。开始时，他们只有一个桶覆盖整个空间。在填充了8个活节点后，桶将被拆分为2个新节点。但前提是我们自己的身份在那个水桶里。如果不是的话--水桶永远不会裂开。因此，很快我们将有160个最接近我们的水桶和其他几个。

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

国会和卡德梅利亚把水桶班视为“离我们的最小距离”和“与我们的最大距离”。因此，我们自己的ID将始终在bucket0中。bucket1中的最大其他2个ids (因为它包含2*1 <= x< 2*2距离)总是最接近我们的。所以我的大脑不会断裂，因为一切都很好。

但是，如果您查看主线DHT或纠缠，您将看到什么样的桶绑定被视为绝对节点id绑定，而不是xor距离！所以在理论上全表in 0,1,2,3,4,5,6,7将在1桶中。

所以。为什么有些实现将桶边界视为“距离我们的最大/分钟距离”，而其他实现则将其视为"max/min 160 min整数值“？？

Answer 1

随着路由表的增长，kademlia论文实际上调用了动态拆分桶的优化。这两种方法之间没有逻辑上的区别，这只是一个节省一些空间的优化。当实现一个固定的全尺寸路由表时，您必须找到要发送请求的k个节点。如果你的目标落在的桶是空的，或者里面有少于k个节点，你必须从相邻的桶中挑选。既然如此，拥有最接近你的桶一开始就不会被分割，使得搜索变得更简单和更快。

至于你的观点(1)，我认为你可能误解了卡德米利亚。路由表的桶边界总是相对于您自己的节点ID，并且每个桶的ID空间都比您远一倍。如果没有这个属性(假设每个桶覆盖了相同范围的ID空间)，您就无法正确地进行搜索，而且它们肯定不是log(n)。

主线DHT实现了kademlia。