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

Ресурс

В Кадемлии для публикации файла берется хеш используемый в самой сети 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;
}

Работа 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;
}

// 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;
}

Подключение к сети

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

Хотя DHT и децентрализованная сеть чтобы подключиться к ней нужно знать хотя бы один узел подключенный к сети. Зная адрес такого узла клиент посылает специальный запрос bootstrap и получает список узлов в ответ. Дальше можно рассылать bootstrap уже этим узлам и так далее. Также существуют сайты с которых можно скачать файлы с наборами узлов в формате ED2K.

Таблица маршрутизации

Сама таблица маршрутизации может быть представлена просто листом 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 это список структур описывающих узел из сети DHT. Реализация может быть произвольной, например можно поместить все это в таблицу базы данных. Таблица не сжимается — если узлы из некоего K-bucket пропадают до полного опустошения контейнера — он останется в таблице. Узлы могут удаляться например в случае недоступности некоторое время.

Обновление таблицы

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

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

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)
);

Заключение

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

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

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

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

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

Ссылки

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

Комментарии (0)