Консистентное хеширование: кольцо хешей, виртуальные узлы и код на Python

Коротко

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

Почему hash(key) % N ломается

Самый очевидный способ раскидать ключи по серверам:

server = hash(key) % N

Работает отлично, пока $N$ не меняется. Распределение равномерное, поиск за $O(1)$, никакого общего состояния. Но как только сервер добавили или он умер, у формулы поменялся делитель, и почти каждый ключ получил новый адрес.

Посчитать долю можно без кода. При переходе с $N$ на $N+1$ ключ остаётся на месте, только если $h \bmod N = h \bmod (N+1)$. На периоде длиной $N(N+1)$ таких значений $h$ ровно $N$, то есть остаётся $1/(N+1)$, а уезжает $N/(N+1)$. Чем больше кластер, тем хуже.

Проверим на миллионе ключей:

import hashlib


def ring_hash(value: str) -> int:
    """Стабильный 64-битный хеш: одинаковый во всех процессах и на всех машинах."""
    digest = hashlib.md5(value.encode()).digest()
    return int.from_bytes(digest[:8], "big")


keys = [f"user:{i}" for i in range(1_000_000)]
hashes = [ring_hash(key) for key in keys]

for old, new in [(10, 11), (10, 9), (100, 101), (10, 20)]:
    moved = sum(h % old != h % new for h in hashes)
    print(f"{old:>3} -> {new:<3} перемещено {moved / len(keys):.2%}")

 10 -> 11  перемещено 90.87%
 10 -> 9   перемещено 90.04%
100 -> 101 перемещено 99.00%
 10 -> 20  перемещено 49.97%

MD5 здесь не ради безопасности: он есть в стандартной библиотеке и хорошо перемешивает биты. В проде обычно берут что-то быстрее, вроде MurmurHash или xxHash.

Последняя строка объясняет, почему удвоение считается меньшим злом: уезжает половина. Но удваивать кластер ради одного лишнего сервера никто не будет.

Сколько это стоит

Обычная хеш-таблица переживает полное перераспределение спокойно: всё лежит в памяти одного процесса. В кластере за каждым переехавшим ключом стоит сеть или база.

Кэш. Условный пример: 100 000 запросов в секунду, равномерно по ключам, hit rate 95%. В базу приходит 5 000 RPS. Добавляем одиннадцатый сервер кэша:

• с % N сразу после смены остывает 91% ключей, в базу летит примерно 91 000 RPS, в 18 раз больше обычного;
• с кольцом остывает 9% ключей, в базу идёт примерно 13 600 RPS, в 2,7 раза больше обычного.

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

Хранилище. 3 ТБ данных на 10 узлах. С % N по сети поедет 2,7 ТБ: копирование идёт на всех узлах сразу и конкурирует с боевым трафиком. С кольцом поедет примерно 273 ГБ, и каждый старый узел отдаст всего около 27 ГБ.

Кольцо хешей

Идея из статьи Каргера и соавторов 1997 года (Consistent Hashing and Random Trees, STOC): хешировать в одно пространство и ключи, и серверы.

1. Берём диапазон значений хеша и замыкаем его в круг: за максимумом снова идёт ноль.
2. Каждый сервер получает точку на круге: hash(имя сервера).
3. Ключ принадлежит первому серверу, который встретится при движении от hash(key) по часовой стрелке.

Возьмём кольцо на 100 позиций и три сервера:

0         10                     45                  80            99 → снова 0
|---------A----------------------B-------------------C-------------|
    5           20         40        50                     90

Ключ 5 идёт к A, ключи 20 и 40 к B, ключ 50 к C. Ключ 90 проходит через конец круга и попадает на A.

Теперь добавим сервер D в точку 30. Он забирает у B только дугу от 10 до 30. Остальные сервера вообще не участвуют в операции:

from bisect import bisect_left

points, owners = [10, 45, 80], ["A", "B", "C"]
for h in (5, 20, 40, 50, 90):
    index = bisect_left(points, h)
    print(h, "->", owners[index % len(points)])

points, owners = [10, 30, 45, 80], ["A", "D", "B", "C"]
print("после добавления D на точку 30")
for h in (5, 20, 40, 50, 90):
    index = bisect_left(points, h)
    print(h, "->", owners[index % len(points)])

5 -> A
20 -> B
40 -> B
50 -> C
90 -> A
после добавления D на точку 30
5 -> A
20 -> D
40 -> B
50 -> C
90 -> A

Переехал один ключ из пяти. Вся механика поиска уложилась в две операции: бинарный поиск первой точки не меньше хеша и % len(points), который замыкает круг, когда хеш больше всех точек.

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

Виртуальные узлы

У кольца в таком виде две проблемы.

Неравномерность. Точки стоят случайно, поэтому дуги получаются разной длины. Самая длинная из $N$ дуг в среднем длиннее средней в $H_N$ раз (гармоническое число), для 10 серверов это примерно в 2,9 раза. Один сервер обрабатывает в три раза больше среднего, другой почти простаивает.

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

Решение: выдать каждому серверу не одну точку, а $V$ штук, хешируя node#0, node#1 и так далее. Сервер становится множеством мелких дуг, разбросанных по кругу. Отсюда три эффекта:

• Равномерность. Нагрузка узла становится суммой $V$ независимых случайных дуг, а относительный разброс такой суммы падает как $1/\sqrt{V}$.
• Плавный отказ. Дуги умершего сервера разъезжаются по разным соседям.
• Плавное добавление. Новый сервер забирает понемногу у всех, а не всё у одного.

Бонус: разная мощность железа решается числом точек. Сервер вдвое мощнее получает вдвое больше виртуальных узлов.

Реализация на Python

ring_hash возьмём из первого листинга. Кольцо храним как отсортированный список пар (точка, узел):

import bisect


class ConsistentHashRing:
    def __init__(self, vnodes: int = 100):
        self.vnodes = vnodes
        self._ring: list[tuple[int, str]] = []  # (точка на кольце, узел), по возрастанию

    def add_node(self, node: str, weight: int = 1) -> None:
        points = [
            (ring_hash(f"{node}#{i}"), node) for i in range(self.vnodes * weight)
        ]
        self._ring.extend(points)
        self._ring.sort()

    def remove_node(self, node: str) -> None:
        self._ring = [point for point in self._ring if point[1] != node]

    def get_node(self, key: str) -> str:
        if not self._ring:
            raise LookupError("на кольце нет узлов")
        # (h,) меньше любого (h, node), поэтому находим первую точку >= h
        index = bisect.bisect_left(self._ring, (ring_hash(key),))
        # Дошли до конца массива: кольцо замыкается на нулевой элемент
        return self._ring[index % len(self._ring)][1]

    def get_nodes(self, key: str, count: int) -> list[str]:
        """Первые count разных физических узлов по часовой стрелке: для реплик."""
        if not self._ring:
            raise LookupError("на кольце нет узлов")
        start = bisect.bisect_left(self._ring, (ring_hash(key),))
        result: list[str] = []
        for offset in range(len(self._ring)):
            node = self._ring[(start + offset) % len(self._ring)][1]
            if node not in result:
                result.append(node)
                if len(result) == count:
                    break
        return result

Как этим пользоваться:

ring = ConsistentHashRing(vnodes=100)
for name in ("cache-a", "cache-b", "cache-c"):
    ring.add_node(name)

print(ring.get_node("user:42"))  # cache-a
print(ring.get_nodes("user:42", 2))  # ['cache-a', 'cache-b']

ring.remove_node(ring.get_node("user:42"))
print(ring.get_node("user:42"))  # cache-b

Пара деталей, которые спросят на ревью:

• Сравнение идёт по кортежам, поэтому совпадение двух точек ничего не ломает: порядок определит имя узла. При 64-битном хеше такие совпадения и так почти невозможны.
• Узел, удалённый и добавленный заново, встаёт на те же точки, и его ключи возвращаются к нему. Положение зависит только от имени.
• get_nodes нужен для реплик. Просто взять следующие точки нельзя: с виртуальными узлами соседняя точка часто принадлежит тому же серверу, и две реплики окажутся на одной машине. Поэтому дубли пропускаем. Так же описан preference list в Dynamo, а в реальной системе обычно пропускают ещё и узлы из той же стойки.
• Код учебный: add_node меняет список на месте, так что параллельные чтения увидят его посреди сортировки. В проде собирают новый массив и подменяют ссылку на него одной операцией.

На моей машине поиск на кольце из 100 000 точек (100 узлов по 1000 виртуальных) занимает порядка 1–2 мкс, из них около 0,6 мкс съедает MD5. Логарифм от размера кольца на практике почти не заметен.

Замер: сколько ключей переезжает на самом деле

Теория обещает $1/(N+1)$, то есть 9,09% при переходе с 10 на 11 узлов. Проверяем, дописав к предыдущим листингам:

from collections import Counter
from statistics import mean, pstdev


def build_ring(vnodes: int, prefix: str = "node") -> ConsistentHashRing:
    ring = ConsistentHashRing(vnodes)
    for i in range(10):
        ring.add_node(f"{prefix}-{i}")
    return ring


def measure(vnodes: int, keys: list[str], prefix: str = "node") -> dict:
    ring = build_ring(vnodes, prefix)
    before = [ring.get_node(key) for key in keys]

    new_node = f"{prefix}-10"
    ring.add_node(new_node)
    after = [ring.get_node(key) for key in keys]

    changed = [(b, a) for b, a in zip(before, after) if b != a]
    load = Counter(before)
    average = len(keys) / 10
    return {
        "moved": len(changed) / len(keys),
        "to_new": sum(a == new_node for _, a in changed) / max(len(changed), 1),
        "donors": len({b for b, _ in changed}),
        "max": max(load.values()) / average,
        "min": min(load.get(f"{prefix}-{i}", 0) for i in range(10)) / average,
        "spread": pstdev(load.get(f"{prefix}-{i}", 0) for i in range(10)) / average,
    }


keys = [f"user:{i}" for i in range(1_000_000)]

print("vnodes  moved   to_new  donors  max   min   spread")
for vnodes in (1, 10, 100, 1000):
    m = measure(vnodes, keys)
    print(
        f"{vnodes:>6}  {m['moved']:.2%}  {m['to_new']:.0%}  {m['donors']:>6}"
        f"  {m['max']:.2f}  {m['min']:.2f}  {m['spread']:.1%}"
    )

# Одно кольцо ничего не доказывает: повторим на 30 наборах имён узлов
sample = keys[:100_000]
print("vnodes  moved: min    avg     max   | max/avg  spread")
for vnodes in (1, 10, 100, 1000):
    runs = [measure(vnodes, sample, f"s{seed}") for seed in range(30)]
    moved = [run["moved"] for run in runs]
    print(
        f"{vnodes:>6}  {min(moved):>10.2%}  {mean(moved):.2%}  {max(moved):.2%}"
        f" | {mean(run['max'] for run in runs):.2f}"
        f"  {mean(run['spread'] for run in runs):.1%}"
    )

Запускал на Python 3.9, всё вместе считается примерно 30 секунд. Результат одного кольца, 1 000 000 ключей, 10 → 11 узлов:

Разброс здесь: стандартное отклонение числа ключей на узел, делённое на среднее. Для сравнения, у % N на этих же данных переезжает 90,87%.

Одно кольцо показывает лишь один случайный исход: 7,71% при V = 100 не значит, что сотня лучше тысячи. Поэтому та же операция на 30 разных наборах имён узлов (100 000 ключей в каждом прогоне):

Что отсюда видно:

• Среднее держится около 9,09% при любом V. Виртуальные узлы не уменьшают число переездов. Они делают результат предсказуемым: при V = 1 новый сервер мог забрать и полпроцента ключей, и треть.
• Все переехавшие ключи ушли на новый узел. Ни один ключ не сменил старого хозяина на другого старого. Это главное свойство кольца, и оно выполняется точно, а не приблизительно.
• При V = 1 новому серверу отдаёт ключи один сосед, при V = 100 все десять.
• Разброс действительно падает как $1/\sqrt{V}$. Чтобы уменьшить его вдвое, нужно вчетверо больше точек.

Что происходит при отказе

Продолжаем в том же файле. Уберём самый загруженный узел и посмотрим, кому достанется его работа:

for vnodes in (1, 100):
    ring = build_ring(vnodes)
    before = [ring.get_node(key) for key in keys]
    load = Counter(before)

    victim = load.most_common(1)[0][0]  # убираем самый загруженный узел
    ring.remove_node(victim)
    after = [ring.get_node(key) for key in keys]

    # Ключи уходят только с убранного узла
    assert all(b == victim for b, a in zip(before, after) if b != a)

    received = Counter(a for b, a in zip(before, after) if b != a)
    neighbor, extra = received.most_common(1)[0]
    print(
        f"vnodes={vnodes}: {victim} держал {load[victim] / len(keys):.1%} ключей, "
        f"приняли узлов: {len(received)}; "
        f"{neighbor}: {load[neighbor] / len(keys):.1%} -> "
        f"{(load[neighbor] + extra) / len(keys):.1%}"
    )

vnodes=1: node-1 держал 27.8% ключей, приняли узлов: 1; node-9: 0.3% -> 28.1%
vnodes=100: node-9 держал 11.0% ключей, приняли узлов: 9; node-2: 10.0% -> 12.0%

При V = 1 единственный сосед вырос с 0,3% до 28,1% ключей. При V = 100 самый невезучий узел вырос с 10% до 12%. Первое легко превращается в каскадное падение, второе система переживает спокойно.

Вес тоже работает. Кольцо с small-1, small-2 и big с weight=2 при V = 1000 разложило миллион ключей как 24,6% / 26,2% / 49,2%. При V = 100 получилось 20,7% / 26,1% / 53,2%: на трёх серверах точек мало, и шум всё ещё заметен.

Сколько виртуальных узлов брать

Универсального числа нет, и зависит оно от того, что лежит за кольцом.

• Кэш, узел без состояния. Цена лишних точек только в памяти и времени поиска, поэтому можно брать сотни. Для примера: реализация ketama в nginx совместима с клиентами Memcached при 160 точках на сервер.
• Хранилище с репликацией. Здесь много точек вредит. У Cassandra до версии 4.0 значение по умолчанию было num_tokens: 256, в 4.0 его снизили до 16, опираясь на детерминированный алгоритм выбора токенов. Документация объясняет почему: каждый токен добавляет узлу новых соседей, поэтому растёт вероятность, что падение нескольких машин затронет какой-то диапазон данных, а заодно растёт число операций восстановления.

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

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

• Истоки. Метод появился в работе о распределённом кэшировании веба. Среди её авторов Том Лейтон и Дэниел Левин, которые вскоре основали Akamai.
• Amazon Dynamo (статья 2007 года): кольцо, виртуальные узлы, реплики на следующих разных узлах. Не путайте с DynamoDB: от Dynamo она взяла имя и опыт, а архитектура у неё своя.
• Apache Cassandra: токены на кольце, каждый узел владеет одним или несколькими.
• Клиенты Memcached с ketama и nginx: директива hash с параметром consistent.
• Envoy: балансировщик ring_hash. По документации, добавление или удаление одного хоста из N затрагивает 1/N запросов.

upstream cache {
    hash $request_uri consistent;
    server cache-1:11211;
    server cache-2:11211;
    server cache-3:11211;
}

Чем кольцо заменяют

Кольцо не единственный способ решить задачу, и упомянуть альтернативы на интервью полезно.

Hash slots стоит запомнить особенно. Это ответ на вопрос «а можно ли починить % N?»: можно, если делить не на число серверов, а на большое постоянное число, и хранить отдельную карту «слот → сервер».

Rendezvous пишется в одну строку:

def rendezvous(key: str, nodes: list[str]) -> str:
    return max(nodes, key=lambda node: ring_hash(f"{node}:{key}"))

В моём прогоне на 200 000 ключей при переходе с 10 на 11 узлов он переместил 9,11%, и все на новый узел. Поиск на 10 узлах занял около 7 мкс и дальше растёт линейно, так что на больших кластерах кольцо заметно быстрее.

Типичные ошибки

Встроенный hash() в Python. Для строк он рандомизирован на каждый запуск процесса, поэтому два сервиса построят разные кольца:

python3 -c "print(hash('user:42'))"
python3 -c "print(hash('user:42'))"   # другое число

Нужен стабильный хеш вроде MD5 или xxHash. В одном процессе ошибку не видно: тесты проходят, а проблемы начинаются, когда инстансов становится два или один из них перезапускается.

Забыть замыкание круга. Без % len(ring) любой ключ с хешем больше максимальной точки вызовет IndexError. На тестах с парой ключей это может не проявиться.

Хешировать IP вместо постоянного имени. Если под в Kubernetes перезапустился с новым адресом, его точки разлетятся по кругу, и кольцо перетасует ключи вместо того, чтобы их сохранить. Нужен стабильный идентификатор узла.

Реплики на соседних точках без проверки. Две копии окажутся на одном сервере, и отказоустойчивости не будет.

Клиенты с разной картиной кольца. Если один клиент уже знает о новом узле, а второй нет, запись и чтение разойдутся. Кольцо не решает задачу согласования состава кластера, для этого нужны gossip или хранилище конфигурации вроде etcd и ZooKeeper.

Считать, что кольцо выравнивает нагрузку. Оно выравнивает число ключей. Ключ знаменитости с 30% трафика останется на одном сервере при любом V.

Как рассказывать на system design интервью

Тема всплывает, когда в дизайне системы данные перестали помещаться на одну машину: распределённый кэш, key-value хранилище, шардирование базы, балансировка с привязкой клиента к серверу. Не начинайте с кольца сразу, покажите, откуда оно взялось. Схема на минуту:

1. Проблема. «Простое hash(key) % N равномерно, но при смене N переезжает $N/(N+1)$ ключей. Для кэша это холодный старт и удар по базе, для хранилища терабайты трафика».
2. Идея. «Кладу ключи и серверы на один круг, ключ принадлежит первому серверу по часовой стрелке. При добавлении сервера переезжает около $1/(N+1)$ ключей, и только с его соседних дуг».
3. Виртуальные узлы. «С одной точкой на сервер перекос в разы, а при отказе всё падает на соседа. Даю каждому серверу сотню точек: разброс около 10%, нагрузка при отказе расходится по всем».
4. Реализация. «Отсортированный массив точек и бинарный поиск, $O(\log(NV))$».
5. Обвязка. «Реплики на следующих разных физических узлах. Состав кластера храню в etcd или распространяю gossip».

Числа производят впечатление, если они к месту: «при переходе с 10 на 11 узлов это 9% ключей вместо 91%, на 3 ТБ это 273 ГБ вместо 2,7 ТБ».

Вопросы, которые спросят следом

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