Kademlia

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

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

Алгоритм Kademlia базируется на расчете «расстояния» между узлами путём применения операции исключающее ИЛИ к ID этих узлов.

Эта «дистанция» не имеет никакого отношения к географическому положению. К примеру, узлы из Германии и Австралии могут быть «соседними» в оверлейной сети.

Информация в Kademlia хранится в так называемых «значениях» (values). Каждое «значение» привязано к «ключу» (key).

При поиске соответствующего ключу значения алгоритм исследует сеть в несколько шагов. Каждый шаг приближает к искомому узлу до полного нахождения «значения» либо до отсутствия таких узлов. Количество контактируемых узлов зависит от размера сети логарифмически: при увеличении количества участников (number of participants) вдвое количество запросов увеличится всего на один.

Использование в файлообменных сетях

Задача хранения индексов файлов в сети Kad раскладывается на всех участников сети. Если узел хочет «расшарить» файл, он обрабатывает его, получая хэш, который идентифицирует этот файл в сети. Затем узел ищет несколько узлов, ID которых близки к хэшу (размеры хешей и идентификаторов узлов должны совпадать), при этом на эти узлы отдается информация об адресе этого узла. Клиент при поиске ищет ID узла, который имеет наименьшую дистанцию к хэшу файла и извлекает из него адреса узлов, которые имеют этот файл. Контакты, хранимые в сети, всегда находятся в постоянном изменении, так как узлы постоянно подключаются и отключаются. Для отказоустойчивости эти контакты реплицируются по нескольким узлам.

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

Клиенты файлообменных сетей, использующие различные вариации протокола Kademlia

• Протокол Kad, используемый в клиентах iMule, eMule, aMule, MLDonkey и др.
• Сеть I2P — в сети используется модифицированный DHT Kademlia и клиент iMule
• Vuze DHT — в клиенте Vuze сети BitTorrent
• Mainline DHT — в большинстве клиентов сети BitTorrent
• В клиенте RevConnect сети Direct Connect, впоследствии — в StrongDC++ и его клонах (не афишируется, но имеется)
• Протокол Overnet — в прекратившем ныне развитие клиенте eDonkey2000

См. также

• Kad Network

Литература

• Klaus Wehrle, Mesut Günes, James Gross. Modeling and Tools for Network Simulation. — Springer Science & Business Media, 2010. — P. 454–. — ISBN 978-3-642-12331-3.
• Cai, X. S., Devroye, L. A Probabilistic Analysis of Kademlia Networks (англ.). — 2013. — Vol. 8283. — P. 711. — DOI:10.1007/978-3-642-45030-3_66.
• Juenemann, Konrad. Confidential Data-Outsourcing and Self-Optimizing P2P-Networks: Coping with the Challenges of Multi-Party Systems. — KIT Scientific Publishing, 2015. — P. 81–. — ISBN 978-3-7315-0328-6.
• Maymounkov, Petar and Mazières, David (2002). "Kademlia: A Peer-to-Peer Information System Based on the XOR Metric" in IPTPS '01. Revised Papers from the First International Workshop on Peer-to-Peer Systems: 53—65, Springer-Verlag. Проверено 2013-12-06.