distributed-computing - K-Bucket 在 Kademlia DHT 中究竟意味着什么？

Question

我想确认我对 Kademlia DHT 中的桶的理解。
Kademlia 有 m 个 k-bucket，其中 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>  | |
| +------------------+ |
|          .           |
|          .           |
|          .           |
└──────────────────────┘

我的假设正确吗？

Answer 1

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

实现完整的 kademlia 算法 requires a dynamic routing table layout .因此 m 不是固定的。固定尺寸布局仅用于简化版 pre-print version of the paper作为理论证明的一部分。