ale*_*.98 6 routing bittorrent dht kademlia
我已经阅读了有关此主题的许多文档，但是有些内容并不清楚。例如，比特种子文档（http://www.bittorrent.org/beps/bep_0005.html）指出
路由表被细分为“存储桶”，每个存储桶覆盖一部分空间。一个空表有一个存储桶，其ID空间范围为min = 0，max = 2 ^ 160。当将ID为“ N”的节点插入表中时，该节点将被放置在最小<= N <最大的存储桶中。空表只有一个存储桶，因此任何节点都必须位于其中。每个存储桶只能容纳K个节点（当前为8个），然后再变为“满”。当存储桶中充满了已知良好的节点时，除非我们自己的节点ID落入存储桶的范围内，否则无法再添加更多节点。在这种情况下，该存储桶将被两个新存储桶替换，每个新存储桶的范围均为旧存储桶的一半，并且旧存储桶中的节点将分布在两个新存储桶中。对于只有一个存储桶的新表，
关于kademlia路由表，它与其他文档有些不同，在kademlia路由表中，根据节点id的位前缀来排列存储桶，但还有另一件令人困惑的事情。当我们回复“查找节点”请求时，我们必须使用XOR操作找到8个最接近所请求节点的节点。我看到一些实现只是通过路由表中的每个项目执行XOR操作，从而找到8个最接近的项目。在我看来，CPU也在浪费。
一切都已经在桶中了。即使我们使用bit torrent文档系统建议的内容，我们也可以更快地找到可能包含所请求节点ID的存储桶，只需枚举存储桶并检查其上的最小和最大数目即可。然后，该存储桶可能应包含关闭节点，但它们是值最接近的节点，而不是异或最相似的XOR最接近的节点（据我所知）。
我使用0到99的数字进行了一个简单的测试，我想找到8个XOR最接近的数字，它们在所寻找的数字附近，但不在附近。现在，考虑一下我们的存储桶，我猜可能存储桶中的所有节点ID都是最接近的，仅是次要异常。因此，例如，如果我们拿这个存储桶，从左边取一个，从右边取一个，并搜索XOR最近的节点ID，我们将找到我们要寻找的东西，并且没有必要遍历路由中的所有节点表。
我是对的还是我错过了什么？
关于kademlia路由表，它与其他文档有些不同，在kademlia路由表中，根据节点id的位前缀来排列存储桶，但还有另一件令人困惑的事情。
bittorrent规范描述了一种路由表实现，该实现仅近似于kademlia论文中描述的路由表。它易于实现，但有一些缺点。
因此，例如，如果我们拿这个存储桶，从左边取一个，从右边取一个，并搜索XOR最近的节点ID，我们将找到我们要寻找的东西，并且没有必要遍历路由中的所有节点表。
在完整的，类似树的路由表实现和简化的BEP5-variant中，每个存储桶都可以被视为具有类似于CIDR的前缀（请参阅此SO答案），该前缀由存储桶覆盖的前缀位和掩码位组成计数。
在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位长，在桶中的任何条目都会有一个XOR距离T的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...
因此算法如下：
TL; DR：“仅向左看一桶，向右看一桶”是不够的。正确地涉及了正确的算法，整个表的线性扫描更易于实现。