Интернет магазин китайских планшетных компьютеров

Компьютеры - Kademlia

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

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

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

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

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

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