Алгоритм Paxos имеет очень важное положение в распределенном поле. Тем не менее, алгоритм Paxos имеет два очевидных недостатка: 1. Трудно понять и 2. Инженерная реализация сложнее.
В Интернете есть много статей, объясняющих алгоритм Paxos, но качество неравномерное. Прочитав много информации о Paxos, я обнаружил, что лучшим материалом для изучения Paxos является статья «Paxos Made Simple», за которой следует введение Paxos в китайской и английской версиях Википедии. Эта статья пытается шаг за шагом помочь вам раскрыть тайну острова Паксос.
Что такое Паксос
Алгоритм Paxos основан наобмен сообщениямии имеетВысокая отказоустойчивостьизалгоритм консенсуса, является принятым в настоящее время решениемРаспределенная согласованностьвопросСамый эффективныйодин из алгоритмов.
Майк Берроуз, автор Google Chubby, сказал, что в этом миреединственныйАлгоритм согласованности, то есть Paxos, другие алгоритмыБракованные изделия.
Хотя Майк Берроуз немного преувеличивает, он, по крайней мере, показывает состояние алгоритма Paxos. Однако алгоритм Paxos также известен своей неясностью. Цель этой статьи - помочь вам понять алгоритм Paxos простым способом, не только понять процесс его выполнения, но также понять процесс вывода алгоритма и то, как автор пришел к окончательному решению шаг за шагом. шаг. Только поняв процесс вывода, мы можем глубоко понять суть алгоритма. Кроме того, понимание процесса вывода также очень полезно для нашего мышления и может дать нам некоторые идеи для решения проблем и вдохновить нас.
предыстория проблемы
В обычных распределенных системах такие вещи, какмашина внизилисетевая аномалия(включая задержку сообщений, потерю, дублирование, нарушение порядка и сетевые разделы). Проблема, которую должен решить алгоритм Paxos, заключается в том, как быстро и правильно реализовать алгоритм внутри кластера в распределенной системе, где могут возникать вышеперечисленные аномалии.значение данныхдостигатьпоследовательный, и убедитесь, что независимо от возникновения любого из вышеперечисленных исключений целостность всей системы не будет нарушена.
Примечание: здесьзначение данныхНе просто число в узком смысле, это может быть лог или команда. . . Согласно различным сценариям применения,значение данныхимеют разные значения.
Связанные концепции
В алгоритме Paxos есть три роли:
- Proposer
- Acceptor
- Learners
В конкретной реализации процесс можетИграйте несколько ролей одновременно. Например, процесс можетИ предлагающий, и принимающий, и обучающийся.
Существует еще одно очень важное понятие, называемоеПредложение. Окончательная стоимость, которая должна быть согласована, указана в предложении.
Примечание:
- в настоящее времядумать"предложение=значение', то есть предложение содержит только значение. В нашем следующем процессе вывода мы обнаружим, что если предложение содержит только ценность, возникнут проблемы, поэтому мы снова проанализируем предложение.Редизайн.
- в настоящее времядумать"Предлагающий может вносить предложения напрямую'. В нашем следующем процессе вывода мы обнаружим, что возникнут проблемы, если предлагающий напрямую предложит предложение, и необходимо добавить процесс изучения предложения.
Предлагающие могут предлагать предложения; Акцепторы могут принимать предложения; если предложение выбрано (выбрано), то выбирается значение в предложении.
Возвращаясь к только что сказанному «соглашению о значении определенных данных», это означает, что Предлагающий, Принимающий и Учащийся думают, что выбрано (выбрано) одно и то же значение. Итак, при каких обстоятельствах Предлагающий, Принимающий и Учащийся могут считать значение выбранным?
- Предлагающий: до тех пор, пока предложение, отправленное Предлагающим, принимается Акцептантом (в начале считается, что для его принятия требуется только один Акцептор, а в процессе вывода обнаружится, что более половины Принимающие должны согласиться), предлагающий считает, что значение в предложении выбрано.
- Принимающий: Пока Принимающий принимает предложение, Принимающий будет выбирать значение в предложении.
- Ученик: Принимающий сообщает Ученику, какое значение выбрано, и Ученик считает, что это значение выбрано.
описание проблемы
Предположим, имеется множествопредложить значение(значение указано в предложении предложения)Коллекция процессов. Алгоритм согласованности должен гарантировать так много значений,единственныйвыбрано значение. Если значение не предложено, его не следует выбирать. Если выбрано значение, то все процессы должны иметь возможностьучитьк выбранному значению. Для алгоритмов консенсусабезопасностьТребования следующие:
- Можно выбрать только предлагаемое значение.
- выбрано только одно значение и
- Если процесс считает, что значение выбрано, то это значение должно быть фактически выбранным.
Мы не определяем точно егоживостьТребовать. Наша цель - обеспечитьВ конце концов выбирается предложенное значение. Когда значение выбрано, процесс может в конечном итоге узнать это значение.
Цель Paxos: гарантировать, что значение в конечном итоге будет выбрано, и когда значение будет выбрано, процесс сможет наконец получить выбранное значение.
Предполагая, что разные роли могут общаться, отправляя сообщения, тогда:
- Каждый символ выполняется с произвольной скоростью, может быть остановлен из-за ошибки или перезапущен. После выбора значения все роли могут дать сбой и перезапуститься.Если только те роли, которые перезапускаются после сбоя, не могут зарегистрировать некоторую информацию, выбранное значение не может быть определено после их перезапуска.
- Сообщения могут быть задержаны на любое время в их доставке, могут быть продублированы или могут быть потеряны. Но сообщение не будет повреждено, то есть содержание сообщения не будет изменено (проблема византийских генералов).
Процесс получения
Самое простое решение - только один акцептор
Предполагая, что есть только один акцептор (может быть несколько предлагающих), до тех пор, пока акцептор принимает первое полученное предложение, предложение выбирается, а значение в предложении является выбранным значением. Это гарантирует, что будет выбрано только одно значение.
Однако, если единственный Акцептор выйдет из строя, то вся система выйдет из строя.не могу работать!
Следовательно, должно бытьНесколько акцепторов!
Несколько акцепторов
Ситуация с несколькими акцепторами показана на рисунке ниже. Итак, как обеспечить выбор значения в случае нескольких предлагающих и нескольких принимающих?
Начните искать решение ниже.
Если нам нужно значение, даже если предлагает только один предлагающий, это значение в конечном итоге будет выбрано.
Тогда получаются следующие ограничения:
P1: Акцептор должен принять первое полученное предложение.
Однако это приведет к другой проблеме: если каждый предлагающий предложит другое значение и отправит его другому акцептору. Согласно P1, Акцептор принимает полученное значение сам, в результате чего выбираются разные значения. Произошло несоответствие. Как показано ниже:
Только потому, что «предложение принимается одним акцептором, выбирается значение предложения», что вызвало указанную выше проблему несоответствия. Поэтому нам необходимо добавить положение:
Требование: Отобранное предложение должно бытьбольше половиныАкцептор принимает
Это правило подразумевает еще раз: «Акцептор должен иметь возможность принять более одного предложения! 』В противном случае это может привести к тому, что в конце не будет выбрано значение. Например, ситуация выше. v1, v2, v3 не выбраны, поскольку все они принимаются только одним акцептором.
С начала "предложение=значение』Он больше не может удовлетворить спрос, поэтому предложение перерабатывается, и к каждому предложению добавляется номер предложения, указывающий порядок, в котором предлагаются предложения. сделать"предложение = номер предложения + стоимость'.
Хотя допускается выбор нескольких предложений, все выбранные предложения должны иметь одинаковое значение. В противном случае снова возникнет несоответствие.
Итак, существуют следующие ограничения:
P2: Если выбрано предложение со значением v, то каждое выбранное предложение с более высоким номером также должно иметь значение v.
Предложение может быть выбрано только в том случае, если оно принято Принимающей стороной, поэтому мы можем переписать ограничение P2 как ограничение P2a для предложения, принятого Принимающей стороной.
P2a: Если выбрано предложение со значением v, то каждое предложение с более высоким номером, принятое Принимающей стороной, также должно иметь значение v.
Пока P2A, мы сможем встретиться с P2.
Однако рассмотрим следующую ситуацию: предположим, что всего имеется 5 акцепторов. Предлагающий2 предложил предложение [M1, V1], а Принимающий2~5 (более половины) принял это предложение, поэтому все Принимающие2~5 и Предложивший2 считали, что был выбран вариант V1. Акцептор1 только что восстановился после простоя (акцептор1 не получал предложений ранее), в это время Предлагающий1 отправляет предложение [M2, V2] Акцептору1 (V2≠V1 и M2>M1), для Акцептора1 это Первое предложение он получил. Согласно P1 (Акцептор должен принять первое полученное им предложение), Акцептор1 должен принять предложение! При этом Acceptor1 считает, что выбран V2. Это представляет две проблемы:
- Acceptor1 считает, что выбран вариант V2, Acceptor2~5 и Proposer2 считают, что выбран вариант V1. Произошло несоответствие.
- Выбирается V1, но предложение с более высоким номером [M2, V2], принятое Acceptor1, имеет значение V2, а V2≠V1. Это противоречит P2a (если выбрано предложение со значением v, то каждое предложение с более высоким номером, принятое Акцептором, также должно иметь значение v).
Итак, мы должны усилить ограничение P2a!
P2a — это ограничение на предложение, принятое Акцептантом, но на самом деле предложение предложено Предлагающим, поэтому мы можем ограничить предложение, предложенное Предлагающим. чтобы получить P2b:
P2b: если выбрано предложение со значением v, то все последующие предложения с более высокими номерами также должны иметь значение v.
Из P2b можно вытолкнуть P2a, а затем P2.
Итак, как гарантировать, что после выбора предложения со значением v значение предложения с более высоким номером, предложенного Предложившим, равно v?
Пока P2c удовлетворен:
P2c: Для любых N и V, если предлагается предложение [N, V], то существует множество S, состоящее более чем из половины акцепторов, которое удовлетворяет любому из следующих двух условий:
- Каждый акцептор в S не принял предложение с номером меньше N.
- Значение предложения с наибольшим номером, принятого Акцептантом в S, равно V.
Предлагающий генерирует предложения
Чтобы удовлетворить P2b, есть более важная идея: прежде чем предлагающий создаст предложение, оно должно перейти к"Учить"Значение, которое было выбрано или может быть выбрано, а затем использует это значение в качестве значения своего собственного предложения. Если значение не выбрано, предлагающий может сам определить значение значения. Вот так можно договориться. Этот этап обучения осуществляется через"Подготовить запрос"осуществленный.
Таким образом, мы получаем следующееАлгоритм генерации предложений:
- Предлагающий выбрать одинНовое предложение номер N, затем кКоллекция акцепторов(более половины) отправить запрос, прося каждого акцептора в наборе дать следующий ответ.
(а) обещание предлагающемубольше не приниматьлюбой номерПредложений меньше, чем N.
(b) Если Акцептант принял предложение, то ответить ПредлагающемуМы получиличисло меньше NПредложение с наибольшим номером.
мы называем этот запросномер NизПодготовить запрос.
- Если предлагающий получаетбольше половиныАкцепторотклик, то он может сгенерировать число N и значение VПредложение[N,V]. где V во всех ответахЗначение предложения с наибольшим номером. если все ответынет предложений, то V может использоваться Предлагающимвыбрать самостоятельно.
После создания предложения предлагающийпредложениеОтправитьбольше половинынабор акцепторов и ожидать, что эти акцепторы примут предложение. Назовем этот запросПринять запрос. (Примечание. Коллекция Acceptor, которая в настоящее время принимает запросы Accept,неуверенныйколлекция Acceptor, которая ранее ответила на запрос Prepare)
Акцептор принимает предложение
Acceptorможет игнорировать любой запрос(включая Подготовить запрос и Принять запрос), не беспокоясь о нарушении алгоритмабезопасность. Итак, мы говорим здесь о том, когда Акцептор может ответить на запрос.
Мы накладываем следующие ограничения на принятие предложений Акцептантом:
P1a: Акцептор до тех пор, покаНе ответилЛюбыечисло больше NизПодготовить запрос, то он можетприниматьэтоПредложение под номером N.
Если акцептор получает запрос на подготовку с номером N, он уже ранее отвечал на запрос на подготовку с номером больше N. Согласно P1a Акцептант не может принять предложение номер N. Следовательно, Акцептор может игнорировать запрос на подготовку с номером N. Конечно, вы также можете ответить с ошибкой, чтобы как можно скорее сообщить Предлагающему, что его предложение не будет принято.
Следовательно, акцепторпросто помни: 1. Принято предложение с наибольшим номером. 2. Наибольшее количество ответов на запросы.
Описание алгоритма Paxos
После приведенного выше вывода мы суммируем процесс алгоритма Paxos.
Алгоритм Paxos делится надва этапа. детали следующим образом:
- Первый этап:
а) Предлагающий выбирает одинПредложение номер N, затем кбольше половиныАкцептор отправляет число NПодготовить запрос.
(b) Если Акцептор получает запрос на подготовку с номером N, и Nбольше, чемАкцептор имеетОтветилвсеПодготовить запросномер, то уже его поставитПринятое предложение с наибольшим номером (если есть)Обратная связь Предлагающему как ответ, а Акцептанту обещаетбольше не приниматьЛюбыеПредложения с номерами меньше N.
- Второй этап:
(a) Если Предлагающий получаетбольше половиныЗапрос Prepare с номером N, отправленный ему Акцептантомотклик, затем отправляет[Н, В] ПредложениеизПринять запросДатьбольше половиныАкцептор. Примечание: V полученоткликсерединазначение предложения с наибольшим номером, если ответНе содержит предложений, то V определяется Предлагающимвам решать.
(b) Если Акцептант получает запрос на Акцепт для предложения номер N, при условии, что Акцептантнетномер парыбольше, чем NизПодготовить запроссделанныйотклик, Так и будетпринять предложение.
Учащийся узнает выбранное значение
Значение обучения учащимся (приобретение) выбрано следующие три варианта:
Как гарантировать активность алгоритма PaxOS
выбравГлавный предлагающий, можно гарантировать работу алгоритма Paxos. Пока что мы получаемИ безопасность, и живучесть гарантированыизАлгоритм распределенной согласованности——Алгоритм Паксос.
использованная литература
- Бумага "Paxos Made Simple"
- Текст научной работы на тему «Парламент неполный рабочий день»
- Паксос в английской Википедии
- Паксос в китайской Википедии
- Книга "От Паксоса до ZooKeeper"