我已经阅读了有关此主题的许多文档，但是有些内容并不清楚。例如，比特种子文档(http://www.bittorrent.org/beps/bep_0005.html)指出
关于kademlia路由表，它与其他文档有些不同，在kademlia路由表中，根据节点ID的位前缀来排列存储桶，但还有另一件令人困惑的事情。当我们回复“查找节点”请求时，我们必须使用XOR操作找到与请求的节点最接近的8个节点。我看到一些实现只是通过执行XOR操作的路由表中的每个项目，从而找到8个最接近的项目。在我看来，CPU也在浪费。
一切都已经在桶中了。即使我们使用bit torrent文档系统建议的内容，我们也可以更快地找到可能包含所请求节点ID的存储桶，只需枚举存储桶并检查其上的最小和最大数目即可。然后可能该存储桶应该包含关闭节点，但它们是值最接近的节点，而不是异或最相似的XOR最接近的节点(据我所知)。
我使用从0到99的数字进行了一个简单的测试，我想找到8个XOR最接近的数字，它们在所寻找的数字附近，但并不在它附近。现在，考虑一下我们的存储桶，我猜可能存储桶中的所有节点ID都是最接近的，仅是次要异常。因此，例如，如果我们使用该存储桶，则从左侧获取一个，从右侧获取一个，然后搜索XOR最近的节点ID，我们将找到所需的内容，并且没有必要遍历路由中的所有节点 table 。
我是对的还是我错过了什么？
最佳答案
bittorrent规范描述了仅适用于kademlia paper中描述的路由表实现的路由表。它易于实现，但有一些缺点。
在完整的树状路由表实现和简化的BEP5-variant中，每个存储桶都可以被认为具有CIDR-like prefix(请参见this SO answer)，该Here's my implementation由存储桶覆盖的前缀位和掩码位计数组成。
在BEP5变体中，每个存储桶的前缀都简单地从数组索引和节点自己的ID派生而来。在树状表中，由于存储桶拆分/合并操作，存储桶必须跟踪其前缀。
使用这些前缀，您可以找到覆盖目标 key 的存储桶。
事实是，存储桶不一定要装满，如果要发送，则假设一个响应中的20个节点不足以满足要求。
因此，您必须相对于目标 key 以升序(XOR)顺序遍历路由表(根据您自己的节点ID或根据自然距离排序)以访问多个存储桶。
由于XOR距离度量在每个位进位时都会折叠(XOR ==无进位加法)，因此无法很好地映射到任何路由表布局。换句话说，访问最近的存储桶是行不通的。
ojit_a用于从树状路由表中找到与特定目标关键字最接近的N个节点。
我认为许多人只是简单地遍历整个路由表，因为对于常规节点而言，它最多仅包含几十个存储桶，而DHT节点不会看到太多流量，因此它仅需每秒执行几次该操作，并且如果您在密集的，易于缓存的数据结构中实现此功能，则最大的份额实际上可能是内存流量，而不是CPU指令在进行一些XOR和比较。
IE。全表扫描很容易实现。
假设我们有一个路由表，其中每个存储桶都具有以下位前缀。字母用作方便的名称)。
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，因为其前缀覆盖了目标 key 。由于
B的前缀是5位长，因此该存储桶中的任何条目都将与T的00000???????...进行XOR距离。共享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
这似乎很困惑。但是，如果我们绘制访问的每个存储桶的前缀到目标 key 的距离，它就会变得更加明显:
00000...
000010...
000011000...
0000110010...
0000110011...
00001101...
因此算法如下:
TL; DR:“仅向左看一桶，向右看一桶”是不够的。正确地涉及了正确的算法，整个表的线性扫描更易于实现。