XOR-расстояние в DHT: как биты определяют соседей

Что такое XOR-расстояние и почему это важно

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

Основы XOR: операция «найди отличия»

XOR (исключающее ИЛИ) — это бинарная операция, которая возвращает 1, если биты различаются, и 0, если они совпадают. Вот таблица истинности:

A | B | A XOR B
0 | 0 |   0
0 | 1 |   1
1 | 0 |   1
1 | 1 |   0

Теперь возьмём два ID (в реальности это 160-битные или 256-битные хеши, но для простоты используем 4 бита):

A = 1100
B = 1010
-----
    0110  (результат XOR)

Читаем 0110 как двоичное число — получаем 6. Значит, расстояние между A и B равно 6. Поздравляю, вы только что вычислили XOR-расстояние вручную!

Почему XOR можно называть «расстоянием»

Математика требует, чтобы «расстояние» удовлетворяло трём свойствам, и XOR их выполняет:

• distance(A, A) = 0 — любой ID, XORнутый сам с собой, даёт все нули. Вы находитесь на нулевом расстоянии от себя.
• Симметричность — A XOR B всегда равно B XOR A. Порядок аргументов не важен.
• Неравенство треугольника — distance(A, C) ≤ distance(A, B) + distance(B, C). Это гарантирует, что если вы переходите к узлам с меньшим XOR-расстоянием до цели, вы не застрянете в локальном минимуме.

Третье свойство — ключевое. Именно оно делает XOR-расстояние не просто математическим трюком, а инструментом, обеспечивающим сходимость маршрутизации.

Не все битовые различия равны

Многие ошибочно думают, что XOR-расстояние — это количество различающихся битов (это расстояние Хэмминга). На самом деле XOR-расстояние учитывает позицию различающихся битов, потому что читается как число. В числах левый бит важнее правого.

1000 XOR 0000 = 1000 = 8   # различие в старшем бите
0000 XOR 0001 = 0001 = 1   # различие в младшем бите

Обе пары различаются одним битом, но одна «дальше» в 8 раз. Всё из-за того, где находится различие.

Пишем код для XOR-расстояния

Хватит теории, давайте посчитаем это на Python:

def xor_distance(a: int, b: int) -> int:
    return a ^ b

def bucket_index(distance: int) -> int:
    """
    Возвращает индекс корзины для данного расстояния.
    Это индекс самого старшего установленного бита.
    Используется в Kademlia для организации таблицы маршрутизации.
    """
    return distance.bit_length() - 1 if distance else -1

A = 0b1100
B = 0b1010
C = 0b1101

print(xor_distance(A, B))  # 6  - довольно далеко
print(xor_distance(A, C))  # 1  - очень близко
print(bucket_index(xor_distance(A, B)))  # 2
print(bucket_index(xor_distance(A, C)))  # 0

Функция bucket_index — скрытая жемчужина. Она показывает, насколько далеко узлы, основываясь на длине общего префикса. Высокий индекс корзины означает, что ID почти не совпадают в начале; индекс 0 — совпадают почти во всём, кроме последнего бита. Именно так Kademlia (алгоритм, лежащий в основе BitTorrent DHT, IPFS и Ethereum) решает, кого запоминать.

Таблица маршрутизации: визуально

Каждый узел хранит несколько корзин, по одной на диапазон расстояний. В каждой корзине — несколько peers с примерно одинаковым расстоянием. Представьте это так:

• Вы детально знаете узлы, близкие к вам.
• Об узлах далёких — лишь примерное представление.

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

Как поиск узла сходится

Допустим, вы хотите найти узел, ближайший к целевому ID T, и вы ещё не там. Вы спрашиваете у самого близкого из известных вам узлов. Он, благодаря структуре корзин, знает кого-то ещё ближе к T, и передаёт вам контакт. Повторяете. Благодаря неравенству треугольника каждый шаг гарантированно уменьшает расстояние до цели. На практике сходимость достигается за O(log n) шагов, где n — число узлов в сети. Никаких GPS-координат — только математика битов.

География не имеет значения

Самое неочевидное: XOR-расстояние полностью игнорирует физическое расположение. Узел в Бангалоре и узел в Рейкьявике могут иметь крошечное XOR-расстояние, если их хеши случайно совпали по длинному префиксу. А два сервера в одной стойке могут быть максимально далеки в XOR-пространстве. Это фича, а не баг: XOR-расстояние заменяет географию на математически удобную метрику, идеальную для маршрутизации.

Где это используется

Чтобы углубиться, изучите:

• Оригинальную статью Kademlia Мэймункова и Мазьера.
• Спецификацию Kad-DHT от libp2p (используется в IPFS).
• Спецификацию Mainline DHT BitTorrent (BEP 5).
• Спецификацию discv5 от Ethereum.

Практический вывод

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

Что делать прямо сейчас: напишите функцию xor_distance и bucket_index на Python, поэкспериментируйте с разными ID. Затем попробуйте реализовать простую симуляцию поиска узла, используя эти функции. Это закрепит понимание на практике.