Введение в семейство алгоритмов Gossip (1/4)

#shark_whitepaper

Gossip — ещё одно слово, часто встречающиеся в литературе и бложиках на медиуме, которое скрывает за собой бесконечные пласты статей разных умных дядек. В качестве знакомства, я осилил четыре из них, но расскажу о трёх, а по четвертой пройдусь вскользь, так как она оказалась супер специфичной. Исторически, gossip появился из дремучей работы 1987 году про эпидемические алгоритмы, о которой я писал тут. Информация оттуда не нужна, чтобы понять этот пост, но может быть интересно. Пост из четырёх частей, так что устраивайтесь поудобнее. В первой введение, затем описание самого протокола на псевдокоде, далее работа gossip в очень больших сетях и в завершении, практические применения и проблемы.

Семейство протоколов gossip — это специфичный набор алгоритмов по обмену данными в сети узлов. Идея в следующем: пусть каждый узел раз в промежуток времени находит один из случайных соседних узлов и направляет ему некоторое сообщение. Так делает каждый узел, который уже получил обновления. Когда все узлы направили сообщение, завершается первый раунд обмена. Раунды проходят до тех пор, пока обновление «не потеряет актуальность». Сообщения содержат не только полезные данные, но и информацию о сети, которой обладает узел. Если проще — каждая нода направляет список соседей, о которых знает она сама. Если долго передавать такую информацию, рано или поздно все ноды сети будут знать о существовании всех узлов. Удобно. В некоторых вариантах gossip информация о других нодах сети — это и есть вся полезная нагрузка.

Киллер фича алгоритмов именно в случайном выборе соседней ноды. Именно случайность позволят gossip алгоритму работать даже при отказах значительной части сети. Почему используется слово «протокол», а не «алгоритм» определить сложно. Возможно это связано с тем, что исторически gossip использовался как низкоуровневый подход для обнаружения топологий в огромных сетях. Сетевики вообще любят всё вокруг называть протоколами.

Семейство gossip это десятки вариаций очень похожих алгоритмов, поэтому разумно выделить их общие характеристики:

- Периодический, попарной обмен данными между узлами сети.
- При обмене данных передаётся небольшое количество информации. Gossip протокол в идеальном мире не должен съедать всю пропускную способность сети.
- Обмен данными происходит редко. «Редко» в данном случае значит сильно реже чем средние задержки (latency) в сети. Идеальный gossip не создаёт значимой нагрузки на сеть узлов. Это позволяет использовать gossip, как дополнение к другим алгоритмам обмена данными.
- Надежный канал связи не требуется. Более того, новые узлы могут вступать в сеть даже во время работы алгоритма.
- При взаимодействии между узлами A и B, либо один из них, либо оба сразу меняют своё состояние. Кинуть пинг другому узлу это ещё не gossip.
- Соседние ноды выбираются случайным образом. В идеальном мире с равномерно распределенной вероятностью. В реальности правда достичь её всё равно не удастся, об этом тоже ниже.
- Время распространения обновления по всем узлам сопоставимо с O(log(n)).

Обмен данными между случайными нодами приводит к тому, что gossip протоколы дают только вероятностью консистентность. Здесь речь идёт не столько о вероятности того, что система перейдёт в консистентное состояния, сколько о времени, когда это произойдет — большинство вариаций практически гарантированно смогут распространить данные по сети когда-нибудь. В случае с gossip консистентность можно объяснить фразой на подобии «с вероятностью 99%, через 30 раундов каждая нода в сети получит обновления». Так сказать, how eventual is eventually consistent?