Атомная трансляция - Atomic broadcast

В отказоустойчивой распределенных вычислений, атомная трансляция или же трансляция всего заказа это транслировать где все правильные процессы в системе из нескольких процессов получают один и тот же набор сообщений в одном и том же порядке; то есть та же последовательность сообщений.[1][2] Трансляция называется "атомный "потому что в конечном итоге он либо завершается правильно на всех участниках, либо все участники прерываются без побочных эффектов. Атомарные широковещательные рассылки являются важным примитивом распределенных вычислений.

Характеристики

От протокола атомарной широковещательной передачи обычно требуются следующие свойства:

  1. Срок действия: если правильный участник передает сообщение, то в конечном итоге его получат все правильные участники.
  2. Единое соглашение: если один правильный участник получает сообщение, то все правильные участники в конечном итоге получат это сообщение.
  3. Единая целостность: сообщение получено каждым участником не более одного раза и только в том случае, если оно ранее транслировалось.
  4. Единый общий порядок: сообщения полностью заказанный в математическом смысле; то есть, если какой-либо правильный участник сначала получает сообщение 1, а второй - сообщение 2, то каждый другой правильный участник должен получить сообщение 1 перед сообщением 2.

Родригес и Рейнал[3] и Schiper et al.[4] несколько иначе определяют свойства целостности и достоверности атомарной трансляции.

Обратите внимание, что общий заказ не эквивалентен ФИФО порядок, который требует, чтобы если процесс отправил сообщение 1 до того, как он отправил сообщение 2, то все участники должны получить сообщение 1 до получения сообщения 2. Это также не эквивалентно «причинному порядку», где сообщение 2 «зависит от» или «происходит» после "сообщения 1 все участники должны получить сообщение 2 после получения сообщения 1. Хотя это сильное и полезное условие, полный порядок требует только, чтобы все участники получали сообщения в одном и том же порядке, но не накладывает других ограничений на этот порядок.[5]

Отказоустойчивость

Разработать алгоритм атомарных широковещательных рассылок относительно легко, если предположить, что компьютеры не откажутся. Например, если нет сбоев, атомарная трансляция может быть достигнута просто за счет того, что все участники общаются с одним «лидером», который определяет порядок сообщений, а остальные участники следуют за лидером.

Однако настоящие компьютеры неисправны; они терпят неудачу и восстанавливаются после неудачи в непредсказуемые, возможно, неподходящие моменты. Например, в алгоритме следования за лидером, что, если лидер выйдет из строя в неподходящий момент? В такой среде сложно добиться атомных трансляций.[1] Был предложен ряд протоколов для выполнения атомарной трансляции при различных предположениях о сети, моделях отказов, наличии аппаратной поддержки для многоадресная передача, и так далее.[2]

Эквивалентно консенсусу

Для удовлетворения условий атомной трансляции участники должны эффективно «согласовать» порядок получения сообщений. Участники, восстанавливающиеся после сбоя, после того, как другие участники «согласовали» порядок и начали получать сообщения, должны быть в состоянии изучить и соблюдать согласованный порядок. Такие соображения указывают на то, что в системах с аварийными отказами атомная трансляция и консенсус эквивалентные проблемы.[6]

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

И наоборот, группа участников может атомарно транслировать сообщения, достигая консенсуса в отношении первого сообщения, которое должно быть получено, с последующим достижением консенсуса по следующему сообщению и так далее, пока все сообщения не будут получены. Таким образом, атомная трансляция сводится к консенсусу. Более формально и более подробно это продемонстрировали Ксавье Дефаго и др.[2]

Фундаментальный результат распределенных вычислений заключается в том, что достижение консенсуса в асинхронных системах, в которых может произойти даже один сбой, невозможно в самом общем случае. Это было показано в 1985 г. Майкл Дж. Фишер, Нэнси Линч, и Майк Патерсон, и иногда называется результатом FLP.[7] Поскольку консенсус и атомарная трансляция эквивалентны, FLP применяется также к атомарной трансляции.[5] Результат FLP не запрещает реализацию атомарной широковещательной передачи на практике, но требует принятия менее строгих допущений, чем FLP, в некоторых отношениях, например, о процессоре и таймингах связи.

Алгоритмы

В Алгоритм Чандра-Туега[6] - это основанное на консенсусе решение атомной трансляции. Другое решение было предложено Родригесом и Рейналом.[3]

Протокол Zookeeper Atomic Broadcast (ZAB) является основным строительным блоком для Apache ZooKeeper, отказоустойчивый сервис распределенной координации, который лежит в основе Hadoop и многие другие важные распределенные системы.[8][9]

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

Рекомендации

  1. ^ а б Кшемкаляни, Аджай; Сингхал, Мукеш (2008). Распределенные вычисления: принципы, алгоритмы и системы (электронная книга Google). Издательство Кембриджского университета. стр.583 –585. ISBN  9781139470315.
  2. ^ а б c Дефаго, Ксавье; Шипер, Андре; Урбан, Петер (2004). «Алгоритмы широковещательной и многоадресной рассылки общего порядка» (PDF). Опросы ACM Computing. 36 (4): 372–421. Дои:10.1145/1041680.1041682.
  3. ^ а б Родригес Л., Рейнал М.: Атомное вещание в асинхронных распределенных системах восстановления после сбоев [1], ICDCS '00: Материалы 20-й Международной конференции по распределенным вычислительным системам (ICDCS 2000)
  4. ^ Ekwall, R .; Шипер, А. (2006). «Решение атомной трансляции с косвенным консенсусом». Международная конференция по надежным системам и сетям (DSN'06) (PDF). С. 156–165. Дои:10.1109 / dsn.2006.65. ISBN  0-7695-2607-1.
  5. ^ а б Дермот Келли. «Групповое общение».
  6. ^ а б Чандра, Тушар Дипак; Туег, Сэм (1996). «Детекторы ненадежных отказов для надежных распределенных систем». Журнал ACM. 43 (2): 225–267. Дои:10.1145/226643.226647.
  7. ^ Майкл Дж. Фишер, Нэнси А. Линч и Майкл С. Патерсон (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом» (PDF). Журнал ACM. 32 (2): 374–382. Дои:10.1145/3149.214121.CS1 maint: несколько имен: список авторов (связь)
  8. ^ Флавио П. Жункейра, Бенджамин К. Рид и Марко Серафини, Yahoo! Исследование (2011). «Заб: высокопроизводительное вещание для систем первичного резервирования». 2011 IEEE / IFIP 41-я Международная конференция по надежным системам и сетям (DSN). С. 245–256. Дои:10.1109 / DSN.2011.5958223. ISBN  978-1-4244-9233-6. S2CID  206611670.CS1 maint: несколько имен: список авторов (связь)
  9. ^ Андре Медейрос (20 марта 2012 г.). "Протокол атомной трансляции ZooKeeper: теория и практика" (PDF). Хельсинкский технологический университет - Лаборатория теоретической информатики.