- PVSM.RU - https://www.pvsm.ru -
Речь пойдет о DHT на примере ее реализации известной под названием Kademlia. DHT переводится как распределенная хеш таблица и предназначена для построения децентрализованной сети обмена информацией. Все ниже изложенное работает в клиенте для ED2K сетей для платформы Android и в виде демона на линуксе. Детали реализации ниже.
Каждый узел сети имеет свой идентификатор. Кроме того любой ресурс в DHT будь то ключевое слово или файл тоже имеет идентификатор. К качестве идентификаторов используется значение хеш функции — в торрентах это MD5, в 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;
}
Для публикации ключевых слов имена файлов разбиваются на слова и каждое слово хешируется. Полученные хеши публикуются. Хеш можно представить в виде большого целого числа с порядком байт 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 хеш (MD5 для торрентов). Часть данных при генерации хеша может смешиваться с адресом, портом и тому подобные манипуляции для большей случайности.
Один из непонятных на первый взгляд моментов — как связан хеш узла который он себе назначил и ресурсы которые он предоставляет. Ответ — никак. Случайный выбор хеша означает что клиент в сети будет отвечать за ресурсы близкие его хешу — к нему будут приходить другие клиенты для публикации и поиска. Свои ресурсы клиент также будет публиковать на других узлах указывая себя в качестве источника.
Хотя DHT и децентрализованная сеть чтобы подключиться к ней нужно знать хотя бы один узел подключенный к сети. Зная адрес такого узла клиент посылает специальный запрос bootstrap и получает список узлов в ответ. Дальше можно рассылать bootstrap уже этим узлам и так далее. Также существуют сайты с которых можно скачать файлы с наборами узлов в формате ED2K.
Таблица маршрутизации в частности предназначена для выбора нод наиболее близких некоторому хешу. Таблица содержит K-buckets. K-bucket на самом деле не более чем контейнер c структурами описывающими узел сети. Обычно таблицу иллюстрируют в виде дерева как например здесь [1].
Сама таблица маршрутизации может быть представлена просто листом 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 (ниже).
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-ов может быть 128 для MD4, но последний букет не может быть использован так-как хеши совпадающие с хешем узла не обрабатываются. Принцип простой — в текущим контейнере остаются узлы с расстоянием равным n, в новый перемещаются все остальные. Таким образом после разделения таблица вырастет на один K-bucket.
Таблица маршрутизации представляет собой лист K-bucket. K-bucket это список структур описывающих узел из сети DHT. Реализация может быть произвольной, например можно поместить все это в таблицу базы данных. Таблица не сжимается — если узлы из некоего K-bucket пропадают до полного опустошения контейнера — он останется в таблице. Узлы могут удаляться например в случае недоступности некоторое время.
Тут нечего подробно рассматривать — обновление это внутренний процесс призванный содержать таблицу маршрутизации в актуальном состоянии. Периодически выбирается K-bucket где требуется обновление, генерируется случайный хеш принадлежащий этому K-bucket, но не совпадающий ни с одним из уже имеющихся и запускается процесс поиска. Условие начала обновления — например последнее обновление было более 15 минут назад.
Публикация и поиск это один и тот-же процесс в конце которого выполняется либо публикация на найденных узлах либо запрос на поиск. Суть его заключается в том, чтобы последовательными итерациями приблизиться к узлам идентификатор которых близок идентификаторам искомых ресурсов. По логике сети именно эти узлы будут содержать информацию о ключевых словах и файлах хеш которых близок их хешу.
Пункт 4 представляет из себя отдельный процесс который может запускаться параллельно основному. Но в представленной реализации он запускается отдельно по окончании основного процесса.
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) потому что не реализовал поддержку этой возможности Кадемлии.
Надеюсь удалось изложить материал ничего не перепутав.
Автор: inkpot
Источник [7]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/251768
Ссылки в тексте:
[1] здесь: https://habrahabr.ru/post/107342/
[2] Проект Mule on Android/JED2K library: https://github.com/a-pavlov/jed2k
[3] Код реализующий поддержку KAD: https://github.com/a-pavlov/jed2k/tree/master/core/src/main/java/org/dkf/jed2k/kad
[4] Пакеты относящиеся к Кадемлии: https://github.com/a-pavlov/jed2k/tree/master/core/src/main/java/org/dkf/jed2k/protocol/kad
[5] Хороший реверс Кадемлии: https://github.com/a-pavlov/libed2k/blob/master/docs/david-mysicka-1.pdf
[6] Разная документация по теме: https://github.com/a-pavlov/libed2k/tree/master/docs
[7] Источник: https://habrahabr.ru/post/325528/
Нажмите здесь для печати.