Gossip-протокол: как узлы кластера узнают новости и замечают отказы
Как работают gossip-протоколы: распространение состояния за O(log n) раундов, push и pull, anti-entropy, обнаружение отказов через heartbeat, SWIM и phi accrual. Cassandra, Consul, Redis Cluster.
Коротко
| Вопрос | Ответ |
|---|---|
| Что это | Способ распространять информацию в кластере, при котором каждый узел периодически делится новостями с несколькими случайными соседями |
| Скорость | Новость доходит до всех узлов примерно за раундов |
| Нагрузка | На каждый узел — константа сообщений за раунд, независимо от размера кластера |
| Сильная сторона | Нет центрального узла, устойчивость к потере сообщений и падениям |
| Слабая сторона | Согласованность только в конечном счёте; нельзя сказать, когда именно все узнают |
| Где встречается | Cassandra, ScyllaDB, Consul и Serf (memberlist, SWIM), Redis Cluster, Akka Cluster |
- Gossip решает две основные задачи: распространение состояния (кто в кластере, какие у кого токены, версии схемы) и обнаружение отказов (кто перестал отвечать).
- Идея пришла из эпидемиологии: в статье Xerox PARC 1987 года (Demers и соавторы) такие алгоритмы так и названы — эпидемическими.
- Gossip даёт вероятностные, а не строгие гарантии. Если нужно, чтобы все узлы согласились на одно значение, нужен консенсус вроде Raft.
Зачем нужен gossip
Представьте кластер из 500 узлов. Каждому нужно знать, какие узлы живы и какие диапазоны ключей они обслуживают, чтобы направлять запросы (как в консистентном хешировании). Какие есть варианты?
Центральный координатор. Все сообщают о себе одному серверу, а он рассылает картину остальным. Просто, но координатор становится узким местом и единой точкой отказа. Можно защитить его консенсусом, как это делают ZooKeeper или etcd, но тогда появляется отдельный кластер, который нужно эксплуатировать.
Все со всеми. Каждый узел раз в секунду пингует остальные 499. Это сообщений в секунду, и с ростом кластера нагрузка растёт квадратично.
Gossip. Каждый узел раз в секунду выбирает одного-трёх случайных соседей и обменивается с ними тем, что знает. Нагрузка на узел постоянна, а новость всё равно быстро расходится по кластеру — как слух в большой компании.
Как распространяется слух
Базовый алгоритм (push):
- Узел, узнавший новость, становится «заражённым».
- Каждый раунд (например, раз в секунду) каждый заражённый узел отправляет новость случайному узлу.
- Получатель тоже становится заражённым и продолжает рассылку.
Почему это быстро? Пока заражённых мало, почти каждое сообщение попадает в новый узел, и число знающих удваивается каждый раунд. Это даёт раундов на первую фазу. Под конец почти все уже знают, и сообщения чаще приходят тем, кто знает. Добить последних «здоровых» занимает ещё порядка раундов. Итого .
Проверим симуляцией:
import math import random def rounds_to_spread(n, fanout=1, seed=None): """Push-gossip: каждый «заражённый» узел за раунд шлёт слух fanout случайным узлам.""" rng = random.Random(seed) informed = {0} rounds = 0 while len(informed) < n: rounds += 1 new = set() for _ in informed: for _ in range(fanout): new.add(rng.randrange(n)) informed |= new return rounds for n in [10, 100, 1_000, 10_000]: avg = sum(rounds_to_spread(n, seed=s) for s in range(20)) / 20 print(f"n={n:>6} раундов: {avg:5.1f} log2(n)+ln(n) = {math.log2(n) + math.log(n):5.1f}")
Результат:
n= 10 раундов: 6.5 log2(n)+ln(n) = 5.6
n= 100 раундов: 12.8 log2(n)+ln(n) = 11.2
n= 1000 раундов: 18.0 log2(n)+ln(n) = 16.9
n= 10000 раундов: 23.1 log2(n)+ln(n) = 22.5
Кластер в 1000 раз больше — и всего примерно на 17 раундов дольше. При раунде в одну секунду новость обходит десять тысяч узлов меньше чем за полминуты. Это и есть главное свойство gossip: логарифмическое время при постоянной нагрузке на узел.
Push, pull и push-pull
- Push — заражённый узел сам рассылает новость. Быстро в начале, медленно в конце: последние незнающие узлы находятся случайно.
- Pull — каждый узел спрашивает случайного соседа «что нового?». Медленно в начале (почти все спрашивают таких же незнающих), но очень быстро в конце.
- Push-pull — узлы обмениваются в обе стороны. Сочетает сильные стороны обоих и используется на практике чаще всего.
Rumor mongering и anti-entropy
В исходной статье 1987 года различались два режима:
- Rumor mongering (распространение слухов): горячая новость пересылается активно, а когда узел несколько раз натыкается на тех, кто её уже знает, он теряет интерес и прекращает рассылку. Дёшево, но с небольшой вероятностью кто-то так и не узнает.
- Anti-entropy: узлы периодически сравнивают всё состояние целиком и исправляют расхождения. Дорого, зато гарантирует, что рано или поздно все сойдутся.
На практике их комбинируют: быстрые слухи для свежих изменений и редкий полный обмен как страховка. Чтобы не гонять всё состояние по сети, его сравнивают через хеши. Cassandra и Dynamo используют для этого деревья Меркла: узлы обмениваются хешами и спускаются только в те поддеревья, где хеши разошлись.
Как сливать состояние
Узел A присылает узлу B свою картину мира. Как B понять, чья информация свежее? Нельзя сравнивать время по часам: часы на разных машинах расходятся (подробнее — в статье о векторных часах).
Стандартный приём — версия, которую увеличивает только владелец. Каждый узел хранит про себя счётчик (heartbeat или версию), увеличивает его, когда что-то меняется, и только он сам может это делать. При слиянии для каждого узла побеждает запись с большей версией. Такое слияние:
- коммутативно и ассоциативно — неважно, в каком порядке и через кого пришли новости;
- идемпотентно — повторная доставка того же сообщения ничего не ломает.
Поэтому gossip спокойно переносит дубли, потери и переупорядочивание сообщений. Это тот же принцип, на котором построены CRDT.
В Cassandra состояние узла — это набор пар «ключ — значение с версией» (статус, токены, версия схемы, нагрузка), плюс поколение (generation), которое растёт при каждом рестарте узла. Раз в секунду каждый узел обменивается этим состоянием с одним-тремя другими узлами.
Обнаружение отказов
Heartbeat через gossip
Самая простая схема: каждый узел раз в раунд увеличивает свой счётчик heartbeat, а таблицы счётчиков расходятся через gossip. Если чей-то счётчик долго не растёт, узел считается подозреваемым.
Важная деталь: «долго не растёт» каждый узел измеряет по своим локальным часам — когда он последний раз видел рост счётчика. Сравнивать чужие временные метки не нужно.
import random T_FAIL = 5 # сколько тиков без роста heartbeat — и узел подозреваемый class Node: def __init__(self, name, peers): self.name = name self.peers = peers
# имя -> (счётчик heartbeat, локальное время последнего роста)
self.table = {name: (0, 0)}
self.alive = True
def tick(self, now, cluster, rng):
if not self.alive:
return
hb, _ = self.table[self.name]
self.table[self.name] = (hb + 1, now)
peer = cluster[rng.choice([p for p in self.peers if p != self.name])]
peer.merge(self.table, now)
def merge(self, remote, now):
if not self.alive:
return
for name, (hb, _) in remote.items():
mine = self.table.get(name)
if mine is None or hb > mine[0]:
self.table[name] = (hb, now) # время ставим своё, не чужое
def suspects(self, now):
return sorted(n for n, (_, t) in self.table.items() if now - t > T_FAIL)
rng = random.Random(42) names = [f"n{i}" for i in range(8)] cluster = {n: Node(n, names) for n in names} for now in range(1, 41): if now == 20: cluster["n3"].alive = False # узел n3 упал for node in cluster.values(): node.tick(now, cluster, rng) if now in (19, 30, 40): print(now, cluster["n0"].suspects(now))
19 []
30 ['n3']
40 ['n3']
Узлу `n0` не обязательно общаться с `n3` напрямую: он узнаёт о нём через других. И точно так же через других замечает, что счётчик `n3` перестал расти.
Проблема фиксированного порога `T_FAIL`: маленький порог даёт ложные срабатывания при сетевых задержках и паузах сборщика мусора, большой — медленно замечает настоящие отказы.
### Phi accrual failure detector
Cassandra и Akka используют детектор **phi accrual** (Hayashibara и соавторы, 2004). Вместо ответа «жив/мёртв» он выдаёт число $\varphi$ — уровень подозрения:
- узел запоминает распределение интервалов между heartbeat от каждого соседа;
- по нему оценивает, насколько маловероятно так долго не получать heartbeat;
- $\varphi = -\log_{10} P$, где $P$ — вероятность, что heartbeat всё-таки придёт позже. $\varphi = 8$ означает примерно один шанс на сто миллионов, что узел жив.
Порог выбирает приложение (в Cassandra это `phi_convict_threshold`, по умолчанию 8). Детектор сам подстраивается под сеть: в шумной сети интервалы разбросаны шире, и подозрение растёт медленнее.
### SWIM
Протокол **SWIM** (Das, Gupta, Motivala, 2002) разделяет две задачи и решает их по-разному:
1. **Обнаружение отказов — прямыми пингами.** Каждый период узел пингует одного случайного соседа. Если ответа нет, он просит $k$ других узлов пингнуть того же соседа (`ping-req`). Только если не ответил никому, сосед объявляется подозреваемым. Косвенная проверка отсекает случаи, когда проблема в сети между двумя конкретными узлами.
2. **Распространение — через gossip.** Новости об изменениях состава кластера (присоединился, подозреваемый, мёртв) не рассылаются отдельно, а «подвозятся» в тех же пингах и ответах (piggybacking).
Плюс **suspicion-механизм**: подозреваемый узел не исключается сразу. Он получает время, чтобы опровергнуть слух, разослав сообщение «я жив» с увеличенной версией (incarnation number). Это резко снижает ложные исключения.
SWIM лежит в основе библиотеки HashiCorp **memberlist**, на которой построены Serf и Consul. HashiCorp добавили к нему расширения Lifeguard: узел, который сам тормозит, понижает доверие к собственным подозрениям.
## Где используется
- **Cassandra и ScyllaDB** — состав кластера, токены, версии схемы и состояние узлов распространяются через gossip; отказы определяет phi accrual. Новые узлы находят кластер через заранее заданные seed-узлы.
- **Consul, Serf, Nomad** — memberlist (SWIM) для состава кластера и обнаружения отказов. При этом данные каталога Consul хранит под Raft: gossip отвечает за «кто жив», консенсус — за «что записано».
- **Redis Cluster** — узлы общаются по отдельной шине кластера сообщениями PING/PONG, в которых передают сведения о других узлах. Узел, которого считает недоступным большинство мастеров, помечается как упавший, и запускается переключение на реплику.
- **Amazon Dynamo** — в статье 2007 года gossip использовался для состава кольца и обнаружения отказов. Подробнее об устройстве таких систем — в статье про [key-value хранилище](/ru/blog/key-value-store-design).
- **Блокчейны** — транзакции и блоки в Bitcoin и Ethereum распространяются между узлами по похожей схеме.
## Gossip против консенсуса
| Критерий | Gossip | Консенсус (Raft, Paxos) |
| ------------------- | ------------------------------------ | -------------------------------------- |
| Гарантия | Все узнают — в конечном счёте | Все видят одно и то же в одном порядке |
| Нужен лидер | Нет | Да |
| Размер кластера | Тысячи узлов | Обычно 3–7 узлов |
| Переживает | Почти любые отказы и разделения сети | Отказ меньшинства |
| Типичное применение | Состав кластера, метрики, отказы | Конфигурация, блокировки, выбор лидера |
Хорошее правило для собеседования: **gossip — для широкой и мягко согласованной информации, консенсус — для узкой и строго согласованной**. Многие системы используют оба механизма. Связанные темы — [выбор лидера](/ru/blog/leader-election) и [CAP-теорема](/ru/blog/cap-theorem): gossip-системы явно выбирают доступность.
## Типичные ошибки и вопросы на собеседовании
**«Gossip гарантирует, что все узнают за $\log n$ раундов».** Это ожидаемое время, а не гарантия. В rumor mongering есть небольшая вероятность, что кто-то не узнает вовсе, поэтому нужен anti-entropy.
**«Отказ определяется точно».** В асинхронной сети медленный узел неотличим от мёртвого. Любой детектор отказов ошибается: либо ложными срабатываниями, либо задержкой. Вопрос только в балансе.
**«Сравниваем метки времени от разных узлов».** Часы расходятся. Сливать нужно по версиям, которые увеличивает владелец, а таймауты считать по локальным часам.
**«Чем больше fanout, тем лучше».** Растёт трафик, а время падает лишь логарифмически. Обычно хватает 1–3 соседей за раунд.
Частые вопросы:
1. Как узнать о новом узле в кластере из 1000 машин без центрального сервера? — Новый узел связывается с seed-узлом, а дальше информация расходится через gossip за $O(\log n)$ раундов.
2. Почему нагрузка не растёт с размером кластера? — Каждый узел за раунд шлёт фиксированное число сообщений.
3. Как избежать ложного исключения узла? — Косвенные пинги, механизм подозрения, адаптивный детектор вроде phi accrual.
4. Почему gossip устойчив к дублям и потере сообщений? — Слияние по версиям идемпотентно и коммутативно, а повторные раунды восполняют потери.
## Итог
Gossip — это способ договориться «примерно и рано или поздно» без центра и без квадратичного трафика. Каждый узел болтает с парой случайных соседей, а благодаря экспоненциальному росту числа знающих новость обходит кластер за логарифмическое число раундов. На этой основе строятся состав кластера, обнаружение отказов (heartbeat, phi accrual, SWIM) и фоновая сверка данных. Если на собеседовании проектируете систему на сотни узлов, gossip — естественный ответ на вопрос «как узлы узнают друг о друге».