如何将Kademlia路由表表示为数据结构

Question

Kademlia论文讨论了桶的组织、分割、合并以及在摘要、简明和混乱的术语中找到正确的桶进行插入。

第2.2节讲述了一组固定的160个桶，每个桶覆盖了keyspace的一个固定子集。但是后面的章节涉及到额外的分割和覆盖keyspace不同部分的桶。这些不适合于固定列表。

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

- the8472

Answer 1

混淆源自不同版本的论文。

扁平布局

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

许多实际实现采用此方法，但它们不实现桶拆分、合并或节点多重归属。

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

基于树的布局

这在第§2.4节中描述。

要实现像在§2.4结尾描述的处理高度不平衡的树或在§4.2中描述的更深层次的非本地分割等改进，需要将每个桶与其所覆盖的键空间范围相关联，这可以类比CIDR范围进行表达，即起始ID和用于掩码ID末尾的共享前缀位数。增加一个前缀位并将添加的位分别设置为0和1来拆分桶。

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

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

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

- the8472

---

当你说“ith”桶时，如果这是基于0的索引，则共享前缀是到包括第ith位。如果这是基于1的索引，则共享前缀从开头长度为i。 - CMCDragonkai

Answer 2

经过一些在线研究和多次阅读论文，我认为我理解了。在论文的最终版本中，在第2节（系统描述）的某个地方，它说：

“本节的其余部分填补了细节，并使查找算法更加具体化。我们首先定义了ID接近的精确概念，使我们能够谈论在距离关键字最近的k个节点上存储和查找对。然后，我们提供了一个查找协议，即使在没有节点与关键字共享唯一前缀或与给定节点相关联的某些子树为空的情况下也可以工作。”

定义“ID接近的精确概念”的部分在2.1小节中完成。因此，在2.2和2.3小节中，我们可以谈论“将对存储和查找K个最接近键的节点上的一对进行处理”，并且我们将了解查找过程的工作原理。现在，第2.4节将解决在没有节点与键共享唯一前缀（也称不平衡树）的情况下进行查找的问题，并在这里完成实际的“查找协议”。因此，数组结构在开始时被用作虚拟结构，我们用它来理解查找过程，然后介绍更高级的树结构。这可能是作者所想的。

- meph