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