routing - 在 torrent kademlia 路由表上实现查找节点

Question

我已经查看了一些关于这个主题的文件，但有一些不是很清楚。例如，bit torrent 文档 ( http://www.bittorrent.org/beps/bep_0005.html ) 状态

The routing table is subdivided into "buckets" that each cover a portion of the space. An empty table has one bucket with an ID space range of min=0, max=2^160. When a node with ID "N" is inserted into the table, it is placed within the bucket that has min <= N < max. An empty table has only one bucket so any node must fit within it. Each bucket can only hold K nodes, currently eight, before becoming "full." When a bucket is full of known good nodes, no more nodes may be added unless our own node ID falls within the range of the bucket. In that case, the bucket is replaced by two new buckets each with half the range of the old bucket and the nodes from the old bucket are distributed among the two new ones. For a new table with only one bucket, the full bucket is always split into two new buckets covering the ranges 0..2^159 and 2^159..2^160.

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

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

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

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

Answer 1

It is somewhat different from other documents regarding kademlia routing table where buckets are arranged in accordance to the bit prefix of the node id but there is another confusing thing.

bittorrent 规范描述了一种路由表实现，它仅近似于 kademlia paper 中描述的实现。 .它更容易实现，但有一些缺点。

So, for example if we take this bucket, take one from the left and one from the right and search for the XOR closest node ids we'll find what we are looking for and there is no point to go through ALL nodes in the routing table.

在完整的树状路由表实现和简化的 BEP5 变体中，每个桶都可以被认为具有 CIDR-like prefix (参见 this SO answer )由桶覆盖的前缀位和掩码位计数组成。

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

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

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

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

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

Here's my implementation用于从树状路由表中找到距离特定目标键最近的 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因为它的前缀覆盖了目标键。

自 B的前缀为 5 位长，该桶中的任何条目都将与 T 有 XOR 距离。的 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...

所以算法如下:

找到覆盖目标键的初始桶

将存储桶的前缀与目标键(零掩码尾随位)进行异或

通过该前缀的最低有效位增加距离

与目标键的异或增量距离

找到覆盖异或键的下一个桶

转到 2

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