Что именно K-Bucket означает в Kademlia DHT?

Question

Я хочу подтвердить свое понимание ведер в Kademlia DHT. Kademlia имеет m k-сегментов, где 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 - количество записей в ведре. Ожидается, что их идентификаторы узлов будут случайным образом распределены в пределах диапазона идентификаторов, охватываемых сегментами, что означает, что удвоение количества записей в сегменте увеличит его разрешение в среднем только на один бит, то есть не будет хорошо масштабироваться. Вот почему у нас есть структурированная таблица маршрутизации с несколькими сегментами с разными областями действия. Это увеличивает локальное разрешение вокруг собственного идентификатора узла.

Реализация полного алгоритма kademlia требует динамической компоновки таблицы маршрутизации. Поэтому m не является фиксированным. Компоновка с фиксированным размером использовалась только в упрощенной допечатной версии статьи как часть теоретического доказательства.

Answer 2

Каждый узел в Kademlia хранит список других узлов. Этот список основан на битовых различиях и слабо обозначается как сегменты. Теперь 'k' - это параметр репликации всей системы. Это означает, что для каждого списка есть k записей внутри этого "сегмента". Это моё понимание. Это ссылка на статью. Надеюсь это поможет..:)