Распределённые системы
Consistent Hashing
Цели урока
- Объяснить почему hash % N разрушает кэш при изменении кластера
- Описать механизм хэш-кольца и lookup ключа за O(log N)
- Понимать роль virtual nodes для равномерного распределения нагрузки
- Знать как репликация работает поверх consistent hashing
- Различать когда применять Consistent Hashing, Jump Hash и Maglev
Предварительные знания
- Хэш-функции: что такое хэш, коллизии, равномерное распределение
- Базовые структуры данных: TreeMap / SortedSet, операция ceiling
- Понятие кластера: узлы, репликация, fault tolerance
Discord обслуживает 200 миллионов пользователей. При добавлении одного кэш-сервера из 10 - без consistent hashing 90% кэша инвалидируется мгновенно. Это не баг, это математика hash % N.
- **DynamoDB** - consistent hashing описан в статье Amazon Dynamo 2007, стал blueprint для NoSQL систем
- **Apache Cassandra** - 256 vnodes на узел, replication factor 3, tunable consistency per query
- **Discord** - 100 vnodes на узел, гильдийный шардинг; в 2023 мигрировали с Cassandra на ScyllaDB (177 -> 72 узла, latency 200мс -> 5мс)
- **Google Maglev (2016)** - O(1) lookup через precomputed table, используется в GFE load balancer
- **Nginx upstream** - встроенный consistent_hash модуль для sticky sessions без дополнительных зависимостей
Каргер и Лейтон: хэш-кольцо за 1997 год
В 1997 году Каргер и Лейтон опубликовали статью 'Consistent Hashing and Random Trees' на STOC - конференции, где задают направление CS на десятилетия. Задача была академической: как распределить нагрузку по веб-кэшам без центрального координатора. Решение - хэш-пространство как кольцо - оказалось настолько элегантным, что через 10 лет слово в слово воспроизведено в статье Amazon Dynamo (2007). Сейчас алгоритм работает в каждой второй production distributed системе планеты.
Проблема: hash % N ломает кэш
**Discord, 2017. 200 миллионов пользователей, тысячи серверов гильдий. Команда решает добавить ещё один кэш-узел - с 9 до 10 серверов. Итог: 90% кэша инвалидировано за секунды, пиковая нагрузка на БД в 10 раз выше нормы, 40 минут деградации сервиса.** Причина - `hash(key) % N`.
Формула `hash(key) % N` проста: берём хэш ключа, делим на количество узлов, остаток - индекс узла. При N=9 и N=10 почти каждый ключ попадает на другой узел.
| Метод | Перемещений при +1 узле | Когда подходит |
|---|---|---|
| hash % N | ~(N-1)/N всех ключей (~90% при N=10) | Статичный кластер без масштабирования |
| Consistent Hashing | ~1/N всех ключей (~10% при N=10) | Production-системы с динамическим кластером |
Кэш-узлы спроектированы чтобы снижать нагрузку на БД. При инвалидации 90% кэша весь трафик идёт напрямую в БД - именно в момент масштабирования, когда система итак под нагрузкой.
hash % N - нормальный выбор, просто перегружается кэш на несколько секунд
В production-кластере из 100+ узлов это несколько минут деградации с 10x нагрузкой на БД при любом изменении кластера
Падение узла - это тоже изменение N. При crash одного сервера из 100 все 100 узлов начинают принимать перераспределённые ключи одновременно. Это происходит в худший момент - когда система уже под стрессом.
Кластер из 99 кэш-серверов расширяют до 100. Сколько ключей сменит узел при использовании hash % N?
Хэш-кольцо: ключи идут к ближайшему узлу
**Consistent hashing, 1997, Каргер и Лейтон из MIT.** Идея: представить хэш-пространство (0..2^32) не как линейку, а как кольцо - замкнутое. Узлы и ключи получают позиции на кольце через одну функцию хэша. Узел обслуживает все ключи до следующего узла по часовой стрелке.
Сбой узла - минимальные потери
Кластер: Node-A (позиция 100), Node-B (300), Node-C (700). Ключи: K1=pos 200 (у B), K2=pos 500 (у C), K3=pos 800 (у A через замыкание). Node-B падает. Только K1 (pos 200) переходит к Node-C. K2 и K3 остаются там же. Перемещается 1/3 ключей - именно те, которые принадлежали упавшему узлу.
Поиск узла через `TreeMap.ceilingKey()` работает за O(log N), где N - число узлов. Даже при 10 000 узлах это 14 операций сравнения.
В кластере 5 узлов на кольце. Один узел падает. Ключи с какого диапазона перейдут на другие узлы?
Virtual nodes: равномерность без удачи
**Cassandra 2013. Команда Netflix обнаруживает: один узел из 10 получает 40% трафика, другой - 7%. Причина - узлы случайно оказались кластером на кольце, один занял большой дуговой сегмент.** Решение - virtual nodes (vnodes): каждый физический узел размещает 150-256 точек на кольце.
| Конфигурация | Узлов | Точек на кольце | Макс. дисбаланс |
|---|---|---|---|
| Без vnodes | 3 | 3 | ~40% |
| 100 vnodes | 3 | 300 | ~5% |
| 256 vnodes | 3 | 768 | ~2% |
| 100 vnodes | 10 | 1000 | <2% |
| 256 vnodes | 100 | 25 600 | <0.5% |
Weighted vnodes: мощный сервер получает больше виртуальных точек. Node-A (128 GB RAM) = 300 vnodes, Node-B (64 GB) = 150 vnodes. Автоматический weighted load balancing без дополнительной логики.
Больше vnodes всегда лучше - надо ставить 1000+
256 vnodes - практический потолок. При 1000 vnodes на 100 узлов кольцо хранит 100 000 точек, lookup замедляется, overhead памяти растёт без заметного улучшения баланса.
Дисбаланс убывает как ~1/sqrt(vnodes). С 100 vnodes - уже ~2% дисбаланс. С 1000 - ~0.6%. Выигрыш ничтожный, цена - в 10 раз больше памяти и медленнее операции с кольцом.
Зачем использовать 150-256 vnodes вместо 1 позиции на узел, если lookup становится медленнее?
Репликация на кольце и альтернативы
**Amazon Dynamo, 2007.** Авторы описали как consistent hashing + репликация на кольце решает проблему отказоустойчивости. Паттерн стал индустриальным стандартом: ключ хранится не на одном узле, а на N последовательных узлах по кольцу.
Репликация на 3 узлах (replication factor=3)
Ключ K хэшируется в позицию P. Первичный узел - Node-A (ближайший по часовой). Реплики - Node-B и Node-C (следующие два по кольцу). При падении Node-A - Node-B становится первичным, создаётся новая реплика на Node-D. Данные не теряются, кластер автоматически восстанавливает replication factor.
| Система | Применение | Масштаб |
|---|---|---|
| Amazon DynamoDB | Партиционирование + репликация ключей, replication factor=3 | Миллионы req/sec |
| Apache Cassandra | 256 vnodes/узел, RF=3, tunable consistency | Петабайты данных |
| Discord (ScyllaDB с 2023) | Гильдийный шардинг, 100 vnodes/узел; 177 Cassandra-узлов -> 72 ScyllaDB-узла, latency 200мс -> 5мс | 200+ млн пользователей, триллионы сообщений |
| Memcached клиенты | Ketama: consistent hashing без vnodes, простая реализация | Стандарт индустрии |
| Nginx upstream | consistent_hash для sticky sessions | Любой масштаб |
Когда consistent hashing не подходит
| Алгоритм | Lookup | Память | Когда использовать |
|---|---|---|---|
| Consistent Hashing + vnodes | O(log N) | O(N * vnodes) | До ~1000 узлов, production default |
| Jump Consistent Hash (Google 2014) | O(ln N) | O(1) | Равновероятные узлы, без удалений из середины |
| Maglev Hash (Google 2016) | O(1) | O(M) lookup table | Load balancer уровня L4, 1000+ backend'ов |
Jump Hash занимает 6 строк кода и не требует хранения кольца вообще - только число узлов. Maglev Hash используется в Google's собственном L4 load balancer для миллионов backend'ов с O(1) lookup через precomputed lookup table.
При replication factor=3 на кольце из 10 узлов падает узел. Что происходит с данными?
Вопросы для размышления
- Кластер кэш-серверов обслуживает hotspot: один ключ запрашивается в 100 раз чаще других. Consistent hashing равномерно распределяет ключи, но не запросы к одному ключу. Как решить эту проблему, оставаясь в рамках consistent hashing?
Связанные уроки
- ds-01-intro — Базовые понятия узла, кластера и отказа
- ds-05-replication — Репликация ключей на N узлах кольца - replication factor поверх consistent hashing
- ds-09-gossip-protocols — Cassandra рассылает изменения кольца через gossip - обнаружение узлов и topology
- sd-04-database — Cassandra и DynamoDB используют consistent hashing для шардинга - конкретные production системы
- ds-04-clocks — Consistent hashing и Lamport clocks - оба решают проблемы координации без центрального арбитра
- opt-04 — Virtual nodes размещение - задача оптимизации распределения нагрузки, аналог bin-packing
- db-23-sharding