DHT：BitTorrent与Kademlia及克隆（Python）
我正在为我的内部集群实现一个自己的分布式哈希表（DHT）。因为它会用于像BitTorrent这样的文件共享程序，所以我首先关注了“主线DHT”。之后我发现了“entangled”（用Python编写，使用twisted matrix的DHT）、“congress”（用Python编写，使用pyev + libev的DHT），当然还有原始的“kademlia”。
它们在组织k-bucket（存储桶）方面有不同的方法：
1) congress和kademlia使用固定的160个存储桶，范围是2*i <= (与我们之间的每个ID的差值) < 2*(i+1)，其中0 <= i < 160。
2) 主线DHT和entangled使用动态存储桶。启动时，它们只有一个存储桶，覆盖整个空间。当这个存储桶里填满8个活跃节点后，它会被分成两个新的存储桶。但只有当我们的ID在那个存储桶里时，才会进行分裂。如果不在里面，存储桶就永远不会分裂。所以，最终我们会有160个离我们最近的存储桶和几个其他的。
这两种方法都不错。但我发现它们在判断某个ID属于哪个存储桶的逻辑上有很大的不同。这就是我想问的问题。
congress和kademlia把存储桶的边界看作是“离我们最近的最小距离”和“离我们最远的最大距离”。所以，我们自己的ID总是会在bucket0里。最多有2个其他ID在bucket1里（因为它覆盖了2*1 <= x < 2*2的距离），这些ID总是离我们最近。所以我觉得很正常，一切都很好。
但是如果你看看主线DHT或entangled，你会发现存储桶的边界被视为绝对的节点ID边界，而不是异或距离！所以在理论上的完整表中，ID 0,1,2,3,4,5,6,7会在一个存储桶里。
那么，为什么有些实现把存储桶的边界看作是“离我们最近/最远的距离”，而其他的则看作是“最大/最小的160位整数值”呢？
1 个回答
Kademlia的论文提到了一种优化方法，就是在路由表变大的时候，动态地拆分存储桶。其实这两种方法在逻辑上没有区别，只是为了节省一些空间而做的优化。当你要实现一个固定大小的完整路由表时，你需要找到k个节点来发送请求。如果你目标节点所在的存储桶是空的，或者里面的节点少于k个，那你就得从相邻的存储桶中选择。这样一来，如果你最靠近的存储桶一开始就没有被拆分，那搜索就会变得更简单、更快。
至于你提到的第一点，我觉得你可能对Kademlia有些误解。路由表的存储桶边界总是相对于你自己的节点ID来说的。而且每个离你更远的存储桶所覆盖的ID空间是前一个的两倍。如果没有这个特性（比如说每个存储桶覆盖的ID空间范围相等），你就无法正确地进行搜索，而且搜索的效率也不会是log(n)的。
主流的DHT实现了Kademlia。