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

Question

kademlia论文讨论了桶的组织、拆分、合并和找到正确的桶以抽象、简洁和令人困惑的术语插入。

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

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

_{Meta：由于混淆反映在许多问题中，并且部分信息分散在许多答案中，因此此问答旨在提供易于链接的澄清}

Answer 1

混乱源于论文的不同版本。

平面布局

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

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

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

基于树的布局

这在第2.4节中进行了描述。

为了实现改进，例如处理§2.4末尾描述的高度不平衡树或§4.2中描述的更深层次的非局部拆分，需要将每个桶与其覆盖的键空间范围相关联，这可以表示为类似于 CIDR 范围，即起始 ID 和共享前缀位数以屏蔽 ID 的尾部。

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

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

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

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

Answer 2

经过一些在线研究并重新阅读了几次论文后，我想我明白了。在论文的最终版本第 2 节（系统描述）的某处，它说：

本节的其余部分将填写详细信息并使查找算法更加具体。我们首先定义了 ID 接近度的精确概念，允许我们谈论在离键最近的 k 个节点上存储和查找对。然后，我们给出了一个查找协议，即使在没有节点与键共享唯一前缀或与给定节点关联的某些子树为空的情况下也能正常工作

定义“ID 接近性的精确概念”的部分在 2.1 小节中完成。因此，这“允许”我们在 2.2 和 2.3 小节中谈到“在离密钥最近的 k 个节点上存储和查找对”，我们将了解查找过程是如何工作的。现在，第 2.4 节将解决在没有节点与密钥共享唯一前缀（也称为不平衡树）的情况下查找的问题，这是实际完成的“查找协议”。

因此，数组结构在开始时用作我们用来理解查找过程的虚拟结构，在了解查找过程的工作原理之后，我们被引入了更高级的树结构。
这就是作者可能想到的。