Consistent hashing: как распределять данные по узлам без полного пересчёта

Прямой ответ

Consistent hashing — схема распределения ключей по узлам, при которой добавление или удаление узла перемещает лишь небольшую часть данных (примерно K/N, где K — число ключей, N — число узлов), а не почти всё, как при наивном hash(key) % N.

Как устроено кольцо:

1. И узлы, и ключи отображаются хеш-функцией в одно пространство — например, в 128-битные значения (Murmur3 в Cassandra).
2. Значения мысленно располагаются по кругу от 0 до 2^128 - 1.
3. Ключ принадлежит первому узлу, который встречается при обходе кольца по часовой стрелке от значения ключа.
4. При удалении узла его диапазон переходит следующему по часовой стрелке; остальные диапазоны не меняются.

Виртуальные узлы (vnodes). Реальные узлы представлены многими точками на кольце (в Cassandra — токенами, в Redis Cluster — 16384 слотами). Это решает две проблемы: равномерность распределения данных при малом числе узлов и пропорциональность нагрузки при разнородном железе.

Отличия от классического шардинга:

• В шардировании с фиксированным маппингом соответствие «ключ → шард» задаётся таблицей или формулой, и изменение топологии требует управляемой миграции.
• Consistent hashing задаёт соответствие вычислением, поэтому топологию можно менять постепенно, а клиенты могут вычислять целевой узел самостоятельно, зная состояние кольца.

Практическое следствие: клиенту нужна актуальная карта кольца. В Cassandra её получают через system.local/system.peers и контрольный протокол, в Redis Cluster — через CLUSTER SLOTS/CLUSTER SHARDS, а рассинхронизация карты приводит к MOVED/REDIRECT-ответам. Распространение информации о топологии обычно выполняет gossip.

Практика: раскладка данных и настройка

Cassandra: токены и vnodes.

-- число виртуальных узлов на узел (Cassandra 4.x, по умолчанию 16)
-- задаётся в cassandra.yaml
num_tokens: 16

-- посмотреть распределение диапазонов
nodetool ring
nodetool status
-- оценить, сколько данных придётся переместить
nodetool decommission --help   # выводит оценку перед выводом узла

Рекомендации:

1. Не ставьте слишком большое num_tokens. Много токенов выравнивает данные, но увеличивает объём метаданных и время восстановления/стриминга при замене узла.
2. Одинаковое железо — одинаковые токены. Разные размеры токенов для разных узлов оправданы только при сознательном взвешивании нагрузки.
3. Планируйте операцию заранее. decommission/bootstrap перемещают данные потоково; запуск без учёта ёмкости диска приводит к заполнению и отказу записи.

Redis Cluster: слоты. Пространство делится на 16384 слота, слоты назначаются узлам; при миграции слот перемещается явно, а клиенты получают MOVED/ASK. Это «дискретный» вариант консистентного хеширования с управляемой миграцией.

Кэши и CDN. Consistent hashing применяют, чтобы при выводе сервера из пула не сбрасывался весь кэш: перераспределяется только доля ключей снятого узла, что защищает origin от всплеска.

Что мониторить:

• перекос по данным и запросам между узлами (nodetool status — размеры, nodetool tablestats);
• число редиректов у клиентов;
• длительность и объём стриминга при изменении топологии;
• ёмкость диска с запасом на перемещение данных — как оценивать нагрузку, см. capacity planning.

Практический сценарий: добавление узла в работающий кластер

Контекст: Cassandra, четыре узла, num_tokens=16, заполнение дисков 65 %. Нужно добавить пятый узел.

1. Подготовка. Проверяем свободное место: новый узел заберёт примерно 1/5 данных каждого диапазона, то есть на существующих узлах объём уменьшится, но во время стриминга потребуется дополнительное место на приём.
2. Bootstrap. Узел стартует с пустыми данными и получает токены; кластер пересчитывает карту кольца, gossip разносит её клиентам.
3. Стриминг. Данные перетекают в фоне; в этот период нагрузка на диск и сеть растёт, поэтому операцию планируют на низкий трафик и следят за nodetool netstats.
4. Проверка. После завершения сверяем nodetool ring (все диапазоны покрыты, нет «дыр»), nodetool status (статус UN у всех), отсутствие ошибок в логах.
5. Клиенты. Проверяем, что клиенты обновили карту кольца: доля редиректов должна вернуться к базовому уровню. Если клиент кэширует топологию надолго, уменьшаем TTL кэша.

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

FAQ

Что произойдёт при обычном hash % N, если добавить узел? Почти все ключи поменяют владельца: hash(key) % 4 и hash(key) % 5 дают разные результаты для подавляющего большинства ключей. Для кэша это означает массовый промах и удар по базе, для хранилища — полный перенос данных.

Сколько виртуальных узлов нужно? Ориентир — десятки на узел: этого достаточно для выравнивания при 5–50 узлах. В Cassandra 4.x по умолчанию 16 токенов на узел; большее число оправдано при крупных кластерах с требованием к равномерности, но увеличивает метаданные и время восстановления.

Consistent hashing даёт репликацию? Нет, он отвечает только за то, какой узел «владеет» диапазоном. Репликация настраивается отдельно: в Cassandra — стратегией и replication factor, а строгость чтения/записи — уровнями согласованности, см. модель quorum NWR.

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

Источники: Wikipedia (consistent hashing), Cassandra docs (Dynamo), Redis Cluster spec — ссылки в шапке.