在洪流kademlia路由表上实现find节点

Question

我已经在这个主题上回顾了许多文档，但是有些东西不完全清楚。例如位洪流文件（http://www.bittorrent.org/beps/bep_0005.html）指出

路由表被细分成“桶”，每个覆盖的空间的一部分 。一个空表有一个ID为 min = 0，max = 2^160的桶。当具有ID“N”的节点插入到 表中时，它被放置在具有最大= N <最大的桶内。 空表只有一个存储桶，因此任何节点都必须适合它。每个 存储桶只能存放八个K节点，然后才能变为“满”。 当一个桶充满已知的好节点时，除非我们自己的节点ID落入该桶的范围内，否则不会再添加更多节点 。在那个 的情况下，该桶被两个新桶替换，每个桶都有旧桶的 范围的一半，旧桶的节点分配到两个新桶中的 。对于只有一个 存储桶的新表格，整个存储桶始终会分成两个新存储桶，分别覆盖 ，范围为0..2^159和2^159..2^160。

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

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

我跑了一个简单的测试，使用从0到99的数字，我想找到8个XOR最接近的数字，他们在寻找的数字附近但不是靠近它。现在，考虑我们的桶，我想有可能桶中的所有节点ID都是最小的异常。所以，举例来说，如果我们拿这个桶，从左边和右边一个拿一个，然后搜索XOR最接近的节点id，我们将找到我们正在寻找的东西，并且没有必要通过路由中的所有节点表。

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

Answer 1

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

bittorrent规范描述了一个路由表实现，它只能近似于kademlia paper中描述的路由表实现。实施起来比较容易，但也有一些缺点。

因此，例如，如果我们采取这种水桶，拿一个从左边，一个从右边并搜索XOR最接近的节点ID，我们会发现我们正在寻找，并没有一点去通过路由表中的所有节点。

在两种 - 充分，树状路由表执行和简化BEP5变 - 每个桶可以被认为是具有CIDR-like prefix（见this SO answer）由前缀比特的铲斗覆盖和掩模位计数。

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

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

问题是桶不一定是满的，如果你想发送，让我们说20个节点在响应单个桶是不够的。

因此，您必须以相对于目标密钥的上升距离（XOR）顺序来遍历路由表（根据您自己的节点ID或自然距离排序）以访问多个存储桶。由于XOR距离度量在每个比特进位（XOR ==无进位加法）处折叠，因此它不能很好地映射到任何路由表布局。换句话说，访问最近的桶不会这样做。

Here's my implementation用于从树形路由表中查找到特定目标密钥的N个最近节点。

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

I.e.全表扫描很容易实现。

---

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

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的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 

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

​​

所以算法如下：

1. 找到最初桶覆盖靶向与目标密钥（零掩模尾随位）
2. 增量由前缀的至少显著位的距离键
3. XOR铲斗的前缀
4. 与目标键
5. XOR递增的距离找到下一桶覆盖XOR的关键
6. 转到2

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