1. Gossip Протокол. Часть 1
  2. Gossip Протокол. Часть 2

Реализация Gossip Protocol

Протокол передает сообщения по протоколу UDP или TCP с настраиваемым, но фиксированным интервалом. Для определения узлов для обмена сплетнями протокол использует службу подбора узлов. Служба использует рандомизированный алгоритм для выбора подходящего узла. API службы должен обеспечивать следующие методы:

  • /gossip/init: возвращает список узлов, известных конкретному узлу при запуске
  • /gossip/get-peer: возвращает адрес (IP-адрес и номер порта) выбранного службой peer узла

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

Состояние приложения может передаваться в виде пар ключ-значение по протоколу gossip. При многократном изменении одного и того же ключа узлом должно передаваться самое последнее значение.

API протокола для организации обмена состояниями приложений:

  • /gossip/on-join
  • /gossip/on-alive
  • /gossip/on-dead
  • /gossip/on-change

Начальные узлы(seed nodes) - это полнофункциональные узлы, основанные на статической конфигурации. Каждый узел в системе должен знать о начальных узлах. Система сплетен взаимодействует с начальными узлами для предотвращения логических разделений.

Ниже приведен высокоуровневый процесс работы узла, когда он получает сплетенное сообщение с метаданными другого peer узла:

  1. сравнивает входящее сообщение, чтобы определить недостающие значения в наборе данных локального узла
  2. сравнивает входящее сообщение для выявления недостающих значений в наборе данных peer узла
  3. более высокое значение версии выбирается в том случае, если узел уже содержит значения, присутствующие во входящем сообщении
  4. добавить недостающие значения в набор данных локального узла
  5. вернуть в ответ недостающие значения в наборе данных peer узла
  6. обновить набор данных peer узла с помощью полученного ответа

Обычно при запуске узла все метаданные узла передаются по протоколу сплетен. Номер версии в памяти может поддерживаться каждым узлом для передачи только инкрементных обновлений метаданных узла по протоколу gossip.

Generation clock представляет собой монотонно возрастающее число, указывающее на поколение сервера. Generation clock увеличивается при каждом перезапуске узла. Номер версии гарантирует упорядоченность и версионность состояния приложения. Номер версии может только увеличиваться. Часы поколения могут использоваться вместе с номером версии для корректного определения изменений метаданных узла при его перезагрузке.

Gossiper timer - это компонент протокола, который гарантирует, что каждый узел в конечном итоге будет содержать важные метаданные об peer узлах, включая узлы, находящиеся вне сети. Каждый узел содержит связанный с ним heartbeat. Состояние heartbeat состоит из поколения и номера версии. Состояние приложения состоит из пар ключ-значение, представляющих состояние узла и номер версии.

Узел, инициирующий обмен сплетнями, посылает сообщение gossip digest synchronization, состоящее из списка gossip digests. Дайджест сплетен состоит из адреса конечной точки, номера поколения и номера версии. Сообщение о подтверждении сплетни состоит из списка сплетен и списка состояний конечных точек.

Примерная схема сплетенного дайджеста выглядит следующим образом:

EndPointState: 10.0.1.42  
  HeartBeatState: generation: 1259904231, version: 761  
  ApplicationState: "average-load": 2.4, generation: 1659909691, version: 42  
  ApplicationState: "bootstrapping": pxLpassF9XD8Kymj, generation: 12

Примеры использования Gossip Protocol

Протокол сплетен используется во множестве приложений, где желательно достижение конечной согласованности(eventual consistency).

  • репликация баз данных
  • распространение информации
  • поддержание членства в кластере
  • обнаружение сбоев
  • создание агрегатов (вычисление среднего, максимального, суммы)
  • создание оверлейных сетей
  • выборы лидера

Протокол сплетен может быть использован для обнаружения отказа узла в распределенной системе с высокой вероятностью. Обнаружение отказа узлов позволяет экономить такие ресурсы, как процессор, пропускная способность и место в очереди. В распределенной системе недостаточно констатировать отказ узла, когда один клиент не может взаимодействовать с конкретным узлом, поскольку может произойти разделение сети(network partition) или отказ клиента. Можно с уверенностью утверждать об отказе конкретного узла, если несколько узлов (клиентов) подтверждают его работоспособность с помощью протокола сплетен.

Протокол сплетен значительно более надежен для обмена данными и командами, чем соединения по протоколу TCP. Протокол позволяет абстрагировать обмен данными о свойствах узлов и подсистем от логики приложения. Статистика узла, такая как средняя загрузка и свободная память, может быть передана в сплетенных сообщениях для улучшения локального принятия решений о выводе узла из работы.

Информация о подсистеме, например глубина очереди, ключевые метаданные, такие как изменения конфигурации, и даже запрос-ответ могут быть переданы по протоколу gossip. Агрегация сообщений об обновлении узлов по протоколу сплетен позволяет передавать данные одним куском, а не несколькими небольшими сообщениями, что снижает накладные расходы на связь.

Сообщения могут быть оптимально направлены по кластеру путем определения liveness узлов. Принятие решений на локальном уровне узла без привлечения централизованной службы является ключом к масштабированию протокола сплетен. Сообщения могут быть версионированы с помощью векторных часов(vector clock) для игнорирования узлом более старых версий сообщений.

В реальном мире протокол сплетен используется в следующих системах:

  • Apache Cassandra использует протокол gossip для поддержания членства в кластере, передачи метаданных узла (назначение маркера), восстановления непрочитанных данных с помощью деревьев Меркла(Merkle trees) и обнаружения отказов узлов.
  • Consul использует вариант протокола swim-gossip для членства в группах, избрания лидеров и обнаружения отказов агентов consul
  • CockroachDB использует протокол сплетен для распространения метаданных узла
  • Блокчейн Hyperledger Fabric использует протокол gossip для членства в группах и передачи ledger metadata
  • Riak использует протокол gossip для передачи consistent hash ring и метаданных узлов по кластеру.
  • Amazon S3 использует протокол gossip для распространения информации о состоянии сервера по всей системе
  • В Amazon Dynamo используется протокол для обнаружения отказов и отслеживания принадлежности узлов.
  • Кластер Redis использует протокол сплетен для распространения метаданных узлов
  • Bitcoin использует протокол сплетен для распространения значения nonce среди майнинговых узлов

Преимущества Gossip Protocol

Масштабируемость (Scalability)

Масштабируемость - это способность системы справляться с возрастающей нагрузкой без снижения производительности. Цикл протокола требует логарифмического времени для достижения сходимости. Кроме того, каждый узел взаимодействует только с фиксированным числом узлов и посылает только фиксированное число сообщений, не зависящее от числа узлов в системе. Узел не ожидает подтверждения для уменьшения задержек(latency).

Отказоустойчивость (Fault Tolerance)

Отказоустойчивость - это способность системы сохранять работоспособность при возникновении сбоев, таких как выход из строя узлов, разделение сети(network partitions) или потеря сообщений. Распределенная система, использующая протокол сплетен, является отказоустойчивой благодаря толерантности к ненадежным сетям. Избыточность, параллелизм и случайность, обеспечиваемые протоколом сплетен, повышают отказоустойчивость системы.

Кроме того, симметричная и децентрализованная природа узлов повышает отказоустойчивость протокола сплетен. Одно и то же сообщение обычно передается несколько раз через несколько узлов. Другими словами, существует множество маршрутов для передачи сообщений между источником и пунктом назначения. Таким образом, отказ узла преодолевается путем передачи сообщения через другой узел.

Надежность (Robustness)

Симметричный характер узлов, участвующих в протоколе сплетен, повышает устойчивость системы. Отказ узла не нарушает качества работы системы. Протокол сплетен также устойчив к переходным разделам сети. Однако протокол сплетен не устойчив к неисправному узлу или злонамеренному сообщению сплетен, если только данные не являются самопроверяемыми.

Для предотвращения повреждения системы сплетен вредоносными узлами можно использовать систему репутации узлов на основе баллов. Для обеспечения конфиденциальности и безопасности системы сплетен должны быть реализованы соответствующие механизмы и политики, такие как шифрование, аутентификация и авторизация.

Конвергентная согласованность (Convergent Consistency)

Согласованность - это техника обеспечения одинакового представления состояния для каждого узла системы. Различные уровни согласованности, такие как сильная(strong), конечная(eventual), причинная(causal) и вероятностная(probabilistic) согласованность, оказывают различное влияние на производительность, доступность и корректность системы. Протокол сплетен сходится к согласованному состоянию за логарифмическое по сложности время за счет экспоненциального распространения данных.

Децентрализация (Decentralization)

Протокол сплетен предлагает чрезвычайно децентрализованную модель поиска информации через одноранговую связь.

Простота (Simplicity)

Большинство вариантов протокола сплетен может быть реализовано с помощью очень небольшого количества кода и низкой сложности. Симметричная природа узлов делает выполнение протокола сплетен тривиальным.

Интеграция и взаимодействие (Integration and Interoperability)

Протокол сплетен может быть интегрирован и взаимодействовать с такими компонентами распределенной системы, как база данных, кэш и очередь. Для реализации протокола сплетен в различных компонентах распределенной системы должны быть определены общие интерфейсы, форматы данных и протоколы.

Ограниченная нагрузка (Bounded Load)

Классические протоколы распределенных систем обычно генерируют большие всплески нагрузки, которые могут перегрузить отдельные компоненты распределенной системы. Протокол сплетен создает только строго ограниченную наихудшую нагрузку на отдельные компоненты распределенной системы, что позволяет избежать нарушения качества обслуживания. Выбор peer узлов в протоколе сплетен может быть настроен таким образом, чтобы снизить нагрузку на сетевые каналы. На практике нагрузка, создаваемая протоколом сплетен, не только ограничена, но и пренебрежимо мала по сравнению с доступной пропускной способностью.

Недостатки Gossip Protocol

Согласованность в конечном итоге (Eventually Consistent)

Протокол относительно медленнее по сравнению с многоадресной рассылкой(multicast). Также существуют накладные расходы, связанные с сообщениями сплетен, а поведение сплетен зависит от топологии сети и неоднородности узлов. Поэтому будет наблюдаться некоторая задержка при распознавании кластером нового узла или отказа узла.

Неосведомленность о разделе сети (Network Partition Unawareness)

Когда происходит разделение сети, узлы, входящие в это подразделение, продолжают сплетничать друг с другом. Таким образом, протокол сплетен не знает о разделах сети и может существенно задерживать распространение сообщений.

Пропускная способность (Bandwidth)

Протокол сплетен не отличается эффективностью, поскольку одно и то же сообщение может быть передано одному и тому же узлу несколько раз, расходуя ненужную пропускную способность. Хотя использование полосы пропускания протоколом сплетен ограничено благодаря ограниченному размеру сообщения и периодическому обмену сообщениями, эффективное распространение сплетен может ухудшиться, когда объем информации, которую должен передать узел, превысит ограниченный размер сообщения.

Точка насыщения(saturation) протокола сплетен зависит от различных параметров, таких как скорость генерации сообщений, размер сообщения, fanout и тип протокола сплетен.

Задержка (Latency)

Использование протокола сплетен приводит к увеличению задержки, поскольку для передачи сообщения узел должен дождаться следующего цикла (интервала) сплетен. Не сообщение запускает обмен сплетнями, а таймер интервала протокола сплетен. Временная сложность, необходимая для распространения сообщения по системе, является логарифмической.

Отладка и тестирование (Debugging and Testing)

Отладка - это выявление и устранение неисправностей, которые приводят к отклонению поведения протокола сплетен от ожидаемого. Тестирование - это возможность проверить, соответствует ли протокол сплетен функциональным и нефункциональным требованиям, таким как производительность, надежность и безопасность.

Присущий протоколу сплетен недетерминизм и распределенная природа затрудняют отладку и воспроизведение сбоев. Для тестирования и отладки системы сплетен можно использовать такие средства и методы, как моделирование, эмуляция, протоколирование, трассировка, мониторинг и визуализация.

Вычислительные ошибки (Computational Error)

Протокол сплетен подвержен вычислительным ошибкам, вызванным злонамеренными узлами. Узлы должны реализовывать механизм самокоррекции, поскольку устойчивость протокола сплетен ограничена определенными классами сбоев. Тем не менее, протокол сплетен чрезвычайно надежен.

Источники

  1. Architecture Gossip, Cassandra
  2. Ken Birman, The Promise, and Limitations, of Gossip Protocols
  3. Felix Lopez, Introduction to Gossip
  4. Unmesh Joshi, Gossip Dissemination

Комментарии в Telegram-группе!