предисловие

В мире существует только один алгоритм консенсуса, которыйPaxos. от одногоGoogleУста Бога.Paxosтакже известныйЗатемнять, процесс рассуждения чрезвычайно сложен.

PaxosВроде того, что я сказал раньше2PC,3PC, но решает различные недостатки этих двух алгоритмов. Этот алгоритм был инженерной практикой на многих крупных фабриках, таких как Али.OceanBaseизРаспределенная база данных, используется нижний слойPaxosалгоритм. Другой примерGoogleизchubby Распределенная блокировкаЭтот алгоритм также используется. Видно, что состояние алгоритма в распределенной системе даже,PaxosэтоРаспределенная согласованностьместоимение.

текст

1. Что такое алгоритм Paxos?

PaxosАлгоритмна основе передачи сообщенийи имеетЭффективная отказоустойчивостьАлгоритм консенсуса признанного в настоящее время решенияПроблема распределенной согласованностиОдин из самых эффективных алгоритмов.

2. Алгоритм Paxos генерирует фон

2.1 Проблема византийских полководцев

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

2.2. Происхождение алгоритма Paxos

Предыстория истории — Древняя Греция.PaxosНесколько судей на острове голосуют по ходатайству в одном зале, как достичь единого результата. Записки между ними передаются обслуживающим персоналом, но судья может уйти или войти в зал, а обслуживающему персоналу может быть лень лечь спать.

2.3 Создать фон

в общемРаспределенные системы, всегда бываетУзел внизилисетевая аномалия(включая новостиповторение,потерял,Задерживать,вышел из строя,сетевой раздел) и т.д.

PaxosАлгоритм в основном заключается в том, чтобы решить, какВышеуказанная неисправность возникаетраспределенная система, быстрая и правильная внутри кластерадоговориться о стоимости, и гарантияСогласованность в системе.

3. Подробный алгоритм

3.1 Роли и предложения

Предложение

Примечание: объем предложения>значение. Как будет упомянуто позже, [предложение=число+значение].Это также может быть выражено как [M,V]. Следующие описания являются предварительными: Proposal=P, Value=V.

Роль

Proposer : ProposerМожетсделать предложение (Proposal).
Accecptor : AcceptorМожетпринять предложение. Как только предложение будет принято,предложениевнутриvalueвыбрано значение.
Learner : AcceptorРассказыватьLearnerкакое предложение было выбрано, тоLearnerузнать выбранныйvalue.

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

3.2 Описание проблемы

PaxosЯдром алгоритма являетсяпоследовательность. Поэтому мы объясним, как алгоритм решает практические задачи, исходя из описания проблемы непротиворечивости.

3.2.1 Предварительные условия алгоритмов консенсуса

в предлагаемомP, только одинVВыбрано.
если нетPбыл поднят, не было быVВыбрано.
существуетPПосле выбора процессы могут изучить выбранныеP.

3.2.2 Различные роли общаются, отправляя сообщения

Каждый символ выполняется с произвольной скоростью, может быть остановлен из-за ошибки или перезапущен. ОдинvalueПосле выбора все роли могут дать сбой и перезапуститься, и если те роли, которые сбой и перезапуск, не могут зарегистрировать некоторую информацию, выбранное значение не может быть определено после их перезапуска.
Сообщения могут появляться во время доставкизадержка любой длины,может бытьповторение, также возможнопотерял, но сообщения не будетповреждать.

3.3 Процесс получения

3.3.1. Есть только один акцептор

ОдинAcceptorпринять одинP, то есть только одинVвыбран.

Проблема: если этот Acceptor выходит из строя, вся системная служба становится недоступной.

3.3.2 Несколько акцепторов

Вопрос: Как выбрать значение в случае нескольких предлагающих и нескольких принимающих?

Шаги объяснения делятся на два этапа:соглашение P1исоглашение P2.

3.3.2.1. Конвенция P1

P1: Acceptor должен принять первый полученный P.

Если каждый предлагающий создает разные P, то несколько предлагающих должны сгенерировать несколько P и отправить их нескольким акцепторам. в соответствии ссоглашение P1,Acceptorполучен отдельноP, что приводит к разнымVвыбирается, как показано на следующем рисунке:

Как показано на фиг.P1Проблемы, которые возникнут:v1,v2,v3не были выбраны, потому что они были выбраны только однимAcceptorпринимать.

Для вышеуказанной проблемы нам нужно дополнительное соглашение:

P1a: Предложение P выбрано и должно быть принято более чем половиной Принимающих.

заP1a, что на самом деле означаетАкцептор должен принять более одного предложения.

Очевидно, это то же самое, что иP1Противоречиво, поэтому предложение необходимо переформулировать. Первоначальный дизайн был:[提案P = value], теперь переработан[提案P = 提案编号 + value]Это может быть выражено как[M，V].

Новый вопрос: выбрано несколько предложений, как убедиться, что выбранные предложения P имеют одинаковое значение?

3.3.2.2. Конвенция P2

P2: Если выбрано предложение P[M0,V0], то все выбранные P с большим номером, чем M0, также имеют значение V0.

заP2середина "выбран": Чтобы предложение было выбрано, оно должно быть сначала выбрано хотя бы однимAcceptorодобрить. Поэтому понятноP2за:

P2a: Если выбрано предложение P[M0,V0], то все P с более высоким номером, чем M0 и [одобренные Акцептантом], имеют значение также V0.

пока это устраиваетP2a, удовлетворитP2.Выбрано несколько предложенийПроблема решена, но из-занестабильность сетииливремя простояПричина (неизбежная) создаст новые проблемы:

Предположим, есть5КусокAcceptor.Proposer2предложить[M1,V1]предложение,Acceptor2~5(больше половины) принял предложение, поэтому дляAcceptor2~5иProposer2говоря, они все думаютV1выбран.Acceptor1только что изнерабочее состояниевыздоровел (доAcceptor1предложений не поступало), в настоящее времяProposer1В направленииAcceptor1послал[M2,V2]предложение(V2≠V1 и M2>M1). заAcceptor1говоря, это то, что он получаетпервое предложение. в соответствии сP1(ОдинAcceptorдолжен принять то, что он получаетпервое предложение),Acceptor1Предложение должно быть принято. в то же времяAcceptor1считатьV2выбран.

Это представляет две проблемы:

Acceptor1считатьV2был выбран,Acceptor2~5иProposer2считатьV1выбран. Появившийсянепоследовательный.
V1был выбран, нобольшее числоодеялоAcceptor1принятое предложение[M2,V2]изvalueзаV2,иV2≠V1. Это то же самое, чтоP2a(еслиvalueзаvпредложение выбрано, то каждоебольшее числоодеялоAcceptorпринятое предложениеvalueтакже должно бытьv)противоречие.

Судя по приведенным выше вопросам, у всехP2b:

P2b: Если выбран P[M0,V0], значение P, сгенерированное любым Предлагающим, также равно V0.

заP2bописано в , как обеспечитьP генерируется любым Proposer, его значение также равно V0? пока это устраиваетP2cПросто:

P2c: Для любых M, V, если предлагается [M, V], то существует комбинация S, состоящая более чем из половины Акцепторов, удовлетворяющая любому из следующих двух условий: ① Ни один из S не принял предложение с номером меньше M. ② Стоимость предложения с наибольшим номером, принятого Акцептантом в S, равна V.

Вывод завершен. . .

3.4 Поток алгоритма

3.4.1 Предлагающий вносит предложение

Общая идея такова:

(1).Этап обучения: Подготовить запрос

ProposerВыбрать новое предложениеP[MN,?]В направленииAcceptorсобиратьS(число вбольше половины) отправить запрос на запросSкаждый изAcceptorОтветьте следующим образом:

еслиAcceptorне принял предложение,ProposerгарантироватьПредложения с номерами меньше N больше не принимаются.
еслиAcceptorпринял заявку,ProposerвозвращениеПредложение с наивысшим номером с номером меньше N, которое было принято.

(2) Стадия принятия: запрос акцептора

еслиProposerПолучатьбольше половиныизAcceptorответ, тоНомер поколения N,valueзаVпредложение[MN,V],Vдля всех ответовмаксимальное количествопредложенияvalue.
еслиProposerполучил в ответнет предложения,ТакvalueЗависит отProposer самогенерируемый, и отправьте это предложение наSи ожидатьAcceptorМогу принять это предложение.

3.4.2 Акцептант принимает предложение

Acceptorможет игнорировать любой запрос (включаяPrepareзапрос иAcceptзапрос), не беспокоясь о нарушенииАлгоритм безопасности. Поэтому мы здесь, чтобы обсудить, когдаAcceptorможет ответить на запрос.

правильноAcceptorПринятие предложения дает следующие ограничения:

P1b: Акцептор может принять предложение с номером N, если он не ответил ни на один запрос на подготовку с номером больше N.

еслиAcceptorполучил рядNизPrepareпросьба, былоОтветилчисло больше, чемNизPrepareпросить. в соответствии сP1b,ДолженAcceptorНевозможно принять числа какNпредложение. СледовательноAcceptorМожетпренебрегатьНетNизPrepareпросить. Конечно, вы также можете ответитьerror,позволятьProposerЗнать свое предложение как можно скореене будет принято.

Следовательно,AcceptorПросто помни:

Предложение с наибольшим номером принято;
Максимальное количество запросов, на которые был получен ответ.

4. Описание алгоритма Paxos

5. Предложение по обучению учащихся

LearnerОбучение (приобретение) выбраноvalueЕсть три следующих варианта:

6. Как обеспечить жизнеспособность алгоритма Paxos

резюме

PaxosсуществуетВосстановление после простоя узла,Сообщения не по порядку или потеряны,Дифференциация сетигарантировано в сложившихся обстоятельствахсогласованность данных. иPaxosОписание сосредоточено натеория, в фактическом проекте приложений, имел дело сNПосле более практических деталей он мог стать другим алгоритмом, и в настоящее время его правильность больше не может быть гарантирована теорией.

Доказать правильность алгоритма распределенного консенсуса часто сложнее, чем реализовать алгоритм. Поэтому многие системы фактически используютPaxos теорияВ качестве основыпроизводнаяВыходят варианты и упрощенные версии. НапримерGoogleизChubby,MegaStore,Spannerсистема и т. д.,ZooKeeperизZABСоглашение, более понятноеRaftпротокол.

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

Ссылки по теме

Распределенная теория (1) - теорема CAP
Распределенная теория (2) - BASE Theory
Распределенная теория (3) - протокол 2PC
Распределенная теория (4) — протокол 3PC
Распределенная теория (5) - Алгоритм согласованности Paxos
Распределенная теория (6) - плот протокола согласованности

Добро пожаловать в номер общественного интереса: Zero One Technology Stack

Эта учетная запись будет продолжать делиться сухими товарами серверных технологий, включая основы виртуальных машин, многопоточное программирование, высокопроизводительные фреймворки, асинхронное ПО, промежуточное ПО для кэширования и обмена сообщениями, распределенные и микросервисы, материалы для обучения архитектуре и расширенные учебные материалы и статьи.