От теории CAP к алгоритму Paxos

Java

1. Проблемы распределенных систем

Есть классика о распределенных системахCAPтеория,

CAPОсновная идея теории заключается в том, что любая сетевая система обмена данными может удовлетворять только согласованность данных (Consistency), доступность (Availability) и допуск на сетевые разделы (Partition Tolerance) два из трех признаков.

  • Последовательность

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

  • Доступность

Доступность означает «Чтение и запись всегда выполняются успешно», то есть служба всегда доступна, а время отклика нормальное.
В доступной распределенной системе каждый исправный узел должен отвечать на каждый запрос. То есть любой алгоритм, используемый системой, должен в конечном итоге завершиться. Когда также требуется устойчивость к разделам, это строгое определение: каждый запрос должен завершаться, даже в случае серьезных сетевых ошибок.

  • Допуск на перегородку Допуск на перегородку

ToleranceЕго также можно перевести как отказоустойчивость.Под устойчивостью к разделам понимается, в частности, «система продолжает работать, несмотря на произвольную потерю сообщений или сбой части системы», то есть система допускает сетевые разделы, а сеть между разделами недоступна. толерантность и расширяемость тесно связаны,Partition ToleranceВ частности, он по-прежнему может предоставлять внешние службы, соответствующие согласованности и доступности при сбое узла или сетевого раздела.

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


Как показано на рисунке,Client Aможет отправлять команды наServerи обновление настроекXзначение ,Client 1отServerЧтение этого значения, в одноточечном случае, т.е. без сетевых разделов, или через простой механизм транзакций, гарантированоClient 1Чтение всегда является последним значением, и проблем с согласованностью нет.

Если в систему добавляется группа узлов,WriteОперация может завершиться успешно на сервере 1, вServer 1не удалось, на этот раз дляClient 1а такжеClient 2, будет прочитано несовместимое значение, и возникнет несогласованность. Если вы хотите, чтобы значения x были согласованными,WriteОперации должны завершаться одновременно, что снижает доступность системы.

Можно видеть, что в распределенной системе невозможно одновременно удовлетворить «непротиворечивость», «доступность» и «отказоустойчивость раздела» закона CAP.

В общей распределенной системе для обеспечения высокой доступности данных обычно хранится несколько копий данных (replica), сетевое разделение — это установленная реальность, поэтому единственный выбор — между доступностью и согласованностью.CAPТеория фокусируется на абсолютных условиях.В разработке доступность и согласованность не являются полностью противоположными.Мы часто сосредотачиваемся на том, как улучшить доступность системы при сохранении относительной согласованности.

2. Модель согласованности данных

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

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

Сильная консистенция:
Когда операция обновления завершена, любой доступ несколькими последующими процессами или потоками вернет последнее обновленное значение. Это самая удобная для пользователя, то есть какой пользователь писал в прошлый раз, гарантированно будет прочитать в следующий раз. согласно сCAP Теоретически эта реализация требует жертвовать удобством использования.

Слабая консистенция:
Система не гарантирует, что последующие процессы или обращения к потокам вернут последнее обновленное значение. Пользователю требуется некоторое время, чтобы прочитать обновление системных данных с помощью операции, и мы называем этот период времени «окном несогласованности». После того, как данные успешно записаны, система не обещает немедленно прочитать вновь записанное значение и не обещает прочитать последнее значение.

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

Модель конечной согласованности можно разделить на несколько моделей в соответствии с различными гарантиями, которые она предоставляет, включая причинно-следственную согласованность и согласованность чтения-записи.

Трех-, двух- и трехэтапные коммиты

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

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

Следовательно, для реализации распределенных транзакций необходимо, чтобы текущий узел знал о статусе выполнения задачи других узлов. Обычное решение состоит в том, чтобы ввести компонент «координатор» для унифицированного планирования выполнения всех распределенных узлов. Знаменитый протокол двухфазной фиксации (Two Phase Commitment Protocol) и протокол трехэтапной фиксации (Three Phase Commitment Protocol).

1. Двухэтапный протокол фиксации

Two PhaseОтноситсяCommit-requestсцена иCommitсцена.

  • этап запроса

На этапе запроса координатор уведомит участников транзакции о том, что они готовы зафиксировать или отменить транзакцию, а затем вступит в процесс голосования. В процессе голосования участники информируют координатора о своем решении: согласиться (выполнение локального задания участника транзакции прошло успешно) или отменить (неудачное выполнение локального задания).

  • Фиксация фазы

На этом этапе координатор примет решение по результатам голосования на первом этапе: зафиксировать или отменить. Координатор уведомляет всех участников о совершении транзакции тогда и только тогда, когда все участники соглашаются на совершение транзакции, в противном случае координатор уведомляет всех участников об отмене транзакции. Участник выполнит соответствующее действие после получения сообщения от координатора.

Видно, что есть явные проблемы с протоколом двухфазной фиксации:

  • синхронная блокировка

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

  • проблема с одной точкой

Как только координатор выходит из строя, участники блокируются навсегда.

  • несогласованность данных

На втором этапе предполагается, что координатор выдает транзакциюcommit, но из-за проблем с сетью уведомление было получено и выполнено только частью участниковcommit, остальные участники находились в состоянии блокировки, не получив уведомление, и в это время произошло несоответствие данных.

2. Трехэтапный протокол фиксации

Three PhaseсоответственноCanCommit,PreCommit,DoCommit.

Трехфазная фиксация улучшает двухэтапную фиксацию:

  • Внедрить механизм тайм-аута. существует2PC, только координатор имеет механизм тайм-аута,3PCВ то же время механизм тайм-аута вводится как в координаторе, так и в участниках.
  • Вставьте этап подготовки между первым и вторым этапом. Гарантируется, что состояние каждого участвующего узла непротиворечиво перед финальной фазой фиксации.

В-четвертых, предложение алгоритма Paxos

Ни двухэтапная фиксация, ни трехфазная фиксация не могут хорошо решить проблему распределенной непротиворечивости, покаPaxosПредлагаемый алгоритм,PaxosСоглашениеLeslie LamportВпервые он был предложен в 1990 году и стал наиболее широко используемым алгоритмом распределенного консенсуса.Google ChubbyавторMike BurrowsОн сказал, что в этом мире есть только один алгоритм консенсуса, то естьPaxos, остальные алгоритмы неисправны.

1. Роль узла

Paxos В протоколе есть три типа узлов:

  • Предлагающий: предлагающий

Proposerможет иметь более одного,Proposer предложить предложение (value). так называемыйvalue, может быть любой операцией в проекте, например, "изменить значение переменной на значение", "установить текущуюprimary для узла" и так далее.Paxos Эти операции единообразно абстрагируются в протоколе какvalue. разныеProposer Разные и даже противоречивыеvalue, напримерProposer Предлагает «установить переменную X в1",еще одинProposer Предлагает «изменить переменнуюXУстановить как2”, но для того же раундаPaxos процесс, максимум одинvalue Это было одобрено.

  • Акцептор: утверждающий

AcceptorимеютNиндивидуальный,ProposerПредложенныйvalueдолжно получиться больше половины(N/2+1)изAcceptorУтверждено пройти.Acceptorполностью равны и независимо.

  • Ученик: Ученик

Learnerисследование одобреноvalue. Учиться, читаяProposer правильноvalue результат выбора, еслиvalue больше половиныProposerпройти, тоLearner узнал этоvalue. вот похожеQuorum парламентский механизм,value нужно получитьW=N/2 + 1изAcceptor утвердить,Learner нужно хотя бы прочитатьN/2+1 индивидуальныйAccpetor, максимум читатьN индивидуальныйAcceptorПосле результата можно узнать прохождениеvalue.

2. Ограничения

Вышеупомянутые три типа ролей являются лишь логическими подразделениями.На практике узел может действовать как эти три типа ролей одновременно. В некоторых статьях будет добавлена ​​роль клиента в качестве эмитента, который фактически не участвует в процессе выборов.Paxosсерединаproposer а такжеacceptorосновная роль алгоритма,paxosописано вproposer и несколькоacceptor В созданной системе, как сделать несколькоacceptor противproposer процесс достижения согласия по различным представленным предложениям, в то время какlearner Просто "изучение" предложения, которое в итоге было одобрено.

Протокольный процесс Paxos также должен соответствовать нескольким ограничениям:

  • Acceptorдолжен принять первое полученное предложение;
  • Если значение v для предложения выбрано большинствомAcceptorПринято, то все последующие принятые предложения также должны содержатьvстоимость(vПод значением можно понимать содержание предложения, которое состоит из одного или несколькихvНомер предложения и состав);
  • Если раундPaxos соглашение утверждаетvalue, то последующие раундыPaxos только одобрить этоvalue;

каждый раундPaxos Соглашение разделено на этап подготовки и этап утверждения, на которыхProposer а такжеAcceptor имеют собственный поток обработки.

Proposerа такжеAcceptorВзаимодействие между основными4Обмен сообщениями класса, как показано ниже:

Этот4сообщение класса соответствуетpaxosДве фазы алгоритма4обработать:

  • Phase 1
    a) proposerболее половины сетиacceptorОтправитьprepareИнформация
    b) acceptorотвечай нормальноpromiseИнформация
  • Phase 2
    а) когда достаточноacceptorОтвечая на сообщение-обещание,proposerОтправитьacceptИнформация
    б) в обычных условияхacceptorОтвечатьacceptedИнформация

3, избирательный процесс

  • Фаза 1 подготовительная фаза

Proposer Создавайте глобально уникальные и инкрементныеProposalID,КPaxos Все машины в кластере отправляютPrepareзапрос, здесь нетvalue, только носитьNкоторыйProposalID .Acceptor получатьPrepareПосле запроса, судья: ПолученоProposalID Больше, чем N всех ранее отвеченных предложений:
Если да, то:
(1) Сохранение локальноN, можно записать какMax_N.
(2) Ответить на запрос и принестиAcceptсреди предложений с наибольшим Nvalue(Если уже неAcceptпредложение, возвратvalueПусто).
(3) Дать обещание: нетAcceptменьше, чемMax_Nпредложение.

Если нет: не отвечайте или отвечайтеError.

  • Этап 2, этап выборов

P2a：ProposerОтправитьAccept
Через некоторое время,Proposer собрать немногоPrepare Ответ, бывают следующие ситуации:
(1) Количество ответов > половиныAcceptorчисло, а значение всех ответов пусто, тоPorposerпроблемаacceptзапрос, и принести свой собственный назначенныйvalue.
(2) количество ответов> половинаAcceptorномер, а часть значений ответа не пуста, тоPorposerпроблемаacceptзапросить и принести ответProposalIDсамый большойvalue(как содержание собственного предложения).
(3) Количество ответов Acceptorчисло, попробуйте обновить, чтобы создать большееProposalID, затем повернитеP1aвоплощать в жизнь.

P2b：AcceptorотвечатьAccept
Accpetor получатьAccpetПосле запроса определите:
(1) получилN >= Max_N(как правило, равно), то ответ отправляется успешно и сохраняетсяNа такжеvalue.
(2) получилN < Max_N, нет ответа или отправка ответа не удалась.

P2c: Proposerподсчет голосов
Через некоторое время,Proposerсобрать немногоAccept Ответ успешно отправлен, есть несколько ситуаций:
(1) Количество ответов > половиныAcceptorколичество, это означает, что подачаvalueуспех. В этот момент трансляция может быть отправлена ​​всемProposer,Learner, сообщите им, что ониcommitизvalue.
(2) Количество ответов Acceptorномер, попробуйте обновить, чтобы создать большийProposalID, затем повернитеP1aвоплощать в жизнь.
(3) Получив ответ о том, что отправка не удалась, попробуйте обновить, чтобы создать более крупныйProposalID, затем повернитеP1aвоплощать в жизнь.

4. Связанные обсуждения

PaxosОсновная идея алгоритма:
(1) Введен рядAcceptor,ОдинAcceptorподобно2PCЕдиная точка проблемы в координаторе, избегающая сбоев
(2)Proposerиспользовать большеProposalIDДля вытеснения временных прав доступа можно сравнить2PCпротокол, предотвращающий одно изProposerСбои и простои вызывают проблемы с блокировкой
(3) Чтобы гарантировать значение N, существует только одинProposerможно переходить ко второму этапу операции,Proposerсогласно сProposalIDзапустить в порядке возрастания (3) новыйProposalIDНапример, предлагающий соглашается с ранее отправленным значением Value и увеличиваетProposalIDизValueэто наследственные отношения

почему вPaxosВ процессе эксплуатации менее половиныAcceptorРаботает ли он, даже если он терпит неудачу?
(1) Если менее половиныAcceptorКогда он истечет, окончательныйvalue, в это время всеProposerБудет соревнование за разрешения предложений, и в конечном итоге одно предложение будет успешно представлено. После этого будут полуоверыAcceptorвозьми этоvalueОтправлено успешно.
(2) Если меньше половиныAcceptorНа момент отказа был определен окончательныйvalue, в это время всеProposerДолжен быть окончательным перед отправкойvalue Отправить, это значение также может быть получено и не будет изменено.

Как сгенерировать уникальный номер?
существует《Paxos made simple》упоминается, чтобы всеProposerоба выбирают из непересекающихся наборов данных, например, система имеет5индивидуальныйProposer, то для каждогоProposerназначить личностьj(0~4), то каждыйproposerНомер каждой предлагаемой резолюции может быть5*i + j(i может использоваться для обозначения того, сколько раз было предложено предложение).

рекомендоватьlarmportа такжеpaxosТри связанных документа:
The Part-Time Parliament
Paxos made simple
Fast Paxos

Ссылаться на:

CAP theorem
Говоря об основных проблемах распределенных систем: доступности и непротиворечивости
Введение в распределенные системы для реального боя
Иллюстрация протокола распределенного консенсуса Paxos
Сводка обучения протоколу Paxos

награда Добро пожаловать в публичный аккаунт Life Designer в WeChat.
Публичный идентификатор: longjiazuoA
Категории