分散コンセンサスアルゴリズム 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 つのレプリカが最初にリーダー選挙を行います。緑のレプリカがリーダーに選出され、次に A、B、C、D の 4 つの値を順番に提案します。

​​

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

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

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

ベーシック Paxos では、各レプリカが提案を行うことができ、可用性は高くなりますが、競合による衝突のため効率は低くなります。マルチ 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 サイズに従って並べ替えられます。実装中に、seq が繰り返される可能性があることが判明しました。EPaxos の論文ではこの点が考慮されていませんでした。この問題と解決策については、後続の記事でさらに詳しく説明します。

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

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

要約する

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

考える

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

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

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

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

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

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