Введение
Хеш-основанная структура данных
Kademlia – это распределенная хеш-таблица для децентрализованных одноранговых компьютерных сетей, разработанная Петером Маймунковым и Дэвидом Мазьером в 2002 году. Она определяет структуру сети и обмен информацией посредством поиска узлов. Узлы Kademlia общаются друг с другом, используя UDP. Виртуальная или наложенная сеть формируется узлами-участниками. Каждый узел идентифицируется номером или идентификатором узла. Идентификатор узла служит не только для идентификации, но и алгоритм Kademlia использует его для поиска значений (обычно хешей файлов или ключевых слов). Чтобы найти значение, связанное с заданным ключом, алгоритм исследует сеть в несколько этапов. Каждый этап находит узлы, более близкие к ключу, пока обращенный узел не вернет значение или не будут найдены более близкие узлы. Это очень эффективно: как и многие другие системы, Kademlia связывается только с узлами во время поиска из общего числа узлов в системе. Дополнительные преимущества заключаются, в частности, в децентрализованной структуре, которая повышает устойчивость к атакам типа "отказ в обслуживании". Даже если целый набор узлов будет перегружен, это окажет ограниченное влияние на доступность сети, поскольку сеть восстановится, "затягивая" сеть вокруг этих "дыр". Реализация Kademlia в I2P модифицирована для снижения уязвимостей Kademlia, таких как атаки Сивиллы.
Протокольные сообщения
У Кадемлии четыре типа сообщений. PING — используется для проверки, активен ли узел. STORE — сохраняет пару (ключ, значение) в одном узле. FIND NODE — получатель запроса возвращает k ближайших к запрошенному ключу узлов из своих корзин. FIND VALUE — аналогично FIND NODE, но если получатель запроса имеет запрошенный ключ в своем хранилище, он возвращает соответствующее значение. Каждое RPC-сообщение содержит случайное значение, сгенерированное инициатором. Это гарантирует соответствие полученного ответа ранее отправленному запросу (см. "магическое печенье").
Определение узлов
Поиск узлов может выполняться асинхронно. Количество одновременных поисков обозначается α и обычно равно трем. Узел инициирует запрос FIND NODE, отправляя запросы α узлам в своих k-корзинах, которые наиболее близки к искомому ключу. Когда эти узлы-получатели получают запрос, они просматривают свои k-корзины и возвращают k ближайших узлов к искомому ключу, которые им известны. Запрашивающий обновляет список результатов, добавляя полученные ID узлов, сохраняя k лучших (k узлов, наиболее близких к искомому ключу) из тех, которые ответили на запрос. Затем запрашивающий выбирает эти k лучших результатов и отправляет им запрос, повторяя этот процесс снова и снова. Поскольку каждый узел лучше знает окрестности, чем любой другой, полученные результаты будут другими узлами, каждый раз все ближе и ближе к искомому ключу. Итерации продолжаются до тех пор, пока не будут возвращены узлы, которые не ближе, чем лучшие предыдущие результаты. Когда итерации завершаются, лучшие k узлов в списке результатов являются ближайшими к искомому ключу во всей сети. Информация об узле может быть дополнена временем кругового обхода, или RTT. Эта информация будет использоваться для установки таймаута, специфичного для каждого запрашиваемого узла. Если время ожидания запроса истекло, можно инициировать новый запрос, но их количество одновременно не должно превышать α.
Определение ресурсов
Информация находится путем сопоставления с ключом. Для этой цели обычно используется хеш-функция. У узлов-хранилищ уже будет информация, полученная из предыдущего сообщения STORE. Поиск значения происходит по той же процедуре, что и поиск ближайших к ключу узлов, за исключением того, что поиск завершается, когда узел находит запрошенное значение в своем хранилище и возвращает его. Значения хранятся на нескольких узлах (в количестве k) для обеспечения доступности даже при выходе из строя некоторых узлов. Периодически узел, хранящий значение, просматривает сеть для поиска k узлов, близких к этому ключу, и реплицирует значение на них. Это компенсирует исчезновение узлов. Кроме того, для популярных значений, к которым часто обращаются, нагрузка на узлы-хранилища снижается за счет того, что узел-получатель хранит это значение на узле, расположенном рядом, но за пределами k ближайших. Такое дополнительное хранилище называется кэшем. Таким образом, значение хранится все дальше от ключа в зависимости от количества запросов. Это позволяет чаще запрашиваемым данным быстрее находить хранилище. Поскольку значение возвращается с узлов, удаленных от ключа, это снижает вероятность возникновения "горячих точек". Кэширующие узлы удаляют значение через определенное время, зависящее от их расстояния до ключа. Некоторые реализации (например, Kad) не используют ни репликацию, ни кэширование. Это делается для быстрого удаления устаревшей информации из системы. Узел, предоставляющий файл, периодически обновляет информацию в сети, отправляя сообщения FIND NODE и STORE. Когда все узлы, содержащие файл, отключаются, никто не обновляет его значения (источники и ключевые слова), и информация в конечном итоге исчезает из сети.
Присоединение к сети
Узел, желающий присоединиться к сети, сначала должен пройти процесс инициализации. На этом этапе присоединяющемуся узлу необходимо знать IP-адрес и порт другого узла – начального узла (полученного от пользователя или из сохраненного списка), – который уже участвует в сети Kademlia. Если присоединяющийся узел еще не участвовал в сети, он вычисляет случайный идентификатор, который, будучи очень большим случайным числом, с высокой вероятностью еще не назначен другому узлу. Он использует этот идентификатор до выхода из сети. Присоединяющийся узел помещает начальный узел в один из своих k-корзин. Затем присоединяющийся узел выполняет поиск своего собственного идентификатора относительно начального узла (единственного другого известного узла). Этот "самопоиск" заполнит k-корзины других узлов новым идентификатором узла, а k-корзины присоединяющегося узла – узлами на пути между ним и начальным узлом. После этого присоединяющийся узел обновляет все k-корзины, находящиеся дальше, чем k-корзина, в которую попадает начальный узел. Это обновление представляет собой поиск случайного ключа, находящегося в пределах диапазона этой k-корзины. Изначально узлы имеют одну k-корзину. Когда k-корзина заполняется, она может быть разделена. Разделение происходит, если диапазон узлов в k-корзине охватывает собственный идентификатор узла (значения слева и справа в двоичном дереве). Kademlia даже смягчает это правило для k-корзины "ближайших узлов", поскольку обычно одна корзина соответствует расстоянию, на котором находятся все узлы, ближайшие к данному узлу, их может быть больше, чем k, и мы хотим, чтобы он знал их всех. Может оказаться, что рядом с узлом существует сильно несбалансированное двоичное поддерево. Например, если k равно 20, и существует 21 или более узлов с префиксом "xxx0011", а новый узел имеет идентификатор "xxx000011001", новый узел может содержать несколько k-корзин для этих 21 или более узлов. Это гарантирует, что сеть знает обо всех узлах в ближайшем регионе.
Ускоренные поиски
Кадемлия использует метрику XOR для определения расстояния. Два идентификатора узлов или идентификатор узла и ключ подвергаются операции XOR, и результат является расстоянием между ними. Для каждого бита функция XOR возвращает ноль, если два бита одинаковы, и единицу, если два бита различны. Расстояния в метрике XOR удовлетворяют неравенству треугольника: если A, B и C – вершины (точки) треугольника, то расстояние от A до B меньше (или равно) сумме расстояний от A до C и от C до B. Метрика XOR позволяет Кадемлии расширять таблицы маршрутизации за пределы отдельных битов. Группы битов могут быть помещены в k-корзины. Группа битов называется префиксом. Для префикса длиной m бит будет 2m - 1 k-корзин. Отсутствующая k-корзина является дальнейшим расширением дерева маршрутизации, содержащим идентификатор узла. Префикс длиной m бит уменьшает максимальное количество поисков с log2 n до log2(m*n). Это максимальные значения, а среднее значение будет значительно меньше, что повышает вероятность нахождения узла в k-корзине, который имеет больше общих битов с целевым ключом, чем просто префикс. Узлы могут использовать различные префиксы в своей таблице маршрутизации, например, сеть Kad, используемая eMule. Сеть Кадемлия может быть даже неоднородной в реализации таблиц маршрутизации, что усложняет анализ поисков.
Академическое значение
Хотя метрика XOR не требуется для понимания Kademlia, она критически важна для анализа протокола. Арифметические операции XOR образуют абелеву группу, что позволяет проводить замкнутый анализ. Другим протоколам и алгоритмам DHT требуется моделирование или сложный формальный анализ для прогнозирования поведения и корректности сети. Использование групп битов в качестве информации для маршрутизации также упрощает алгоритмы.
Использование в сетях обмена файлами
Kademlia используется в сетях обмена файлами. С помощью поиска по ключевым словам в Kademlia можно найти информацию в сети обмена файлами для последующей загрузки. Поскольку централизованного хранилища индексов существующих файлов нет, эта задача распределяется равномерно между всеми клиентами: если узел хочет поделиться файлом, он обрабатывает содержимое файла, вычисляя на его основе число (хеш), которое идентифицирует этот файл в сети обмена файлами. Поскольку хеши файлов и идентификаторы узлов имеют одинаковую длину, клиент может использовать функцию XOR-расстояния для поиска нескольких узлов, идентификаторы которых близки к хешу, и даёт указание этим узлам сохранить IP-адрес издателя в порядке, определяемом реализацией. Таким образом, узлы с идентификаторами, наиболее близкими к хешу файла, будут содержать список IP-адресов одноранговых узлов/издателей этого файла, с которых клиент может загрузить файл в порядке, определяемом реализацией. Клиентам, желающим загрузить файл от этого издателя, не требуется знать IP-адрес издателя (их может быть несколько), достаточно знать только хеш файла. Клиент, выполняющий поиск, использует Kademlia для поиска в сети узла, идентификатор которого имеет наименьшее расстояние до хеша файла, а затем получает список источников, хранящийся в этом узле. Поскольку одному ключу может соответствовать несколько значений, например, множество источников одного и того же файла, каждый узел хранения может содержать различную информацию. Затем источники запрашиваются у всех k узлов, ближайших к ключу, где k – размер корзины. Хеш файла обычно получают из специально сформированной интернет-магнитной ссылки, найденной в другом месте, или из индексирующего файла, полученного из других источников. Поиск по имени файла реализуется с использованием ключевых слов. Имя файла разбивается на составляющие его слова. Каждое из этих ключевых слов хешируется и сохраняется в сети вместе с соответствующим именем файла и хешем файла. Поиск включает в себя выбор одного из ключевых слов, установление связи с узлом, идентификатор которого наиболее близок к хешу этого ключевого слова, и получение списка имен файлов, содержащих это ключевое слово. Поскольку каждое имя файла в списке имеет прикрепленный к нему хеш, выбранный файл можно получить обычным способом.