Речь пойдет о DHT на примере ее реализации известной под названием Kademlia. DHT переводится как распределенная хеш таблица и предназначена для построения децентрализованной сети обмена информацией. Все ниже изложенное работает в клиенте для ED2K сетей для платформы Android и в виде демона на линуксе. Детали реализации ниже.
Каждый узел сети имеет свой идентификатор. Кроме того любой ресурс в DHT будь то ключевое слово или файл тоже имеет идентификатор. В качестве идентификаторов используется значение хеш функции — в торрентах это SHA1, в ED2K это MD4. Разница только в длине — 160 бит против 128. Таким образом чтобы опубликовать или найти что-то в сети требуется хеш искомого ресурса.
В Кадемлии для публикации файла берется хеш используемый в самой сети ED2K, правда с некоторыми оговорками. Если сам хеш файла сериализуется просто как последовательность байт, KAD идентификатор сериализуется как последовательность 4-х 32-х битных слов. Это особенность Кадемлии.
Приходится вращать байты:
Для публикации ключевых слов имена файлов разбиваются на слова и каждое слово хешируется. Полученные хеши публикуются. Хеш можно представить в виде большого целого числа с порядком байт big endian — старшие байты по младшим адресам (в начале) или просто массивом байт.
Работа DHT основана на возможности вычисления расстояния между хешами, это позволяет последовательно приближаться к цели сокращая дистанцию. HASH_SIZE равно 128.
Просто xor:
Компаратор двух хешей относительно некоторого целевого хеша. Обычно целевой хеш это собственный хеш узла.
Самая ходовая функция определения расстояния в K-bucket, если так можно выразиться.
Первым делом клиент генерирует свой идентификатор. Это случайный MD4 хеш (SHA1 для торрентов). Часть данных при генерации хеша может смешиваться с адресом, портом и тому подобные манипуляции для большей случайности.
Один из непонятных на первый взгляд моментов — как связан хеш узла который он себе назначил и ресурсы которые он предоставляет. Ответ — никак. Случайный выбор хеша означает что клиент в сети будет отвечать за ресурсы близкие его хешу — к нему будут приходить другие клиенты для публикации и поиска. Свои ресурсы клиент также будет публиковать на других узлах указывая себя в качестве источника.
Хотя DHT и децентрализованная сеть чтобы подключиться к ней нужно знать хотя бы один узел подключенный к сети. Зная адрес такого узла клиент посылает специальный запрос bootstrap и получает список узлов в ответ. Дальше можно рассылать bootstrap уже этим узлам и так далее. Также существуют сайты с которых можно скачать файлы с наборами узлов в формате ED2K.
Таблица маршрутизации в частности предназначена для выбора нод наиболее близких некоторому хешу. Таблица содержит K-buckets. K-bucket на самом деле не более чем контейнер c структурами описывающими узел сети. Обычно таблицу иллюстрируют в виде дерева как например здесь.
Сама таблица маршрутизации может быть представлена просто листом K-bucket-ов отсортированным в порядке убывания расстояния до нашего идентификатора.
Изначально таблица не содержит ни одного K-bucket — они добавляются в процессе добавления узла.
Пусть таблица содержит такой параметр как количество уже созданных K-bucket — N(numBuckets). Номер K-bucket расчитывается используя выше упомянутую функцию distanceExp как 128 — 1 — distanceExp, более близкие нашему хешу узлы распологаются ближе к хвосту списка.
Каждый K-bucket позиции меньше чем N-2 может содержать узлы расстояние которых от нашего хеша равно n. К-bucket номер которого равен N-1 (крайний) содержит не только узлы с расстоянием n, но и все узлы расположенные ближе, проще говоря все остальные узлы. Диапазон значений n [0..127]. Понятнее это выглядит в коде функции поиска K-bucket (ниже).
K-bucket может разделиться только если это крайний контейнер и это не последний возможный K-bucket. Теоретически всего K-bucket-ов может быть 128 для MD4, но последний букет не может быть использован так-как хеши совпадающие с хешем узла не обрабатываются. Принцип простой — в текущим контейнере остаются узлы с расстоянием равным n, в новый перемещаются все остальные. Таким образом после разделения таблица вырастет на один K-bucket.
Таблица маршрутизации представляет собой лист K-bucket. K-bucket это список структур описывающих узел из сети DHT. Реализация может быть произвольной, например можно поместить все это в таблицу базы данных. Таблица не сжимается — если узлы из некоего K-bucket пропадают до полного опустошения контейнера — он останется в таблице. Узлы могут удаляться например в случае недоступности некоторое время.
Тут нечего подробно рассматривать — обновление это внутренний процесс призванный содержать таблицу маршрутизации в актуальном состоянии. Периодически выбирается K-bucket где требуется обновление, генерируется случайный хеш принадлежащий этому K-bucket, но не совпадающий ни с одним из уже имеющихся и запускается процесс поиска. Условие начала обновления — например последнее обновление было более 15 минут назад.
Публикация и поиск это один и тот-же процесс в конце которого выполняется либо публикация на найденных узлах либо запрос на поиск. Суть его заключается в том, чтобы последовательными итерациями приблизиться к узлам идентификатор которых близок идентификаторам искомых ресурсов. По логике сети именно эти узлы будут содержать информацию о ключевых словах и файлах хеш которых близок их хешу.
Пункт 4 представляет из себя отдельный процесс который может запускаться параллельно основному. Но в представленной реализации он запускается отдельно по окончании основного процесса.
Несколько слов об архитектуре. Поддержка DHT реализована в отдельном трекере представляющим собой асинхронный UDP сервер работающий в выделенном треде. Он может быть запущен отдельно от клиентского приложения что удобно для тестирования. Собственно сейчас этот трекер работает в виде демона на отдельной машине. Запросы в сеть организованы в RPC вызовы через RPC менеджер — это решает задачу ограничения по времени ожидания ответа, позволяет пометить не отвечающие узлы и так далее.
Логически исходящие запросы объединены в менеджере (algorithm). Для каждого запроса создается контрольная структура (observer). Ну и все это запускается как уже упоминалось через RPC менеджер. Более подробно можно посмотреть в коде по ссылкам.
Особенность Кадемлии в том, что не всегда есть возможность точно определить ответ на какой запрос прислал хост в случае если несколько процессов работают одновременно и посылают одновременно несколько запросов одному узлу. К примеру процессы поиска узлов вполне могут пересечься и тут приходится прибегать к некоторым ухищрениям.
В торрентах более грамотная поддержка транзакций — при посылке запроса клиент посылает специальный блок transaction_id который должен быть ему возвращен. Это не только позволяет точно идентифицировать транзакцию, но и дает небольшую защиту сети.
Не стал рассматривать публикацию и поиск заметок (notes) потому что не реализовал поддержку этой возможности Кадемлии.
Надеюсь удалось изложить материал ничего не перепутав.
Ресурс
Каждый узел сети имеет свой идентификатор. Кроме того любой ресурс в DHT будь то ключевое слово или файл тоже имеет идентификатор. В качестве идентификаторов используется значение хеш функции — в торрентах это SHA1, в ED2K это MD4. Разница только в длине — 160 бит против 128. Таким образом чтобы опубликовать или найти что-то в сети требуется хеш искомого ресурса.
В Кадемлии для публикации файла берется хеш используемый в самой сети ED2K, правда с некоторыми оговорками. Если сам хеш файла сериализуется просто как последовательность байт, KAD идентификатор сериализуется как последовательность 4-х 32-х битных слов. Это особенность Кадемлии.
Приходится вращать байты:
/**
* save/load as 4 32 bits digits in little endian save as 4 32 bits digits network byte order
* rotate bytes in each 4 byte portion
*
*/
@Override
public ByteBuffer get(ByteBuffer src) throws JED2KException {
for (short i = 0; i < value.length; ++i) {
byte b = src.get();
value[(i / 4)*4 + 3 - (i % 4)] = b;
}
return src;
}
@Override
public ByteBuffer put(ByteBuffer dst) throws JED2KException {
for (short i = 0; i < value.length; ++i) {
dst.put(value[(i / 4) * 4 + 3 - (i % 4)]);
}
return dst;
}
Сериализация в ED2K сетях
Исторически так сложилось что все примитивы занимающие болee одного байта сериализуются в том же порядке что и на целевой платформе, а именно LITTLE ENDIAN (старшие часть по старшим адресам). Я думаю что это произошло из-за того что клиент eDonkey/eMule изначально разрабатывался только для платформы Windows и соответствующей архитектуры. Исключением являлся MD4 хеш сериализуемый как последовательность байт. IP адрес хранится в 32-х битном unsigned integer LITTLE ENDIAN и так-же записывается в пакет. Поддержка Кадемлиии была добавлена позже и скорее всего другими людьми. Эти люди почему-то решили что следует применять сетевой порядок байт — возможно потому что он является (или считается) стандартным для сетей TCP/IP. Причем применили новый порядок байт только к IP адресу — при записи в KAD пакеты он преобразуется в BIG ENDIAN, все остальное осталось как было. Новый примитив KadId был добавлен не как хеш, а как массив 4-х 32-х битных чисел — вот почему при записи и чтении KAD идентификатора приходится производить некие преобразования.
Для публикации ключевых слов имена файлов разбиваются на слова и каждое слово хешируется. Полученные хеши публикуются. Хеш можно представить в виде большого целого числа с порядком байт big endian — старшие байты по младшим адресам (в начале) или просто массивом байт.
Работа DHT основана на возможности вычисления расстояния между хешами, это позволяет последовательно приближаться к цели сокращая дистанцию. HASH_SIZE равно 128.
Просто xor:
// returns the distance between the two nodes
// using the kademlia XOR-metric
public static KadId distance(final KadId n1, final KadId n2) {
assert n1 != null;
assert n2 != null;
KadId ret = new KadId();
for(int i = 0; i < MD4.HASH_SIZE; ++i) {
ret.set(i, (byte)(n1.at(i) ^ n2.at(i)));
}
return ret;
}
Компаратор двух хешей относительно некоторого целевого хеша. Обычно целевой хеш это собственный хеш узла.
// returns -1 if: distance(n1, ref) < distance(n2, ref)
// returns 1 if: distance(n1, ref) > distance(n2, ref)
// returns 0 if: distance(n1, ref) == distance(n2, ref)
public static int compareRef(final KadId n1, final KadId n2, final KadId ref) {
for (int i = 0; i != MD4.HASH_SIZE; ++i) {
int lhs = (n1.at(i) ^ ref.at(i)) & 0xFF;
int rhs = (n2.at(i) ^ ref.at(i)) & 0xFF;
if (lhs < rhs) return -1;
if (lhs > rhs) return 1;
}
return 0;
}
Самая ходовая функция определения расстояния в K-bucket, если так можно выразиться.
// returns n in: 2^n <= distance(n1, n2) < 2^(n+1)
// useful for finding out which bucket a node belongs to
public static int distanceExp(final KadId n1, final KadId n2) {
int bt = MD4.HASH_SIZE - 1;
for (int i = 0; i != MD4.HASH_SIZE; ++i, --bt) {
assert bt >= 0;
int t = (n1.at(i) ^ n2.at(i)) & 0xFF;
if (t == 0) continue;
assert t > 0;
// we have found the first non-zero byte
// return the bit-number of the first bit
// that differs
int bit = bt * 8;
for (int b = 7; b >= 0; --b)
if (t >= (1 << b)) return bit + b;
return bit;
}
return 0;
}
Подключение к сети
Первым делом клиент генерирует свой идентификатор. Это случайный MD4 хеш (SHA1 для торрентов). Часть данных при генерации хеша может смешиваться с адресом, портом и тому подобные манипуляции для большей случайности.
Один из непонятных на первый взгляд моментов — как связан хеш узла который он себе назначил и ресурсы которые он предоставляет. Ответ — никак. Случайный выбор хеша означает что клиент в сети будет отвечать за ресурсы близкие его хешу — к нему будут приходить другие клиенты для публикации и поиска. Свои ресурсы клиент также будет публиковать на других узлах указывая себя в качестве источника.
Хотя DHT и децентрализованная сеть чтобы подключиться к ней нужно знать хотя бы один узел подключенный к сети. Зная адрес такого узла клиент посылает специальный запрос bootstrap и получает список узлов в ответ. Дальше можно рассылать bootstrap уже этим узлам и так далее. Также существуют сайты с которых можно скачать файлы с наборами узлов в формате ED2K.
Таблица маршрутизации
Таблица маршрутизации в частности предназначена для выбора нод наиболее близких некоторому хешу. Таблица содержит K-buckets. K-bucket на самом деле не более чем контейнер c структурами описывающими узел сети. Обычно таблицу иллюстрируют в виде дерева как например здесь.
Сама таблица маршрутизации может быть представлена просто листом K-bucket-ов отсортированным в порядке убывания расстояния до нашего идентификатора.
Изначально таблица не содержит ни одного K-bucket — они добавляются в процессе добавления узла.
Пусть таблица содержит такой параметр как количество уже созданных K-bucket — N(numBuckets). Номер K-bucket расчитывается используя выше упомянутую функцию distanceExp как 128 — 1 — distanceExp, более близкие нашему хешу узлы распологаются ближе к хвосту списка.
Каждый K-bucket позиции меньше чем N-2 может содержать узлы расстояние которых от нашего хеша равно n. К-bucket номер которого равен N-1 (крайний) содержит не только узлы с расстоянием n, но и все узлы расположенные ближе, проще говоря все остальные узлы. Диапазон значений n [0..127]. Понятнее это выглядит в коде функции поиска K-bucket (ниже).
Алгоритм добавления узла
- Ищем номер K-bucket для новой ноды. Проще проиллюстрировать это кодом.
public int findBucket(final KadId id) { int numBuckets = buckets.size(); if (numBuckets == 0) { buckets.add(new RoutingTable.RoutingTableBucket()); ++numBuckets; } int bucketIndex = Math.min(KadId.TOTAL_BITS - 1 - KadId.distanceExp(self, id), numBuckets - 1); assert (bucketIndex < buckets.size()); assert (bucketIndex >= 0); return bucketIndex; }
- Если K-bucket имеет свободное место — добавляем узел
- Если K-bucket не имеет свободного места — пытаемся очистить его используя метрики узлов типа последнего обновления, количество неотвеченных запросов и так далее. Если место появилось — узел добавляется
- Если K-bucket не имеет свободного места после всех попыток — пробуем разделить его. Разделение не удалось — узел игнорируется
Разделение K-bucket
K-bucket может разделиться только если это крайний контейнер и это не последний возможный K-bucket. Теоретически всего K-bucket-ов может быть 128 для MD4, но последний букет не может быть использован так-как хеши совпадающие с хешем узла не обрабатываются. Принцип простой — в текущим контейнере остаются узлы с расстоянием равным n, в новый перемещаются все остальные. Таким образом после разделения таблица вырастет на один K-bucket.
Таблица маршрутизации представляет собой лист K-bucket. K-bucket это список структур описывающих узел из сети DHT. Реализация может быть произвольной, например можно поместить все это в таблицу базы данных. Таблица не сжимается — если узлы из некоего K-bucket пропадают до полного опустошения контейнера — он останется в таблице. Узлы могут удаляться например в случае недоступности некоторое время.
Обновление таблицы
Тут нечего подробно рассматривать — обновление это внутренний процесс призванный содержать таблицу маршрутизации в актуальном состоянии. Периодически выбирается K-bucket где требуется обновление, генерируется случайный хеш принадлежащий этому K-bucket, но не совпадающий ни с одним из уже имеющихся и запускается процесс поиска. Условие начала обновления — например последнее обновление было более 15 минут назад.
Публикация и поиск
Публикация и поиск это один и тот-же процесс в конце которого выполняется либо публикация на найденных узлах либо запрос на поиск. Суть его заключается в том, чтобы последовательными итерациями приблизиться к узлам идентификатор которых близок идентификаторам искомых ресурсов. По логике сети именно эти узлы будут содержать информацию о ключевых словах и файлах хеш которых близок их хешу.
- Из таблица извлекаются первые 50 (или сколько есть) наиболее близких узлов и формируется опросный список.
- Рассылается запрос Kad2Req или попросту реквест узлов которые еще ближе чем опрашиваемый узел. Узел смотрит в свой таблице маршрутизации и формирует ответ из узлов которые ближе чем он к запрашиваемому хешу.
- Ответ помещается обратно в опросный список и все начинается сначала
- Ноды расположенные достаточно близко к цели опрашиваются на предмет наличия искомого ресурса или выполняется публикация. Существует такое понятие как tolerance zone — насколько может отличаться хеш для того чтобы имел смысл запуск прямого поиска или публикации
- Пункт 2 повторяется до достижения ограничивающих условий — найдено достаточно узлов, все опрошены и так далее
Пункт 4 представляет из себя отдельный процесс который может запускаться параллельно основному. Но в представленной реализации он запускается отдельно по окончании основного процесса.
Структура публикации ключевых слов и источников
Без лишних слов приведу структуру таблиц для хранения ключевых слов и источников. Эта структура используется в агрегаторе на отдельном хосте.
Видно что источник публикуется для некоего хеша файла один к одному. Ключевое слово же публикуется с относящимися к нему хешами файлов в названии которых оно упоминается как один ко многим. Таблицы денормализованы для удобства использования — можно было бы иметь некую таблицу ключей как мастер над sources/keywords.
create table kad.sources (
kad_id character(32) not null
, host inet not null
, port_tcp int not null default 0
, port_udp int not null default 0
, packet bytea not null
, last_update timestamp not null default current_timestamp
, total_updates int not null default 0
, source_type int not null
, constraint sources_pk primary key (kad_id, host, port_tcp, port_udp)
);
create table kad.keywords (
kad_id character(32)
, file_id character(32)
, host inet not null
, packet bytea not null
, last_update timestamp not null default current_timestamp
, total_updates int not null default 0
, constraint keywords_pk primary key(kad_id, file_id, host)
);
Видно что источник публикуется для некоего хеша файла один к одному. Ключевое слово же публикуется с относящимися к нему хешами файлов в названии которых оно упоминается как один ко многим. Таблицы денормализованы для удобства использования — можно было бы иметь некую таблицу ключей как мастер над sources/keywords.
Заключение
Несколько слов об архитектуре. Поддержка DHT реализована в отдельном трекере представляющим собой асинхронный UDP сервер работающий в выделенном треде. Он может быть запущен отдельно от клиентского приложения что удобно для тестирования. Собственно сейчас этот трекер работает в виде демона на отдельной машине. Запросы в сеть организованы в RPC вызовы через RPC менеджер — это решает задачу ограничения по времени ожидания ответа, позволяет пометить не отвечающие узлы и так далее.
Логически исходящие запросы объединены в менеджере (algorithm). Для каждого запроса создается контрольная структура (observer). Ну и все это запускается как уже упоминалось через RPC менеджер. Более подробно можно посмотреть в коде по ссылкам.
Особенность Кадемлии в том, что не всегда есть возможность точно определить ответ на какой запрос прислал хост в случае если несколько процессов работают одновременно и посылают одновременно несколько запросов одному узлу. К примеру процессы поиска узлов вполне могут пересечься и тут приходится прибегать к некоторым ухищрениям.
В торрентах более грамотная поддержка транзакций — при посылке запроса клиент посылает специальный блок transaction_id который должен быть ему возвращен. Это не только позволяет точно идентифицировать транзакцию, но и дает небольшую защиту сети.
Не стал рассматривать публикацию и поиск заметок (notes) потому что не реализовал поддержку этой возможности Кадемлии.
Надеюсь удалось изложить материал ничего не перепутав.