Компьютерные сети
Consistent Hashing
Добавляете сервер к кластеру из 10 машин. С обычным хешированием 90% кеша становится невалидным. С consistent hashing - только 10%. Это разница между деградацией сервиса и плавным масштабированием.
- **Amazon DynamoDB**: consistent hashing для партиционирования петабайтов данных с автоматическим масштабированием
- **Discord**: распределение миллионов guilds/channels по серверам с минимальным resharding
- **Akamai CDN**: routing контента к edge серверам для максимального cache hit rate
Предварительные знания
Hash Ring
**Consistent Hashing** решает проблему: при добавлении/удалении сервера нужно перераспределить минимум ключей. Обычный modulo hash (key % N servers) требует переноса почти всех ключей при изменении N.
**При добавлении сервера** перемещаются только ключи между новым сервером и его соседом. При N серверах перемещается ~1/N ключей вместо ~(N-1)/N.
Hash ring - это концептуально кольцо от 0 до 2^32 (или другого max). Серверы и ключи хешируются в точки на кольце. Ключ принадлежит ближайшему серверу по часовой стрелке.
Сколько ключей перемещается при добавлении 1 сервера к 10 существующим в consistent hashing?
Virtual Nodes
Проблема базового hash ring: при малом числе серверов распределение неравномерное. **Virtual nodes** (vnodes) решают это: каждый физический сервер имеет множество точек на кольце.
**Количество vnodes**: обычно 100-200 на физический сервер. Больше vnodes = равномернее распределение, но больше памяти для хранения ring metadata.
Virtual nodes также упрощают работу с разными мощностями серверов: мощный сервер получает больше vnodes, слабый - меньше. Это weighted consistent hashing.
Зачем нужны virtual nodes в consistent hashing?
Rebalancing
При добавлении/удалении серверов данные нужно **rebalance**. Consistent hashing минимизирует объём, но процесс всё равно требует аккуратности: данные должны быть доступны во время переноса.
**Zero-downtime rebalancing**: новый сервер сначала становится replica для нужного range, затем primary. Старый сервер отдаёт ownership только после полной синхронизации.
Удаление сервера сложнее: его данные нужно срочно передать соседям, иначе потеря. Graceful shutdown: сначала копируем данные, потом удаляем. Crash: восстанавливаем с replicas.
Как обеспечить доступность данных во время rebalancing?
Use Cases
Consistent hashing используется везде, где нужно **распределить данные по кластеру** с минимальным перемещением при масштабировании: distributed cache, databases, load balancing.
**Cassandra** использует consistent hashing как основу архитектуры. Partition key хешируется, данные распределяются по ring. Vnodes с replication factor 3 = данные на 3 соседних узлах.
Почему CDN использует consistent hashing для распределения контента?
Implementation: Memcached & Redis
**Memcached** клиенты (не сервер!) реализуют consistent hashing. Сервер не знает о кластере - это просто key-value store. Клиент решает куда направить запрос.
**Hash tags в Redis**: {user123} в ключе означает хешировать только 'user123'. Все ключи с {user123} попадут на один slot для atomic операций.
Consistent hashing полностью устраняет перемещение данных при масштабировании
Consistent hashing минимизирует перемещение до ~1/N ключей вместо ~(N-1)/N, но некоторое перемещение всё равно происходит. Репликация и careful rebalancing всё ещё необходимы
Ни один алгоритм не может добавить сервер без переноса данных на него. Consistent hashing оптимизирует: переносятся только ключи для нового сегмента, а не весь датасет.
Почему Memcached клиент, а не сервер, реализует consistent hashing?
Итоги
- **Hash Ring**: серверы и ключи на кольце, ключ → ближайший сервер по часовой
- **Virtual Nodes**: много точек на сервер для равномерного распределения
- **Минимальный rebalancing**: ~1/N ключей при добавлении сервера вместо ~(N-1)/N
- **Use cases**: distributed cache, database sharding, load balancing, CDN
Связанные темы
Consistent hashing - фундамент distributed систем:
- Load Balancing — Consistent hashing для sticky sessions
- CAP Theorem — Rebalancing влияет на consistency/availability trade-offs
- System Design Cases — Применение в design distributed cache, database
Вопросы для размышления
- Как consistent hashing работает с репликацией (replication factor 3)?
- Что происходит при внезапном crash сервера vs graceful shutdown?
- Как weighted consistent hashing учитывает разную мощность серверов?