6

我已经查看了有关此主题的许多文档，但有些内容并不完全清楚。例如比特种子文件（http://www.bittorrent.org/beps/bep_0005.html）状态

路由表被细分为“桶”，每个桶都覆盖了一部分空间。一张空表有一个桶，ID空间范围为min=0，max=2^160。当一个 ID 为“N”的节点被插入到表中时，它被放置在 min <= N < max 的桶中。一张空表只有一个桶，因此任何节点都必须适合它。每个桶在“满”之前只能容纳 K 个节点，目前是 8 个。当一个桶装满了已知的好节点时，除非我们自己的节点ID在桶的范围内，否则不能再添加节点。在这种情况下，桶被两个新桶替换，每个桶的范围是旧桶的一半，并且来自旧桶的节点分布在两个新桶中。对于只有一个桶的新表，

它与其他关于 kademlia 路由表的文档有些不同，其中桶是根据节点 id 的位前缀排列的，但还有另一个令人困惑的事情。当我们回复“查找节点”请求时，我们必须使用 XOR 操作找到与请求节点最近的 8 个节点。我看到一些实现只是通过执行 XOR 操作的路由表中的每个项目，从而找到 8 个最接近的项目。在我看来，CPU也浪费了。

一切都已经在桶里了。即使我们使用 bit torrent 文档系统建议的方法，我们也可以更快地找到可能包含请求的节点 ID 的存储桶，只需枚举存储桶并检查其上的最小和最大数量。然后可能该存储桶应该包含关闭节点，但它们是值最接近的节点而不是 XOR 最接近的节点（据我了解），这有点不同但有点相似。

我使用从 0 到 99 的数字进行了一个简单的测试，我想在其中找到 8 个 XOR 最接近的数字，它们在所寻找的数字附近但不在它附近。现在，考虑到我们的存储桶，我猜可能存储桶中的所有节点 id 都是最接近的一个小异常。因此，例如，如果我们拿这个桶，从左边取一个，从右边取一个，并搜索 XOR 最接近的节点 ID，我们将找到我们正在寻找的内容，并且没有必要遍历路由中的所有节点桌子。

我是对的还是我错过了什么？

4

1 回答 1

5

它与其他关于 kademlia 路由表的文档有些不同，其中桶是根据节点 id 的位前缀排列的，但还有另一个令人困惑的事情。

bittorrent 规范描述了一个路由表实现，它只近似于kademlia 论文中描述的那个。它更容易实现，但有一些缺点。

因此，例如，如果我们拿这个桶，从左边取一个，从右边取一个，并搜索 XOR 最接近的节点 ID，我们将找到我们正在寻找的内容，并且没有必要遍历路由中的所有节点桌子。

在两者中 - 完整的树状路由表实现和简化的 BEP5 变体 - 每个桶都可以被认为具有类似CIDR 的前缀（参见这个 SO answer），由桶覆盖的前缀位和掩码位组成数数。

在 BEP5 变体中，每个存储桶的前缀都简单地从数组索引和您的节点自己的 ID 派生。在树状表中，由于桶拆分/合并操作，桶必须跟踪它们的前缀。

使用这些前缀，您可以找到覆盖目标键的存储桶。

问题是桶不一定是满的，如果你想发送，假设一个响应中有 20 个节点，一个桶是不够的。

因此，您必须以相对于目标键的升序距离 (XOR) 顺序遍历路由表（根据您自己的节点 ID 或自然距离排序）以访问多个存储桶。

由于 XOR 距离度量在每个位进位（XOR == 无进位加法）处折叠，它不能很好地映射到任何路由表布局。换句话说，访问最近的桶是行不通的。

这是我从树状路由表中找到与特定目标键最近的 N 个节点的实现。

我认为很多人只是简单地遍历整个路由表，因为对于常规节点，它最多只包含几十个桶，而 DHT 节点看不到太多流量，所以它只需要每秒执行几次这个操作并且如果你在一个密集的、缓存友好的数据结构中实现它，那么最大的份额实际上可能是内存流量，而不是 CPU 指令进行一些 XOR 和比较。

即全表扫描很容易实现。

假设我们有一个路由表，每个存储桶都有以下位前缀。这些字母用作方便的名称）。

A 000... 
B 00100... 
C 0010100... 
D 0010101000... 
E 0010101001...
F 001010101... 
G 00101011... 
H 001011... 
I 0011... 
J 01... 
K 1...

现在假设我们正在寻找这个目标键：

T = 0010011010111111001111100101011000001010010100001100100010011100000000100100000111001101100110110110101100010100111010111001101111110101001001001000100000001001

此外，桶并没有完全装满，或者我们需要比单个桶装更多的条目，所以我们必须访问多个桶才能获得所需的数量。

现在，要访问的第一个存储桶相当明显，B因为它的前缀覆盖了目标键。

由于B' 的前缀是 5 位长，因此该桶中的任何条目都将具有到 的 XORT距离00000???????...。5 个前缀位共享。

B是最近的桶T，这意味着不能有任何路由表条目比相对距离更近00000...。相反，这意味着任何外部条目B可以具有的最小距离是00001...。这意味着下一个最近的桶必须覆盖T xor 00001... -> 00101110101111110[...].

覆盖这个的桶是H.

H不相邻B

最终 - 假设我们必须访问 6 个存储桶 - 顺序将如下所示：

00100...      -> B
001011...     -> H
001010101...  -> F
0010101000... -> D
0010101001... -> E
00101011...   -> G

这似乎相当混乱。但是，如果我们绘制每个访问过的桶的前缀到目标键的距离，它就会变得更加明显：

00000...
000010...
000011000...
0000110010...
0000110011...
00001101...

所以算法如下：

  1. 找到覆盖目标键的初始桶
  2. XOR 桶的前缀与目标键（零掩码尾随位）
  3. 将距离增加该前缀的最低有效位
  4. 与目标键 XOR 递增距离
  5. 找到下一个覆盖 XORed 键的存储桶
  6. 转到 2

TL;DR：“只看左边一桶，右边一桶”是不够的。正确的算法相当复杂，整个表的线性扫描更容易实现。

于 2015-06-04T22:38:45.470 回答