Распределённые системы

Gossip-протоколы

Цели урока

Объяснять принцип эпидемического распространения и O(log N) конвергенцию gossip
Различать Push, Pull и Push-Pull режимы и их trade-off
Понимать алгоритм SWIM для обнаружения отказов с косвенным пингом
Знать роль anti-entropy и Merkle tree для долгосрочной консистентности реплик

Предварительные знания

Понятие eventual consistency и репликации
Базовое знакомство с CAP-теоремой
Понимание хэш-функций

Cassandra кластер из 100 узлов: схема таблицы распространяется на все узлы за 30 секунд без единого координатора и без broadcast-шторма. Математика эпидемий в production.

**Cassandra** - gossip для membership и schema changes, промышленный стандарт
**Consul** - SWIM поверх gossip для service discovery миллионов сервисов
**Redis Cluster** - gossip для распространения topology changes между узлами
**HashiCorp Serf** - gossip как standalone библиотека для embedded membership
**CockroachDB** - liveness detection через SWIM для distributed SQL

Xerox PARC, 1987

Gossip-протоколы описал Alan Demers из Xerox PARC в 1987 году в статье "Epidemic Algorithms for Replicated Database Maintenance". Авторы заметили, что распространение обновлений в базах данных математически аналогично распространению эпидемий в популяции - и применили модель SIR (susceptible-infected-recovered) для анализа конвергенции. SWIM появился в 2002 году в Cornell как практическая реализация для production-систем.

Эпидемическое распространение информации

**Cassandra, производственный кластер, 100 узлов. Один инженер добавляет новую схему таблицы. Через 30 секунд все 100 узлов знают об изменении - без единого центрального сервера, без broadcast-шторма, без координатора.** Это gossip: каждый узел раз в секунду выбирает 3 случайных соседа и обменивается состоянием. Математика эпидемий работает.

Скорость распространения gossip: при fanout=3 и N узлах информация достигает всех за O(log N) раундов. При 1000 узлах - примерно 10 раундов = 10 секунд. При 1 000 000 узлов - 20 раундов. Это экспоненциальное убывание незнания.

Подход к распространению	Нагрузка на узел	Устойчивость к сбоям	Примеры
Broadcast (всем сразу)	O(N) сообщений	Низкая - single point of failure	UDP multicast, ранние системы
Master-slave репликация	O(slaves) на мастере	Средняя - мастер узкое место	MySQL replication, Redis Sentinel
Gossip (эпидемический)	O(fanout) на узел	Высокая - нет координатора	Cassandra, Consul, Redis Cluster

Gossip ненадёжен - часть узлов может вообще не получить информацию

Вероятность недоставки убывает экспоненциально. При fanout=3 и k=O(log N) раундах вероятность что узел НЕ получил данные стремится к нулю.

Каждый раунд узел выбирает случайных соседей независимо. Даже если в раунде k узел пропустил нужное сообщение, в раунде k+1 он получит его от одного из трёх новых случайных соседей. Математика: P(не получил) = (1 - 1/N)^(fanout*rounds) -> 0.

Gossip-кластер из 1024 узлов с fanout=3. За сколько примерно раундов новость дойдёт до всех?

Push, Pull и Push-Pull режимы

Gossip-обмен бывает трёх видов: Push (отправить свои данные), Pull (запросить у соседа), Push-Pull (обмен в обе стороны). Cassandra использует Push-Pull - это самый эффективный режим для быстрой конвергенции.

Режим	Сообщений на раунд	Конвергенция	Когда применять
Push	1 (отправить дайджест)	Медленнее	Broadcast нотификаций о событиях
Pull	2 (запрос + ответ)	Средне	Периодическая синхронизация состояния
Push-Pull	3-4 (дайджест + diff в обе стороны)	Быстрее всех	Membership state, schema changes в Cassandra

Дайджест (digest) - это краткое резюме состояния: только ключи и номера версий, без самих данных. Обычно занимает единицы килобайт даже для тысяч ключей. Полные данные запрашиваются только при расхождении версий.

Почему в gossip отправляют дайджест (ключи + версии), а не полные данные?

SWIM: обнаружение отказов

**SWIM** (Scalable Weakly-consistent Infection-style Membership, 2002) - стандартный алгоритм обнаружения отказов в gossip-кластерах. Используется в Cassandra, Consul, HashiCorp Serf. Ключевое свойство: избегает ложных срабатываний через косвенный ping.

Косвенный ping решает проблему ложных срабатываний: если между detector и target временный разрыв сети, но target жив, то один из 3 соседей достучится до него. Это резко снижает false positive rate без увеличения времени обнаружения реальных отказов.

Если узел не ответил на ping - его можно сразу объявить мёртвым

Нужен косвенный ping через соседей, иначе temporary network partition даст ложные срабатывания.

В реальных сетях часто бывает кратковременный разрыв между конкретными парами узлов (BGP flap, перегрузка коммутатора). Если detector сразу объявляет target мёртвым - кластер начинает ненужные rebalance операции. SWIM ждёт подтверждения от нескольких независимых путей.

Зачем SWIM использует косвенный ping через соседей вместо повторного прямого пинга?

Anti-entropy и Merkle tree

Gossip быстро распространяет новые данные, но не гарантирует что реплики идентичны через долгое время - хардварные сбои, GC паузы, сетевые разделения могут создавать расхождения. Anti-entropy - фоновый процесс синхронизации реплик который периодически сравнивает реплики и синхронизирует различия.

Merkle tree - дерево хэшей: каждый листовой узел = хэш значения ключа, каждый промежуточный = хэш дочерних. Для сравнения двух реплик нужно O(log N) сравнений: спускаемся по дереву, отсекая одинаковые ветки. Cassandra использует Merkle tree для repair операций.

Система	Использование gossip
Cassandra	Membership, schema changes, repair coordination
Consul	Service discovery, health checks, KV store
Redis Cluster	Node state, cluster topology
CockroachDB	Liveness detection, range lease negotiation
HashiCorp Serf	Membership protocol как standalone библиотека

Gossip-протоколы гарантируют consistency как Paxos или Raft, только через распределённый алгоритм

Gossip даёт eventual consistency и probabilistic delivery, а не consensus: нет линеаризуемости, нет total order, есть только вероятностная сходимость за O(log N) раундов

Gossip - это AP в терминах CAP, не CP. Никакой узел не знает точно, дошло ли сообщение до всех (есть только high probability). Это делает gossip отличным выбором для membership, failure detection, метрик - и неподходящим для primitives вроде транзакций или распределённых локов. Cassandra использует Paxos для lightweight transactions поверх gossip-membership именно по этой причине.

Почему anti-entropy использует Merkle tree вместо прямого сравнения всех ключей?

Связь с предыдущим

Consistent hashing и sharding молчат о том, откуда узлы знают текущее membership. Gossip даёт эпидемическую сходимость за O(log N) без центрального координатора.

Consistent hashing — задаёт схему размещения данных по кольцу, но не источник знания о составе кластера
Sharding — предполагал существование актуальной routing-таблицы где-то снаружи
Strongly-consistent registry — альтернатива gossip (ZooKeeper-style), требующая централизации и координации

Итоги

Gossip-протоколы распространяют информацию через случайный peer-to-peer обмен: каждый раунд узел выбирает k случайных соседей и обменивается состоянием, сходимость к полному кластеру происходит за O(log N) раундов
Push/pull/push-pull варианты дают разные trade-off: pull эффективен при редких обновлениях, push при частых, push-pull сочетает оба и используется в большинстве production-систем
SWIM (2002) добавляет к gossip явное failure detection через ping/indirect-ping и suspicion-таймер, отделяя transient network glitches от настоящих отказов
Anti-entropy через Merkle trees позволяет двум узлам найти расхождения в данных за O(log N) хэшей вместо передачи всего датасета - используется в Cassandra и Dynamo для reconciliation
Gossip даёт eventual consistency и probabilistic delivery, не consensus: подходит для membership, metrics, schema gossip, но не для транзакций или линеаризуемых операций

Вопросы для размышления

В gossip-кластере часть узлов намеренно искажает информацию о других узлах (Byzantine failure). Как протокол можно усилить чтобы обнаруживать такие узлы?

Связанные уроки

ds-09-gossip-protocols — Базовое введение в gossip, эта тема - SWIM и anti-entropy
dist-11-replication — Anti-entropy синхронизирует реплики через Merkle
ds-05-replication — Eventual repair реплик через gossip-канал
dist-12-consistency — Gossip обеспечивает eventual consistency состояния
ds-10-crdts — CRDT часто синхронизируются через gossip
dist-10-byzantine — Byzantine-устойчивые версии gossip существуют
alg-12-bfs