Распределённые системы
Gossip Protocols
Цели урока
- Понимать механику gossip: экспоненциальное распространение за O(log N) раундов
- Различать push, pull и push-pull режимы и знать когда применять каждый
- Объяснять SWIM protocol и зачем нужен косвенный ping через helpers
- Понимать роль Merkle Tree в anti-entropy синхронизации реплик
Предварительные знания
- Репликация и eventual consistency (ds-05-replication)
- Failure detection и heartbeat паттерны
- Базовые структуры данных: хэш-таблица, бинарное дерево
Cassandra кластер из 1000 узлов - каждые 7 секунд весь кластер знает о любом изменении состояния. Без единого координатора. Без broadcast. Только gossip.
- **Cassandra** - gossip каждые 1000 мс для membership и schema propagation, SWIM для failure detection
- **Consul (HashiCorp)** - SWIM-based membership, service discovery в кластерах тысяч сервисов
- **Redis Cluster** - gossip для распространения состояния шардов и обнаружения отказов
- **CockroachDB** - gossip для liveness detection и метаданных репликации
- **Amazon DynamoDB (2007)** - Merkle Tree anti-entropy для repair реплик после партиций
Gossip protocols: от биологии к distributed systems
В 1987 году Alan Demers и команда в Xerox PARC опубликовали "Epidemic algorithms for replicated database maintenance" - работу, которая перенесла модель распространения эпидемий в CS. Идея: если вирус заражает каждого человека, который заражает k случайных других - за log(N/log(N)) шагов заражены все. Та же математика для данных. Протокол Cassandra и Consul сегодня - прямые потомки этой статьи.
Механика gossip: эпидемия за O(log N) раундов
**Cassandra, кластер из 6 узлов, production 2019. Два узла упали ночью. Утром весь кластер знает об этом - хотя ни один узел не отправил broadcast, нет центрального координатора, нет shared state.** Это gossip protocol: каждые 1000 мс каждый узел выбирает 3 случайных соседа и обменивается с ними состоянием. За log2(N) раундов информация покрывает весь кластер.
**Математика распространения:** при fanout=3 и N=1000 узлов достаточно log3(1000) ≈ 7 раундов, чтобы все узлы получили обновление. Каждый раунд: 3 × 3 × 3 ... = 3^k узлов охвачено. При k=7 это уже 2187 - больше 1000, значит покрытие 100%. Время: 7 секунд при интервале 1 сек.
| Свойство | Значение | Почему важно |
|---|---|---|
| Сложность | O(log N) раундов | 1000 узлов = 7 раундов; 1 000 000 = 20 раундов |
| Отказоустойчивость | Работает при p% падений | Нет single point of failure, нет координатора |
| Масштабируемость | Линейная нагрузка на узел | Каждый узел делает ровно fanout запросов независимо от N |
| Eventual consistency | Секунды, не миллисекунды | Подходит для membership, не для транзакций |
Gossip - это broadcast: один источник рассылает всем
Gossip - децентрализованный: каждый узел пересылает случайным соседям. Нет источника после первого раунда.
В broadcast источник создаёт O(N) соединений - бутылочное горлышко при N=1000. В gossip каждый узел делает ровно fanout (3-5) запросов независимо от размера кластера. Нагрузка равномерно распределена.
Кластер из 1000 узлов, gossip interval 1 сек, fanout 3. Сколько времени займёт распространение обновления?
Push, Pull, Push-Pull: три режима обмена
**Режим обмена определяет кто инициирует передачу данных.** Это не вкусовщина: push конвергирует медленнее, pull перегружает при разных версиях, push-pull - оптимум для большинства production систем.
| Режим | Как работает | Когда применять |
|---|---|---|
| Push | Узел A отправляет свои данные узлу B | Быстрое начальное распространение новых данных |
| Pull | Узел A запрашивает данные у узла B | Обнаружение пропущенных обновлений |
| Push-Pull | A отправляет digest, B отвечает diff, оба синхронизируются | Production: минимальный трафик + полная синхронизация |
**Почему digest, а не сами данные?** Узел может хранить гигабайты. При каждом gossip-раунде передаётся только digest: map из ключей и номеров версий. Это килобайты вместо гигабайт. Полные данные передаются только по конкретному запросу после сравнения версий.
Узел A запускает gossip-раунд с узлом B. A отправляет digest: {user:5, config:3}. B отвечает: у меня {user:4, config:5}. Что произойдёт дальше?
SWIM: обнаружение отказов через gossip
**HashiCorp Consul, 2014. В production-кластер добавляют SWIM протокол для membership. Результат: время обнаружения отказа узла сокращается с 30 секунд (heartbeat timeout) до 5 секунд - при нулевой нагрузке на координатор.** SWIM (Scalable Weakly-consistent Infection-style Membership) решает проблему false positives: медленный узел != мёртвый узел.
**Зачем косвенный ping?** Сетевые партиции могут быть частичными: A не видит B, но C видит B нормально. Если только A выносит вердикт - возможен false positive. Косвенный ping через 3 разных helper снижает вероятность ошибки до статистически незначимой.
| Система | Использование SWIM / gossip |
|---|---|
| Cassandra | Membership + schema changes, gossip каждые 1000 мс |
| Consul | Service discovery + health checks (SWIM-based) |
| Redis Cluster | Node state propagation между шардами |
| CockroachDB | Liveness detection, replication metadata |
| HashiCorp Serf | Membership protocol, basis for Consul |
Если узел не отвечает на ping - его нужно сразу пометить мёртвым
Медленный ответ, сетевая партиция, GC-пауза - всё это вызывает timeout. Косвенный ping отличает временный сбой от реального отказа.
JVM GC stop-the-world может длиться 500+ мс. PostgreSQL autovacuum иногда замораживает IO. В обоих случаях прямой ping даст timeout, а косвенный через helpers покажет что узел жив. SWIM специально создан чтобы минимизировать false positives в таких сценариях.
Почему SWIM использует косвенный ping через helpers вместо простого повтора прямого ping?
Anti-Entropy: Merkle Trees для синхронизации реплик
**Amazon DynamoDB 2007, whitepaper Dynamo. Проблема: после сетевой партиции 2 реплики расходятся. Как найти различия между 10 миллионами ключей без полного сравнения?** Anti-entropy через Merkle Tree: сравниваем не сами данные, а хэши поддеревьев. O(log N) сравнений вместо O(N). Dynamo использует это до сих пор.
**Merkle Tree** - бинарное дерево хэшей. Листья = хэши отдельных ключей. Родители = хэш конкатенации дочерних хэшей. Корень = отпечаток всего набора данных. Если корни совпали - данные идентичны. Если нет - рекурсивно спускаемся по ветке с разным хэшем до нахождения конкретных ключей.
| Подход | Сложность поиска различий | Трафик при N=1M ключей |
|---|---|---|
| Полное сравнение | O(N) | Передать все 1M ключей |
| Merkle Tree | O(log N + diff) | log2(1M) = 20 запросов, затем только diff |
| Bloom filter | O(N) false positives | Компактнее но с ошибками |
**Anti-entropy через gossip работает для eventual consistency, не для strong consistency.** Если система требует linearizable reads (etcd, Spanner) - gossip слишком медленный: данные расходятся на секунды. Gossip идеален для membership, config propagation, CRDT-based data - там eventual достаточно.
Gossip protocols подходят для любых данных в распределённой системе
Gossip - инструмент eventual consistency. Для финансовых транзакций, лидер-выборов, конфигурации кластера нужны протоколы консенсуса (Raft, Paxos).
Gossip гарантирует что данные Eventually распространятся - но не когда именно. Cassandra использует gossip для membership (кто жив) и schema changes. Для записи данных с consistency guarantees - quorum writes с W+R>N, а не gossip.
После партиции 2 Cassandra-реплики расходятся на 500 ключей из 10 млн. Как Merkle Tree помогает при anti-entropy синхронизации?
Вопросы для размышления
- Gossip обеспечивает eventual consistency с задержкой в секунды. Для каких данных в production-системе это достаточно, а для каких категорически нет? Какой критерий позволяет это определить?
Связанные уроки
- ds-10-crdts — Gossip + CRDT gives coordination-free eventual consistency
- ds-12-service-discovery — Consul SWIM protocol uses gossip for membership
- dist-12-consistency — Gossip achieves only eventual consistency
- alg-12-bfs