分散コンセンサスアルゴリズム EPaxos について 1 つの記事で学ぶ

分散システムにおける中心的な問題はデータの一貫性です。 Paxos アルゴリズムは分散一貫性における古典的なアルゴリズムであり、分散システムが特定の値 (解決) についてどのように合意に達するかという問題を解決するために使用されます。この記事では、Paxos の問題から EPaxos を紹介し、EPaxos の基本的な概念と直感的な理解を紹介します。この記事を読むには、Paxos や Raft などの分散コンセンサス アルゴリズムに関するある程度の知識が必要です。

導入

EPaxos（Egalitarian Paxos）は、業界で大きな注目を集めている次世代の分散コンセンサスアルゴリズムとして、幅広い応用の見通しを持っています。しかし、業界を見てみると、EPaxos のエンジニアリング実装はまだ存在せず、EPaxos をより一般的な方法で説明できる記事さえ見たことがありません。 EPaxos アルゴリズムは理論的には優れていますが、実際には理解が難しく、エンジニアリング実装には多くの課題があるため、実際の応用はまだ成熟していません。

この記事の目的は、EPaxos アルゴリズムをシンプルで分かりやすい方法で段階的に紹介することです。これにより、Paxos や Raft などの分散コンセンサス アルゴリズムについて基本的な知識しか持っていない学生でも EPaxos を簡単に理解できるようになり、あまり知られていない EPaxos が本当に身近なものとなり、何百万もの家庭に普及するようになります。

パクソスの問題

すべてはパクソスから始まります。 Paxos は分散コンセンサス アルゴリズムの創始者であり、2F+1 個のコピーのうち F 個のコピーの同時障害を許容できます。

通常の状況では、Paxos が解決に到達するには、準備フェーズと承認フェーズの 2 つのフェーズが必要です。

準備フェーズでは、各レプリカが提案する権利を競います。承認フェーズでは、提案権を獲得したレプリカが提案を開始し、すべてのレプリカ間で解決策が合意できるようにします。

Paxos を使用して一連の値について合意に達するプロセスを図 1 に示します。異なる色でマークされた 3 つのレプリカ A、B、C、D は、提案された値です。彼らは各インスタンスで競争し、独自の価値を提案します。

​​

図1. Paxosを使用して一連の価値観について合意に達する

Paxos は各インスタンスの値を個別に決定します。各インスタンスについて、完全な Paxos 2 フェーズ プロセスを実行して、インスタンスの値を決定します。

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

Multi-Paxos は各レプリカでリーダーを選出し、提案はリーダーによって開始されます。競争がないので、ライブロック問題は解決します。すべての提案がリーダーによって開始されると、準備フェーズをスキップして 2 つのフェーズを 1 つのフェーズにまとめ、効率を向上させることができます。

Multi-Paxos を使用して一連の値について合意に達するプロセスを図 2 に示します。異なる色でマークされた 3 つのレプリカが最初にリーダー選挙を実施します。緑のレプリカがリーダーとして選出され、4つの値A、B、C、Dを順番に提案します。

​​

図2 Multi-Paxosを使用して一連の価値観について合意に達する

Multi-Paxos はまずリーダーを選出します。リーダーが選出されると、インスタンスの提案権はリーダーに帰属します。インスタンスの提案権をめぐって競争する必要はありません。したがって、準備フェーズは省略でき、必要なフェーズは 1 つだけです。リーダーの存在により意思決定の効率は向上しますが、パフォーマンスと可用性のボトルネックにもなります。

リーダーは他のレプリカよりも多くのメッセージを処理する必要があり、各レプリカの負荷は不均衡で、リソースの使用率が低くなります。リーダーがダウンすると、システムは利用できなくなり、新しいリーダーが選出された後にのみサービスを復元できるため、可用性が低下します。

基本的な Paxos では、各レプリカが提案を行うことができ、可用性は高くなりますが、競合の衝突により効率は低くなります。 Multi-Paxos では、競合を回避して効率を向上させるためにリーダーが選出されますが、同時にリーダーのボトルネックが発生し、可用性が低下します。効率性と可用性を同時に実現できますか?この問題を解決するために EPaxos が提案されました。競合を回避するためにリーダーを導入する Multi-Paxos とは異なり、EPaxos は競合に直接対処して解決を試みる別のアプローチを採用しています。

EPaxosのソリューション

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

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

Paxos とは異なり、すべてのインスタンスには事前に番号が付けられ、各インスタンスの値は 1 つずつ独立して合意されます。 EPaxos は、インスタンスに事前に番号を付けることなく、複数のインスタンスを同時に処理できます。代わりに、インスタンスの順序は実行時に動的に決定されます。

EPaxos は、各インスタンスの値について合意に達するだけでなく、インスタンス間の相対的な順序についても合意に達します。 EPaxos は、異なるインスタンス間の相対的な順序も一貫性の問題と見なし、各レプリカ間で合意に達します。したがって、各レプリカは異なるインスタンスで同時に提案を開始できます。これらのインスタンスの値と相対順序が一致すると、各レプリカは相対順序に従ってそれらを並べ替え、一貫した順序を形成します。

EPaxos を使用して一連の値について合意に達するプロセスを図 3 に示します。異なる色でマークされた 3 つのレプリカがあり、それぞれが独自のインスタンス空間を持ち、それぞれのインスタンスで独自の値を提案します。 A、B、C、D は彼らが提案する値です。各インスタンスは、値だけでなく、他のインスタンス間の相対的な順序についても同意します。

​​

図3 EPaxosを使用して一連の価値観について合意に達する

EPaxos のインスタンス空間は 2 次元です。各レプリカは、2 次元インスタンス空間内の行を所有します。インスタンスを提案する権利をめぐって競争する必要はありません。各レプリカは、インスタンス間の相対的な順序を維持し、インスタンスの値と相対的な順序について合意に達しながら、独自のインスタンス空間で同時に提案を開始できます。最後に、各レプリカはインスタンスを相対的な順序で決定論的に並べ替え、一連の値について合意に達します。

EPaxos は、インスタンス間の相対的な順序を示すために、インスタンスの属性として依存性 (deps) の概念を導入します。 A ← B は、B が A に依存することを意味し、つまり A が B の前に来ることを意味します。各インスタンスには独自の依存関係セットがあります。 EPaxos はインスタンス間の依存関係を維持し、レプリカ間で依存関係セットと値の一貫性を保ちます。最後に、各レプリカは依存関係に従ってインスタンスを並べ替え、一貫した値のシーケンスを取得します。図 3 の場合、レプリカが最終的に同意する値の系列は、A ← B ← C ← D です。

EPaxos インスタンスをグラフ上のノードと考え、インスタンスの依存関係セットをノードの出力エッジと考えます。インスタンスの値と依存関係セットが解決に達すると、グラフのノードとエッジはレプリカ間で一貫性を持つため、各レプリカは同じグラフを参照します。

EPaxos のインスタンスの並べ替えのプロセスは、グラフの決定論的なトポロジカル ソートに似ています。ただし、EPaxos インスタンス間の依存関係がサイクルを形成する場合、つまりグラフ内にループが存在する場合があり、完全なトポロジカル ソートではないことに注意してください。

循環依存関係を処理するために、EPaxos のインスタンス並べ替えアルゴリズムは、まずグラフの強く接続されたコンポーネントを見つける必要があります。ループはすべて強連結成分に含まれます。すべての強く接続されたコンポーネントは有向非巡回グラフ (DAG) を形成し、強く接続されたコンポーネントに対して決定論的なトポロジカル ソートを実行します。

EPaxos がインスタンスを並べ替えるプロセスを図 4 に示します。強く接続されたコンポーネントは背景色で囲まれています。

​​

図4 EPaxosインスタンスの並べ替えプロセス

Tarjan アルゴリズムは一般に、グラフの強く接続されたコンポーネントを見つけるために使用されます。これは再帰アルゴリズムです。実際のストレス テストでは、再帰実装はスタック オーバーフローを起こしやすいことが判明しており、これもエンジニアリング アプリケーションに一定の課題をもたらします。

異なる強く接続されたコンポーネント内のインスタンスは、決定論的な位相順序でソートされます。同じ強く接続されたコンポーネント内のインスタンスは同時に提案され、理論的には任意の決定論的ルールに従ってソートできます。 EPaxos は、各インスタンスの seq シーケンス番号を維持するソリューションを提供します。 seq のサイズはインスタンス提案の順序をほぼ反映しており、グローバルに一意であり、増加すると予想されます。同じ強く接続されたコンポーネント内のインスタンスは、シーケンス サイズに従ってソートされます。実装中に、seq が繰り返される可能性があることが判明しました。 EPaxos の論文ではこの点が考慮されていませんでした。この問題と解決策については、以降の記事でさらに詳しく紹介します。

インスタンスが解決に達し、その依存インスタンスもすべて解決に達すると、ソート プロセスを開始できます。実際、新しいインスタンスが実行し続けると、古いインスタンスが新しいインスタンスに依存し、新しいインスタンスが更新されたインスタンスに依存する可能性があり、依存関係チェーンが終わりなく拡張され続けます。ソート処理を実行できず、ライブロックが発生します。これは、EPaxos エンジニアリング アプリケーションにとっても大きな課題です。

インスタンスのソート アルゴリズムは決定論的であるため、各レプリカは一貫した依存関係グラフに基づいてインスタンスを並べ替え、一貫したインスタンス シーケンスを取得します。つまり、一連の値について合意に達します。

要約する

EPaxos は、効率性と可用性の両方を考慮した動的順序を導入し、Basic Paxos と Multi-Paxos の利点を統合しており、幅広い応用の可能性を秘めています。この記事では、EPaxos の基本的な概念と直感的な理解について簡単に紹介し、読者に EPaxos の全体的な印象を与えることを目的としています。

考える

最後に、考えるべき質問がいくつかあります。

EPaxos インスタンスは事前に番号が付けられていないので、インスタンスはどのように識別されるのでしょうか?

EPaxos はインスタンスの依存関係セットをどのように決定し、依存関係セットの一貫性をどのように維持するのでしょうか?

EPaxos インスタンス間の依存関係がループを形成するのはなぜですか?どのような状況で循環依存関係が形成されるのでしょうか?

【この記事は51CTOコラムニスト「アリババオフィシャルテクノロジー」によるオリジナル記事です。転載については原著者にお問い合わせください。

この著者の他の記事を読むにはここをクリックしてください