Как представить таблицу маршрутизации kademlia как структуру данных
В документе kademlia говорится об организации сегментов, разбивке, объединении и поиске правильных блоков, которые можно вставить в абстрактных, кратких и запутанных терминах.
§2.2 говорит о фиксированном наборе из 160 сегментов, каждый из которых покрывает фиксированное подмножество пространства ключей. Но более поздние главы включают дополнительное разделение и сегменты, охватывающие различные части пространства клавиш. Это не вписывается в фиксированный список
Как правильно организовать ведра?
Мета: Поскольку путаница отражена во многих вопросах, а частичная информация разбросана по многим ответам, эти вопросы и ответы предназначены для предоставления легко связанного пояснения
1 ответ
Путаница проистекает из разных версий статьи. Многие реальные реализации просто реализуют подход из предварительной печати, который все еще отражен в §2.2 полной версии, но они не реализуют разбиение на сегменты, слияние или множественное нахождение узлов. Они просто помещают контакты в iэто ведро, которое разделяет i Префикс битов с узлом.
Чтобы реализовать такие усовершенствования, как обработка сильно несбалансированных деревьев, описанных в конце п. 2.4, или более глубокое нелокальное разбиение, описанное в п. 4.2, необходимо связать каждый сегмент с диапазоном пространства ключей, который он охватывает, это можно выразить аналогично диапазонам CIDR, т.е. идентификатор начала и количество префиксных битов, используемых для маскировки хвоста идентификатора.
Разделение сегмента выполняется путем увеличения количества префиксных битов на единицу и установки добавленного бита в 0 и 1 соответственно для двух новых сегментов.
Поскольку количество сегментов в такой таблице маршрутизации меняется со временем, она должна быть представлена в структуре данных с изменяемым размером. Поскольку доступ больше не может быть сделан с помощью фиксированного индекса, так как точная область, которая будет охватывать какой-либо конкретный идентификатор узла, неизвестна, пока диапазоны префиксов не будут исследованы каким-либо видом O(log n) Поиск необходим, если вы хотите избежать сканирования всего списка сегментов каждый раз.
Сортировка сегментов по наименьшему идентификатору, который будет охватывать сегмент, является естественным подходом для достижения этой цели. Для этого можно использовать BTrees или отсортированные массивы в сочетании с двоичным поиском.
Независимо от того, какой подход вы используете, заполнение ответа на find_node запросы с правильным набором контактов, которые соответствуют цели запроса, не являются тривиальными, так как для заполнения одного отдельного сегмента может быть недостаточно, и, следовательно, необходимо пройти несколько сегментов. Может быть проще просканировать всю таблицу маршрутизации на предмет наилучших доступных кандидатов для ответа.
После некоторого онлайн-исследования и перечитывания газеты несколько раз, я думаю, что получил это. В окончательном варианте статьи где-то в разделе 2 (Описание системы) говорится:
Оставшаяся часть этого раздела заполняет детали и делает алгоритм поиска более конкретным. Сначала мы определим точное понятие близости идентификаторов, что позволит нам говорить о сохранении и поиске пар на k ближайших узлах к ключу. Затем мы даем протокол поиска, который работает даже в тех случаях, когда ни один узел не разделяет уникальный префикс с ключом или некоторые из поддеревьев, связанных с данным узлом, пусты
Часть определения "точного понятия близости идентификаторов" выполняется в подразделе 2.1. Таким образом, это "позволяет" нам в подразделах 2.2 и 2.3 говорить о "хранении и поиске пар на k ближайших узлах к ключу", и мы узнаем, как работает процедура поиска. В разделе 2.4 теперь будет рассмотрен вопрос поиска в тех случаях, когда ни один узел не имеет уникального префикса с ключом (так называемые несбалансированные деревья), и здесь фактически завершен "протокол поиска".
Таким образом, структура массива используется вначале как фиктивная структура, которую мы используем, чтобы понять процедуру поиска, и после того, как мы поймем, как работает процедура поиска, мы познакомимся с более продвинутой древовидной структурой.
Это то, что авторы, вероятно, имели в виду.