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

    Речь пойдет о DHT на примере ее реализации известной под названием Kademlia. DHT переводится как распределенная хеш таблица и предназначена для построения децентрализованной сети обмена информацией. Все ниже изложенное работает в клиенте для ED2K сетей для платформы Android и в виде демона на линуксе. Детали реализации ниже.

    Ресурс


    Каждый узел сети имеет свой идентификатор. Кроме того любой ресурс в 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 (ниже).

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


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

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

    Заключение


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

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

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

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

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

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

    Ссылки


    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 16

      0
      Честно говоря ничего не понял. Ну присвоили мы узлам какие-то id-хеши, а что дальше? Нам же надо получить их ip адреса, допустим скачали мы таблицу маршрутизации с bs ноды и нашли там нужный хеш, взяли оттуда ip, это просто, а если этого узла ещё нет в списке, что делать? Ну вычислим мы «расстояние», а как оно поможет нам узнать его ip?
        +1
        Не случайно длина хеша документа совпадает с длиной ID ноды.

        На пальцах. Пусть мой ID — ab12, я публикую документ 871e.

        Для публикации я опрашиваю топ 10 известных пиров, с адресом, ближайшим к 871e.
        Например, у меня в списке пир 8022, я его спрашиваю — кого ты знаешь максимально близкого к 871e? Он отвечает — это пир 87a0. Я отправляю пиру 87a0 инфмацию что у меня, у ab12, есть документ 871e.

        Аналогично пиру ab15 (как и всем из топ-10 наиболее близких к моему ab12), я отправляю свой IP/порт.

        Если кто-то ищет документ 871e, он спрашивает у топ-10 пиров, с адресом, наиболее близким к 871e, какие есть пиры, с ID, ещё ближе расположенным к 871e. Например, пир 5611 скажет, что ближе — 77a1, а 77a1 — скажет, что 87a0 (процес движения к хешу по пирам повторяется N итераций, обычно N=3 достаточно).

        Дальше, пир 87a0 отвечает этому клиенту, что документ 871e есть у пира ab12. Он запускает аналогичный поиск, но уже не хешу, а по ID пира. Так он натыкается либо сразу на ab12, либо на «соседа» ab15, который сообщит IP-адрес пира ab12.
          0
          Благодарю, это уже понятнее.

          > Например, у меня в списке пир 8022, я его спрашиваю — кого ты знаешь максимально близкого к 871e? Он отвечает — это пир 87a0. Я отправляю пиру 87a0 инфмацию что у меня, у ab12, есть документ 871e.

          а как определяется что пора прекратить искать ближайший к 871e и уже передать информацию о документе?
          Пир 87a0 должен сказать что более близких нет?
            +1
            87a0 может отдать 2 списка:

            1) список известных ему пиров, наиболее близких к искомому ID

            2) список известных пиров-владельцов файла с искомым хешем (посколько он хранит файлы, наиболее близкие к его ID, у него и имеет смысл спрашивать владельцев этих файлов)

            Причём, 87a0 знает, что владелец файла — ab12, но не хранит его IP, т.к. факт владения — долгосрочная информация, а текущий IP — краткосрочная. Пира ab12 нужно искать по его соседям, у них наиболее достоверная инфа по IP, т.к. они друг друга периодически пингуют.

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

                  Итерация 1 — опрашиваем пиров из своих k-buckets с ID, ближайшим к искомому хешу. При этом, возможно, мы уже получим владельцев искомого файла. Остаётся только соединиться с ними и запросить файл.

                  Итерация i+1 — опрашиваем пиров с ID, полученными от ответов итерации i, но не опрошенных ранее

                  Выполняем S раз (S — константа глубины поиска)
                  0
                  а как определяется что пора прекратить искать ближайший к 871e и уже передать информацию о документе?
                  Ступил, вопрос по публикации, а я продолжаю про поиск )))
                  Публикация и поиск — симметричные процессы. Поэтому всё вышеописанное к публикации тоже относится.
                0
                Не понял что вы имеете ввиду под присвоили узлам хеши и скачали таблицу маршрутизации.
                Хеш или свой идентификатор вы сами себе выбираете случайно ну или не случайно. Скачать можно список узлов — это просто список структур типа ip адрес + udp порт + хеш.
                Подобный список можно получить зная адрес и порт подключенного к сети узла.
                Собственно как ниже и расписали процесс поиска это по сути два параллельных процесса — ищем новые узлы которые ближе искомому хешу опрашивая уже известные узлы и добавляя их ответы в список опроса и выполняем запрос ресурса на узлах которые достаточно близко к искомому хешу(tolerance zone).

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

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

                Например всем кто в опросном списке рассылаем Kad2Req, a тем кто еще и достаточно близко к искомому хешу дополнительно Kad2SearchKeysReq.
                0
                в торрентах это MD5
                В торрентах SHA1.
                  0
                  Спасибо за уточнение, действительно SHA1.
                  0
                  А кто-нибудь может рассказать об отравлении DHT?
                  Типа берем намеренно себе хэш, который максимально близок к хэшу некоторого контента, потом под видом того, что мы знаем где контент хранится выдавать неверные хэши тем, кто за контентом к нам придет?
                    0
                    На каждой итерации поиска запрос рассылается N нодам, максимально близким к хешу.

                    Для StrongDC++ значение N=50.

                    Как минимум, надо держать 50 фальшивых нод, но клиенты случайно могут выйти на нефальшивые, достаточно близкие к искомому хешу, но не совсем близкие к искомому хешу.

                    Конечно, на одном IP можно держать хоть 10000 нод на разных портах, если написать соответствующий софт.

                    Однако, это заблочит только один хеш. Мой опыт файлообмена говорит о том, что у крупных релизов бывает по 10-15 альтернатив для фильмов с разными хешами (разные рипы, разные вложены файлы), 3-8 альтернатив для игр. Так что, если один хеш плохо качается, в сети появится другой.
                      0
                      На одном IP не получится держать много нод, ну как минимум без ухищрений. Была идея поднять в облаке супер ноду как-раз с кучей кад клиентов каждый на своем порту — но облом, узел идентифицируется по IP — если порт не совпадает то узел апдейтится, а не добавляется. Конечно можно хеши выбрать сильно разные и теоретически пересечения не произойдет.
                        0
                        Интересно, я изучал DHT в DC++, там тоже заявлен алгоритм Kademlia. Но есть небольшие различия вроде вышеупомянутого (в dc клиент определяется по ip/port), а также там превосходно реализована защита от фильтрации протокола DPI-системами (все пакеты шифруются).

                        Но зато там нет поиска по словам, только по хешам файлов.
                      0
                      По ссылке «Хороший реверс Кадемлии» pdf в котором в конце рассматривается вариант отравления сети KAD.

                    Only users with full accounts can post comments. Log in, please.