- Gossip Протокол. Часть 1
- Gossip Протокол. Часть 2
Gossip (сплетник) — это группа протоколов в одноранговой компьютерной коммуникации, в которых распространение информации идёт способом, схожим с образом распространения эпидемий, и сводящимся к тому, что каждый или некоторые из узлов могут передавать обновляемые данные известным этому узлу соседям.
Типичными проблемами распределенных систем:
- поддержание состояния системы (liveness of nodes)
- коммуникация между узлами
Возможные решения этих проблем:
- централизованная служба управления состоянием
- одноранговая служба управления состоянием
Централизованная служба управления состоянием
Централизованный сервис управления состоянием, например Apache Zookeeper, может быть сконфигурирован как сервис обнаружения (service discovery) для отслеживания состояния каждого узла в системе. Хотя такой подход обеспечивает сильную гарантию согласованности(strong consistency), его основные недостатки заключаются в том, что служба управления состоянием становится единой точкой отказа и сталкивается с проблемами масштабируемости для больших распределенных систем.
Одноранговая служба управления состоянием (Peer-To-Peer)
Одноранговый подход к управлению состоянием склонен к высокой доступности (high availability) и конечной согласованности (eventual consistency). Алгоритмы протокола gossip могут быть использованы для реализации одноранговых сервисов управления состоянием с высокой масштабируемостью (high scalability) и повышенной устойчивостью(improved resilience).
Broadcast Protocols
В распределенных системах распространены следующие методы передачи сообщений:
- point-to-point broadcast
- eager reliable broadcast
- gossip protocol
Point-To-Point Broadcast
Производитель (producer) отправляет сообщение непосредственно потребителям (consumer) в режиме point-to-point broadcast. Механизм повторных попыток на производителе и механизм дедупликации на потребителях делают трансляцию “точка-точка” надежной. Сообщения будут потеряны при одновременном отказе производителя и потребителя.
Eager Reliable Broadcast
Каждый узел ретранслирует сообщения всем другим узлам по надежным сетевым каналам. Такой подход обеспечивает повышенную отказоустойчивость, поскольку сообщения не теряются при одновременном отказе производителя и потребителя. Сообщение будет повторно передано оставшимися узлами.
К недостаткам eager reliable broadcast можно отнести следующие:
- значительное использование пропускной способности сети из-за O(n²) сообщений, передаваемых для n-ного числа узлов
- узел-отправитель может стать узким местом из-за O(n) линейной трансляции
- каждый узел хранит список всех узлов системы, что приводит к увеличению затрат на хранение данных
Gossip Protocol
Gossip Protocol(Протокол сплетен) представляет собой децентрализованную одноранговую коммуникационную технику для передачи сообщений в огромной распределенной системе. Ключевая концепция протокола заключается в том, что каждый узел периодически посылает сообщение подмножеству других случайных узлов. В конечном итоге вся система с высокой вероятностью получит конкретное сообщение.
Говоря простым языком, gossip protocol - это техника построения узлами глобальной карты через ограниченное локальное взаимодействие.
Gossip протокол построен на основе надежного(robust), масштабируемого(scalable) и в конечном итоге согласованного алгоритма(eventually consistent). Протокол сплетен обычно используется для поддержания списка членов узла, достижения консенсуса и обнаружения неисправностей в распределенной системе. Кроме того, дополнительная информация, например, данные прикладного уровня, может передаваться в виде сплетен.
Gossip протокол является надежным, поскольку отказ узла может быть преодолен повторной передачей сообщения другим узлом. С помощью протокола сплетен можно реализовать широковещательную передачу по принципу FIFO, причинно-следственную передачу(causality broadcast) и передачу в общем порядке(total order broadcast).
Параметры протокола, такие как цикл(cycle) и fanout, могут быть настроены для улучшения вероятностных гарантий протокола. Следующие инструменты предлагают высококлассное моделирование и визуализацию протокола:
Следующие характеристики gossip протокола делают его оптимальным выбором в качестве коммуникационного протокола в крупномасштабной распределенной системе:
- ограничивает количество сообщений, передаваемых каждым узлом
- ограничивает потребление полосы пропускания(the bandwidth consumption) для предотвращения снижения производительности приложения
- устойчивость к отказам сети и узлов
Протокол сплетен может быть использован для обеспечения согласованности узлов только в том случае, если выполняемые операции коммутативны и сериализуемость не требуется.
Tombstone - это специальная запись для аннулирования записей данных, имеющих совпадающий ключ, без фактического удаления данных. Протокол удаляет данные из узла с помощью tombstone.
Types Of Gossip Protocol
При выборе типа протокола для конкретного случая использования необходимо учитывать время, необходимое протоколу для распространения сообщения по системе, и сетевой трафик, генерируемый при распространении сообщения. В целом протоколы сплетен можно разделить на следующие типы:
- антиэнтропийная модель(anti-entropy model)
- модель распространения слухов (rumor-mongering model)
- модель агрегирования (aggregation model)
Anti-Entropy Gossip Protocol
Алгоритм антиэнтропии был введен для уменьшения энтропии между репликами сервиса с состоянием(stateful), например базы данных. Реплицированные данные сравниваются, и разница между репликами исправляется. Узел с самым новым сообщением делится им с другими узлами в каждом gossip раунде.
При использовании антиэнтропийной модели обычно передается весь набор данных, что приводит к излишнему расходованию пропускной способности (bandwidth). Такие методы, как контрольная сумма, список последних обновлений и дерево Меркла (Merkle tree), могут быть использованы для выявления различий между узлами, чтобы избежать передачи всего набора данных и уменьшить пропускную способность сети. Антиэнтропийный протокол будет посылать неограниченное количество сообщений без завершения.
Rumor-Mongering Gossip Protocol
Протокол распространения слухов известен также как протокол распространения информации(dissemination protocol). Цикл распространения слухов происходит относительно чаще, чем антиэнтропийные циклы, и наводняет сеть наихудшей нагрузкой(worst-case load). Модель распространения слухов использует меньше ресурсов, таких как пропускная способность сети, поскольку между узлами передаются только последние обновления.
Чтобы ограничить количество сообщений, после нескольких раундов общения они помечаются как удаленные. Обычно существует высокая вероятность того, что сообщение достигнет всех узлов.
Aggregation Gossip Protocol
Агрегатный протокол сплетен вычисляет общесистемный агрегат(system-wide aggregate) путем выборки информации по каждому узлу и объединения значений для получения общесистемного значения(system-wide value).
Стратегии распространения информации с помощью gossip протокола
Gossip протокол является оптимальной основой для построения высокодоступного сервиса. Стратегия распространения сообщения по gossip протоколу должна выбираться исходя из требований к сервису и доступных условий сети. Для каждой стратегии распространения сообщения существует компромисс в отношении пропускной способности, задержки и надежности. Стратегии распространения сообщений применимы как к антиэнтропийной модели, так и к модели распространения слухов.
Push Model
Push модель эффективна при наличии небольшого количества сообщений об обновлении, что связано с перерасходом трафика. В модели push узел с последним сообщением отправляет его случайному подмножеству других узлов.
Pull Model
В pull модели каждый узел активно опрашивает случайное подмножество узлов на предмет наличия сообщений об обновлении. Этот подход эффективен при большом количестве сообщений об обновлениях, поскольку высока вероятность найти узел с последним сообщением об обновлении.
Push-Pull Model
Модель push-pull оптимальна для быстрого и надежного распространения сообщений об обновлениях. Узел может передать новое сообщение об обновлении, а также опросить узел на предмет получения новых сообщений об обновлении. Подход push эффективен на начальном этапе, когда существует лишь очень небольшое количество узлов с сообщениями об обновлении. Подход pull эффективен на заключительном этапе, когда имеется множество узлов с большим количеством сообщений об обновлении.
Gossip Protocol Performance
Число узлов, которые получат сообщение от конкретного узла, называется fanout. Количество раундов сплетен, необходимое для распространения сообщения по всему кластеру, называется циклом(cycle).
Циклы, необходимые для распространения сообщения по кластеру = O(log n) в базисе fanout, где n = общее число узлов.
Например, для распространения сообщения по 25.000 узлам требуется примерно 15 раундов(gossip rounds). Интервал сплетен может быть установлен на значение 10мс, что позволит распространить сообщение по центру обработки данных примерно за 3 секунды. Распространение сообщения в протоколе сплетен должно автоматически устаревать, чтобы снизить ненужную нагрузку.
Производительность реализации протокола сплетен может быть измерена следующими метриками:
- остаток(residue): количество оставшихся узлов, не получивших сообщения, должно быть минимальным
- трафик(traffic): среднее количество сообщений, передаваемых между узлами, должно быть минимальным
- сходимость(convergence): каждый узел должен получить сообщение как можно быстрее
- среднее время(time average): среднее время, затрачиваемое на отправку сообщения каждому узлу, должно быть низким
- время последнего(time last): время, необходимое для получения сообщения последним узлом, должно быть низким
Свойства gossip протокола
В общем случае предполагается, что протокол сплетен должен удовлетворять следующим свойствам:
- выбор узлов должен быть случайным для осуществления веерной рассылки (fanout)
- каждому узлу доступна только локальная информация, и узлы не знают о состоянии кластера
- коммуникация между узлами предполагает периодическое, попарное, межпроцессное взаимодействие
- ограниченный объем передачи информации за один раунд сплетен
- каждый узел использует один и тот же протокол сплетен
- предполагается ненадежность сетевых путей между узлами
- частота взаимодействия узлов мала
- взаимодействие узлов приводит к обмену состояниями
Gossip Algorithm
В общих чертах алгоритм выглядит следующим образом:
- каждый узел хранит список подмножества узлов и их метаданные
- периодически производится сплетня на случайную конечную точку узла-аналога
- каждый узел проверяет полученное сообщение, чтобы объединить в локальный набор данных наибольший номер версии
Счетчик(heartbeat counter) узла увеличивается всякий раз, когда узел участвует в обмене сплетнями. Узел считается здоровым, если счетчик сердцебиений продолжает увеличиваться. С другой стороны, узел считается нездоровым, если счетчик не изменяется в течение длительного периода времени из-за разделения сети или отказа узла.
Источники
- Architecture Gossip, Cassandra
- Ken Birman, The Promise, and Limitations, of Gossip Protocols
- Felix Lopez, Introduction to Gossip
- Unmesh Joshi, Gossip Dissemination
Комментарии в Telegram-группе!