routing - 为什么 Kademlia 如何构建它的路由表？

Question

我知道 Kademlia 路由表由 160 个桶组成。

节点被放入 0-159 桶，这取决于它们的前缀长度(这是本地节点 key 和节点的 XOR 中的前导未设置位的数量)。

为什么会这样，是否有任何性能优势(除了遍历 160*20 节点以找到最接近的节点是不可行的)？。

Answer 1

Kademlia 使用 2 个节点 ID 的异或作为它们之间距离的度量。路由表桶的想法是，一个节点对“靠近”它的网络有详细的了解，而你从它的 ID 中获得的知识越少。

为了找到最接近特定键的一组节点，节点首先会从它自己的路由表中查询它所知道的最近的节点。平均而言，这些查找的一半将落入桶 0 覆盖的地址空间。但该桶只允许包含 20 个节点，因此这些节点实际上是最接近的可能性很小。但是，该桶中的每个节点都将拥有该部分地址空间的更详细信息，并且可能能够从其自己的路由表中提供更好的关闭节点列表，然后也可以对其进行查询，依此类推。

通过这种方式，迭代查找非常快速地在实际最近的节点组上磨练。

当你说

iterating through 160*20 nodes to find the closest is infeasible

我认为您的意思是实际查询它们中的每一个都是不可行的；因为遍历这样的列表以提取最接近的列表正是节点处理查找请求 (RPC) 的方式。

请注意，在实际场景中，桶的数量不太可能接近 160。例如，对于 10 亿节点的网络，平均桶数为 27。

至于原始 Kademlia 论文中选择的实际值，我不知道为什么将桶大小指定为 20。但是，我认为 160 是从 SHA1 哈希的位大小得出的。通常，散列函数用于为要存储的给定值生成 key 。如果使用 SHA1 发生哈希冲突的风险低到可以接受，那么这很好。如果没有，可以使用不同的哈希算法，例如SHA256 将产生多达 256 个桶。