Кворумная репликация и консенсус согласуют пользовательские данные — но оба опираются на незаметную предпосылку: каждый узел знает, кто ещё в кластере и кто из соседей жив. Эта глава — про тот самый слой ниже: масштабируемое членство (membership) и обнаружение отказов (failure detection) без центрального координатора.
Наивная схема «каждый шлёт heartbeat каждому» захлёбывается в O(N²) трафике уже на тысячах узлов. Gossip-протоколы (эпидемические) заменяют её случайной болтовнёй с постоянной нагрузкой на узел: слух о новом, ушедшем или упавшем узле расходится до всех за O(log N) раундов, как инфекция.
SWIM (Das, Gupta, Motivala, DSN 2002) разделяет детекцию (прямой ping + косвенный ping-req через k узлов) и распространение (piggyback на ping), а suspicion и incarnation-номера гасят ложные срабатывания. φ-accrual (Hayashibara и др., 2004) выдаёт непрерывную подозрительность вместо бинарной. Вместе — фундамент Cassandra, Consul и Serf.
Практическая польза главы
Постоянная нагрузка на узел
Gossip и SWIM держат трафик и память на узел независимыми от размера кластера: один ping за период плюс k косвенных при сбое — вместо O(N²) пакетов heartbeat-all-to-all.
Меньше ложных срабатываний
Косвенный ping-req через k посредников, suspicion-таймер и опровержение через incarnation-номер не дают объявить мёртвым узел, который просто притормозил из-за GC-паузы или всплеска задержки.
Адаптивные пороги вместо магических секунд
φ-accrual выдаёт непрерывное φ из наблюдаемой истории heartbeat: один порог осмыслен в разных дата-центрах, а Lifeguard учитывает «локальное здоровье» самого детектора.
Членство — не консенсус
Gossip согласует «кто в кластере» лишь отложенно; для линеаризуемых решений (кто лидер, кому шард) поверх берут отдельный консенсус — Cassandra и Consul именно так и делают.
Соседняя глава
Leaderless-репликация и кворумы
Соседняя глава распространяет пользовательские данные через кворумную запись на любую реплику. Эта глава — про слой ниже: как узлы вообще узнают, кто в кластере и кто из них ещё жив.
Две соседние главы решают задачу согласия о данных. В -репликации согласованность держится на арифметике — записать на N реплик, прочитать из R. В главе про согласие достигается через лидера и большинство, с одной линеаризуемой историей. Но и кворум, и консенсус опираются на незаметную предпосылку: каждый узел знает, кто ещё в кластере и кто из соседей сейчас жив.
Эта глава — про тот самый незаметный слой: членство (membership) и обнаружение отказов (failure detection). В кластере из тысяч узлов нет центрального координатора, который ведёт список живых, — иначе он стал бы и узким местом, и единой точкой отказа. Информацию приходится распространять децентрализованно: каждый узел периодически болтает со случайными соседями, и слухи о новых узлах, ушедших узлах и отказах расходятся по кластеру сами, как эпидемия.
Отсюда два героя главы. Gossip-протоколы (их же зовут эпидемическими) отвечают за распространение: за O(log N) раундов слух доходит до всех. SWIM и φ-accrual отвечают за вторую половину — как надёжно решить, что узел отказал, не объявив мёртвым того, кто просто притормозил. Вместе они дают масштабируемое членство без лидера — фундамент, на котором стоят Cassandra, Consul и Serf.
Gossip и SWIM нужны там, где кластер слишком велик для центрального реестра, а полная схема «каждый шлёт каждому» захлёбывается в O(N²) трафике. Цена децентрализации — представления о членстве: узлы какое-то время видят чуть разные списки, а детектор отказов принципиально может ошибаться. Задача протоколов — сделать эти расхождения короткими, а ошибки — редкими.
Почему не лидер
Консенсус: Paxos и Raft
Можно было бы вести единый список членов через консенсус. Но прогонять каждый сигнал присутствия (heartbeat) через лидера и большинство — это убить масштаб ради точности, которая в задаче живости и не нужна.
Зачем: почему сигнал присутствия по схеме all-to-all не масштабируется
Наивное решение задачи «кто жив» очевидно: пусть каждый узел шлёт каждому остальному, и если от соседа давно нет вестей — считаем его мёртвым. Для пяти узлов это прекрасно работает. Для пяти тысяч — ломается по трём осям сразу.
Трафик O(N²)
При all-to-all каждый узел шлёт N−1 сигнал присутствия за период, и всего по сети летит порядка N² сообщений. На 1000 узлов это около миллиона пакетов за интервал — нагрузка растёт квадратично, и сеть упирается раньше, чем CPU.
Нагрузка на каждый узел
Узлу приходится поддерживать таймер и состояние по каждому из N−1 соседей и обрабатывать входящий поток от всех них. Память и обработка на узел растут линейно с размером кластера — плохо для тысяч узлов.
Чувствительность тайм-аутов
Чтобы быстро ловить отказы, тайм-аут делают коротким — но тогда любой всплеск задержки даёт лавину ложных срабатываний. Делают длинным — отказ замечают медленно. Идеального значения нет.
Ключевая идея, которая всё спасает: не нужно, чтобы каждый проверял каждого. Если узел рассылает свой статус лишь нескольким случайным соседям, а те — своим, информация всё равно расходится по всему кластеру — но нагрузка на узел становится постоянной, не зависящей от N. Это и есть переход от детерминированного all-to-all к вероятностному gossip.
Эпидемические протоколы: push, pull и O(log N) раундов
(он же эпидемический) работает по аналогии с распространением слуха или инфекции. В каждом раунде узел выбирает случайного соседа и обменивается с ним частью своего состояния. Один заражённый узел на следующем шаге заражает соседа — заражённых становится двое, потом четверо, восемь. Число осведомлённых удваивается каждый раунд, поэтому слух доходит до всех N узлов за O(log N) раундов — для миллиона узлов это около двадцати раундов.
Эпидемическое распространение: число знающих удваивается каждый раунд
Один узел знает новость. Каждый раунд знающий заражает случайного соседа — 1, 2, 4, 8… За O(log N) раундов охвачен весь кластер, а каждый узел шлёт лишь по одному сообщению за раунд.
Push
Заражённый узел проталкивает новость случайному соседу. Распространяется молниеносно, пока заражённых мало, но к концу буксует: почти все уже знают, и push всё чаще попадает в уже осведомлённого.
Pull
Узел сам запрашивает у случайного соседа: «что нового?». Эффективен на финальной стадии — когда осведомлённых уже большинство, неосведомлённый почти наверняка наткнётся на того, кто расскажет.
Push-pull
Стороны обмениваются состоянием в обе стороны за один раунд. Сочетает быстрый старт push с быстрым финишем pull — на практике сходится быстрее всего, поэтому используется чаще всего.
Важно различать две стратегии, описанные ещё в классической статье Demers и др. (Xerox PARC, 1987). Rumor-mongering (распространение слуха) — узел активно «горит» новостью и шлёт её соседям, но через несколько повторных попаданий в уже знающего перестаёт: быстро, дёшево, но без гарантии, что дошло до каждого. — узлы периодически сверяют всё состояние целиком и подтягивают расхождения: медленнее и дороже, зато гарантированно сходится. На практике их сочетают: rumor для скорости, anti-entropy как страховка, что ни одно обновление не потеряется насовсем.
Фундаментальный предел
Теорема CAP
Невозможность идеального детектора отказов — родственница CAP: в асинхронной сети нельзя отличить упавший узел от медленного, поэтому детектор вынужден выбирать между точностью и полнотой.
Детекторы отказов: полнота, точность и почему идеала нет
Прежде чем чинить SWIM, договоримся о терминах. Теорию заложили Chandra и Toueg (1996), формализовав ненадёжные детекторы отказов двумя свойствами.
Полнота (completeness)
Каждый реально упавший узел рано или поздно будет заподозрен всеми (или хотя бы одним) корректными узлами. Полнота отвечает за то, чтобы отказ не остался незамеченным — ни один мертвец не «притворится живым» навсегда.
Точность (accuracy)
Корректный (живой) узел не должен быть ошибочно заподозрен. Точность отвечает за отсутствие ложных срабатываний — чтобы здоровый узел не выбросили из кластера только за то, что его пакет задержался.
Фундаментальная ловушка: в чисто (нет верхней границы на задержку сообщения) совершенный детектор отказов невозможен. Получив молчание соседа, узел не может отличить «он упал» от «его ответ ещё в пути». Любой тайм-аут — это ставка: короткий повышает полноту ценой точности (ловим отказы быстро, но плодим ложные срабатывания), длинный — наоборот. Это та же дилемма, что у в CAP: нельзя одновременно быть и быстрым, и непогрешимым. Практические детекторы лишь сдвигают баланс, а не устраняют компромисс.
Где это используется
Leaderless-репликация
Список живых узлов из SWIM — это вход для маршрутизации записи в хранилище без выделенного ведущего узла (leaderless): координатор шлёт запись только тем репликам, что детектор считает доступными.
SWIM: косвенный ping и разделение детекции и распространения
SWIM (Scalable Weakly-consistent Infection-style process group Membership) — протокол Das, Gupta и Motivala, представленный на конференции DSN 2002. Его главное архитектурное решение — разделить две задачи, которые наивный смешивает: обнаружение отказа и распространение этого факта. Детекция работает через ping, а распространение — через piggyback поверх тех же сообщений (об этом — следующая секция).
SWIM: прямой ping, затем косвенный ping-req через k посредников
Узел A пингует случайного соседа D. Нет ответа — A не объявляет отказ, а просит k посредников (B, C) пингануть D их путями. Молчит и на них — только тогда D становится suspect.
Прямой ping
Каждый период узел выбирает одного случайного члена и шлёт ему ping, ожидая ack. Не N−1 сообщений, а одно — поэтому нагрузка на узел постоянна и не зависит от размера кластера. Пришёл ack вовремя — сосед жив, инцидент исчерпан.
Косвенный ping-req (через k узлов)
Если ack не пришёл, узел не спешит объявлять отказ. Он просит k случайных других членов: «пингани его за меня» (ping-req). Те шлют свои ping и пересылают ответ. Так отсеивается случай, когда виноват не сосед, а конкретная пара путей или временный потерянный пакет.
Косвенный ping — сердце точности SWIM. Прямой запрос мог потеряться из-за сети именно на маршруте между этими двумя узлами. Спросив у k посредников, идущих другими путями, узел резко снижает шанс ложного срабатывания: чтобы цель сочли мёртвой, она должна молчать и на прямой ping, и на k косвенных — а это уже куда более надёжный сигнал, чем один пропущенный .
Suspicion и incarnation-номера: как не убить живого
Даже после k косвенных ping узел мог не ответить из-за паузы GC или всплеска задержки. Чтобы не выбрасывать таких из кластера, SWIM вводит промежуточное состояние и механизм «опровержения».
Suspect, а не dead
Не дозвонившись, узел помечает цель не «мёртвой», а подозреваемой (suspect) и распространяет это подозрение. Запускается таймер: если за отведённое время никто подозрение не опроверг — статус повышается до confirmed dead, и узел исключается из членства.
Опровержение (refute)
Подозреваемый узел рано или поздно узнаёт, что про него ходит слух «suspect». Если он жив, он опровергает подозрение, рассылая «я жив» с увеличенным incarnation-номером. Слух о смерти гасится прежде, чем дойдёт до confirm.
Incarnation-номер
У каждого узла есть монотонный счётчик «воплощений» (incarnation). Менять статус узла может только он сам — повышая свой номер. Сообщение «alive» с бо́льшим incarnation бьёт «suspect» со старым. Так разрешаются гонки между слухами «жив»/«подозреваю».
Зачем incarnation вообще нужен: без него слух «A мёртв» и слух «A жив» конкурировали бы без правила старшинства, и устаревшее подозрение могло бы вечно «воскрешать-убивать» узел. Привязав право менять статус к самому узлу и его растущему счётчику, SWIM делает порядок событий однозначным: свежее воплощение всегда побеждает. По духу это близко к version-векторам из соседней главы про репликацию — монотонный номер разводит конкурентные утверждения о состоянии.
Распространение членства поверх gossip: piggyback на ping
Обнаружить отказ — половина дела; о нём должен узнать весь кластер. Наивно было бы слать отдельный мультикаст «узел X умер». SWIM поступает экономнее: подсаживает (piggyback) новости о членстве в уже летящие ping, ack и ping-req. Отдельных сообщений для распространения нет вовсе.
Бесплатный канал распространения
К каждому пробному сообщению прицепляется небольшой список свежих изменений членства: «X присоединился», «Y под подозрением», «Z подтверждён мёртвым». Раз ping всё равно летит каждый период, распространение едет «зайцем» и почти не добавляет трафика.
Инфекционная динамика
Поскольку цели ping выбираются случайно, новость о членстве расходится как инфекция — те самые O(log N) раундов до полного охвата. Чтобы не возить устаревшее вечно, каждое изменение подсаживают лишь несколько раз, отдавая приоритет более новым.
Именно это разделение — детекция через ping, распространение через piggyback — вынесено в само название: infection-style membership. Нагрузка на узел остаётся постоянной (один ping за период плюс k косвенных при сбое), а время сходимости растёт лишь логарифмически. Так SWIM держит и трафик, и память на узел независимыми от размера кластера — ровно то, чего не умел heartbeat-all-to-all.
Связь со временем
Синхронизация часов
φ-accrual оценивает «нормальный» интервал между сигналами присутствия по истории прибытий — он адаптируется к дрейфу и джиттеру вместо жёсткого порога, привязанного к абсолютному времени.
φ-accrual: непрерывная подозрительность вместо бинарной
Бинарный тайм-аут заставляет принимать решение раньше времени: в момент порога узел разом переходит из «жив» в «мёртв», хотя уверенности ещё нет. Accrual-детекторы снимают эту резкость. Их идею ввели Hayashibara, Défago, Yared и Katayama в статье «The φ Accrual Failure Detector» (SRDS 2004). Ключевой сдвиг: детектор выдаёт не бинарное «жив / мёртв», а непрерывное число подозрительности φ — насколько сильно стоит сомневаться в узле прямо сейчас. Решение «считать ли отказом» отдаётся приложению через порог.
φ-accrual: подозрительность растёт плавно, а не скачком
Бинарный тайм-аут переключает «жив→мёртв» одним порогом. φ-accrual выдаёт непрерывное φ: оно низкое сразу после и плавно растёт с тишиной. Приложение выбирает свой порог — осторожный или агрессивный.
Как считается φ
Детектор копит историю интервалов между приходящими и оценивает их распределение. По времени с последнего сигнала он вычисляет φ — это, грубо, логарифм вероятности, что узел ещё ответит. Чем дольше тишина относительно привычного ритма, тем выше φ. Растёт оно плавно, а не скачком на тайм-ауте.
Адаптация к джиттеру
Поскольку порог берётся из наблюдаемой истории, детектор сам подстраивается под сеть. На стабильном канале φ взлетает быстро — отказ ловится резво. На капризном, с большим джиттером, тот же порог φ соответствует более долгой тишине — и здоровые узлы не выбрасываются за случайный всплеск задержки.
Практическая выгода: один и тот же порог φ (скажем, φ = 8) даёт осмысленный уровень уверенности в разных условиях, тогда как жёсткий тайм-аут в секундах пришлось бы перенастраивать под каждый дата-центр. Разные подсистемы могут читать одно значение φ с разными порогами: осторожный сервис ждёт φ = 12, агрессивный реагирует уже на φ = 5 — детектор общий, а политика у каждого своя.
Реальная система
Apache Cassandra
Членство и распространение состояния — через gossip с (generation, version), живость — через вариант φ-accrual детектора с порогом phi_convict_threshold.
Системы: Cassandra, Consul/Serf, memberlist и Lifeguard
Эти протоколы — не теория из статей, а рабочая основа промышленных кластеров. Две большие линии: Cassandra (gossip + φ-accrual) и экосистема HashiCorp (SWIM + Lifeguard поверх memberlist).
| Система | Членство / распространение | Детектор отказов |
|---|---|---|
| Apache Cassandra | Gossip раз в секунду со случайными узлами; состояние версионируется парой (generation, version); начальная загрузка (bootstrap) через seed-узлы | Вариант φ-accrual: каждый узел независимо «осуждает» (convict) соседа, если φ превышает phi_convict_threshold по истории heartbeat |
| HashiCorp Serf | Поверх memberlist: SWIM-распространение событий членства через piggyback; user-события и запросы по тому же gossip | SWIM: прямой ping + косвенный ping-req через k узлов, suspicion-механизм с опровержением |
| HashiCorp memberlist | Библиотека SWIM-членства; ускоренное распространение и сходимость, отложенная согласованность списка | SWIM + расширения Lifeguard: учёт «локального здоровья» детектора против ложных срабатываний при тормозах узла |
| Consul / Nomad | Используют Serf/memberlist для обнаружения узлов и LAN/WAN-членства поверх той же gossip-основы | SWIM + Lifeguard из memberlist; согласие о данных при этом — отдельный Raft-консенсус, не gossip |
Lifeguard (HashiCorp Research, статья «Lifeguard: Local Health Awareness for More Accurate Failure Detection», arXiv 2017) — набор улучшений SWIM. Главная мысль: ложные срабатывания часто вызывает не отказ соседа, а собственное нездоровье узла-детектора (нехватка CPU, потери пакетов). Lifeguard вводит «локальное здоровье»: притормаживающий узел становится осторожнее, прежде чем обвинять других, и даёт подозреваемому больше шанса опровергнуть. По заявлению авторов, это резко снижает долю ложных срабатываний, не замедляя детекцию реальных отказов (оценка из их статьи, не независимый бенчмарк).
Компромиссы: скорость, ложные срабатывания и разделы
Скорость детекции против ложных срабатываний
- Короткий тайм-аут и низкий порог φ ловят отказ быстро — но плодят ложные срабатывания на джиттере.
- Косвенный ping и suspicion смещают баланс к точности, добавляя небольшую задержку перед confirm.
- Подбор k, числа раундов suspicion и порога φ — это явная настройка точки между полнотой и точностью.
Нагрузка на сеть и поведение при разделах
- Gossip держит трафик и память на узел постоянными — ценой того, что членство согласовано лишь отложенно.
- При каждая сторона объявит другую мёртвой; после восстановления узлы воскресают через свежий incarnation.
- Gossip даёт членство, но не консенсус: для линеаризуемых решений (кто лидер, кому шард) поверх берут отдельный консенсус.
Частые ошибки
- Ждать от детектора непогрешимости. В асинхронной сети ложные срабатывания неизбежны; система должна переживать ошибочное «узел мёртв», а не падать от него.
- Путать членство с консенсусом. Gossip согласует «кто в кластере» лишь отложенно — на нём нельзя строить выбор лидера или уникальность без отдельного консенсуса.
- Жёсткий тайм-аут в секундах на все среды. То, что норма в одном дата-центре, — ложные срабатывания в другом; φ-accrual и Lifeguard как раз про адаптацию.
- Игнорировать раздел. Без incarnation-номеров и опровержения восстановившийся раздел оставит узлы навсегда «мёртвыми» друг для друга.
Что важно запомнить
- Сигнал присутствия по схеме all-to-all не масштабируется: O(N²) трафика и линейная нагрузка на узел. Gossip заменяет это случайной болтовнёй с постоянной нагрузкой на узел.
- Эпидемическое распространение доходит до всех за O(log N) раундов; push быстр в начале, pull — в конце, push-pull сходится быстрее всего.
- Идеального детектора отказов в асинхронной сети нет: нельзя отличить упавший узел от медленного, поэтому всегда выбираешь между полнотой и точностью.
- SWIM разделяет детекцию (прямой ping + косвенный ping-req через k узлов) и распространение (piggyback на ping), а suspicion и incarnation-номера гасят ложные срабатывания.
- φ-accrual выдаёт непрерывную подозрительность вместо бинарной и адаптируется к джиттеру сети, отдавая решение приложению через порог.
- В бою это Cassandra (gossip + φ-accrual) и экосистема HashiCorp (SWIM + Lifeguard в memberlist); для линеаризуемых решений поверх членства берут отдельный консенсус.
Источники и материалы
Карта источников: SWIM держит membership и infection-style dissemination; φ-accrual paper — вероятностную модель подозрения; Lifeguard/memberlist — практические улучшения SWIM; Cassandra docs — эксплуатационный пример gossip и Phi Accrual. Probe interval, suspicion timeout и φ-threshold зависят от задержек сети, профиля потерь и цены ложного срабатывания.
Связанные главы
- Leaderless-репликация и кворумы - Соседняя глава распространяет данные через кворумную запись на любой узел; здесь — как сами узлы узнают друг о друге и о живости соседей.
- Консенсус: Paxos и Raft - Контрастный подход к согласию через лидера и большинство; gossip же намеренно отказывается от единой истины ради масштаба.
- Теорема CAP - Объясняет, почему детектор отказов вынужден гадать при разделении: нельзя одновременно быть точным и полным в асинхронной сети.
- Apache Cassandra - Реальная система, где членство держится на gossip, а живость узлов — на φ-accrual детекторе отказов.