Paxos и Raft

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

Definition

Paxos и Raft — это протоколы, основанные на кворумах, которые позволяют набору реплик согласовывать упорядоченную последовательность команд (реплицированный журнал), несмотря на сбои, обеспечивая, что зафиксированные записи никогда не будут потеряны или переупорядочены, пока большинство реплик остаются доступными.

Scope

Эта тема охватывает семейство Paxos — Paxos с одним решением, Multi-Paxos и его инженерные усовершенствования — а также протокол Raft, который реорганизует те же гарантии вокруг явного лидера, репликации журнала и изменения членства для лучшего понимания. Она охватывает роли инициаторов/акцепторов и лидеров/последователей, пересечение кворумов, выборы лидера и сроки полномочий, сопоставление журналов и практические аспекты снимков и реконфигурации.

Core questions

• Как пересечение кворумов и нумерация предложений обеспечивают безопасность Paxos в разных раундах и при смене лидера?
• Как Raft декомпозирует консенсус на выборы лидера, репликацию журнала и безопасность?
• Какие инженерные проблемы возникают при превращении этих протоколов в производственные системы?

Key theories

Paxos с одним решением и Multi-Paxos

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

Декомпозиция Raft

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

От спецификации к работающей системе

Развертывание Paxos на практике требует обработки сбоев дисков, аренды лидера, компактирования журнала и реконфигурации — деталей, часто упускаемых в исходном алгоритме, но необходимых для корректности и производительности.

Clinical relevance

Paxos и Raft используются в широко применяемых службах координации, распределенных базах данных и хранилищах конфигураций; их понимание необходимо для создания или эксплуатации любой системы, которая должна поддерживать строгую согласованность реплик при сбоях.

History

Лампорт описал Paxos в своей статье 1998 года «парламент неполного рабочего дня» и уточнил его в «Paxos made simple» (2001); Чандра и коллеги сообщили о реалиях его реализации в масштабе в 2007 году; а Онгаро и Аустерхаут представили Raft в 2014 году, чтобы сделать эквивалентные гарантии намного проще для обучения и реализации.

Debates

Понятность против минимальности в протоколах консенсуса

Raft был явно разработан, чтобы быть более понятным, чем Paxos, что вызвало дебаты о том, жертвует ли его дополнительная структура (сильный лидер) гибкостью; сторонники утверждают, что понятность уменьшает количество ошибок реализации, в то время как другие отмечают, что варианты Paxos могут быть более общими.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Являются ли Paxos и Raft принципиально разными алгоритмами?

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