PaxosとRaft

PaxosとRaftは、最も影響力のある実用的な合意プロトコルであり、現実世界の協調システムを支える複製されたログに対するクラッシュ耐性のある合意を提供します。

Definition

PaxosとRaftは、クォーラムベースのプロトコルであり、クラッシュ障害にもかかわらず、一連のレプリカがコマンドの順序付けられたシーケンス（複製されたログ）について合意することを可能にし、レプリカの過半数が利用可能である限り、コミットされたエントリが失われたり順序が変更されたりしないことを保証します。

Scope

このトピックでは、Paxosファミリー（単一決定Paxos、Multi-Paxos、およびその工学的改良）とRaftプロトコルについて扱います。Raftは、理解しやすさのために、明示的なリーダー、ログ複製、およびメンバーシップ変更を中心に同じ保証を再編成しています。提案者/承認者とリーダー/フォロワーの役割、クォーラムの交差、リーダー選出と任期、ログの一致、スナップショットと再構成の実用的な懸念事項について説明します。

Core questions

• クォーラムの交差と提案番号付けは、どのようにしてラウンドとリーダーの変更を通じてPaxosの安全性を維持するのでしょうか？
• Raftはどのようにして合意をリーダー選出、ログ複製、安全性に分解するのでしょうか？
• これらのプロトコルを本番システムに変換する際に、どのような工学的課題が生じるのでしょうか？

Key theories

単一決定PaxosとMulti-Paxos

Paxosは、単調な提案番号と過半数のクォーラムによって管理される準備フェーズと承認フェーズを通じて1つの値について合意に達します。Multi-Paxosは、安定したリーダーによって導かれる一連の決定にわたって準備フェーズを償却し、複製されたログを構築します。

Raftの分解

Raftは、任期ごとに単一のリーダーを選出し、リーダーがフォロワーが複製するエントリを追加し、ログ一致プロパティを強制することにより、Paxosと同じ安全性を達成します。これは、最小限の構造を理解しやすさと実装の容易さのために意図的に交換したものです。

仕様から稼働システムへ

Paxosを実際に展開するには、ディスク障害、リーダーリース、ログ圧縮、再構成を処理する必要があります。これらは元のアルゴリズムではしばしば省略されていますが、正確性とパフォーマンスには不可欠な詳細です。

Clinical relevance

PaxosとRaftは、広く使用されている協調サービス、分散データベース、および構成ストアの内部で動作します。これらを理解することは、障害発生時にもレプリカを強力に一貫させる必要があるシステムを構築または運用するために不可欠です。

History

Lamportは1998年の「パートタイム議会」論文でPaxosを記述し、2001年の「Paxos made simple」でそれを明確にしました。Chandraらは2007年に大規模での実用化の現実を報告し、OngaroとOusterhoutは2014年にRaftを導入し、同等の保証をはるかに教えやすく実装しやすくしました。

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を再編成したものです。