4

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

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

为什么会这样，是否涉及任何性能优势（除了迭代 160*20 节点以找到最接近的节点是不可行的事实之外）？

4

3 回答 3

4

Kademlia 使用 2 个节点 ID 的 XOR 作为它们之间距离的度量。路由表存储桶的想法是，节点对“靠近”它的网络有详细的了解，而您从其 ID 中获得的知识越少。

为了找到最接近特定键的一组节点，节点将首先从它自己的路由表中查询它所知道的最近的节点。平均而言，这些查找中有一半会落入存储桶 0 所覆盖的地址空间。但是该存储桶只允许包含 20 个节点，因此这些节点实际上是最近的节点的可能性很小。但是，该桶中的每个节点都将更详细地了解地址空间的那一部分，并且可能能够从其自己的路由表中提供更好的关闭节点列表，然后也可以查询这些节点，等等。

通过这种方式，迭代查找非常快速地在实际最近的节点组上进行磨练。

当你说

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

我认为您的意思是实际查询它们中的每一个是不可行的；因为遍历这样的列表以提取最接近的列表正是节点处理查找请求 (RPC) 的方式。

请注意，在现实世界的场景中，桶的数量不太可能接近 160。例如，对于十亿节点的网络，平均桶数为 27。

至于在原始 Kademlia 论文中选择的实际值，我不知道为什么将桶大小指定为 20。但是，我认为 160 是从 SHA1 哈希的位大小派生的。通常，散列函数用于为要存储的给定值生成密钥。如果使用 SHA1 的哈希冲突的风险相当低，那么这很好。如果不是，可以使用不同的散列算法，例如 SHA256 将产生多达 256 个桶。

于 2012-06-30T11:54:12.263 回答
3

为什么会这样，是否涉及任何性能优势

该组织与 XOR 度量相结合创建了分层的局部性，以保证查询离目标更近的节点会知道更近的节点。这会产生指数收敛。

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

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

（最多）160 个桶的平面数组只是许多实现用来近似正确路由表布局的原始方式。

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

事实上，这里有一个多宿主 DHT 节点的树状路由表的一小部分，它有 89 个节点 ID，完整的表比这个大（这些基本上是 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 个存储桶组成。

于 2012-07-07T00:25:24.193 回答
0

这个算法是在 2001 年左右创建 P2P 文件共享服务的。为了把它放在上下文中，假设每个 P2P 节点都存储和提供 mp3 文件。路由表包含这些文件的哈希值。

使用当时的存储硬件，不可能在每个节点上存储所有文件。这个想法是每个 P2P 用户在他们的 PC 上存储这个 mp3 数据库的一部分。最大 160*20 = 3200 个 mp3 文件大约需要 15 Gb。感觉很合理。

必须有一种方法以公平的方式分发数据。对数距离（基于前缀长度）就是其中之一。具有“更多”哈希的文件更频繁地发生冲突。他们相应的存储桶很快就满了，进入那里的文件更加随机。具有“更接近”哈希值的文件将是您作为对等方负责存储更长时间的文件。这些文件较少，它们填充存储桶的速度较慢。

除了迭代 160*20 个节点来找到最近的节点是不可行的之外

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

于 2022-02-15T13:23:16.230 回答