dht - 如何将 kademlia 路由表表示为数据结构

Question

kademlia paper抽象地讨论桶的组织、拆分、合并和找到要插入的正确桶，concise和 confusing条款。

§2.2 讨论了一组固定的 160 个桶，每个桶覆盖键空间的一个固定子集。但后面的章节涉及额外的拆分和覆盖键空间不同部分的桶。这不太适合固定列表

组织桶的正确方法是什么？

_{Meta:由于混淆反射(reflect)在许多问题中，部分信息分散在许多答案中，因此此问答旨在提供易于链接的澄清}

Answer 1

混淆源于 from different versions of the paper 。

平面布局

这来自预印本，主要用于以理论方式概述 kademlia 的基本属性，并且仍然反射(reflect)在完整版本的 §2.2 和 §3 中。

许多现实世界的实现都实现了这种方法，但它们没有实现桶拆分、合并或 node multihoming 。

它涉及将联系人放入与节点共享 i 前缀位的第 i 个桶中。这意味着布局使用相对于节点自身 ID 的距离。

树状布局

这在 §2.4 节中有描述。

要实现改进，例如在 §2.4 末尾描述的处理 highly unbalanced trees 或在§4.2 中描述的更深层次的非本地拆分，需要将每个桶与键空间相关联它涵盖的范围，this can be expressed similar to CIDR ranges，即起始 ID 和共享的前缀位数，以屏蔽 ID 的尾部。

通过将前缀位的数量增加一位并将添加的位分别设置为两个新桶的 0 和 1 来执行拆分桶。

与平面布局不同，此结构不涉及相对于节点自身 ID 的距离，尽管一些决定是基于节点自身的 ID 是否会落入桶中。

由于此类路由表中的桶数会随时间变化，因此必须在可调整大小的数据结构中表示，这在§2.4 中有所提及。由于无法再通过固定索引进行访问，因为在检查前缀范围之前不知道将覆盖任何特定节点 ID 的确切存储桶某种 O(log n) 搜索如果想要避免每次都扫描整个遗愿 list ，则需要此选项。
按桶将覆盖的最低 ID 对桶进行排序是实现此目的的自然方法。可以使用 B 树或排序数组结合二进制搜索来实现这一点。

无论您采用哪种方法，使用与请求的目标 is not trivial 匹配的正确联系人集填充对 find_node 请求的响应，因为任何单个存储桶都可能不足以填充它，因此需要多个存储桶被遍历。扫描整个路由表以寻找最佳可用候选答复可能更简单。