System Design
Consistent Hashing
Цели урока
- Понять проблему naive hashing при масштабировании
- Изучить Hash Ring и принцип распределения ключей
- Освоить Virtual Nodes для равномерного распределения
- Разобраться в репликации на hash ring и quorum consistency
Предварительные знания
- Rate Limiting (предыдущий урок)
- Основы баз данных и репликации
Consistent Hashing - фундамент всех распределённых хранилищ: Cassandra, DynamoDB, Memcached, CDN. На интервью часто спрашивают: 'Как распределить данные между серверами?' - и ожидают знания consistent hashing.
- Используется в production системах
Проблема обычного хеширования
**Consistent Hashing** решает проблему распределения данных между серверами так, чтобы добавление или удаление сервера минимально затрагивало существующее распределение.
**Проблема обычного хеширования:**
**Что происходит при добавлении сервера?**
При naive hashing добавление одного сервера требует перемещения почти ВСЕХ данных. Для петабайтных систем это дни простоя.
**Consistent Hashing решает эту проблему:**
**Где используется Consistent Hashing:**
- **Amazon DynamoDB** - распределение партиций
- **Apache Cassandra** - token ring
- **Memcached** - ketama algorithm
- **Riak** - распределение данных
- **Akamai CDN** - маршрутизация запросов
- **Discord** - распределение серверов
При naive hashing (hash % N) и N=10 серверах, добавление 11-го сервера потребует перемещения примерно:
При naive hashing добавление сервера меняет распределение для ~(N-1)/N ключей. При N=10: (10-1)/10 = 90% данных нужно перемещать.
Hash Ring
**Hash Ring** - ключевая структура Consistent Hashing. Представь кольцо с числами от 0 до 2³² (или другой максимум hash функции).
**Как определить сервер для ключа?**
1. Вычисляем hash(key) - получаем точку на кольце 2. Двигаемся по часовой стрелке до первого сервера 3. Этот сервер отвечает за ключ
**Что происходит при добавлении сервера D?**
При добавлении нового сервера в consistent hashing ring, какие данные нужно перемещать?
Новый сервер "забирает" часть ключей только у своего соседа по часовой стрелке. Остальные серверы не затронуты. Это и есть ключевое преимущество consistent hashing.
Virtual Nodes (Vnodes)
**Проблема:** при малом количестве серверов распределение может быть неравномерным. Один сервер может получить большую дугу кольца.
**Решение: Virtual Nodes (Vnodes)**
Каждый физический сервер представлен НЕСКОЛЬКИМИ точками на кольце. Вместо 1 точки - 100-200 virtual nodes.
**Преимущества Virtual Nodes:**
- **Равномерное распределение** - больше точек = лучшее распределение
- **Heterogeneous servers** - производительному серверу больше vnodes
- **Быстрое восстановление** - при падении сервера его vnodes распределяются между МНОГИМИ серверами, не одним
- **Плавное добавление** - новый сервер забирает понемногу от каждого
Cassandra использует 256 vnodes по умолчанию. DynamoDB использует partition key для определения партиции, внутри - consistent hashing.
Зачем нужны Virtual Nodes?
Virtual Nodes решают две проблемы: 1. равномерное распределение при малом числе серверов 2. возможность давать производительным серверам больше vnodes = больше данных.
Репликация на Hash Ring
Consistent Hashing естественно поддерживает репликацию: данные хранятся не на одном, а на N следующих серверах по кольцу.
**Quorum: согласованность чтения и записи**
**Cassandra Consistency Levels:**
**Hinted Handoff:**
**Anti-Entropy: Read Repair и Merkle Trees**
Consistent Hashing + Replication + Quorum - основа всех современных distributed databases: Cassandra, DynamoDB, Riak. Понимание этих концепций критично для System Design.
При N=3, W=2, R=2. Можно ли гарантировать чтение актуальных данных?
W + R > N гарантирует, что при чтении хотя бы одна реплика будет иметь последнюю версию данных. W=2 + R=2 = 4 > 3, значит пересечение множеств записи и чтения непустое.
Ключевые идеи
- Naive hashing (hash % N) требует перемещения ~100% данных при добавлении сервера
- Consistent Hashing с hash ring минимизирует это до ~1/N
- Virtual Nodes обеспечивают равномерное распределение и поддержку серверов разной производительности
- Репликация: данные на N следующих серверах, Quorum (W+R>N) для consistency
Что дальше
Следующий урок: Distributed Transactions - как обеспечить атомарность операций, затрагивающих несколько сервисов: 2PC, Saga pattern, eventual consistency.
- System Design — продолжение курса