0

在 Kademlia 中，节点存储的所有（键、值）对，除了当前节点本身最初发布的对，都有一个基于当前节点相对于键的位置的过期时间。如果当前节点是离该键最近的 k 个节点，则 (key, value) 对将在其从最初发布时的 24 小时后过期。如果不是 k-closest 节点，则过期时间为

与当前节点和ID最接近key ID的节点之间的节点数成反比

根据 Kademlia 论文。论文还说

这个数字可以从当前节点的桶结构中推断出来。

计算当前节点和给定节点之间的节点似乎有两种截然不同的方法，我不确定哪一种是正确的。我们接下来假设平面数组路由表实现，一个预先分配了 160 个桶的数组。

  1. Xlattice Kademlia 设计规范页面说，您应该找到给定节点将落入的存储桶索引 j 并计算存储桶 0..j 中的节点，计算 0..j-1 中的所有节点并仅计算更接近的节点比最终桶 j 中的 key 到当前节点。

  2. Bruno Spori 的“Kademlia 分布式哈希表的实现”学期论文（“中间节点数的计算”部分）计算当前节点与给定节点之间的距离，并仅计算距离较小的桶中的节点或等于当前节点和给定节点之间的距离。

这两种方法对我来说似乎都是正确的，但它们完全不同并且产生不同的结果。第一种方法根据当前节点与桶中其他节点之间的距离计算当前节点与给定节点之间的节点。第二种方法根据给定节点与桶中其他节点之间的距离计算当前节点和给定节点之间的节点。

例如，如果当前节点具有 ID 0001_0100（为了示例，我们假设 8 位 id），则只有 8 个存储桶包含具有以下前缀的节点： 0001_0101, 0001_011x, 0001_00xx, 0001_1xxx, 0000_xxxx, 001x_xxxx, 01xx_xxxx, 1xxx_xxxx。假设我们要计算 key 的过期时间1010_0010。当前节点和给定节点之间的距离是 182 ( 0001_0100 xor 1010_0010 = 182)。

使用第一种方法，我们将计算存储桶 0..6 中的所有节点以及存储桶 7 中比给定 ID 更接近当前节点的节点。这是有效的，因为当前节点和所有桶之间的距离是：1、2、4、12、20、52、84、148。您可以通过将我们的 ID 与桶覆盖的范围进行异或来找到它们（我将 x 替换为0 以获得最小但不一定是最接近的 ID 将落入该桶），例如0001_0100 xor 0001_0101 = 1和0001_0100 xor 1000_0000 = 148。直到最后一个节点的所有节点都将具有距离当前节点 <= 182（当前节点和给定 ID 之间的距离）的节点。最后一个桶可以有更远的节点。所以我们计算所有 8 个存储桶中的节点数（部分计算最后一个）。

使用第二种方法，我们计算存储桶 1、2、4、5 和 7 中的所有节点。我们不计算存储桶 0、3、6。这是有效的，因为给定 ID 和存储桶之间的距离为：183、180、 178, 186, 162, 130, 226, 34。您可以通过将给定 ID 与存储桶覆盖的范围异或来找到它们（我将 x 替换为 0 以获得最小但不一定是最接近的 ID）桶），例如1010_0010 xor 0001_0101 = 183和1010_0010 xor 1000_0000 = 34。只有桶 1、2、4、5 和 7 的节点相对于给定 ID 的距离小于 182（当前节点与给定 ID 之间的距离）。所以我们只计算 8 个桶中的 5 个桶中的节点。

计算 8/8 桶和 5/8 桶中的节点是一个很大的区别。哪种方法是正确的？两者似乎都在计算当前节点和给定键之间的节点数，但结果却如此不同。

请注意，xor 度量在这里成立，这里似乎没有任何错误。例如，当前节点与位于最后一个桶的节点之间的距离为0001_0100 xor 1000_0000 = 148。给定节点与最后一个桶中的同一节点之间的距离为1010_0010 xor 1000_0000 = 34。148 xor 34 = 182，所以d(a, b) = d(a, c) xor d(c, b)成立。

第一种方法似乎计算了当前节点知道的距离当前节点小于 182 的所有节点。第二种方法似乎计算了当前节点知道的距离给定节点比 182 更近的所有节点。

我认为第二种方法更正确，因为我们想知道我们是否是给定键的 k-closest 节点。当查找接近给定 ID 的节点时，即FIND_NODERPC，您可以使用类似于第二种方法的过程来识别哪些桶包含最接近给定 ID 的节点，例如在给定的示例中，这些节点将是桶 7、5、4 , 2, 1, 0, 3, 6 - 以最接近的顺序排列。

但是话又说回来，第一种方法也很有意义，因为我们最了解自己的周围环境。我们知道距离当前节点比 182 更近的全部 8 个节点桶，而我们只知道距离给定 key 比 182 更近的大约 5 个节点桶。

4

1 回答 1

0

我对平面路由表布局缺乏直觉，在我自己的实现中早已切换到基于树的布局。因此，我将基于后者进行争论。

在基于树的布局中衰减存储时间的最简单方法是查看存储键将落入哪个桶。如果它落入最深的桶（深度d），它将获得完整的时间（T）。对于d-1它得到T/2，对于d-2它得到T/4等等。

如果实现了非局部分割，这可能是不准确的，在这种情况下，应该将 k-closest 集合中最浅的桶视为最大深度。

另一种也适用于平面布局的方法是，首先估计键空间中的全局节点密度，然后使用三规则来获取任何距离的节点数。可以通过多种方式获得估计值。使用从路由表到本地节点 ID 的 k-closest 集合中的距离是最简单但也是最嘈杂的一种（这应该相当于上面对非本地分裂的校正）。

为了检查算法，我会使用数值模拟，因为甚至可以在几秒钟内计算出数百万个 ID 和距离。构建由它们的 ID 表示的 N 个节点的种群（对于不同的 N），然后为每个种群中的随机节点 ID 构建一堆完美的路由表，然后运行你的估计器以获得一堆间隔并计算相对于实际计数的误差来自模拟人群。

于 2019-06-20T14:00:51.857 回答