Как представить таблицу маршрутизации kademlia как структуру данных

Question

В документе kademlia говорится об организации сегментов, разбивке, объединении и поиске правильного сегмента для вставки в абстрактных, лаконичных и запутанных терминах.

§2.2 говорит о фиксированном наборе из 160 сегментов, каждый из которых покрывает фиксированное подмножество пространства ключей. Но последующие главы включают дополнительное разделение и сегменты, охватывающие различные части пространства клавиш. Это не вписывается в фиксированный список

Как правильно организовать ведра?

_{Мета: Поскольку путаница отражена во многих вопросах, а частичная информация разбросана по многим ответам, эти вопросы и ответы предназначены для предоставления легко связанного пояснения}

Answer 1

После некоторого онлайн-исследования и перечитывания статьи несколько раз, я думаю, я понял. В окончательном варианте статьи где-то в разделе 2 (Описание системы) написано:

Остальная часть этого раздела заполняет детали и делает алгоритм поиска более конкретным. Сначала мы определим точное понятие близости идентификаторов, что позволит нам говорить о сохранении и поиске пар на k ближайших узлах к ключу. Затем мы даем протокол поиска, который работает даже в тех случаях, когда ни один узел не разделяет уникальный префикс с ключом или некоторые из поддеревьев, связанных с данным узлом, пусты

Часть определения «точного понятия близости идентификаторов» выполняется в подразделе 2.1. Таким образом, это «позволяет» нам в подразделах 2.2 и 2.3 говорить о «хранении и поиске пар на k ближайших узлах к ключу», и мы узнаем, как работает процедура поиска. В разделе 2.4 теперь будет рассмотрен вопрос поиска в тех случаях, когда ни один узел не имеет уникального префикса с ключом (так называемые несбалансированные деревья), и здесь фактически завершен «протокол поиска».

Таким образом, структура массива используется вначале как фиктивная структура, которую мы используем, чтобы понять процедуру поиска, и после того, как мы поймем, как работает процедура поиска, мы познакомимся с более продвинутой древовидной структурой.
Это то, что авторы, вероятно, имели в виду.

Answer 2

Путаница проистекает из разных версий бумаги .

Плоская планировка

Это из допечатной версии и в основном используется для теоретического описания основных свойств kademlia и все еще отражено в §2.2 и §3 полной версии.

Во многих реальных реализациях реализован этот подход, но они не реализуют разбиение на сегменты, объединение или множественное нахождение узлов .

Он включает в себя размещение контактов в i-ом сегменте, который разделяет префиксные биты i с узлом. Это означает, что макет использует расстояния относительно собственного идентификатора узла.

Древовидный макет

Это описано в разделе §2.4 .

Для реализации уточнений, таких как обработка сильно несбалансированных деревьев , описанных в конце §2.4 или более глубокого нелокального разбиения, описанного в §4.2 , необходимо свяжите каждый сегмент с диапазоном пространства ключей, который он охватывает, это можно выразить аналогично диапазонам CIDR , т. е. идентификатору старта и количеству префиксных битов, используемых для маскировки хвоста идентификатора.

Разделение сегмента выполняется путем увеличения количества префиксных битов на один и установки добавленного бита в 0 и 1 соответственно для двух новых сегментов.

В отличие от плоской компоновки, эта структура не включает расстояния относительно собственного идентификатора узла, хотя некоторые решения основаны на том, попадет ли собственный идентификатор узла в корзину.

Поскольку количество сегментов в такой таблице маршрутизации меняется с течением времени, которое она должна представлять в структуре данных с изменяемым размером, это упоминается в §2.4 . Поскольку доступ больше не может быть сделан с помощью фиксированного индекса, так как точный сегмент, который будет охватывать какой-либо конкретный идентификатор узла, неизвестен до тех пор, пока не будут исследованы диапазоны префиксов, необходим какой-то O(log n) поиск, если кто-то хочет избежать сканирования весь список ведра каждый раз.
Сортировка сегментов по наименьшему идентификатору, который будет охватывать область, является естественным подходом для достижения этой цели. Для этого можно использовать BTrees или отсортированные массивы в сочетании с двоичным поиском.

Независимо от того, какой подход вы выберете, заполнение ответа на find_node запросов правильным набором контактов, которые соответствуют цели запроса , не является тривиальным , так как одного отдельного сегмента может быть недостаточно для его заполнения и, следовательно, нескольких ведра должны быть пройдены. Может быть проще просканировать всю таблицу маршрутизации на предмет наилучших доступных кандидатов для ответа.