K-Bucket在Kademlia DHT中的确切含义是什么？

Question

K-Bucket在Kademlia DHT中的确切含义是什么？

6

我希望确认一下我对Kademlia DHT中buckets的理解。 Kademlia有m个k-buckets，其中m是网络大小（以位为单位），k是每个bucket存储的键值对数。例如，假设m=4，那么我们可以有2^4个节点，即从0到15。

+========+
| NodeId |
+========+
|   0000 |
+--------+
|   0001 |
+--------+
|   0010 |
+--------+
|   0011 |
+--------+
|   0100 |
+--------+
|   0101 |
+--------+
|   0110 |
+--------+
|   0111 |
+--------+
|   1000 |
+--------+
|   1001 |
+--------+
|   1010 |
+--------+
|   1011 |
+--------+
|   1100 |
+--------+
|   1101 |
+--------+
|   1110 |
+--------+
|   1111 |
+--------+

每个节点都有0位匹配、1位匹配、2位匹配等路由表，总共有m个桶。此外，对于每个桶，它将存储k个代表而不是单个NodeId。因此，如果我们说k=2，节点0101的路由表应该类似于：

┌──────────────────────┐
│         0101         │
├──────────────────────┤
|                      |
| +==================+ |
| |       xxxx       | |
| +==================+ |
| |   1001, <value>  | |
| +------------------+ |
| |   1010, <value>  | |
| +------------------+ |
|                      |
| +==================+ |
| |       0xxx       | |
| +==================+ |
| |   0000, <value>  | |
| +------------------+ |
| |   0111, <value>  | |
| +------------------+ |
|                      |
| +==================+ |
| |       01xx       | |
| +==================+ |
| |   0110, <value>  | |
| +------------------+ |
| |   0111, <value>  | |
| +------------------+ |
|          .           |
|          .           |
|          .           |
└──────────────────────┘

我的假设正确吗？

- Nawras

不是的，k 是路由表中一个桶中节点的数量。一个节点可以存储大量的 键值对。 - Encombe

但是每个_key_都是一个nodeId，因此节点数和键数是相同的东西。你能再解释一下吗？ - Nawras

2个回答

1

每个Kademlia节点都存储其他节点的列表。该列表基于位差异，并松散地称为桶。现在，“k”是系统范围内的复制参数。这意味着对于每个列表，该“桶”内有k个条目。这是我的理解。这是论文链接。希望这可以帮助... :)

- Anirban Chatterjee

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- the8472 · Accepted Answer

k是一个桶中条目的数量。这些节点ID应该在桶所覆盖的ID范围内随机分布，这意味着每个桶中条目数量的加倍只会平均增加一位分辨率，也就是说它的可扩展性不好。

这就是为什么我们有一个结构化路由表，其中每个桶具有不同的范围。它增加了节点自身节点ID周围的本地分辨率。

实现完整的Kademlia算法需要动态路由表布局。因此，m不是固定的。固定大小的布局仅在简化版论文的预印本中作为理论证明的一部分使用。