Распределённые системы
Consistent Hashing
Цели урока
- Понимать, почему hash % N непригоден для динамических кластеров
- Объяснять принцип работы хэш-кольца и поиска сервера для ключа
- Знать роль виртуальных узлов и их trade-off с памятью
- Применять consistent hashing для репликации (RF=3 в Dynamo-стиле)
Предварительные знания
- Понимание хэш-функций и коллизий
- Базовое знакомство с CAP-теоремой
- Понятие репликации в распределённых системах
Discord, 2017: инженер добавил один сервер из десяти - и 90% кэша стали невалидными. Одна строка `hash % N` положила сервис на 20 минут.
- **Cassandra** - consistent hashing с 256 vnodes, петабайты данных в production
- **Amazon Dynamo** - описан в классической статье 2007 года, лег в основу DynamoDB
- **Discord guild sharding** - 200+ миллионов пользователей, 100 vnodes на каждый узел; в 2023 мигрировали с Cassandra на ScyllaDB (177 -> 72 узла, latency 200мс -> 5мс, триллионы сообщений)
- **Memcached libketama** - первая open-source реализация 2007 года, ставшая стандартом
- **Google Maglev** - O(1) lookup без хранения кольца, используется в Google LB
Karger et al., MIT, 1997
Consistent hashing придумали в MIT в 1997 году - Karger, Lehman, Leighton и соавторы. Статья называлась "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web". Изначально задача была про распределение нагрузки в веб-кэшах эпохи раннего интернета. Amazon взял эту идею в 2007 году для Dynamo и превратил её в основу всех современных NoSQL баз данных.
Проблема hash % N
**Discord, 2017. 200 миллионов пользователей, 10 серверов кэша. Инженер добавляет 11-й сервер - и за несколько секунд 90% кэша становятся недействительными. Миллионы запросов бьют напрямую в базу данных. Сервис деградирует на 20 минут.** Причина - одна строка кода: `hash(key) % N`.
При изменении числа серверов с N на N+1 перемещается не 1/N ключей, а примерно N/(N+1) - то есть почти все. Modulo хэширование работает только при фиксированном числе узлов.
| Подход | При добавлении 1 узла | Подходит для |
|---|---|---|
| hash % N | ~(N-1)/N ключей переезжают | Статичный кластер, нет масштабирования |
| Consistent Hashing | ~1/N ключей переезжают | Динамическое масштабирование, production |
| Rendezvous Hashing | ~1/N ключей переезжают | Малое число узлов, простота реализации |
Хорошая хэш-функция решит проблему массового перераспределения при масштабировании
Проблема не в хэш-функции - она в самой операции modulo. Нужна другая структура данных.
Modulo создаёт жёсткое отображение ключ→сервер через остаток от деления. При изменении делителя N все остатки пересчитываются заново. Это математическое свойство операции, а не артефакт конкретной хэш-функции.
Кластер из 99 серверов расширяется до 100. Сколько ключей переедет при modulo хэшировании?
Хэш-кольцо: ключевая идея
Идея consistent hashing из статьи Karger et al., MIT, 1997: хэш-пространство 0..2^32 замкнуть в кольцо. Серверы и ключи хэшируются на позиции в этом кольце. Ключ принадлежит первому серверу по часовой стрелке.
При удалении сервера только его ключи переходят к следующему по часовой стрелке - все остальные серверы не затрагиваются. При добавлении сервера он перехватывает только часть ключей у своего правого соседа.
На кольце 3 сервера: A на позиции 100, B на 200, C на 300. Ключ хэшируется в позицию 250. На какой сервер попадёт ключ?
Виртуальные узлы и дисбаланс
С тремя физическими серверами на кольце вероятность равномерного распределения низкая - статистика плохо работает при малой выборке. Один сервер может получить 50% ключей, другой - 10%.
| Число физических серверов | Без vnodes (дисбаланс) | С 150 vnodes (дисбаланс) |
|---|---|---|
| 3 | до 50% | < 5% |
| 10 | до 30% | < 3% |
| 50 | до 20% | < 1% |
| 100+ | до 15% | < 0.5% |
Vnodes решают ещё одну проблему: серверы разной мощности. Сервер с 64 ГБ RAM получает вдвое больше vnodes, чем сервер с 32 ГБ - и принимает вдвое больше нагрузки. Cassandra и Dynamo используют это для weighted partitioning.
Больше vnodes всегда лучше - надо брать 1000+ для максимальной равномерности
Есть trade-off: больше vnodes = лучше баланс, но больше памяти и медленнее перестройка кольца при изменениях.
Cassandra при 1000 узлах с 256 vnodes хранит 256 000 записей в sorted map. Перестройка при добавлении узла - O(vnodes * log(total_vnodes)). Практический оптимум - 100-256 vnodes, что даёт < 1% дисбаланс при приемлемой сложности.
Зачем нужны виртуальные узлы при 3 физических серверах?
Репликация на кольце и альтернативы
Amazon Dynamo (2007) использует consistent hashing для репликации: данные записываются на N последовательных серверов по часовой стрелке от позиции ключа (replication factor RF=3 означает 3 сервера). При отказе одного из них оставшиеся два продолжают обслуживать запросы.
| Система | Реализация | Особенность |
|---|---|---|
| Amazon Dynamo / DynamoDB | Consistent hashing + RF=3 | Preference list для graceful degradation |
| Apache Cassandra | 256 vnodes на узел | Rack-aware репликация поверх кольца |
| Discord (guild sharding, ScyllaDB с 2023) | 100 vnodes на узел | Определяет, какой сервер обслуживает гильдию; в 2023 переехали с Cassandra на ScyllaDB (177 -> 72 узла, latency 200мс -> 5мс) |
| Memcached клиенты | libketama, 160 vnodes | Первая open-source реализация (2007) |
| Nginx upstream | consistent_hash директива | Sticky sessions для stateful бэкендов |
При масштабе 1000+ узлов стандартное кольцо замедляется. Альтернативы: **Jump Consistent Hash** (Google, 2014) - O(log N) без хранения кольца в памяти; **Maglev** (Google, 2016) - O(1) lookup через lookup table; **Rendezvous Hashing** - без структуры данных вообще, но O(N) на каждый lookup.
Чем больше виртуальных нод на сервер, тем равномернее распределение - значит надо ставить тысячи
Виртуальные ноды снижают дисперсию загрузки, но имеют вычислительные и memory-расходы: log lookup по отсортированному кольцу из N*V точек, плюс хранение метаданных
Стандартный Dynamo использует 100-200 vnode на физический узел - это разумный compromise. Бесконтрольное увеличение V раздувает структуру ring (сотни тысяч точек), замедляет gossip-синхронизацию членства, увеличивает memory footprint клиентских libraries. Альтернатива - Jump Hash (Google, 2014) или Maglev hashing, которые дают O(1) lookup без хранения кольца вообще.
Dynamo использует RF=3 на кольце с 10 серверами. Сервер на позиции 200 падает. Ключи с позицией 150-200 теперь обслуживает...
Связь с предыдущим
Hash%N даёт ровное распределение, но при изменении N переписывает (N-1)/N ключей. Consistent hashing мигрирует лишь 1/N и делает rebalancing фоновой операцией.
- Hash sharding (modulo N) — ломается при изменении кластера: одно добавление узла переписывает почти все ключи
- Hash ring — общее пространство для ключей и серверов - база consistent hashing
- Rebalancing — превращается из аварии в фоновую операцию благодаря локальной миграции 1/N
Итоги
- Hash-кольцо проецирует и ключи, и серверы на одно пространство (2^160 для SHA-1), ключ попадает на ближайший сервер по часовой стрелке - lookup за O(log N) через бинарный поиск в отсортированном кольце
- При изменении кластера переезжает только 1/N ключей вместо (N-1)/N, что делает добавление/удаление узлов рутинной операцией без миграции датасета
- Виртуальные ноды (Dynamo: 100-200 vnode на физический узел) решают проблему неравномерности: без них дисперсия загрузки достигает 30%+, с vnode стабилизируется на уровне нескольких процентов
- Replication factor RF=N реализуется проходом по кольцу: primary плюс N-1 следующих серверов хранят копию - тривиальная схема репликации без отдельной координации
- Альтернативы (Jump Hash, Maglev, Rendezvous Hashing) дают O(1) lookup без хранения кольца ценой потери runtime-гибкости при изменении кластера
Вопросы для размышления
- Cassandra позволяет задавать разное число vnodes для разных узлов кластера. Как это используется при миграции с маломощных серверов на мощные без остановки кластера?
Связанные уроки
- ds-04-consistent-hashing — Базовое определение, эта тема разворачивает реализацию
- dist-14-sharding — Шардирование строится поверх consistent hashing
- dist-11-replication — Replication factor реализуется через соседей на кольце
- ds-05-replication — RF=N - N последовательных узлов на кольце
- ds-09-gossip-protocols — Cassandra использует gossip для распространения кольца
- ds-02-cap-theorem — Dynamo выбирает AP, кольцо - его реализация
- db-23-sharding