PaxosアルゴリズムがRaftプロトコルとZabプロトコルの祖先である理由とその原理分析

Paxos アルゴリズムは分散分野で非常に重要な役割を果たします。ただし、Paxos アルゴリズムには 2 つの明らかな欠点があります。1. 理解するのが難しい、2. エンジニアリングでの実装が難しい、です。

[[313088]]

インターネット上には Paxos アルゴリズムを説明する記事が多数ありますが、その質はさまざまです。 Paxos に関する多くの情報を読んだ後、Paxos を学ぶための最良の教材は「Paxos Made Simple」という論文と、それに続く中国語版と英語版の Wikipedia の Paxos の紹介であることがわかりました。この記事では、Paxos の謎を段階的に解明していきます。

パクソスとは

Paxos アルゴリズムは、メッセージ パッシングに基づく一貫性アルゴリズムであり、高度なフォールト トレランスを備えています。現在、分散一貫性の問題を解決するための最も効果的なアルゴリズムの 1 つとして認識されています。

Google Chubby の作者である Mike Burrows 氏は、世界には一貫性アルゴリズムが 1 つだけ存在し、それが Paxos であり、他のアルゴリズムは欠陥製品であると述べています。

Mike Burrows 氏の発言は少し誇張されているが、少なくとも Paxos アルゴリズムの現状を示している。しかし、Paxos アルゴリズムはわかりにくく、理解しにくいことでも有名です。この記事の目的は、Paxos アルゴリズムを、その実行プロセスだけでなく、アルゴリズムの導出や著者が最終ソリューションを段階的に導き出した経緯も含めて、シンプルでわかりやすい方法で理解できるようにすることです。導出プロセスを理解することによってのみ、アルゴリズムの本質を深く理解することができます。さらに、導出プロセスを理解することは、私たちの思考にも非常に役立ちます。問題を解決するためのアイデアやインスピレーションを与えてくれるかもしれません。

問題の背景

一般的な分散システムでは、マシンのクラッシュやネットワーク異常（メッセージの遅延、損失、重複、障害、ネットワークの分割など）などの状況が常に発生します。 Paxos アルゴリズムが解決する必要がある問題は、上記の例外が発生する可能性がある分散システムにおいて、クラスター内の特定のデータの値について迅速かつ正確に合意に達し、上記のどの例外が発生してもシステム全体の一貫性が損なわれないようにすることです。

注意: ここでいう特定のデータの値は、狭義の数字だけではありません。ログやコマンドの場合もあります。 。 。アプリケーションシナリオに応じて、特定のデータの値は異なる意味を持ちます。

関連概念

Paxos アルゴリズムには、次の 3 つの役割があります。

提案者

アクセプター

学習者

特定の実装では、プロセスが同時に複数の役割を果たす場合があります。たとえば、プロセスは提案者、受け入れ者、学習者の両方である場合があります。

また、提案という非常に重要な概念もあります。最終的に合意された価値は提案の中にあります。

注記：

ここでは、「提案＝価値」、つまり提案には価値しか含まれていないと仮定します。その後の導出プロセスで、提案に価値だけが含まれていると問題があることがわかり、提案を再設計します。

当面は「提案者が直接提案を提出できる」ことを前提とします。その後の導出プロセスでは、提案者が直接提案を行うと問題が発生するため、提案を学習するプロセスを追加する必要があることがわかります。

提案者は提案 (propose) できます。受け入れ者は提案 (accept) を受諾できます。提案が選択された (chosen) 場合、提案内の値が選択されます。

先ほど述べた「特定のデータの値について合意に達する」という点に戻ると、これは、提案者、受け入れ者、学習者全員が同じ値が選択されたと考えることを意味します。では、どのような状況で、提案者、受け入れ者、学習者は値が選択されたとみなすのでしょうか?

提案者: 提案者が送信した提案が受け入れ者によって受け入れられる限り (最初は受け入れる必要がある受け入れ者は 1 人だけであると考えられていましたが、導出プロセス中に半数以上の受け入れ者の同意が必要であることが判明しました)、提案者は提案内の値が選択されたと見なします。

アクセプター: アクセプターが提案を承認する限り、アクセプターは提案内の値が選択されるものとみなします。

学習者: アクセプタは選択された値を学習者に伝え、学習者はその値が選択されたとみなします。

問題の説明

値を提案できるプロセスのセットがあるとします (値は提案の中にあります)。一貫性アルゴリズムでは、提案された多数の値の中から 1 つの値だけが選択されるようにする必要があります。値が提案されていない場合は、値を選択しないでください。値が選択されると、すべてのプロセスが選択された値を学習できる必要があります。コンセンサス アルゴリズムの場合、安全要件は次のとおりです。

提案された値のみ選択できます。

選択された値は1つだけであり、

プロセスが値が選択されたと判断する場合、その値は実際に選択された値である必要があります。

活性要件を正確に定義していません。私たちの目標は、提案された値の 1 つが最終的に選択されるようにすることです。値が選択されると、プロセスは最終的にその値を学習できるようになります。

Paxos の目標は、値が最終的に選択されることを保証し、値が選択されると、プロセスが最終的に選択された値を取得できるようにすることです。

異なるロールがメッセージを送信して通信できると仮定すると、次のようになります。

各ロールは任意の速度で実行され、エラーにより停止したり、再起動したりすることがあります。値が選択された後、すべてのロールが失敗して再起動する可能性があります。失敗して再起動するロールが何らかの情報を記録できない限り、再起動後に選択された値を判別することはできません。

メッセージは配信中に長時間遅延したり、重複したり、失われたりする可能性があります。ただし、メッセージは破損しません。つまり、メッセージの内容は改ざんされません (ビザンチン将軍問題)。

導出プロセス

最もシンプルな解決策 - アクセプタは1つだけ

アクセプターが 1 つだけであると仮定すると (プロポーザーは複数存在する可能性があります)、アクセプターが最初に受信した提案を受け入れる限り、その提案が選択され、提案内の値が選択された値になります。これにより、1 つの値のみが選択されるようになります。

ただし、唯一の Acceptor がダウンすると、システム全体が機能しなくなります。

したがって、複数の Acceptor が存在する必要があります。

複数のアクセプタ

複数の Acceptor の状況は次の図に示されています。では、複数の提案者と複数の受け入れ者が存在する場合に、値が確実に選択されるようにするにはどうすればよいでしょうか?

解決策を探し始めましょう。

たとえ 1 人の提案者だけが値を提案したとしても、その値が選択されるようにしたい場合。

すると、次の制約が得られます。

P1: アクセプターは、最初に受け取った提案を受け入れる必要があります。

ただし、各 Proposer が異なる値を提案し、それを異なる Acceptor に送信する場合、別の問題が発生します。 P1によれば、Acceptorは受信した値を個別に受け入れるため、異なる値が選択されます。不整合が発生しました。以下のように表示されます。

上記の矛盾の問題は、「提案が Acceptor によって受け入れられる限り、提案の値が選択される」ために発生します。したがって、次の条項を追加する必要があります。

ルール: 提案が選ばれるには、承認者の半数以上が承認する必要があります。

このルールは、「アクセプターは複数の提案を受け入れることができなければならない」ことも意味します。そうでない場合、最終的に値が選択されない可能性があります。例えば、上の写真のような状況です。 v1、v2、v3 はすべて 1 つの Acceptor によってのみ受け入れられるため、選択されません。

冒頭で述べた「提案＝価値」ではニーズに応えられなくなったため、提案書をリニューアルし、各提案書に提案番号を付与して、提案書が提出された順番がわかるようにしました。 「提案 = 提案番号 + 値」とします。

複数の提案を選択することは可能ですが、選択された提案はすべて同じ値を持つようにする必要があります。そうしないと、矛盾が再び発生します。

したがって、次のような制約があります。

P2: 値が v の提案が選択された場合、それより大きい番号の選択された各提案の値も v である必要があります。

提案はアクセプターによって受け入れられた場合にのみ選択されるため、アクセプターによって受け入れられた提案に対する制約 P2 を制約 P2a に書き換えることができます。

P2a: 値 v を持つ提案が選択された場合、アクセプターによって受け入れられる、それより大きい数値を持つ各提案の値も v である必要があります。

P2a が満たされる限り、P2 は満たされます。

ただし、次の状況を検討してください。合計 5 つの Acceptor があると仮定します。提案者2は[M1, V1]を提案し、受け入れ者2〜5（半数以上）が提案を受け入れます。したがって、受け入れ者2〜5と提案者2は両方ともV1が選択されると考えています。 Acceptor1 はダウンタイムから回復したばかりです (Acceptor1 はこれまで提案を受け取っていません)。この時点で、Proposer1 は提案 [M2, V2] を Acceptor1 に送信します (V2≠V1 かつ M2>M1)。Acceptor1 にとって、これは受信した最初の提案です。 P1 (Acceptor は受信した最初の提案を受け入れなければなりません) によれば、Acceptor1 は提案を受け入れなければなりません! 同時に、Acceptor1 は V2 が選択されると信じています。これにより、2つの疑問が生じます。

Acceptor1 は V2 が選択されたと信じ、Acceptor2～5 と Proposer2 は V1 が選択されたと信じます。不整合が発生しました。

V1が選択されますが、Acceptor1によって受け入れられたより大きな数値を持つ提案[M2、V2]の値はV2であり、V2≠V1です。これは P2a と矛盾します (値 v を持つ提案が選択された場合、アクセプターによって受け入れられる、より大きな数値を持つ各提案の値も v である必要があります)。

したがって、P2a 制約を強化する必要があります。

P2a は Acceptor によって受け入れられる提案に対する制約ですが、実際には提案は Proposer によって行われるため、Proposer によって行われた提案に制約を課すことができます。 P2b を入手:

P2b: 値 v を持つ提案が選択された場合、提案者が提案した、それより大きい数値を持つ提案も値 v を持つ必要があります。

P2b から P2a を、そして P2 を推測できます。

では、値 v を持つ提案が選択された後に、提案者が提出したより高い数値を持つすべての提案の値が v になるようにするにはどうすればよいでしょうか。

P2cが満たされている限り:

P2c: 任意のNとVに対して、提案[N、V]が提案された場合、次の2つの条件のいずれかを満たすアクセプタの半数以上で構成される集合Sが存在する。

S 内のすべての Acceptor は、N 未満の番号の提案を受け入れていません。

S で Acceptor によってこれまでに受け入れられた最大の数値を持つ提案の値は V です。

提案者が提案を生成する

P2b を満たすために、ここで重要な考え方があります。提案者が提案を生成する前に、まず選択された値または選択される可能性がある値を「学習」し、次にこの値を自身の提案の値として使用する必要があります。値が選択されていない場合は、提案者が値の値を決定できます。これが合意に達する唯一の方法です。この学習フェーズは、「準備リクエスト」を通じて実現されます。

したがって、次の提案生成アルゴリズムが得られます。

提案者は新しい提案番号 N を選択し、特定のアクセプタ セット (半分以上) にリクエストを送信し、セット内の各アクセプタに次のように応答するよう要求します。

(a) 提案者に対して、N未満の番号の提案は受理しないことを約束する。

(b) 受諾者がすでに提案を受諾している場合、受諾者はすでに受諾した提案番号の中でN未満の最大の提案番号を提案者に返答します。

このリクエストを番号 N の準備リクエストと呼びます。

提案者が受け入れ者の半数以上から応答を受け取った場合、番号 N と値 V を持つ提案 [N, V] を生成できます。ここで、V はすべての応答の中で最も高い数値を持つ提案の値です。すべての応答に提案がない場合、提案者自身が V を選択できます。

提案を生成した後、提案者はその提案を承認者セットの半数以上に送信し、これらの承認者が提案を承認することを期待します。このリクエストを Accept リクエストと呼びます。 (注: この時点で Accept 要求を受け入れる Acceptor セットは、必ずしも以前の Prepare 要求に応答した Acceptor セットであるとは限りません)

受諾者は提案を受諾する

アクセプターは、アルゴリズムのセキュリティが侵害されることを心配することなく、あらゆるリクエスト (Prepare リクエストと Accept リクエストを含む) を無視できます。したがって、ここで説明するのは、アクセプターがリクエストに応答できるタイミングについてです。

提案を受け入れるために、アクセプターに次の制約を与えます。

P1a: Acceptor が N より大きい番号の Prepare 要求に応答していない限り、番号 N の提案を受け入れることができます。

アクセプターが番号 N の準備要求を受信した場合、N より大きい番号の準備要求にすでに応答しています。 P1a によれば、受諾者が番号 N の提案を受諾することは不可能です。したがって、Acceptor は番号 N の準備要求を無視できます。もちろん、エラーを返信して、提案者が提案を受け入れられないことをできるだけ早く知らせることもできます。

したがって、受け入れ側が覚えておく必要があるのは、次の点だけです。1. 受け入れられた提案数が最も多い提案 2. 応答されたリクエスト数が最も多い提案

Paxosアルゴリズムの説明

上記の導出の後、Paxos アルゴリズムのプロセスを要約します。

Paxos アルゴリズムは 2 つのフェーズに分かれています。詳細は以下の通りです。

フェーズ1:

(a) 提案者は提案番号 N を選択し、番号 N の準備要求を半数以上の承認者に送信します。

(b) アクセプターが番号 N の準備要求を受信し、N がアクセプターがすでに応答したすべての準備要求の数より大きい場合、アクセプターは、すでに受け入れた最大の番号の提案 (ある場合) を提案者に応答し、アクセプターは、番号 N 未満の提案を受け入れないことを約束します。

フェーズ2:

(a) 提案者が、番号Nの準備要求に対して承認者の半数以上から応答を受け取った場合、提案者は提案[N、V]の承認要求を承認者の半数以上に送信します。注: V は、受信した応答の中で最も高い数値を持つ提案の値です。応答に提案が含まれていない場合、V は提案者自身によって決定されます。

(b) アクセプターが番号 N の提案に対する Accept 要求を受信した場合、アクセプターが N より大きい番号の準備要求に応答していない限り、その提案を受け入れます。

学習者は選択された値を学習する

学習者が選択した値を学習（取得）するには、次の 3 つのオプションがあります。

Paxosアルゴリズムの活性を保証する方法

メイン Proposer を選択することで、Paxos アルゴリズムのアクティビティが保証されます。この時点で、セキュリティとアクティビティの両方を保証できる分散コンセンサス アルゴリズム、つまり Paxos アルゴリズムが得られました。