В этом посте - поверхностный обзор протокола Gossip.
Распределенная система - это система, состоящая из нескольких узлов (серверов) объединенных в сеть, которые выполняют некоторую полезную задачу. В распределенной системе необходимо решать два типа задач:
- Контроль состояния узлов в системе. Работают ли они, отключены ли.
- Осуществление коммуникации между узлами.
Их можно решать двумя способами, используя:
- Централизованный сервис.
- Одноранговый (peer-to-peer) сервис.
1. Централизованный сервис.
Узлы в системе не общаются напрямую. Коммуникация идет через единственный сервис, который можно реализовать в виде Service Discovery. Он в автоматическом порядке будет обнаруживать новые узлы в сети, регистрировать их и мониторить состояние.
Плюсы: Обеспечивается высокий уровень согласованности данных.
Минусы: Централизованный сервис - единая точка отказа.
2. Peer-to-peer сервис.
Коммуникация происходит непосредственно между узлами в сети.
Плюсы: Высокая доступность системы в любой момент времени, нет единой точки отказа.
Минусы: Согласованность может страдать.
Рассмотрим 3 способа организовать peer-to-peer коммуникацию.
- Point-to-point (точка-точка)
- Eager Reliable broadcast (жадная и надежная трансляция)
- Gossip протокол
Point-to-point
В этом случае узел (писатель) оправляет сообщения всем остальным узлам (читателям). На стороне писателя реализован механизм повтора отправки в случае сбоя, а на стороне читателя - механизм устранения дублированных сообщений. Но сообщение все равно может потеряться, если оба узла, читатель и писатель, упадут.
Eager Reliable broadcast
Каждый узел отправляет сообщение каждому из узлов.
Плюсы:
- Высокая отказоустойчивасть. Даже если оба узла упадут, сообщение все равно будет переслано другими узлами.
Минусы:
- Каждый узел хранит информацию обо всех остальных, что приводит увеличению объемов хранилища.
- По сети передается
O(n^2)сообщений, что может занимать значительную ширину полосы пропускания. - Каждый узел отправляет
O(n)сообщений, что может вести к задержкам.
Gossip протокол
Узел периодически отправляет сообщения некоторому случайному подмножеству других узлов.
Это похоже на то, как распространяются сплетни в офисе. Также, по-другому протокол называется epidemic, т.к. похожим образом распространяются эпидемии.
Протокол обеспечивает согласованность данных, т.к. потерянные сообщения будут восстановлены повторной отправкой от других узлов.
Протокол имеет параметры:
- количество соседей, которым узел случайным образом отправит сообщение (fanout)
- количество раз, когда будет повторен цикл отправки (cycle)
Если fanout = 1, то нужно O(log N) циклов, чтобы гарантировать, что все узлы получили сообщение (n - число узлов).
На этом сайте представлена симуляция, которая показывает процент узлов, получивших в итоге сообщение в зависимости от параметров.
Плюсы:
- устойчив к отказам узлов
- занимает ограниченную ширину пропускания
- отправляет меньшее количество сообщений
Типы протоколов gossip:
- Модель анти-энтропии (anti-entropy model)
- Модель распространения слухов (rumor-mongering model)
Аnti-entropy model
Используется для устранения несогласованности между репликами stateful сервиса, например узлами базы данных. Сравниваются две реплики и находятся несоответствия. Затем узел с более новой версией данных рассылает сообщения другим узлам в новых циклах. Чтобы не обновлять весь объем данных в каждом цикле, можно находить конкретное расхождение, например, используя контрольные суммы или дерево Меркла. И обновлять только расходящиеся данные.
Rumor-mongering model
Узел, получая некоторое сообщение, помечает его как “горячее”. Он начинает рассылать его другим узлам. Если некий узел уже получал такое сообщение, второй раз он его не принимает. Наш отправитель, получив некоторое количество отказов, помечает сообщение как “негорячее”, и перестает его рассылать.
Ссылки: