Kademlia DHT: как работает распределённая сеть

Вы когда-нибудь задумывались, как BitTorrent находит пиров без центрального трекера? Или как IPFS и Ethereum обнаруживают друг друга в децентрализованной сети? Ответ — алгоритм Kademlia, распределённая хеш-таблица (DHT), которая лежит в основе этих систем. В этой статье мы разберём, как Kademlia использует XOR-дистанцию для построения маршрутизации и поиска данных за O(log n) шагов. Вы узнаете, что такое k-buckets, как работает итеративный поиск и почему этот алгоритм так устойчив к сбоям.

Проблема: поиск в сети без центрального сервера

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

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

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

Маршрутизация: k-buckets

Вчера мы разобрали XOR-дистанцию — метрику, которая ведёт себя как расстояние. Сегодня посмотрим, как она применяется на практике. Каждый узел хранит таблицу маршрутизации, разделённую на «buckets» (корзины). Bucket i хранит узлы, чьё XOR-расстояние до текущего узла находится в диапазоне [2^i, 2^(i+1)).

Проще говоря: bucket 0 содержит узлы, отличающиеся от вас только последним битом, а самый старший bucket — узлы, почти не имеющие с вами общих битов. Вместимость каждого bucket обычно ограничена (например, 20 узлов).

class KBucket:
    def __init__(self, capacity=20):
        self.capacity = capacity
        self.peers = []  # недавно виденные — в конце

    def add(self, peer):
        if peer in self.peers:
            # узел уже известен — перемещаем в конец (самый свежий)
            self.peers.remove(peer)
            self.peers.append(peer)
        elif len(self.peers) < self.capacity:
            self.peers.append(peer)
        else:
            # bucket полон: пингуем самый старый узел (в начале списка)
            # если он жив — оставляем его, новый не добавляем
            # если мёртв — удаляем его и добавляем новый
            pass  # обработка проверки живости происходит отдельно

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

Обратите внимание на асимметрию: нижние buckets покрывают крошечный диапазон ID, поэтому там мало узлов, и вы знаете их очень хорошо. Верхние buckets покрывают огромный диапазон, поэтому вы храните лишь небольшую выборку, а не пытаетесь знать всех.

Поиск: итеративный lookup

Допустим, вы хотите найти узел, ближайший к некоторому целевому ID. Вы не спрашиваете одного и не надеетесь. Kademlia параллельно опрашивает alpha узлов (обычно 3) и повторяет цикл: спрашивает текущих кандидатов, кого они знают ещё ближе, добавляет новые ответы и повторяет, пока никто не сможет предложить более близкий узел.

def find_node(target_id, initial_peers, alpha=3):
    shortlist = sorted(initial_peers, key=lambda p: xor_distance(p.id, target_id))
    contacted = set()

    while True:
        to_query = [p for p in shortlist[:alpha] if p not in contacted]
        if not to_query:
            break  # некого спрашивать — сошлись

        for peer in to_query:
            contacted.add(peer)
            new_peers = peer.query_closer_nodes(target_id)
            shortlist.extend(new_peers)

        shortlist = sorted(set(shortlist), key=lambda p: xor_distance(p.id, target_id))[:20]

    return shortlist

Благодаря неравенству треугольника, о котором мы говорили вчера, этот цикл гарантированно монотонно приближается к цели. Никаких тупиков и зацикливаний. Обычно поиск сходится за O(log n) шагов для сети из n узлов — именно поэтому Kademlia масштабируется до миллионов пиров без сбоев.

Где это применяется

Один и тот же базовый алгоритм используется в разных проектах:

BitTorrent Mainline DHT (BEP 5) — поиск пиров без центрального трекера.
IPFS / libp2p — поиск узлов, хранящих определённый контент.
Ethereum discv5 — обнаружение других узлов Ethereum.

Особый интерес представляет Ethereum Swarm. Вместо простого XOR-расстояния Swarm группирует узлы в «окрестности» на основе общего префикса битов (это называется порядок близости, Proximity Order). Вся окрестность коллективно отвечает за хранение одних и тех же фрагментов данных. Это переосмысление идеи маршрутизации Kademlia для назначения хранилища, а не только для поиска.

Swarm также использует «пересылающую Kademlia» вместо классической «итеративной». В итеративном режиме вы лично опрашиваете каждый более близкий узел, и ответ возвращается напрямую вам. В пересылающем режиме каждый узел передаёт запрос следующему более близкому, а ответ возвращается по той же цепочке. Это даёт анонимность: никто в цепочке (кроме первого узла) не знает, кто инициировал запрос. Бесплатная анонимность как побочный эффект маршрутизации.

Практический вывод: что делать прямо сейчас

Теперь, когда вы знаете, как работает Kademlia, попробуйте реализовать простую DHT на Python. Начните с классов Node и KBucket, затем напишите функцию find_node. Это отличное упражнение для понимания распределённых систем. Если хотите углубиться, изучите спецификации BEP 5 или discv5 и попробуйте воспроизвести их поведение в учебном проекте. Не бойтесь экспериментировать — так вы лучше поймёте, как работает одна из самых важных алгоритмических основ современного интернета.

Kademlia DHT: как работает распределённая сеть