分散システムにおける「ゴースト再発」を解決するにはどうすればよいでしょうか?

[[318383]]

アリガールの紹介: 「ゴースト再発」問題は本質的には分散システムの「第 3 の状態」問題です。つまり、ネットワーク システムでは、要求に対して成功、失敗、および不明なタイムアウトの 3 つの結果が返されます。タイムアウトが不明な場合、要求コマンドに対するサーバーの処理結果は成功または失敗になりますが、どちらか一方である必要があり、矛盾があってはなりません。

1. 「幽霊再出現」問題

業界には、Paxos、Raft、Zab、Paxos バリアントなど、高可用性のデータ一貫性を実現するために広く使用されている分散一貫性レプリケーション プロトコルが数多く存在することがわかっています。 Paxos グループは通常、3 つまたは 5 つの冗長ノードで構成されており、少数のノードに障害が発生した場合でも、サービスの提供を継続し、データの一貫性を確保できます。最適化のため、プロトコルは通常、提案を開始する責任を負うノードの中からリーダーを選出します。リーダーの存在により、通常の状況下では並行した提案の干渉が回避され、提案処理の効率が大幅に向上します。

ただし、ネットワークの分離やマシンの障害などの極端な異常状況を考慮すると、リーダーは複数のスイッチとデータの回復を経る場合があります。 Paxos プロトコルを使用してログのバックアップとリカバリを処理する場合、大多数を確認するログが失われないようにすることができますが、「ゴースト再発」と呼ばれる現象を回避することはできません。次のシナリオを考えてみましょう。

上記の表に示すように、第 1 ラウンドでは、A が指定リーダーとなり、ログ 1 ～ 10 を送信します。しかし、次の 6 ～ 10 は多数派を形成せず、ランダムにクラッシュします。そして、第 2 ラウンドでは、B が指定リーダーとなり、ログ 6 ～ 20 を送信し続けます (B はログ 6 ～ 10 の存在を認識しません)。今回は、ログ 6 と 20 が多数派を形成します。 A は再びランダムに切り替わり、A が戻ってきます。大多数から得られた最大の LogId は 20 なので、穴を埋めることにしました。実際、今回は A が 6 から開始して 20 まで検証する可能性が非常に高くなります。1 つずつ何が起こるか見てみましょう。

1. インデックス 6 のログについては、A は基本 paxos の別のラウンドを実行し、より大きな proposalid を持つログが 6 の解決に達したことを検出します。したがって、A はローカル ログ 6 を放棄し、多数決で承認されたログを受け入れます。
2. インデックス 7 からインデックス 10 については、多数派が有効な配置を形成しなかったため、A はローカル ログを使用してランダムに提案を開始し、多数派を形成しました。
3. インデックス 11 からインデックス 19 については、有効なデータがディスクに保存されていないため、ギャップを埋めるために noop が使用されます。
4. インデックス 20 の場合、これは最も単純で、大多数によって承認されたログを受け入れます。

上記の 4 つの状況分析では、1、3、4 は深刻な問題ではありません。主にシナリオ2では、第2ラウンドでは存在しなかった7-10に相当し、その後第3列で再登場しました。 Oceanbase によれば、この問題はデータベース ログの同期の場合には許容できないとのことです。簡単な例としては転送シナリオがあります。ユーザーが送金するときに返される結果がタイムアウトした場合、多くの場合、ユーザーは送金が成功したかどうかを確認し、再試行するかどうかを決定します。初回の照会時に振替結果が有効でなく、再試行が実行され、振替取引ログがゴーストログとして再表示される場合、ユーザーは繰り返し振替を強いられることになります。

2. マルチパクソスに基づく「ゴースト再出現」問題を解決する

「ゴースト再発」問題に対処するために、Multi-Paxos に基づいて実装された一貫性システムは、各ログ コンテンツに epochID を保存し、このログを生成するときに Proposer が現在の ProposalID を epochID として使用するように指定できます。ログを logID 順に再生する場合、リーダーはサービスを開始する前に必ず StartWorking ログを書き込むため、epochID が前のログよりも小さくなると、これは「ゴースト再発」ログであり、無視する必要があることを意味します (説明すると、ここでの順序は、最初にギャップを埋め、次に StartWorkingID を書き、最後にサービスを提供することであると私は考えています)。

上記の例では、ラウンド 3 で A がリーダーとして開始する場合、ログの再生と再確認が必要であることが示されています。インデックス 1 から 5 までのログは、epochID 1 でクリアされます。次に、epochID フェーズに入り、インデックス 6 が epochID 2 の StartWorking ログとして確認されます。次に、インデックス 7 から 10 が確認されます。これは、前のログの epochID よりも小さい epochID 1 のログであるため、無視されます。インデックスが 11 から 19 のログの場合、EpochID はリーダーが確認した前のラウンドの StartWorkingID に従う必要があります (もちろん、ProposeID は 3 のまま維持される必要があります)。または、これらは noop ログであるため、特別に処理できます。つまり、ログのこの部分は epochID サイズの比較に参加しません。するとインデックス20のログも再確認されます。最後に、インデックス 21 が StartWorking ログに書き込まれ、多数派によって確認されると、A はリーダーとして要求の受信を開始します。

3. Raft に基づいて「ゴーストの再出現」問題を解決する

3.1 ラフトログの回収について

まず、Raft のログ回復について説明します。 Raft では、選出された各リーダーにはコミットされたデータが含まれている必要があります (引き出し原則、選出されたリーダーは大多数の最新データを持ち、大多数のノードでコミットされたデータが含まれている必要があります)。新しいリーダーは他のノード上の矛盾したデータを上書きします。新しく選出されたリーダーには、前期のリーダーがコミットしたログ エントリを含める必要がありますが、前期のリーダーがコミットしなかったログ エントリを含めることもできます。ログ エントリのこの部分はコミット済みに変換する必要がありますが、これは比較的面倒です。リーダーが複数回切り替わり、ログリカバリが完了しない可能性があることを考慮する必要があります。最終的な提案が一貫性があり最終的なものであることを確認する必要があります。そうでないと、いわゆるゴースト再発問題が発生します。

したがって、Raft に制約が追加されます。以前の用語のコミットされていないデータは大多数のノードに修復され、新しい用語の少なくとも 1 つの新しいログ エントリは大多数のノードにコピーまたは修復されて初めて、以前にコミットされていないログ エントリがコミット済みと見なされます。

前の用語のコミットされていないログ エントリをコミット済みのものに変換するための Raft のソリューションは次のとおりです。

Raft アルゴリズムでは、リーダーが選出された後、Noop の特別な内部ログが直ちに追加され、他のノードに直ちに同期されるため、以前にコミットされていないすべてのログが暗黙的にコミットされます。

これにより、次の 2 つのことが保証されます。

• 最大コミット原則は、データが失われないように、つまりコミットされたすべてのログ エントリが失われないようにするために使用されます。
• Noop が大多数のノードによって合意されコミットされた後にのみサービスが正常に動作するため (以前のログをすべて一緒に同期できるようにするため)、コミットされていないデータは読み取られないことが保証されます。 Noop ログ自体も境界線です。 Noop の前のログ エントリはコミットされ、Noop の後のログ エントリは破棄されます。

3.2 Raft は「ゴーストの再出現」問題を解決します

第1セクションのシナリオに関して、AはRaftの第3ラウンドでリーダーに選出されません。まず、選挙では、候補者は最後のログの用語番号 (lastLogTerm) と長さ (lastLogIndex) を比較します。 B と C の lastLogTerm(t2) と lastLogIndex(20) は、どちらも A の lastLogTerm(t1) と lastLogIndex(10) よりも大きいです。したがって、リーダーは B と C にのみ出現できます。C がリーダーになった後、リーダーは操作中にレプリカを修復すると想定します。 A の場合、ログ インデックス 6 から始めて、C はインデックス 6 以降のログ エントリを A にコピーします。したがって、インデックス 6 ～ 10 の A の元のログは削除され、C との一貫性が保たれます。最後に、C はフォロワーに noop ログ エントリを送信します。大多数の方に承認され提出されれば、正常に動作し始めます。したがって、インデックス 7 ～ 10 の値は読み取られません。

より一般的な幽霊の再出現のシナリオをもう一つ考えてみましょう。次のログシナリオを検討してください。

1) ラウンド 1、ノード A がリーダーであり、ログ エントリ 5 と 6 の内容はコミットされておらず、ノード A がクラッシュします。現時点では、クライアントはログ エントリ 5 と 6 の内容を照会できません。

2) ラウンド 2 では、B がリーダーになり、B のログ エントリ 3 と 4 の内容が C にコピーされます。B がリーダーである期間中は、内容は書き込まれません。

3) ラウンド 3、A が回復し、B と C が再開します。 A がリーダーとして再選され、ログ エントリ 5 と 6 の内容が B と C にコピーされます。この時点で、クライアントはログ エントリ 5 と 6 の内容を照会できます。

この問題は、現在の期間のログエントリを書き込む必要がある新しいリーダーを Raft に追加することで解決できます。これは実際には、MultiPaxos で説明されている StartWorking ログを記述するのと同じアプローチです。 B がリーダーになると、term 3 の noop ログが書き込まれ、上記の 2 つの問題が解決されます。

• Term 3 の noop ログがコミットされる前に、まず B のインデックス 3 と 4 のログ コンテンツが C にコピーされ、最大コミットの原則が実装されて、データが失われず、コミットされたログ エントリが失われないことが保証されます。
• ノード A が回復したとしても、 lastLogTerm が B および C よりも小さいため、リーダーになることはできません。この場合、A の未完了のコミットは削除されるだけなので、後続の読み取りではログ エントリ 5 および 6 の内容は読み取られません。

4. Zabに基づいて「ゴースト再出現」問題を解決する

4.1 Zabログリカバリについて

Zab の動作は、原子ブロードキャストとクラッシュ回復の 2 つの段階に分かれています。アトミック ブロードキャスト プロセスは、raft がトランザクションを送信するプロセスと比較することもできます。

クラッシュリカバリは、リーダー選出とデータ同期の 2 つの段階に分けられます。

初期のザブ議定書によって選出されるリーダーは、以下の条件を満たします。

a) 新しく選出されたリーダーノードは、このラウンドのすべての候補者の中で最大の zxid を持ちます。リーダーが最新のデータを持っていると単純に考えることもできます。この保証により、リーダーは可能な限り最新のデータを入手できるようになります。

b) リーダー選出プロセス中に比較される zxid は、各候補者がコミットしたデータに基づいて生成されます。

zxid は 64 ビットのネットワークで、上位 32 ビットはエポック番号です。各リーダー選出後、新しいリーダーが生成され、新しいリーダーはエポック番号を 1 増やします。下位 32 ビットはメッセージ カウンターで、受信されたメッセージごとに 1 ずつ増加し、新しいリーダーが選出された後は 0 にリセットされます。この設計の利点は、古いリーダーがクラッシュして再起動された場合、リーダーとして選出されないため、その zxid が現在の新しいリーダーよりも確実に小さくなることです。古いリーダーがフォロワーとして新しいリーダーに接続すると、新しいリーダーは古いエポック番号を持つコミットされていないすべての提案をクリアするように要求します。

リーダーが選出された後、ログ回復フェーズが始まります。各フォロワー ノードによって送信された zxid に基づいて、ノードは各フォロワーに送信するデータを決定し、フォロワーがデータに追いつくことができるようにすることで、最大コミットの原則を満たし、コミットされたデータがフォロワーにコピーされることを保証します。データに追いついた後、各フォロワーはリーダーに ACK を送信します。リーダーがフォロワーの半数以上から ACK を受信すると、リーダーは動作を開始し、zab プロトコル全体がアトミック ブロードキャスト フェーズに入ります。

4.2 Zab は「ゴーストの再出現」問題を解決します

セクション 1 のシナリオでは、ZAB の選出フェーズのメカニズムに従って、エポックは各選出後に +1 され、次のラウンドの zxid の上位 32 ビットとして使用されます。したがって、ラウンド 1 で A、B、C の EpochId が 1 であると仮定すると、次のラウンド 2 では EpochId が 2 になり、この Epoch に基づいて生成されたすべての zxid は A のすべての zxid よりも大きくなければなりません。したがって、ラウンド 3 では、B と C の zxid はどちらも A の zxid よりも大きいため、A はリーダーとして選択されません。 A がフォロワーとして参加すると、そのデータは新しいリーダーのデータによって上書きされます。状況 1 では、zab を回避できることがわかります。

セクション 3.2 のシナリオでは、ラウンド 2 で B がリーダーに選出された後、トランザクションは生成されません。第 3 ラウンドの選挙では、A、B、C の最新のログは変更されていないため、A の最後のログの zxid は B と C の zxid よりも大きいため、A がリーダーとして選出されます。 A がデータを B と C にコピーすると、「ゴースト レプリケーション」現象が発生します。

「ゴースト再発」問題を解決するために、最新の Zab プロトコルでは、リーダー選出のたびに、現在の EpochId (CurrentEpoch と表記) を記録するローカル ファイルが保存されます。選挙中は、CurrentEpoch が最初に読み取られ、投票用紙に追加され、他の候補者に送信されます。候補者は、CurrentEpoch が自身のものより小さいと判断した場合、この投票を無視します。 CurrentEpoch が自身のものより大きいことが判明した場合、この投票を選択します。等しい場合は、zxid が比較されます。したがって、この問題では、ラウンド 1 では、A、B、C の CurrentEpoch は 2 になります。ラウンド 2 では、A の CurrentEpoch は 2 で、B と C の CurrentEpoch は 3 です。ラウンド3では、BとCのCurrentEpochがAより大きいため、Aはリーダーになることができません。

5. さらなる議論

Alibaba Cloud の Nuwa 一貫性システムでは、Raft や Zab と同様のアプローチを採用しており、ゴースト再発を引き起こす可能性のあるロールが新しい選挙ラウンドでリーダーに選出されないよう保証し、ゴースト ログが再び出現するのを防ぎます。サーバーの観点から見ると、「ゴースト再発」の問題は、フェイルオーバーが発生した場合に、新しいリーダーが現在コミットされているインデックスを明確に把握していないこと、つまり、ログ エントリがコミットされた状態かコミットされていない状態かが明確でないことです。したがって、コミットされたログが失われないようにするための特定のログ回復方法が必要であり (最大コミット原則)、ログをコミットするかドロップするかを決定する境界線 (MultiPaxos の StartWorking、Raft の noop、Zab の CurrentEpoch など) を使用して、あいまいな状態を回避します。 「ゴースト再発」問題は、本質的には分散システムにおける「第 3 の状態」の問題です。つまり、ネットワーク システムでは、要求に対して成功、失敗、および不明なタイムアウトの 3 つの結果が返されます。タイムアウトが不明な場合、要求コマンドに対するサーバーの処理結果は成功または失敗になりますが、どちらか一方である必要があり、矛盾があってはなりません。クライアントでは、リクエストがタイムアウトになった場合、クライアントは現在の基礎ステータスが何であるかがわからず、成功か失敗かが不明になります。したがって、クライアントは通常再試行します。この場合、基礎となる適用されたビジネス ロジックは冪等性を保証する必要があります。そうでないと、再試行によってデータの不整合が発生します。