Как понять протокол Kademlia(KAD)
Недавно я прочитал документ протокола Kademlia, я попытался понять протокол, но у меня все еще остается вопрос: почему узел должен найти другой узел, когда он знает свой идентификатор, но ip или порт? Почему у него есть идентификатор, когда он не знает IP-адрес или порт, где он получил идентификатор? Я думаю, что "расстояние" между двумя разными узлами - это не расстояние маршрутизации или реальное расстояние, это всего лишь виртуальное расстояние, которое может использовать алгоритм для быстрого поиска узла, верно?
Может быть, мой английский не очень понятен, потому что английский не мой родной язык, но я постараюсь ясно выразить себя, если вам нужно. Спасибо большое!
2 ответа
Как сказал cHao, распределенная природа сети означает, что узлам необходимо публиковать свои идентификаторы и свои контактные данные на других узлах, с которыми они общаются. Не существует централизованного места, где идентификаторы сопоставляются с контактной информацией, поэтому каждый узел должен хранить это сопоставление для подмножества узлов в сети в своей собственной таблице маршрутизации.
Таблицы маршрутизации Kademlia структурированы таким образом, что узлы будут подробно знать близкую к ним сеть, и экспоненциально уменьшать знания дальше.
Использование побитового XOR в качестве меры условного расстояния между идентификаторами имеет то преимущество, что для данного идентификатора цели два идентификатора не могут иметь одинаковое расстояние до цели.
Представьте себе простой пример, где идентификаторы находятся в диапазоне от 00 до 63. Если бы Kademlia использовал, например, чистую математическую разницу в качестве меры расстояния, 15 и 35 были бы одинаковым расстоянием до 25 - оба имели бы расстояние 10. Используя XOR, расстояние между 15 и 25 - 22, а между 25 и 35 - 58.
Таким образом, группа из k ближайших идентификаторов к целевому идентификатору может быть вычислена однозначно.
Константа k имеет несколько применений в Kademlia, но это в первую очередь фактор репликации. Другими словами, часть данных хранится в k ближайших узлах к идентификатору данных.
Процесс поиска предназначен для возврата либо группы из k узлов (перед сохранением данных на каждом из них), либо для возврата одного фрагмента данных (от первого узла, содержащего его во время итераций поиска).
Из-за этого чистый Kademlia не лучше всего подходит для поиска только одного узла, поэтому я не уверен, что часть вашего вопроса слишком актуальна. Если вы хотите использовать Kademlia для поиска одного узла, вероятно, стоит изменить процесс поиска так, чтобы он заканчивался как можно раньше, как только какой-либо узел возвращает контактные данные целевого узла (так же, как поиск заканчивается рано, если целевое значение находится в процессе).
Поскольку сеть распределена, по определению не существует единой главной таблицы сопоставления адресов -> адресов. Узлы не должны (и обычно не знают) обо всех других узлах. Процесс "нахождения" узла в основном состоит в том, чтобы спрашивать известные узлы, "наиболее близкие" к цели, не столько непосредственно о целевом узле, сколько о том, какие узлы находятся ближе к цели. Результат этого запроса дает вам следующую группу узлов для запроса, и процесс повторяется - и поскольку узел будет возвращать результаты, которые ближе, чем он есть, каждая итерация стремится найти узлы ближе и ближе к цели, пока вы, наконец, не получите достичь узла, который может сказать: "О, узел X? Он прямо там".
По крайней мере, это то, что я понимаю.