Gossip-протокол: как узлы кластера узнают новости и замечают отказы

Как работают gossip-протоколы: распространение состояния за O(log n) раундов, push и pull, anti-entropy, обнаружение отказов через heartbeat, SWIM и phi accrual. Cassandra, Consul, Redis Cluster.

11 мин чтениясистемный дизайн · распределённые системы · python

Коротко

ВопросОтвет
Что этоСпособ распространять информацию в кластере, при котором каждый узел периодически делится новостями с несколькими случайными соседями
СкоростьНовость доходит до всех nn узлов примерно за O(log⁡n)O(\log n) раундов
НагрузкаНа каждый узел — константа сообщений за раунд, независимо от размера кластера
Сильная сторонаНет центрального узла, устойчивость к потере сообщений и падениям
Слабая сторонаСогласованность только в конечном счёте; нельзя сказать, когда именно все узнают
Где встречаетсяCassandra, ScyllaDB, Consul и Serf (memberlist, SWIM), Redis Cluster, Akka Cluster
  • Gossip решает две основные задачи: распространение состояния (кто в кластере, какие у кого токены, версии схемы) и обнаружение отказов (кто перестал отвечать).
  • Идея пришла из эпидемиологии: в статье Xerox PARC 1987 года (Demers и соавторы) такие алгоритмы так и названы — эпидемическими.
  • Gossip даёт вероятностные, а не строгие гарантии. Если нужно, чтобы все узлы согласились на одно значение, нужен консенсус вроде Raft.

Зачем нужен gossip

Представьте кластер из 500 узлов. Каждому нужно знать, какие узлы живы и какие диапазоны ключей они обслуживают, чтобы направлять запросы (как в консистентном хешировании). Какие есть варианты?

Центральный координатор. Все сообщают о себе одному серверу, а он рассылает картину остальным. Просто, но координатор становится узким местом и единой точкой отказа. Можно защитить его консенсусом, как это делают ZooKeeper или etcd, но тогда появляется отдельный кластер, который нужно эксплуатировать.

Все со всеми. Каждый узел раз в секунду пингует остальные 499. Это n2=250 000n^2 = 250\,000 сообщений в секунду, и с ростом кластера нагрузка растёт квадратично.

Gossip. Каждый узел раз в секунду выбирает одного-трёх случайных соседей и обменивается с ними тем, что знает. Нагрузка на узел постоянна, а новость всё равно быстро расходится по кластеру — как слух в большой компании.

Как распространяется слух

Базовый алгоритм (push):

  1. Узел, узнавший новость, становится «заражённым».
  2. Каждый раунд (например, раз в секунду) каждый заражённый узел отправляет новость случайному узлу.
  3. Получатель тоже становится заражённым и продолжает рассылку.

Почему это быстро? Пока заражённых мало, почти каждое сообщение попадает в новый узел, и число знающих удваивается каждый раунд. Это даёт log⁡2n\log_2 n раундов на первую фазу. Под конец почти все уже знают, и сообщения чаще приходят тем, кто знает. Добить последних «здоровых» занимает ещё порядка ln⁡n\ln n раундов. Итого O(log⁡n)O(\log n).

Проверим симуляцией:

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 — естественный ответ на вопрос «как узлы узнают друг о друге».

Потренироваться в спокойной обстановке

Все задачи