Kademlia (DHT) — практическое руководство

Речь пойдет о 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 структурами описывающими узел сети. Обычно таблицу иллюстрируют в виде дерева как например здесь.

Сама таблица маршрутизации может быть представлена просто листом 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 (ниже).

Алгоритм добавления узла

1. Ищем номер 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;
   }
   

2. Если K-bucket имеет свободное место — добавляем узел
3. Если K-bucket не имеет свободного места — пытаемся очистить его используя метрики узлов типа последнего обновления, количество неотвеченных запросов и так далее. Если место появилось — узел добавляется
4. Если 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 минут назад.

Публикация и поиск

Публикация и поиск это один и тот-же процесс в конце которого выполняется либо публикация на найденных узлах либо запрос на поиск. Суть его заключается в том, чтобы последовательными итерациями приблизиться к узлам идентификатор которых близок идентификаторам искомых ресурсов. По логике сети именно эти узлы будут содержать информацию о ключевых словах и файлах хеш которых близок их хешу.

1. Из таблица извлекаются первые 50 (или сколько есть) наиболее близких узлов и формируется опросный список.
2. Рассылается запрос Kad2Req или попросту реквест узлов которые еще ближе чем опрашиваемый узел. Узел смотрит в свой таблице маршрутизации и формирует ответ из узлов которые ближе чем он к запрашиваемому хешу.
3. Ответ помещается обратно в опросный список и все начинается сначала
4. Ноды расположенные достаточно близко к цели опрашиваются на предмет наличия искомого ресурса или выполняется публикация. Существует такое понятие как tolerance zone — насколько может отличаться хеш для того чтобы имел смысл запуск прямого поиска или публикации
5. Пункт 2 повторяется до достижения ограничивающих условий — найдено достаточно узлов, все опрошены и так далее

Пункт 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)
);

Заключение

Несколько слов об архитектуре. Поддержка DHT реализована в отдельном трекере представляющим собой асинхронный UDP сервер работающий в выделенном треде. Он может быть запущен отдельно от клиентского приложения что удобно для тестирования. Собственно сейчас этот трекер работает в виде демона на отдельной машине. Запросы в сеть организованы в RPC вызовы через RPC менеджер — это решает задачу ограничения по времени ожидания ответа, позволяет пометить не отвечающие узлы и так далее.

Логически исходящие запросы объединены в менеджере (algorithm). Для каждого запроса создается контрольная структура (observer). Ну и все это запускается как уже упоминалось через RPC менеджер. Более подробно можно посмотреть в коде по ссылкам.

Особенность Кадемлии в том, что не всегда есть возможность точно определить ответ на какой запрос прислал хост в случае если несколько процессов работают одновременно и посылают одновременно несколько запросов одному узлу. К примеру процессы поиска узлов вполне могут пересечься и тут приходится прибегать к некоторым ухищрениям.

В торрентах более грамотная поддержка транзакций — при посылке запроса клиент посылает специальный блок transaction_id который должен быть ему возвращен. Это не только позволяет точно идентифицировать транзакцию, но и дает небольшую защиту сети.

Не стал рассматривать публикацию и поиск заметок (notes) потому что не реализовал поддержку этой возможности Кадемлии.

Надеюсь удалось изложить материал ничего не перепутав.

Ссылки

• Проект Mule on Android/JED2K library
• Код реализующий поддержку KAD
• Пакеты относящиеся к Кадемлии
• Хороший реверс Кадемлии
• Разная документация по теме

Автор: inkpot

Источник