高度不平衡的Kademlia路由表

Question

在Kademlia论文的第2.4节的最后一段中，指出为了正确处理高度不平衡的树，Kademlia节点将所有有效联系人保留在至少包含k个节点的子树中，即使这需要分裂桶（bucket），其中节点自身ID不存在。

然而，论文的前一节似乎表明，如果k-bucket已经有k个元素，则对该k-bucket的任何进一步添加都需要删除最陈旧的节点（先ping它以查看其是否存活），否则将缓存该添加，直到k-bucket中有可用的插槽。

这篇论文似乎在这两点上存在矛盾。

在什么情况下应该拆分k-bucket？为什么？将“所有有效联系人”保存在路由表中似乎是不切实际的，因为路由表会很快变得非常大。该例子讨论了一个具有许多以001开头的节点和一个以000开头的节点的树。以000开头的节点将不得不不断地分裂其k-bucket，以便001能够容纳以001开头的每个有效节点？在160位地址空间中，这不会最终可能在000的路由表中存储2^157个节点吗？

引用块中的措辞也非常令人困惑...

“在一个子树中”--在路由表的哪个子树中？

“至少包含k个节点的子树”--我们使用什么指标来确定子树的大小？这里的节点是指Kademlia节点、k-buckets还是其他东西？

- offbynull

Answer 1

然而，论文的前一部分似乎表明，如果一个k-bucket已经有k个元素，那么任何进一步添加到该k-bucket中的内容都需要删除最陈旧的节点（先ping它以查看其是否存活），或者在该k-bucket中的某个空槽位可用之前缓存该内容。这就是每当有节点联系要插入但该桶不符合拆分条件时维护桶的方法。

在什么情况下应该拆分k-bucket？为什么？

作为第一个近似值：每当无法插入新节点且桶的ID空间覆盖您的节点ID时，就拆分桶。这是为了在只对远程键空间部分有模糊意识的情况下保持对邻域的完全感知。即为了实现本地性。

为了涵盖不平衡树的情况 - 这可能发生在节点ID不是（伪）随机的情况下，或者至少在叶子桶中由于在随机分配时由于统计偶然性而导致的情况下 - 必须放松方法如下：

• 尝试在路由表中插入新联系人C
• C所属的桶已满
• C比您路由表中第K近的节点更接近您的节点ID，其中K是桶的大小

然后拆分桶。

实际上，这还需要进一步修改，以便在响应时使用松散的拆分，而不经请求应该只使用严格的拆分，否则在启动早期表尚未填充时，当松散的拆分发生时，您可能会得到一些奇怪扭曲的路由表。

当合并桶时，当路由表中没有更接近的节点时，由松散拆分创建的桶不会合并回单个非主桶中，这也需要考虑在内。

---

在S/Kademlia paper提出的改进之一是使用兄弟列表来跟踪节点的最近邻居，这可能比非本地分割更容易实现。

- the8472

---

谢谢你的回答。我已经苦苦思索了一个星期才明白这个问题。你在这里概述的是原始论文中所述的内容吗？ - offbynull

这是一个比较难以理解的问题。我的理解是，这是一种实现方法，它与论文中各自段落的意图相当。几个月前，有人在 IRC 上提到了这部分内容，我花了相当长的时间才完全理解。我之前对 Kademlia 的推理是错误的，所以我不愿意确定我所理解的正确性。也就是说，在实际应用中，往往只实现第一近似，但只要 ID 均匀分布，实现仍然有效，只是会更嘈杂些。 - the8472

我也在苦苦挣扎着原始论文。它似乎自相矛盾。在一个部分中，它谈到了基于160距离的k个桶，而在另一个部分中，则是基于k个桶的键值二叉树，其大小是动态的。有没有什么网络资源可以将这个东西翻译成简单易懂的英语呢？ - Sentinel

如何枚举一组最接近某个目标ID T 的N个节点的算法并不影响本答案。但是，我在另一个答案中概述了这样的算法。在这种特殊情况下，T = 您自己的节点ID。 - the8472

@masterwok 在 Freenode 上的 IRC 频道是 ##bittorrent。 - the8472