この記事の要約: 分散一貫性テクノロジーはどのように進化してきたか?

[[334877]]

分散一貫性 (コンセンサス) は、分散システムの基礎として、コンピュータ システムの分野で常に注目されている話題です。近年、分散システムの規模がますます大きくなるにつれて、可用性と一貫性に対する要件がますます高くなり、分散一貫性の適用範囲がますます広範になっています。業界における分散一貫性の応用を見ると、最も初期の祖先である Paxos の優位性から、新興の Raft の人気、そして多くの注目を集め始めている現在のリーダーレス EPaxos まで、その背後にあるテクノロジーはどのように進化してきたのでしょうか。この記事では、技術的な観点から業界における分散一貫性の適用を検討し、理解しやすさ、使いやすさ、効率性、適用可能なシナリオなど、いくつかの観点から比較分析を行います。

分散一貫性

分散一貫性とは、簡単に言えば、1 つ以上のプロセスが値を提案した後、システム内のすべてのプロセスがこの値について合意に達することを意味します。

値について合意に達するために、各プロセスは独自の提案を行うことができ、最終的には、正しく実行されているすべてのプロセスが分散コンセンサス アルゴリズムを通じて同じ値を学習します。

業界での分散一貫性の応用は、マルチコピー ステート マシン モデル (複製ステート マシン) を構築して、高可用性と強力な一貫性を実現することです。

分散一貫性により、複数のマシンが同じ状態を持ち、同じ決定論的状態マシンを実行できるようになるため、いくつかのマシンに障害が発生しても全体は正常に動作し続けることができます。

パクソス

Paxos では、解決に到達するために少なくとも 2 つのフェーズ (準備フェーズと承認フェーズ) が必要です。

準備段階の役割:

• プロポーズする権利のために戦いましょう。提案権を取得した後にのみ、承認段階で提案を開始できます。そうでなければ、もう一度戦う必要があります。
• 以前に提案された値を学習します。

承認段階では、提案が多数決をとることができます。提案が過半数を獲得すると、決議が成立し、その決議についての学習を開始できます。承認フェーズが拒否された場合は、準備フェーズを再度実行する必要があります。

マルチパクソス

基本的な Paxos では、解決に達するまでに少なくとも 2 回のネットワーク ラウンド トリップが必要であり、同時実行状況ではさらに多くのラウンド トリップが必要になる場合があります。極端な場合には、ライブロックが発生する可能性があり、非効率的です。この問題を解決するために Multi-Paxos が提案されました。

Multi-Paxos はリーダーを選出し、提案はリーダーによって開始されます。競争がないので、ライブロック問題は解決します。すべての提案がリーダーによって開始されると、準備フェーズをスキップして 2 つのフェーズを 1 つのフェーズにまとめ、効率を向上させることができます。 Multi-Paxos では、単一のリーダーを想定しません。セキュリティに影響を与えることなく、複数のリーダーが同時に提案を行うことができます。極端な場合には、Basic Paxos に退化します。 Multi-Paxos と Basic Paxos の違いは、Multi ではないことです (Basic Paxos も Multi にすることができます)。ただし、同じ提案者が連続して提案を行った場合、準備フェーズをスキップして直接 Accept フェーズに進むように最適化されています。それだけです。

ラフト

分散一貫性の問題から直接派生した Paxos とは異なり、Raft はマルチレプリカ ステート マシンの観点から提案されており、より強力な仮定を使用して考慮する必要のある状態を削減し、理解と実装を容易にしています。 Raft と Multi-Paxos は密接に関連しています。以下は、Raft と Multi-Paxos の類似点と相違点をまとめたものです。 Raft と Multi-Paxos における類似の概念:

• Raft のリーダーは Multi-Paxos の提案者です。
• Raft の Term と Multi-Paxos の Proposal ID は本質的に同じものです。
• Raft のログエントリは Multi-Paxos の提案です。
• Raft のログ インデックスは、Multi-Paxos のインスタンス ID です。
• Raft のリーダー選出は、Multi-Paxos の準備フェーズと基本的に同じです。
• Raft のログのレプリケーションは、Multi-Paxos の Accept フェーズです。

Raft と Multi-Paxos の違い:

Raft では、システムにはいつでも最大 1 人のリーダーしか存在せず、提案はリーダー (強力なリーダー) によってのみ発行できると想定されています。そうでない場合、正確性に影響します。 Multi-Paxos もリーダーを選出しますが、これは効率性向上のためだけであり、提案がリーダー (弱いリーダー) によってのみ発行されるように制限するものではありません。強力なリーダーは通常、プロジェクトでリーダー リースとリーダー スティッキネスを使用して次のことを保証します。

• リーダー リース: 前のリーダーのリースの有効期限が切れると、システムは、新しいリーダーと古いリーダーのリースが重複しないように、一定期間ランダムに待機してからリーダー選出を開始します。
• リーダーの粘着性: リーダー リースの有効期限が切れていないフォロワーは、新しいリーダー選出リクエストを拒否します。

Raft では、最新のコミットログを持つノードがリーダーになる資格を制限しますが、Multi-Paxos にはこの制限はありません。 Raft はログを確認する前にログの連続性をチェックします。ログが不連続であることが検出された場合、ログの連続性を保証するためにログを拒否します。 Multi-Paxos はこのチェックを実行せず、ログに穴が残ります。 Raft はリーダーのコミット インデックスを AppendEntries に保持します。ログが過半数に達すると、リーダーはローカル コミット インデックスを更新してコミットを完了します。次の AppendEntries は、他のノードに通知するための新しいコミット インデックスを持ちます。 Multi-Paxos にはログ接続の想定がないため、他のノードに通知するために追加のコミット メッセージが必要です。

エパックス

EPaxos (Egalitarian Paxos) は、Raft より少し前に SOSP'13 で提案されました。しかし、Raft が業界で人気を博していた頃、EPaxos は長い間無視されていました。最近まで、EPaxos は業界から注目を集め始めていました。

EPaxos はリーダーレスコンセンサスアルゴリズムです。どのレプリカでもログを送信できます。通常、ログの送信には 1 回または 2 回のネットワーク ラウンド トリップが必要です。

EPaxos にはリーダー選出のオーバーヘッドはありません。 1 つのレプリカが利用できない場合は、他のレプリカにすぐにアクセスできるため、可用性が高まります。各レプリカには負荷が分散されており、リーダーのボトルネックがなく、スループットが高くなります。クライアントはサービスを提供するために最も近いレプリカを選択できるため、AZ 間およびリージョン間のシナリオでのレイテンシが短縮されます。

Paxos や Raft とは異なり、すべてのインスタンス番号は事前にソートされ、その後各インスタンスの値について合意に達します。 EPaxos はインスタンスの順序を事前に指定せず、実行時にインスタンス間の順序を動的に決定します。 EPaxos は、各インスタンスの値について合意に達するだけでなく、インスタンス間の相対的な順序についても合意に達します。 EPaxos は、異なるインスタンス間の相対的な順序も一貫性の問題として扱い、レプリカ間で合意に達します。したがって、各レプリカは独自のインスタンスで同時に提案を開始できます。これらのインスタンスの値と相対的な順序が一致すると、相対的な順序に従って並べ替えられ、最終的にステート マシンに順番に適用されます。

グラフ理論の観点から見ると、ログはグラフのノードであり、ログ間の順序はグラフのエッジです。 EPaxos はノードとエッジについて個別に合意に達し、トポロジカル ソートを使用してログの順序を決定します。グラフ内にループが形成される可能性もあり、EPaxos は循環依存関係の問題に対処する必要があります。

EPaxos は、ログ競合の概念を導入します (Parallel Raft に似ていますが、同時実行競合とは異なります)。 2 つのログ間に競合がない場合 (たとえば、異なるキーにアクセスする場合)、それらの相対的な順序は重要ではないため、EPaxos は競合するログ間の相対的な順序のみを処理します。

同時提案のログ間に競合がない場合、EPaxos は送信するために PreAccept フェーズのみを実行する必要があります (高速パス)。競合がない場合は、送信するために Accept フェーズを実行する必要があります (低速パス)。

PreAccept フェーズでは、ログと他のログ間の競合関係を維持しながら、ログと他のログの相対的な順序について合意に達しようとします。 PreAccept フェーズの実行後に、ログと他の同時に提案されたログとの間に競合が見つからない場合、ログと他のログ間の相対的な順序が合意され、非同期の Commit メッセージが直接送信されて送信されます。そうでない場合、ログと他の同時に提案されたログとの間に競合が見つかった場合、ログ間の相対的な順序はまだ合意されておらず、競合する依存関係の過半数に到達するために Accept フェーズを実行する必要があり、その後、Commit メッセージが送信されて送信されます。

EPaxos の Fast Path Quorum は 2F であり、これは F + [ (F + 1) / 2 ] に最適化できます。これは、レプリカが 3 つと 5 つある場合の Paxos および Raft と一致します。スロー パスは Paxos Accept フェーズであり、Quorum は F + 1 に固定されます。EPaxos には、リカバリ中にログに追いつくために使用できるアクティブ ラーニング アルゴリズムもあります。ここでは詳細には触れません。興味があれば、論文を読んでみてください。

比較分析

Paxos から Raft、そして EPaxos へと、基盤となるテクノロジーはどのように進化してきましたか?アルゴリズム自体から比較することができます。以下の比較・分析は、主に分かりやすさ、効率性、使いやすさ、適用可能なシナリオの観点から行われます。

1. 分かりやすさ

周知のとおり、Paxos は非常にわかりにくく、理解するのが難しいだけでなく、実装も困難です。 Raft は、理解しやすく、実装しやすいことを目指しています。 Raft の導入により、分散一貫性の使用のハードルが大幅に下がり、分散一貫性が一般の人々にも普及し、利用しやすくなりました。そのため、Raft が提案されるとすぐに支持を得て、分散一貫性のエンジニアリング アプリケーションが大きく促進されました。

EPaxos は Raft よりも早く提案されましたが、長い間誰も注目していませんでした。その大きな理由は、EPaxos が本当に理解しにくいことです。 EPaxos は Paxos をベースにしていますが、Paxos よりも理解が難しく、EPaxos のエンジニアリングへの応用を大きく妨げています。しかし、金は常に輝きます。 EPaxos は、その独自の利点により、ついに人々に発見され、幅広い可能性を秘めています。

2. 効率性

Paxos から Raft、そして EPaxos に移行して、効率は向上しましたか?主に、負荷分散、メッセージの複雑さ、パイプライン、並行処理の観点から、Multi-Paxos、Raft、EPaxos を比較します。

負荷分散

Multi-Paxos と Raft のリーダー負荷は高く、レプリカ間の負荷が不均衡になり、リーダーがボトルネックになりやすくなります。ただし、EPaxos ではリーダーは必要なく、レプリカ間の負荷は完全に分散されます。

メッセージの複雑さ

Multi-Paxos と Raft がリーダーを選出した後、ログをコミットするには通常 1 回のネットワーク ラウンドトリップのみが必要です。ただし、Multi-Paxos では、送信するために追加の非同期コミット メッセージが必要です。 Raft は追加のメッセージを使用せずに、ローカルコミットインデックスを進めるだけで済みます。 EPaxos では、ログの競合状況に応じて 1 回または 2 回のネットワーク ラウンド トリップが必要になります。したがって、メッセージの複雑さの点では、Raft の複雑さが最も低く、次に Paxos が続き、EPaxos の複雑さが最も高くなります。

パイプライン

パイプラインは、シーケンシャル パイプラインとアウトオブオーダー パイプラインに分けられます。 Multi-Paxos と EPaxos は順序なしのパイプラインをサポートしますが、Raft は対数連続性の仮定により順次パイプラインのみをサポートします。ただし、Raft は順序なしのパイプラインを実装することもできます。リーダーは、フォロワーごとに TCP のようなスライディング ウィンドウと、フォロワーごとに対応する受信ウィンドウを維持するだけで済みます。ウィンドウの内側のログは不連続になる場合がありますが、ウィンドウの外側のログはすでに連続しています。ログが連続すると、ウィンドウが前方にスライドされ、ウィンドウ内に順序外パイプラインを実装できるようになります。

並行処理

Multi-Paxos は Paxos 戦略に従います。同時実行の競合が検出されると、ロールバックして成功するまで再試行します。 Raft は同時実行の競合を回避するために強力なリーダーを使用します。フォロワーはリーダーと競合しないため、同時実行の競合を回避できます。 EPaxos は同時実行の競合問題に直接対処し、競合する依存関係を一貫性の問題として扱い、同時実行の競合を解決します。 Paxos は競合フォールバック、Raft は競合回避、EPaxos は競合解決です。 Paxos と Raft のログはどちらも線形ですが、EPaxos のログはグラフ状であるため、EPaxos の方が並列性が高く、スループットも高くなります。

3 可用性

EPaxos のレプリカであればどれでもサービスを提供できます。レプリカが利用できない場合は、すぐに他のレプリカに切り替えることができます。レプリカ障害による可用性への影響は最小限です。ただし、Multi-Paxos と Raft はどちらもリーダーに依存しています。リーダーが不在の場合は、新しいリーダーを選出する必要があります。新しいリーダーが選出されるまで、このサービスは利用できません。明らかに、EPaxos は Multi-Paxos や Raft よりも可用性が優れていますが、どちらの方が可用性が優れているのでしょうか?

ラフトは強いリーダーです。フォロワーは、選挙を開始する前に、古いリーダーのリースの有効期限が切れるまで待つ必要があります。マルチパクソスは弱いリーダーです。フォロワーはいつでもリーダーに立候補できます。これは効率に一定の影響を及ぼしますが、リーダーに障害が発生した場合にサービスを迅速に復旧できます。したがって、Multi-Paxos は Raft よりも可用性が優れています。

4つの適用可能なシナリオ

EPaxos は、AZ 間およびリージョン間のシナリオ、可用性要件が非常に高いシナリオ、リーダーがボトルネックになりやすいシナリオに適しています。 Multi-Paxos と Raft は非常に類似しており、イントラネット シナリオ、一般的な高可用性シナリオ、リーダーがボトルネックを形成する可能性が低いシナリオなど、同様のシナリオに適用できます。

考える

最後に、皆さんに考えていただきたい質問をいくつか残しておきます。興味のある学生はそれについて考えることができます。コメント欄にメッセージを残してください。

1) Paxos の提案 ID は一意である必要がありますか?非一意性は正確性に影響しますか?

2) Paxos が最大提案 ID と承認提案 ID を区別せず、それらを 1 つの最大提案 ID に統合し、提案 ID が最大提案 ID 以下の準備要求と承認要求をフィルターする場合、正確性に影響しますか?

3) Raft の PreVote の役割は何ですか?事前投票は必要ですか?