distributed-computing - K-Bucket 在 Kademlia DHT 中到底意味着什么？

Question

我想确认我对 Kademlia DHT 中存储桶的理解。Kademlia 有m 个 k-buckets，其中m是以比特为单位的网络大小，k是每个桶存储的键值对的数量。例如，假设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>  | |
| +------------------+ |
|          .           |
|          .           |
|          .           |
└──────────────────────┘

我的假设正确吗？

标签： distributed-computingp2pdhtkademlia

Answer 1

k是桶中的条目数。它们的节点 ID 预计将随机分布在存储桶覆盖的 ID 范围内，这意味着将每个存储桶的条目数加倍只会将其分辨率平均提高一位，即它不能很好地扩展。这就是为什么我们有一个结构化的路由表，其中包含多个具有不同范围的存储桶。它增加了围绕节点自己的节点 ID 的本地分辨率。

实现完整的 kademlia 算法需要动态路由表布局。因此m不是固定的。固定尺寸布局仅用于简化的预印本论文，作为理论证明的一部分。