[1901] 第03講：Paxo アルゴリズムを徹底的に理解するには？

この授業では「Paxosアルゴリズムを徹底的に理解する方法」について説明します。

Paxosアルゴリズムは分散システムにおいて非常に重要な地位を占めており、オープンソースの分散ロックコンポーネントであるGoogle Chubbyの作者であるMike Burrowsは、「この世界には一つの一貫性アルゴリズムしか存在しない。それはPaxosアルゴリズムであり、他のアルゴリズムは劣ったものである」と述べています。

Paxosアルゴリズムは重要ですが、アルゴリズムが複雑であるため有名です。しかし、Paxosアルゴリズムは分散システムを学ぶ上で必要な知識の一つであり、この授業では難しさに立ち向かい、一緒にPaxosアルゴリズムを学びましょう。

Quorumメカニズム#

Paxosアルゴリズムを学ぶ前に、まず分散システムにおけるQuorum選挙アルゴリズムを見てみましょう。さまざまな一貫性アルゴリズムの中でQuorumメカニズムの影が見られ、主な数学的思想は引き出しの原理に由来しています。簡単に言うと、N個のレプリカの中で、1回の更新が成功した場合、W個が成功したなら、データを読み取る際にはN-W個以上のレプリカから読み取る必要があります。こうすることで、少なくとも1つの更新されたデータを読むことができます。

Quorumメカニズムに対応するのはWARO、つまりWrite All Read Oneであり、これはシンプルなレプリカ制御プロトコルです。クライアントが特定のレプリカにデータを書き込むリクエストを行うとき（データを更新する場合）、すべてのレプリカが成功裏に更新されるまで、この書き込み操作は成功と見なされず、そうでなければ失敗と見なされます。

WAROは読み取りサービスを優先して保証します。すべてのレプリカが成功裏に更新されて初めて更新が成功と見なされ、これによりすべてのレプリカが一致していることが保証されます。そうすれば、任意のレプリカからデータを読むだけで済みます。書き込みサービスの可用性は低く、1つのレプリカが更新に失敗すれば、その書き込み操作は失敗と見なされます。N個のレプリカがあると仮定し、N-1個がダウンしても、残りの1つのレプリカは読み取りサービスを提供できます。しかし、1つのレプリカがダウンすれば、書き込みサービスは成功しません。

WAROは更新サービスの可用性を犠牲にし、読み取りサービスの可用性を最大限に高めます。一方、Quorumは更新サービスと読み取りサービスの間で妥協を行います。

Quorumの定義#

Quorumの定義は次の通りです：N個のレプリカがあると仮定し、更新操作wiがW個のレプリカで成功した場合、今回の更新操作wiは成功と見なされます。この成功した更新操作に対応するデータを「成功したデータ」と呼びます。読み取り操作に関しては、少なくともR個のレプリカを読み取る必要があり、今回の更新データを得るためには、W+R>Nであり、すなわちWとRが重複している必要があります。一般的に、W+R=N+1です。

N = データのレプリカの数

W = 更新成功に必要なレプリカ

R = 一度のデータオブジェクト読み取りにアクセスするレプリカの数

Quorumは、少なくともN+1-Wのレプリカデータを読み取る必要があることを制限します。少し抽象的に聞こえるかもしれませんが、例を挙げると、10個のレプリカを維持していて、3つが成功裏に更新された場合、少なくとも8つのレプリカのデータを読み取る必要があります。これにより、最新のデータを読み取ることができます。

Quorumの応用#

Quorumメカニズムは強い一貫性を保証することはできません。つまり、任意の時点で任意のユーザーまたはノードが最近成功裏に提出されたレプリカデータを読み取ることができるわけではありません。

Quorumメカニズムの使用には、最新の成功した提出のバージョン番号を取得するためのメタデータサービスが必要です。これにより、最新の成功した提出のバージョン番号を確認し、既に読み取ったデータから最新の書き込まれたデータを確認できます。

Quorumは分散システムで一般的に使用されるメカニズムであり、データの冗長性と最終的一貫性を保証する投票アルゴリズムです。Paxos、Raft、ZooKeeperのZabなどのアルゴリズムでQuorumメカニズムの応用を見ることができます。

Paxosノードの役割と相互作用#

Quorumメカニズムを理解した後、次にPaxosアルゴリズムを学びます。まず、Paxosアルゴリズムにおけるノードの役割と相互作用を見てみましょう。

Paxosのノードの役割#

Paxosプロトコルには、Proposer、Acceptor、Learnerの3つのノードの役割があります。さらに、議題を生成するクライアントもあります。

上記の3つの役割は論理的な区分に過ぎず、実際の作業では、1つのノードが同時にこれら3つの役割を果たすことができます。

Proposer 提案者#

Proposerは複数存在することができ、プロセスが始まると、Proposerは提案を行います。つまり、valueです。valueとは、エンジニアリングにおいては任意の操作を指し、例えば「特定の変数の値を新しい値に変更する」といったことです。Paxosプロトコルでは、これらの操作を統一してvalueとして抽象化します。

異なるProposerは異なる、さらには矛盾するvalueを提案することができます。例えば、あるProposerが「変数Xを1に設定する」と提案し、別のProposerが「変数Xを2に設定する」と提案することがあります。しかし、同じラウンドのPaxosプロセスでは、最大で1つのvalueのみが承認されます。

Acceptor 批准者#

クラスター内にはN個のAcceptorが存在し、Acceptor同士は完全に対等で独立しています。Proposerが提案したvalueは、過半数（N/2+1）のAcceptorの承認を得なければ通過できません。

Learner 学習者#

Learnerは選挙には参加せず、承認されたvalueを学習します。Paxosにおいて、Learnerは主に関連する状態機械の同期プロセスに参加します。

ここでLearnerのプロセスはQuorum議会メカニズムを参考にしており、あるvalueがW=N/2 + 1のAcceptorの承認を得る必要があります。Learnerは少なくともN/2+1個のAcceptorの結果を読み取った後、最大でN個のAcceptorの結果を読み取ることで、通過したvalueを学習できます。

Client 生成者#

Clientの役割は、生成者として実際には選挙プロセスには参加せず、例えば変更リクエストの発信源などです。

ProposerとAcceptorの相互作用#

Paxosにおいて、ProposerとAcceptorはアルゴリズムの核心的な役割を果たします。Paxosが説明するのは、複数のProposerと複数のAcceptorからなるシステム内で、どのようにして複数のAcceptorがProposerが提案したさまざまな提案に対して合意に達するかというプロセスです。一方、Learnerは最終的に承認された提案を「学習」するだけです。

ProposerとAcceptorの間の相互作用は主に4種類のメッセージ通信があります。以下の図を参照してください：

この4種類のメッセージは、Paxosアルゴリズムの2つの段階の4つのプロセスに対応しています。以下で選挙プロセスを分析する際に説明します。

Paxos選挙プロセス#

選挙プロセスは準備段階と選挙段階の2つの部分に分けることができ、以下の時系列図を参照してください：

Phase 1 準備段階#

Proposerは、グローバルに一意で増加するProposalIDを生成し、Paxosクラスター内のすべてのマシンにPrepareリクエストを送信します。ここではvalueを持たず、N、すなわちProposalIDのみを持ちます。

AcceptorはPrepareリクエストを受信した後、受信したProposalIDが以前に応答したすべての提案のNより大きいかどうかを判断します。もしそうであれば：

ローカルにNを永続化し、Max_Nとして記録します。
リクエストに応答し、すでにAcceptした提案の中でNが最大のvalueを持ちます。もしこの時点でまだAcceptした提案がない場合は、valueは空として返します。
Max_Nより小さい提案はAcceptしないと約束します。

もしそうでなければ、応答しないか、Errorを返します。

Phase 2 選挙段階#

説明を簡単にするために、Phase 2の選挙段階をP2a、P2b、P2cに分けます。

P2a：ProposerがAcceptを送信#

しばらくして、ProposerはPrepareの応答をいくつか収集します。以下のような状況があります：

もし応答の数がAcceptorの半数を超え、すべての応答のvalueが空である場合、Proposerはacceptリクエストを発行し、自分が指定したvalueを持ちます。
もし応答の数がAcceptorの半数を超え、いくつかの応答のvalueが空でない場合、Proposerはacceptリクエストを発行し、応答の中でProposalIDが最大のvalueを持ち、自分の提案内容とします。
もし応答の数がAcceptorの半数以下である場合、より大きなProposalIDを生成することを試み、準備段階に戻ります。

P2b：AcceptorがAcceptに応答#

AcceptorはAcceptリクエストを受信した後、次のように判断します：

もし受信したNがMax_N以上（一般的には等しい）であれば、成功を応答し、Nとvalueを永続化します。
もし受信したNがMax_N未満であれば、応答しないか、提出失敗を返します。

P2c: Proposerが投票を集計#

しばらくして、ProposerはいくつかのAcceptの応答を収集し、提出成功の状況を確認します。例えば：

応答の数がAcceptorの半数を超える場合、valueの提出が成功したことを示し、この時点ですべてのProposer、Learnerに対して、コミットされたvalueを通知するためにブロードキャストを発信できます。
応答の数がAcceptorの半数以下の場合、より大きなProposalIDを生成することを試み、準備段階に戻ります。
提出失敗の応答を受け取った場合、より大きなProposalIDを生成することを試み、準備段階に戻ります。

Paxosの一般的な問題#

Paxosプロトコルに関して、いくつかの一般的な問題がありますので、簡単に紹介します。

1. 半数以下のAcceptorが失効した場合、どのように正常に動作しますか？

Paxosプロセスにおいて、半数以下のAcceptorが失効した場合、2つの状況に分けられます：

第一の状況は、半数以下のAcceptorが失効した時点で最終的なvalueが決定されていない場合です。この場合、すべてのProposerは再び提案を競い合い、最終的に1つの提案が成功裏に提出されます。

第二の状況は、半数以下のAcceptorが失効した時点で最終的なvalueが決定されている場合です。この場合、すべてのProposerは最終的なvalueを提出しなければなりません。つまり、valueはすでに有効であり、取得可能であり、変更されることはありません。

2. Acceptorはより大きなN、すなわちProposalIDを受け入れる必要がありますが、これは何の意味がありますか？

このメカニズムは、1つのProposerがクラッシュしてブロック問題を引き起こすのを防ぎ、他のProposerがより大きなProposalIDを使用して一時的なアクセス権を奪うことを許可します。

3. どのようにして一意の番号、すなわちProposalIDを生成しますか？

『Paxos made simple』の論文では、一意の番号はすべてのProposerが交差しないデータセットから選択することを要求し、異なるProposer間で重複しないことを保証する必要があります。例えば、システムに5つのProposerがある場合、各Proposerに識別子j（0〜4）を割り当てることができ、各Proposerが提案する決議の番号は5*i + jとなります。ここで、iは提案の回数を示すことができます。

まとめ#

この授業ではPaxosプロトコルに関連する知識を共有しました。Paxosは古典的な分散プロトコルであり、これを理解することで他の分散プロトコルの学習がはるかに簡単になります。

Paxosアルゴリズムで最も重要なのはプロセスを理解することであり、各プロセスを暗記する必要はありません。文中で紹介されたもの以外にも、関連する分岐判断や選択シナリオはたくさんあります。Paxosアルゴリズムに関連する導出や証明について知りたい場合、最後にPaxosに関連するいくつかの論文のリンクを添付しましたので、興味のある方はぜひ学んでみてください：

《Javaエンジニア高給トレーニングキャンプ》

実戦トレーニング+面接シミュレーション+大手企業内紹介。技術力を向上させ、大手企業で高給を得たい方は、リンクをクリックして自己を高めてください！

選りすぐりのコメント#

* 鑫：#

応答の数が Acceptor の半数を超え、いくつかの応答の value が空でない場合、Proposer は accept リクエストを発行し、応答の中で ProposalID が最大の value を持ち、自分の提案内容とします。

これはあまり理解できません。自分の提案内容とはどういう意味ですか？

講師の返信：

投票後、他のノードの一意の ID が自分を超えた場合、ローカル操作を放棄し、他のノードの提案を選択します。

** 露：#

先生、1 つの Proposer が ProposalID を生成したら、より大きな ProposalID を生成しないのでしょうか？もしそうなら、最後の Proposer が生成する ProposalID は常に最大になるのではないでしょうか？そうすると、Proposer がクラッシュしてブロックされるのを防ぐことはできませんよね？

講師の返信：

Proposer が生成する ProposalID はローカルの記録情報に基づいて生成されるため、単一の最大値です。

** 文：#

半数以上の Acceptor が失効した場合、どのような状況が発生し、どのように対処しますか？

講師の返信：

アルゴリズムは機能しなくなります。具体的には各社の実装によります。

**9904：#

いいですね、保存する価値があります。

* 星：#

教わりました、選挙の問題！これは基本的なアルゴリズムであり、各社の製品はこの基盤の上に一定のカスタマイズと詳細な最適化を行っています。

桑：#

準備段階で Acceptor が Prepare リクエストを受信した場合、すべての Proposer に応答するのか、それともリクエストした者に応答するのか？

講師の返信：

提案者に応答します。

桑：#

先生、文中で複数の Proposer の提案が異なる可能性があると述べられていますが、提案が半数以上に受け入れられなかった場合、Proposer はより大きな ProposalID を生成すると言っています。そうすると、どの Proposer の値が保存されるべきかをどうやって確認するのでしょうか？不正確な値がより大きな ProposalID を生成することで選ばれることはありませんか？

講師の返信：

Paxos には悪意のあるノードは存在しないはずです。バイザンティン問題と比較できます。