Как работает поиск в Kad Network

Довольно часто встречаются жалобы на то, что в Mainline DHT битторрента нет поиска по ключевым словам. Обычно просьбы о добавлении такого поиска на форумах BitTorrent Inc. игнорируются или получают традиционный ответ о том, что DHT не позволяет искать по ключевым словам, а только по индивидуальным ключам. Это в принципе верно, но существует такой выход из этой прискорбной ситуации как создание инвертированного индекса ключевых слов у каждой ноды.

Собственно так и работает поиск в Kad Network, реализации распределённой хэш-таблицы, основанной на довольно широко используемом протоколе Kademlia. Kad Network используется такими программами как eMule, iMule, aMule и MLDonkey для поиска хэшей файлов по ключевым словам и источников файлов по их хэшам.

Общее описание процесса поиска в Kad Network.
(для лучшего понимания полезно представлять, как работает Kademlia)

Итак, у каждой ноды в сети Kad Network есть 128-битный ID, генерируемый случайно каждый раз при входе в сеть. Для хэширования файлов и слов используется алгоритм, основанный на MD4, что дает распределение хэшей-ключей в том же пространстве, что и ID всех нод. Каждая нода ответственна за хранение нескольких типов информации. Во-первых, каждая нода хранит карту источников, т.е. информацию об участниках сети, которые готовы поделиться определенным файлом. Карта представляет собой хэш файла в качестве ключа и список источников в качестве значения. Карта источников ноды содержит контактную информацию по хэшам всех файлов, чей хэш совпадает с ID ноды или близок к ней (используется XOR-метрика). Так, имея хэш файла, можно найти ноды с ID, близкими к хэшу файла (конкретный механизм поиска примерно соответствует тому, что используется в Kademlia) и запросить у них список источников для закачки файла. Во-вторых, если хэша файла нет, то можно осуществить его поиск по ключевым словам. Для этого имя публикуемого файла разбивается на несколько последовательных слов, и каждое слово хэшируется отдельно. В целях поиска по этим ключевым словам каждая нода имеет вторую карту, которая содержит хэши слов, близких к ID самой ноды, в качестве ключей и хэши файлов и их имена в качестве значений.

Теперь более подробно о том, как осуществляется поиск конкретно в eMule.

Когда инициируется процесс поиска, то создается соответствующий объект и вносится в карту поиска. Каждый поисковый запрос имеет целевой ключ (хэш файла, хэш слова), который ищется в сети Kad Network. Поисковые запросы осуществляются с помощью двух параллельных процессов.
Первый процесс ищет ноды с ID, близкими к ключу-хэшу искомого объекта. Чтобы найти нужные ноды, ищущая нода берет 50 нод с ближайшими к ключу искомого объекта ID из своей таблицы маршрутизации и помещает их во временную карту. Затем ищущая нода начинает обращаться к этим 50 нодам для того, чтобы получить ноды, находящиеся ближе к ключу искомого объекта. Одновременно опрашивается только 3 ноды. Ищущая нода посылает сообщение KADEMLIA_REQ с такими параметрами как ключ объекта (хэш слова, хэш файла или ID ноды) и количество запрошенных нод (т.е. сколько нод запрашиваемая нода должна вернуть в качестве ответа). Последний параметр зависит от типа поискового запроса. Если это поиск ноды, то параметр равен 11, если это поиск источников или поиск по слову, то – 2. Когда нода получает такое сообщение, она отвечает сообщением KADEMLIA_RES с запрошенным количестом контактов (нод). Когда ищущая нода получает это сообщение, она добавляет полученные контакты в свою таблицу маршрутизации и во временную карту текущего поиска. Затем ищущая нода опять опрашивает три ближайших к ключу объекта ноды, но только если их ID ближе к ключу, чем ID нод, которые предоставили их контактную информацию. Эта процедура повторяется до тех пор, пока во временной карте есть новые ноды, чьи ID ближе к ключу искомого объекта. Если ноды не отвечают на запрос KADEMLIA_REQ, то они удаляются.

Второй процесс посылает нодам, которые ответили сообщением KADEMLIA_RES, начиная с ближайшей, соответствующий поисковый запрос в зависимости от того, что ищется. Это может быть SEARCH_REQ для поиска источников или файлов по ключевым словам, PUBLISH_REQ для публикации источников или ключевых слов и т.д. В этих запросах используется дополнительный флаг, принимающий значения 0 или 1, для определения того, что именно запрашивается – источники или хэши с именами по ключевым словам. Когда нода получает такой поисковый запрос, она должна обработать его (поискать запрашиваемую информацию в своей карте ключевых слов или карте источников) и ответить сообщением SEARCH_RES с отобранными результатами. Для каждого типа результатов существует предельная величина, при достижении которой поиск прекращается. Для поиска источников или поиска по ключевым словам эта предельная величина составляет 300 полученных оригинальных объектов. Также поиск источников или файлов останавливается, если прошло 45 секунд с начала поиска.

Полезные статьи:
Petar Maymounkov, David Mazières «Kademlia: A Peer-to-peer information system based on the XOR Metric».
Подробное описание протокола Kad Network:
David Mysicka «Reverse Engineering of eMule: An Analysis of the Implementation of Kademlia in eMule».
Stefan Schmid, Thomas Locher «When KAD meets BitTorrent — Building a Stronger P2P Network».