Протоколы / Kademlia

Kademlia — реализация распределённой хеш-таблицы (DHT) для одноранговых компьютерных сетей. Протокол определяет структуру сети регулирующую связь между узлами и способ обмена информацией в ней. Узлы сети общаются между собой по протоколу транспортного уровня UDP и хранят данные посредством распределённых хеш-таблиц. В итоге над существующей LAN/WAN создаётся оверлейная сеть в которой каждый узел обозначается специальным идентификатором («Node ID») играющим роль адреса и распределителя ролей для поисковой классификации в сети.

Узел, который хочет присоединиться к сети, обязан пройти «загрузочную» процедуру (bootstrap process), для этого он должен знать адрес другого узла (полученный от пользователя или взятый из списка), который уже входит в оверлейную сеть. Если подключаемый узел ещё не входил в эту сеть, то происходит расчет случайного значения ID, которое ещё не принадлежит никакому узлу. ID используется до момента выхода из сети.Алгоритм Kademlia базируется на расчете битовой дистанции между узлами путём применения операции исключающее ИЛИ (XOR) к ID этих узлов. Дистанция не имеет никакого отношения к географическому положению.Информация в Kademlia хранится в базе типа ключ-значение.

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

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

Применение:

BitTorrent (Mainline DHT, Vuze DHT)
DirectConnect (RevConnect, StrongDC+)
I2P (iMule)
Kad (iMule, eMule, aMule, MLDonkey)
Overnet (eDonkey2000)