Эта статья переведена сОтвет на Quora
Я думаю, что прежде чем разбираться в Paxos, можно поговорить о других способах решения проблемы консенсуса, и на этой основе понять Paxos будет проще.
Брачные клятвы — это интуитивный способ достижения консенсуса.
- «Вы готовы (некоторые умолчания)?» «Да!» «Да!»
- «Теперь я заявляю вам (некоторые пропуски)»
двухэтапная фиксация
Теперь предположим, что этот брак заключен не между двумя людьми, а между мужчиной и несколькими женщинами. Мужчина может либо жениться на всех, либо вообще ни на ком. Затем свадебные клятвы должны быть соответственно изменены следующим образом:
- «Готовы ли (некоторые пропуски)?» «Готовы!» «Готовы!» «Готовы!»…
- «Теперь я заявляю вам (некоторые пропуски)»
Если одна из женщин не ответит «Да!», свадьба не состоится.
Компьютерщики называют это двухфазной фиксацией.
Процесс двухфазной фиксации (2PC) выглядит следующим образом:
- этап голосования. Координатор публикует значение для всех узлов и собирает их ответы (принятые или нет). В нашем сценарии координатор транзакций спрашивает всех RM менеджеров ресурсов (экземпляров сервера базы данных), могут ли они зафиксировать транзакцию, и RM отвечают да или нет.
- фаза фиксации. Если все согласны, координатор сообщит всем узлам, что значение определено; если хотя бы один узел не согласен, координатор сообщит всем узлам, что значение не определено. В нашем сценарии координатор просит RM зафиксировать транзакцию или завершить транзакцию.
Обратите внимание, что на этот раз голосование проводится только за предложенное значение, и узлы могут отвечать «да» или «нет», но не могут предлагать альтернативное значение. Если узел хочет предложить значение, он должен запустить свой собственный 2PC. Очевидно, что этот алгоритм работает, и предлагаемое узлом значение должно быть согласовано всеми узлами, в то же время этот алгоритм неэффективен: для кластера с N узлами необходимо передать 3N фрагментов информации для завершения консенсуса.
Что делать, если узел умирает? Например, на этапе 1 координатор умирает после отправки предложений некоторым (но не всем) узлам.
- Сейчас некоторые узлы начинают вторую фазу, а другие еще не знают. Те узлы, которые начинают вторую фазу, будут заблокированы.
- В нашем сценарии RM с правом голоса может заблокировать некоторые ресурсы и не может включить механизм тайм-аута, потому что координатор может восстановиться и продолжить вторую фазу.
На втором этапе, если координатор зависнет после отправки сообщения о коммите некоторым узлам, будет существовать аналогичная проблема. Частично проблема может быть решена за счет того, что другой координатор вступает во владение при обнаружении тайм-аута; узел поддерживает связь с другими узлами, чтобы узнать голоса других узлов (узлы должны сохранять результаты голосования) и завершить транзакцию. Но этот процесс также может завершиться ошибкой, и транзакцию нельзя будет восстановить. Эпилог: В случае сбоя узла2PCНенадежный.
трехэтапная фиксация
Основная проблема с 2PC заключается в том, что когда координатор умирает, никакая другая роль не может завершить соглашение. Это можно сделать, добавив дополнительный шаг:
- Первый этап. Как и 2PC, координатор предлагает значение всем узлам.
- вторая стадия. Если все узлы возвращают «да» на первом этапе, координатор отправляет сообщение «готов к фиксации», позволяя узлам выполнять действия, которые можно отменить, но на которые нельзя ответить. Каждый узел подтверждает координатору, что он получил сообщение «готов к фиксации».
- Третья фаза. Как и в фазе 2PC, если координатор получает подтверждения от всех узлов, он отправляет значение координации первого шага всем узлам для отправки узлами. Если координатор не получает подтверждения от всех узлов, то координатор отменяет транзакцию.
Если координатор не выполняет какой-либо из вышеперечисленных шагов, любой другой участник может взять на себя эту роль и запросить состояние других узлов.
- Если какой-либо RM сообщает новому координатору, что он не получил сообщения «готов к фиксации», новый координатор будет знать, что ни один узел не зафиксировал транзакцию. Новый координатор может отменить транзакцию или повторно выполнить процесс.
- Если RM, зафиксировавший транзакцию, умирает, мы будем знать, что другие RM получили и подтвердили сообщение «готов к фиксации», иначе координатор не перейдет к фазе фиксации. Таким образом, координатор может начать с последней фазы получения.
Как видно из вышеизложенного, 3PC хорошо справляется с отказом узла. Цена — еще один шаг, который приводит к увеличению задержки в системе.
В случае с сетевыми разделами 3PC также справляется недостаточно хорошо. Предположим, что все RM, получившие статус «готов к фиксации», находятся в разделе 1, а остальные RM — в разделе 2. Это приводит к тому, что каждый раздел выбирает свой собственный узел восстановления, который либо фиксирует транзакцию, либо отменяет транзакцию. В случае исчезновения сетевого раздела система остается в несогласованном состоянии.
Paxos
Сначала вопрос, есть ли алгоритм лучше, чем 3PC? Единственная проблема, с которой сталкивается 3PC, — это разделение сети, верно? Чтобы ответить на этот вопрос, давайте предположим, что разбиение сети является единственной проблемой (это не так, как мы увидим позже). Стоит ли решать проблемы согласованности, вызванные сетевыми разделами?
Во-первых, с появлением облачных вычислений службы могут быть развернуты на разных континентах для обеспечения масштабируемости; в этом случае действительно необходим алгоритм, допускающий разделение сети.
Во-вторых, разделение сети — не единственная проблема, с которой сталкивается 3PC. Обрабатывает временные сбои узлов, наиболее частым случаем является отказ-восстановление-продолжение последнего выполнения. Этот шаблон восстановления после сбоя также можно использовать для описания асинхронной сетевой модели, в которой нет верхней границы времени, которое может потребоваться узлу для ответа на сообщение, потому что узел никогда не может считаться неработоспособным — его можно медленно, Или сеть может быть медленной. Для этой модели нельзя использовать механизм тайм-аута.
3PC может работать с аварийным остановом, но не с аварийным восстановлением. К сожалению, в реальном мире необходимо обрабатывать восстановление после сбоя, поэтому нам нужно более общее решение. Paxos — одно из таких решений.
процесс работы
Рабочий процесс Paxos очень похож на 2PC:
- Выберите узел, который будет лидером/предлагающим.
- Лидер выбирает значение и отправляет его всем узлам (называемым акцепторами в Paxos), и это сообщение называется сообщением «принять запрос». Акцептор может ответить принять или отклонить.
- Как только большинство узлов ответили, достигается консенсус, и координатор отправляет сообщение «фиксация» всем узлам.
Ключевое отличие от 2PC заключается в том, что 2PC требует согласия всех узлов, а Paxos требует согласия только большинства узлов. Эта идея интересна тем, что в двух разных наборах большинства узлов хотя бы один узел будет в обоих наборах. Это гарантирует, что если большинство узлов согласны со значением, то любой узел, который хочет сделать предложение, может узнать это значение от других узлов и согласиться. Это означает, что даже если на половину срочных заказов невозможно ответить, алгоритм Paxos может продолжать работу.
Конечно, сам лидер тоже может потерпеть неудачу. По этой причине Paxos не возлагает ответственность на лидера узла в данный момент времени. Алгоритм позволяет любому узлу стать лидером и координировать транзакции. Это, естественно, означает, что в данный момент времени может быть несколько узлов, считающих себя лидером. В этом случае два лидера могут предложить разные значения. Итак, как достичь консенсуса в этой ситуации? Paxos разработал для этого два механизма:
- Отдайте приказ лидерам. Таким образом, каждый узел может различать существующего лидера и лидера, восстановившегося после сбоя, тем самым предотвращая блокирование консенсуса старым лидером.
- Ограничьте значение, предложенное лидером. Как только достигается консенсус по определенному значению, Paxos заставляет последующих лидеров также выбирать это значение, чтобы обеспечить сохранение консенсуса. Это достигается за счет того, что акцептор отправляет свое последнее подтвержденное значение и порядковый номер ведущего, отправившего это значение. Новый лидер может выбрать значение, полученное от акцептора; если значение не отправлено, лидер может выбрать свое собственное предложенное значение.
Процесс протокола
этап подготовки
- Узел выбирает быть лидером, выбирая порядковый номер x и значение v для создания предложения P1(x, v). Лидер отправляет это предложение акцептору и ждет возврата большинства узлов.
- Получив предложение P1(x, v), акцептор оценивает:
- Если предложение является первым предложением, которое будет принято акцептантом, ответьте «согласен», обещая, что акцептант не будет принимать запросы меньше x в будущем.
- Если акцептант ранее принял предложение:
- Сравните между x и ранее принятым предложением с наибольшим порядковым номером, скажем, P2(y,v2)
- Если x
- Если x>y, ответьте yes и P2(y, v2)
этап приемки
- Если большинство принимающих ответят «отклонить» или не ответят, лидер отменяет предложение.
- Если большинство принимающих ответит «да», лидер также может знать, что принимающая сторона приняла предложение. Лидер выбирает одно из этих значений (если никакое значение не принимается, выбирает свое) и отправляет сообщение «accept request» с предложенным порядковым номером и значением (x, v).
- Когда акцептор получает сообщение «принять запрос», если выполняются следующие два условия, он отправляет «принять», в противном случае возвращает «отклонить».
- v совпадает с некоторым ранее принятым значением
- x - максимальный порядковый номер в предложении, принятом акцептантом
- Если лидер не получает сообщения «принять» от большинства узлов, он отменяет предложение и начинает все сначала; если лидер получает сообщение «принять» от большинства узлов, переговоры заканчиваются. В качестве оптимизации лидер может отправлять сообщения «фиксация» другим узлам.
Обработка сбоев Paxos
Что, если в алгоритме Paxos мы укажем, что в кластере может быть только один лидер одновременно, и потребуем, чтобы все узлы голосовали? Да, у нас есть 2 шт.2PC — это частный случай Paxos.
Как упоминалось выше, Paxos более устойчив к сбоям, чем 2PC:
- Лидер вешает трубку. Другие лидеры могут внести свои предложения по продолжению протокола.
- Неудавшийся лидер возобновляет. Поскольку узлы соглашаются только с предложениями с наибольшим значением последовательности и отправляют только ранее принятые значения, два узла могут сосуществовать одновременно.
Paxos также более устойчив к сбоям, чем 3PC, особенно с сетевыми разделами. В 3PC, если каждый из двух разделов согласуется со значением, то когда раздел исчезает, система остается в несогласованном состоянии. В Paxos этой проблемы не существует, потому что для согласования значения требуется участие большинства узлов. Консенсус не может быть достигнут, если в разделе нет большинства узлов. Если раздел с большинством узлов достигает консенсуса, консенсус должен быть принят узлами другого раздела.
Возможная проблема Paxos заключается в том, что, когда два лидера не могут знать о существовании друг друга, они продолжают вносить предложения с более высоким порядковым номером, чем исходное предложение, что заставит Paxos остановиться. В конце концов два лидера узнали о существовании друг друга, и один из них сдался.
Это компромисс между согласованностью и режимом реального времени. Paxos гарантирует согласованность, и после достижения консенсуса значения не могут быть изменены. Однако доступность Paxos не гарантируется, и в некоторых крайних случаях консенсус может быть не достигнут. На самом деле нельзя гарантировать безопасность асинхронного алгоритма и его работу в режиме реального времени. это называетсяНевозможные результаты ФЛП.
дальнейшее чтение
- [Принципы обработки транзакций] (Принципы обработки транзакций), глава 8 содержит подробное описание 2PC.
- Non-blocking Commit Protocols, статья Дейла Скина, описывающая 3PC.
- The Part-time Parliament.
- Paxos Made Simple.
- Paxos Made Live.
Приглашаю всех обратить внимание на мой публичный аккаунт WeChat "Person Park"