SWIM-протокол
Масштабируемый протокол членства в группах процессов в стиле слабо согласованного заражения (SWIM) — это протокол членства в группах, основанный на «аутсорсинговых контрольных сигналах ». [1] используемый в распределенных системах , впервые представленный Индранилом Гуптой в 2001 году. [2] [3] Это гибридный алгоритм, который сочетает в себе обнаружение сбоев и распространение информации о членстве в группах.
Протокол
[ редактировать ]Протокол состоит из двух компонентов: компонента обнаружения сбоев и компонента распространения .
Компонент детектора отказов работает следующим образом:
- Каждые единицы времени T' , каждый узел ( ) отправляет пинг случайному другому узлу ( ) в своем списке участников.
- Если получает ответ от , решено быть здоровым, и N1 обновляет свою временную метку «последнего известия от» для быть текущим временем.
- Если не получает ответа, связывается с k другими узлами в своем списке ( ) и запрашивает пинг .
- Если через Т' единиц времени: если успешный ответ не получен, знаки как не удалось.
функционирует Компонент распространения следующим образом:
- На обнаружение отказавшего узла , отправляет групповое сообщение остальным узлам в своем списке участников с информацией о вышедшем из строя узле.
- Добровольные запросы узла на вход/выход из группы также отправляются посредством многоадресной рассылки.
Характеристики
[ редактировать ]Протокол предоставляет следующие гарантии:
- Сильная полнота: полная полнота гарантирована (например, сбой любого узла в группе в конечном итоге обнаруживается всеми работающими узлами).
- Время обнаружения : ожидаемое значение времени обнаружения (от отказа узла до обнаружения) равно , где - продолжительность периода протокола, и — доля исправных узлов в группе. [3]
Расширения
[ редактировать ]В исходном документе SWIM перечислены следующие расширения, призванные сделать протокол более надежным: [2]
- Подозрение : узлы, которые не отвечают на сообщения ping, изначально не помечаются как неисправные. Вместо этого они помечаются как «подозрительные»; узлы, обнаружившие «подозрительный» узел, по-прежнему отправляют многоадресную рассылку всем остальным узлам, включая этот механизм. Если «подозрительный» узел отвечает на пинг до достижения определенного порога тайм-аута, «активное» сообщение отправляется через многоадресную рассылку для удаления «подозрительной» метки с узла.
- Распространение в стиле заражения : вместо распространения информации о сбое узла посредством многоадресной рассылки сообщения протокола добавляются к сообщениям ping, используемым для определения работоспособности узла. Это эквивалентно распространению сплетен .
- Выбор цели зонда по круговому алгоритму . Вместо случайного выбора узла для зондирования на каждом временном шаге протокола протокол модифицируется таким образом, что каждый узел выполняет циклический выбор цели зонда. Это ограничивает время обнаружения протокола в наихудшем случае, не ухудшая среднее время обнаружения.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Петров, Алекс (2019). Внутреннее устройство базы данных . О'Рейли Медиа .
- ^ Перейти обратно: а б Гупта, Индранил; Чандра, Тушар Д.; Гольдшмидт, Герман С. (1 августа 2001 г.). «О масштабируемых и эффективных распределенных детекторах отказов» . Материалы двадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . ПОДК '01. Ньюпорт, Род-Айленд, США: Ассоциация вычислительной техники. стр. 170–179. дои : 10.1145/383962.384010 . ISBN 978-1-58113-383-7 . S2CID 216594 .
- ^ Перейти обратно: а б Дас, А.; Гупта, И.; Мотивала, А. (23 июня 2002 г.). «SWIM: Масштабируемый слабосогласованный протокол членства в группах процессов в стиле заражения» . Материалы Международной конференции по надежным системам и сетям . стр. 303–312. дои : 10.1109/DSN.2002.1028914 . ISBN 0-7695-1597-5 . S2CID 11094028 .
