Как понять протокол Kademlia (KAD)

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

Таблицы маршрутизации Kademlia структурированы таким образом, что узлы будут иметь подробные сведения о сети, расположенной рядом с ними, и экспоненциально уменьшающиеся знания о сети, расположенной дальше.

Использование побитового исключающего ИЛИ в качестве меры условного расстояния между идентификаторами имеет то преимущество, что для данного целевого идентификатора никакие два идентификатора не могут иметь одинаковое расстояние до цели.

Представьте себе простой пример, где идентификаторы находятся в диапазоне от 00 до 63. Если бы Kademlia использовала, например. чисто математическая разница как мера расстояния, 15 и 35 будут одинаковым расстоянием до 25 - оба будут иметь расстояние 10. Используя XOR, расстояние между 15 и 25 равно 22, а между 25 и 35 - 58.

Таким образом, группа из k ближайших идентификаторов к целевому идентификатору может быть вычислена однозначно.

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

Процесс поиска предназначен для возврата либо группы из k узлов (до сохранения данных на каждом из них), либо возврата одного фрагмента данных (из первого узла, содержащего его во время итераций поиска).

Из-за этого чистая Kademlia не подходит для поиска только одного узла, поэтому я не уверен, что часть вашего вопроса слишком актуальна. Если вы хотите использовать Kademlia для поиска одного узла, возможно, стоит изменить процесс поиска, чтобы он завершался раньше, как только какой-либо узел возвращает контактную информацию целевого узла (так же, как поиск завершается раньше, если целевое значение обнаруживается в процессе).

Поскольку сеть распределена, по определению не существует единой главной таблицы сопоставлений идентификаторов и адресов. Узлы не должны (и обычно не знают) обо всех других узлах. Процесс «нахождения» узла в основном состоит в том, чтобы спросить известные узлы, «ближайшие» к цели, не столько непосредственно о целевом узле, сколько о том, какие узлы ближе к цели. Результат этого запроса дает вам следующую группу узлов для запроса, и процесс повторяется — и поскольку узел будет возвращать результаты, которые ближе, чем он есть, каждая итерация имеет тенденцию находить узлы все ближе и ближе к цели, пока вы, наконец, не достичь узла, который может сказать: «О, узел X? Он прямо там».

По крайней мере, я так это понимаю.