为什么Kademlia要以它目前的方式构建路由表？

Question

我了解Kademlia路由表由160个存储桶组成。

节点被放入0-159号存储桶中，具体取决于它们的前缀长度（即本地节点密钥和节点的XOR中未设置的领先位数）。

为什么会这样做，除了查找最接近的节点需要通过160 * 20个节点进行迭代是不可行的之外，是否还涉及性能优势呢？

- liamzebedee

---

是的，有性能优势。这有助于将查找时间保持在O(log n)。完整解释请参见http://gleamly.com/article/introduction-kademlia-dht-how-it-works。 - Joshua Kissoon

Answer 1

Kademlia使用2个节点ID的异或作为它们距离的衡量标准。路由表桶的想法是，节点对其附近的网络具有详细的了解，并且距离其ID越远，了解越少。

要查找最接近特定键的一组节点，节点首先会从自己的路由表中查询已知的最接近的节点。平均而言，这些查询的一半会落入桶0覆盖的地址空间中。但是，该桶只允许包含20个节点，因此这些节点很少可能是实际最接近的节点。然而，该桶中的每个节点都将更详细地了解该地址空间的那部分，并且很可能能够提供更好的接近节点列表，然后也可以进行查询，以此类推。

通过这种方式，迭代查询非常快速地缩小到实际最接近的节点组。

当你说“通过160*20个节点进行迭代查找最接近的节点是不可行的”时，我认为你的意思是实际上查询每个节点是不可行的；因为通过这样的列表进行迭代以提取最接近的节点，正是节点处理查找请求（RPC）的方法。

请注意，在现实世界的情况下，桶数很难达到160。例如，对于10亿个节点的网络，平均桶数将为27。

至于原始Kademlia论文中选择的实际值，我不知道为什么指定桶大小为20。但是，我想160源于SHA1哈希的位大小。通常使用哈希函数生成要存储的给定值的密钥。如果使用SHA1的哈希冲突风险可以容忍较低，则这是可以接受的。如果不行，则可以使用其他哈希算法，例如SHA256将产生多达256个桶。

- Fraser

Answer 2

为什么会这样，是否有性能方面的好处？

该组织与XOR指标相结合，创建分层本地性保证，在查询接近于您目标节点的节点时，将了解更接近的节点。这产生了指数级的收敛。

也许您可以将其视为分布式区间搜索。

我知道Kademlia路由表由160个桶组成。

一个由（最多）160个桶组成的平坦数组只是许多实现用来近似正确的路由表布局的基本方法。

使用桶分裂或多主路由表，您需要一个实际的树形布局，其中可能包含超过160个桶。

事实上，以下是具有89个节点ID的多主DHT节点的基于树的路由表的一个小部分，完整表格比此更大（这些基本上是89个ID的两个区域）：

0000000...   entries:8 replacements:8
0000001000...   entries:8 replacements:8
0000001001000...   entries:8 replacements:8
00000010010010...   entries:8 replacements:8
00000010010011000...   entries:8 replacements:8
000000100100110010...   entries:8 replacements:8
0000001001001100110...   entries:8 replacements:8
00000010010011001110...   entries:8 replacements:8
0000001001001100111100...   entries:5 replacements:0
0000001001001100111101...   entries:8 replacements:0
000000100100110011111...   entries:8 replacements:0
0000001001001101...   entries:8 replacements:8
000000100100111...   entries:8 replacements:8
000000100101...   entries:8 replacements:8
00000010011...   entries:8 replacements:8
000000101...   entries:8 replacements:8
00000011...   entries:8 replacements:8
0000010...   entries:8 replacements:8
0000011000...   entries:8 replacements:8
0000011001000...   entries:8 replacements:8
00000110010010...   entries:8 replacements:8
00000110010011000...   entries:8 replacements:8
000001100100110010...   entries:8 replacements:8
0000011001001100110...   entries:8 replacements:8
00000110010011001110...   entries:8 replacements:5
0000011001001100111100...   entries:6 replacements:0
0000011001001100111101...   entries:2 replacements:0
000001100100110011111...   entries:8 replacements:0
0000011001001101...   entries:8 replacements:8
000001100100111...   entries:8 replacements:8
000001100101...   entries:8 replacements:8
00000110011...   entries:8 replacements:8
000001101...   entries:8 replacements:8
00000111...   entries:8 replacements:8

它的查找缓存甚至更大，由7k个桶组成。

- the8472

---

这个多重主机 DHT 客户端是什么？您能再多说一些吗？我不介意看看它的源代码。它是否在比特流 DHT 上运行？我自己用 Python 写了一个 MDHT 客户端。 - gsk

这意味着一个客户端作为多个节点运行，例如用于多个IP。是的，这是BitTorrent DHT。源代码可以在此处找到：http://azsmrc.svn.sourceforge.net/viewvc/azsmrc/mldht/trunk/ - the8472

Answer 3

该算法是为了在2001年左右创建P2P文件共享服务而设计的。想象一下，每个P2P节点都存储并提供mp3文件，路由表包含这些文件的哈希值。

由于当时的存储硬件无法在每个节点上存储所有文件，因此每个P2P用户将在其PC上存储mp3数据库的一部分。最多160*20=3200个mp3文件大约需要15 Gb的存储空间。这感觉很合理。

必须有一种公平分配数据的方法。基于前缀长度的对数距离是其中之一。具有“更远”哈希值的文件更容易发生冲突。它们对应的桶很快就会满，更随机地选择哪些文件进入其中。具有“更接近”哈希值的文件将是您作为对等方负责长时间存储的文件。这些文件较少，它们填充桶的速度较慢。

除了遍历160*20个节点以找到最接近的节点是不可行的之外

现在比较3200个距离并不是什么大问题，但是是的，桶有助于找到与您“最接近”的节点进行复制。

- battlmonstr