DHT

Узлы Tycho знают друг друга по криптографическим идентификаторам, но чтобы установить соединение, нужен сетевой адрес. Адреса меняются, а центрального справочника в децентрализованной сети нет. Эту задачу решает DHT — распределённая хеш-таблица, через которую узлы публикуют подписанные записи о себе и находят друг друга. Реализация Kademlia-подобная, с собственным протоколом сообщений на TL-схеме.

Распределённый справочник контактов

Задача — по идентификатору узла получить его актуальную контактную информацию. Держать полный справочник «идентификатор → адрес» на каждом узле нельзя, как нельзя и назначить для этого выделенный сервер-справочник. Остаётся распределить справочник по самим участникам: каждый хранит небольшой фрагмент, а правило «у кого какой фрагмент» известно всем заранее и вычисляется из ключа.

Такое правило требует меры близости между ключом и узлом, который его хранит. С неё и начинается устройство DHT.

Адресное пространство и XOR-метрика

Идентификаторы узлов и хеши ключей значений живут в одном 256-битном адресном пространстве, поэтому расстояние измеряется не только между узлами, но и между узлом и ключом. Расстояние между двумя идентификаторами — это позиция старшего различающегося бита их XOR, число от 0 до 256. Чем длиннее общий префикс битов, тем ближе идентификаторы.

Идентификатор узла — это и есть его публичный ключ ed25519: те же 32 байта, скопированные побайтово. Обратно ключ восстанавливается разбором этих же байтов, но восстановление может и не удаться: не всякий 32-байтный набор является корректной точкой кривой, и тогда идентификатор непригоден для проверки подписи. На этом совпадении держится вся конструкция. Получатель подписанной записи берёт публичный ключ прямо из идентификатора в ключе значения и проверяет подпись, не обращаясь ни к какому реестру: подделать запись под чужим идентификатором нельзя. Заодно и сам идентификатор не выбрать произвольно, не имея секретного ключа, так что распределение идентификаторов по адресному пространству остаётся равномерным.

Метрика превращает поиск в навигацию. Узел опрашивает известных ему участников, ближайших к целевому ключу, получает в ответ ещё более близких кандидатов и на каждом шаге сужает поиск, пока не доберётся до цели. Навигация работает, только если у узла есть с чего начинать — локальный запас известных участников на разных дистанциях. За этот запас отвечает таблица маршрутизации.

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

Таблица маршрутизации группирует известные узлы в бакеты по XOR-дистанции от собственного идентификатора: для каждой дистанции от 1 до 256 предусмотрен отдельный бакет ёмкостью K узлов. Бакеты создаются лениво, только когда на этой дистанции появляется первый узел. Схема фиксированная — один бакет на дистанцию, без разбиения бакетов.

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

Качество таблицы держится на двух правилах.

• Живой узел не вытесняется. При добавлении узла в бакет возможны три исхода. Запись с таким же идентификатором уже есть: она обновляется. В бакете есть свободный слот: узел занимает его. Бакет полон — новый узел встаёт только на место самого старого и только если тот устарел: истёк срок его контактной информации или запись давно не обновлялась. Полный бакет из живых узлов новых записей не принимает. Так проверенные долгоживущие контакты защищены от вытеснения свежими, в том числе при попытке заспамить таблицу.
• Узел не хранит сам себя. Попытка добавить запись с собственным идентификатором отклоняется: дистанция до самого себя равна нулю, а бакета с нулевой дистанцией не существует. Проверка продублирована на уровне DHT-сервиса, а в поисковых запросах кандидат с собственным идентификатором явно пропускается. Без этого узел отвечал бы сам себе при поиске.

Таблица отвечает на вопрос, кого спрашивать. Дальше начинается сам поиск.

Поиск значения

Поиск получает на вход ключ и возвращает значение, найденное у любого из опрошенных узлов. Он стартует с K ближайших к ключу узлов из локальной таблицы маршрутизации и идёт волнами параллельных запросов: одновременно их не больше 10. Ответ «не найдено» тоже полезен — вместе с ним приходит список узлов, ещё более близких к ключу. Они пополняют множество кандидатов, и опрос продолжается.

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

Публикация значения

Публикация значения — это локальная вставка плюс одна рассылка ближайшим узлам. Узел сначала кладёт значение в собственное хранилище, затем берёт из своей таблицы маршрутизации K узлов, ближайших к хешу ключа, и отправляет каждому запрос на сохранение. Рассылка идёт не более чем в 10 параллельных запросов, каждый со своим таймаутом. Итеративного поиска более близких узлов при публикации нет: множество получателей определяется один раз по локальному знанию и в ходе рассылки не расширяется. Поэтому качество публикации напрямую зависит от того, насколько полна локальная таблица маршрутизации в нужном диапазоне дистанций.

Публикация считается успешной по локальной вставке, а не по ответам сети. Ошибка вернётся вызывающему только в одном случае: если значение не принято собственным хранилищем узла. Рассылка дожидается завершения всех запросов, но её итог не агрегируется — отказ узла и таймаут попадают в лог предупреждением, успешное сохранение в отладочный лог. Ни счётчика подтверждений, ни минимального кворума копий, ни повторной отправки отказавшим узлам нет.

Успешная публикация не означает, что значение доступно в сети: оно может лежать только на узле-издателе, и при диагностике это стоит держать в уме. Не подтверждения компенсируют слабую гарантию, а периодический повтор публикации и то, что издатель сам отвечает на поиск этого значения.

Виды значений

DHT хранит значения двух видов, различающихся тем, кто контролирует ключ.

Подписанные владельцем ключа. Ключ — «имя + идентификатор узла». Только владелец этого идентификатора может опубликовать такое значение: подпись ed25519 проверяется при приёме. Подменить чужую запись, не владея ключом узла, нельзя. Так публикуется контактная информация узла.

Групповые. Ключ — «имя + идентификатор группы», и значение не привязано к одному узлу, но объединения вкладов разных узлов в версии 0.3.11 не происходит. Обработчик слияния решает, что делать с приходящим значением: его регистрирует потребитель DHT-сервиса под конкретный идентификатор группы. Единственная рабочая реализация такого обработчика ничего не сливает: она принимает только локально сформированное значение и целиком заменяет им предыдущее, а всё пришедшее по сети отвергает как значение из недопустимого источника. Слияние в названии механизма описывает возможность интерфейса, а не поведение этой реализации. Значение для группы без зарегистрированного обработчика молча игнорируется.

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

Сетевой рассылки у групповых значений нет. Издатель кладёт снимок только в собственное хранилище, а другие узлы получают его, когда обычный поиск по хешу ключа группы доходит до узла-издателя и тот отвечает своей локальной копией.

Правила хранилища

Принимая значение, хранилище проверяет срок: уже истёкшее отклоняется с ошибкой, как и то, у которого остаток срока больше потолка хранилища. Подписанное значение с уже существующим ключом заменяется только если новое истекает позже сохранённого, иначе вставка молча пропускается. Правило «заменять только более свежим» закрывает атаку отката: перезаписать чужую запись менее свежими данными злоумышленник не может.

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

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

Фоновые механизмы

Фоновый цикл DHT-сервиса выполняет по расписанию четыре действия: обновляет локальную копию информации об узле, анонсирует её в сеть, обновляет таблицу маршрутизации и пополняет таблицу бутстрап-пирами. Последнее работает, только если перезаливка включена. Пятое действие расписанием не управляется: разобрав очередь анонсов, цикл проверяет подпись и срок пришедшей контактной информации и при успехе добавляет узел в таблицу маршрутизации.

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

Анонс собственной контактной информации

Узел периодически подписывает актуальную информацию о себе — идентификатор, адреса, срок действия — и сохраняет её в DHT как значение с ключом «NodeInfo + собственный идентификатор». По этим записям другие узлы и находят адрес узла по его идентификатору. Период анонса, случайная задержка к нему и срок жизни публикуемой записи конфигурируются. Локальная копия информации об узле обновляется чаще, отдельным периодом.

Обновление таблицы маршрутизации

Анонс работает в одну сторону: узел сам напоминает о себе. Его дополняет встречный механизм — разведка. Фоновая задача сначала вычищает из таблицы устаревшие узлы. Затем она берёт непустые бакеты, не больше 15 за раз, и для каждого генерирует случайный идентификатор на дистанции этого бакета и запускает поиск узлов вокруг него. Одновременно идёт не больше 3 поисков, каждый глубиной 3 итерации. Найденные узлы добавляются в таблицу, при дублях побеждает более свежая информация об узле. Период запуска и случайная задержка к нему здесь конфигурируются.

Перезаливка бутстрап-пиров

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

При запуске фоновых задач DHT каждая запись списка обязана быть полностью корректной, с верной подписью и неистёкшим сроком действия, иначе запуск завершается ошибкой. Дальше список периодически вливается в таблицу маршрутизации заново, и здесь просроченная контактная информация уже допускается. Расчёт на долгую работу узла: статический список со временем неизбежно устаревает, но по старым адресам всё ещё можно постучаться и получить свежие данные. Так узел восстанавливает связь с бутстрап-пиром, чья запись устарела после старта или которого вытеснили из таблицы. Подпись и срок проверяются один раз при запуске, путь перезаливки запись не перепроверяет, и гарантия корректности держится на неизменности проверенного при старте списка. Периодическую перезаливку можно отключить.

Резолвер узлов

Итеративный поиск отвечает на разовый вопрос: где сейчас находится узел. Некоторым подсистемам адрес конкретного узла нужен постоянно, например адрес участника приватного оверлея, с которым нужно поддерживать связь. Для них поверх DHT работает резолвер узлов: подсистема получает подписку, и пока подписка жива, фоновая задача периодически ищет свежую запись контактной информации в DHT и обновляет её заранее, до истечения срока. Неудачные попытки повторяются с экспоненциальной задержкой — несколько быстрых повторов, затем редкие с фиксированным интервалом.

Задачи дедуплицируются по идентификатору узла, поэтому несколько подписок на один узел разделяют одну задачу. Число одновременных обновлений ограничено, все интервалы конфигурируются. Для забаненного узла задача останавливается.

Интерфейс DHT-сервиса

Со стороны сети DHT-сервис принимает четыре вида входящих обращений.

Запрошенное количество узлов ограничено сверху собственным K узла: больше клиент не выпросит. Некорректные запросы молча игнорируются, без ответа об ошибке. Любое обращение может быть обёрнуто префиксом с контактной информацией отправителя: сервис проверяет, что она принадлежит именно отправителю, и передаёт её в фоновую задачу для добавления в таблицу маршрутизации. Так даже входящий трафик пополняет знание узла о сети. Передача идёт через очередь ограниченной ёмкости, и обработка запроса никогда не ждёт в ней места: при переполнении очереди самые старые ещё не разобранные анонсы теряются, а запросы обслуживаются с прежней скоростью.

Бан узла и его следствия для DHT

Забаненный узел выпадает из работы DHT в двух местах: итеративные запросы его пропускают, а задача резолвера для него останавливается. Сам бан к DHT не относится — реестр известных узлов на уровне сетевого транспорта ставит пометку, и DHT лишь считается с ней.

Пометка не снимается по команде: операции явного снятия бана нет. У узла с живыми подписками бан действует ровно пока жива хотя бы одна из них, и после освобождения последней узел снова считается незабаненным. Только надгробная запись переживает освобождение подписок — в неё превращается узел, забаненный без живых подписок.

В версии 0.3.11 бан реализован, но рабочими узлами не вызывается.

Метрики и диагностика

Наблюдаемость DHT ограничена входящей стороной. Все метрики — монотонные счётчики входящих запросов с общим префиксом tycho_net_dht_in_req_, ровно семь штук, и все выведены в генерируемый Grafana-дашборд отдельной строкой:

• tycho_net_dht_in_req_total — общее число входящих запросов;
• tycho_net_dht_in_req_fail_total — число неудачно обработанных;
• tycho_net_dht_in_req_with_peer_info_total — число запросов с приложенной контактной информацией отправителя;
• tycho_net_dht_in_req_find_node_total — метод «поиск узлов»;
• tycho_net_dht_in_req_find_value_total — метод «поиск значения»;
• tycho_net_dht_in_req_get_node_info_total — метод «запрос своей записи»;
• tycho_net_dht_in_req_store_value_total — метод «сохранение значения».

Тип каждой — монотонный счётчик, поэтому в запросах Grafana такие имена обычно оборачивают в rate(...).

Исходящая активность и состояние узла метриками не покрыты. Итеративные поиски, рассылка значений, обновление таблицы маршрутизации и перезаливка бутстрап-пиров не считаются никак. Размер таблицы маршрутизации, заполненность бакетов и число записей в хранилище значений через метрики оператору недоступны. О них судят по общим сетевым метрикам транспорта и по логам фоновых задач уровня debug: там видно, сколько новых узлов найдено при обновлении таблицы и сколько бутстрап-пиров перезалито.

О переполнении очереди анонсов сообщает предупреждение announced peers channel lagged с числом пропущенных записей. Оно означает, что фоновая задача не успевает разбирать очередь, приложенная к запросам контактная информация теряется и узел медленнее узнаёт о новых участниках. Обработка самих запросов при этом не замедляется. Лечится увеличением announced_peers_channel_capacity.

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

Ручная диагностика сводится к одной команде управления — dht find-node. Команда обращается к работающему узлу через контрольный сокет и просит вернуть не более k узлов, ближайших к заданному хешу ключа. Без дополнительных параметров узел отвечает из собственной таблицы маршрутизации, ничего не спрашивая по сети. Если указан идентификатор целевого узла, узел вместо этого шлёт ему обычный DHT-запрос поиска узлов и возвращает ответ. Результат печатается как JSON со списком контактной информации найденных узлов.

Так одной командой можно заглянуть в локальную таблицу маршрутизации и проверить, что удалённый узел отвечает на DHT-запросы и знает нужный участок пространства ключей. Команда доступна, только если контрольный сервер собран с DHT-клиентом. Других средств диагностики DHT нет — посмотреть содержимое хранилища значений, список бакетов или статистику итеративных поисков нельзя.

Конфигурация

Параметры DHT задаются в локальном конфиге узла, в секции dht рядом с секциями сетевого транспорта, резолвера узлов и оверлеев. Секция целиком опциональна, при её отсутствии применяются значения по умолчанию. Разделение с глобальной конфигурацией сети принципиальное: список бутстрап-пиров есть только в глобальном файле, параметры DHT — только в локальном. Поэтому настройки DHT нельзя навязать узлу извне, а список бутстрап-пиров не задать в обход общего для сети файла.

Значения по умолчанию секции dht:

Значение из колонки «По умолчанию» пишется в конфиг ровно так, как приведено, включая кавычки. Десять интервальных полей записываются строкой вида "1m" или "500ms" — число вместо строки в них не принимается вовсе. Внутри строки допустима любая эквивалентная запись того же интервала: "1h", "60m" и "3600s" равнозначны. Целыми числами здесь заданы только max_k и announced_peers_channel_capacity. Литерал null принимают storage_item_time_to_idle и bootstrap_peers_refill_period, и только они: у остальных полей отключающего значения нет.

У ёмкости хранилища свои правила: max_storage_capacity записывается либо строкой размера, либо целым числом байт. В таблице приведена точная форма — "16 MiB", то же самое можно записать как 16777216. Сам узел при выводе конфига печатает это значение как "16.8 MB", потому что использует десятичные приставки: обратно такая строка читается как 16 800 000 байт, а не как исходные 16 777 216. Скопированное из вывода значение поэтому слегка отличается от значения по умолчанию.

Резолвер узлов настраивается своей секцией peer_resolver. Она лежит на верхнем уровне локального конфига узла, рядом с network, dht и overlay, и тоже опциональна целиком: отсутствующая секция и отсутствующее поле берут значение по умолчанию.

Форма записи в этой секции различается по полям, и значение из колонки «По умолчанию» копируется в конфиг дословно. Первые четыре параметра записываются целыми числами, а оставшиеся четыре интервальных — строкой вида "1s" или "10m". Число вместо строки в интервальном поле не принимается.

Имя min_successfull_resolve_interval содержит опечатку — два l в successfull. Это часть ключа конфига, писать его нужно ровно так.