図解された Raft コンセンサス アルゴリズム: ログを複製する方法は?

[[402526]]

ラフトログフォーマット

Raft アルゴリズムでは、分散一貫性を実現するために必要なデータはログと呼ばれます。Java バックエンドのほとんどの人がログについて話すとき、通常は、log4j などのログ フレームワークを通じてプロジェクトによって出力される情報を思い浮かべます。Raft アルゴリズムのデータ送信レコードは、時系列順に追加されます。Raft は、それらを厳密な時系列順と特定の形式でログ ファイルに書き込みます。

上図に示すように、Raft ログはログエントリ (LogEntry) の形式で構成されます。各ログエントリには、コマンド、用語情報、ログ内でのログエントリの位置情報 (インデックス値 LogIndex) が含まれます。

• 指示: クライアント要求によって送信される実行指示。少しわかりにくいですが、クライアントが保存する必要があるログデータとして理解できると思います。
• インデックス値: ログ内のログ項目の位置。インデックス値は連続的で単調に増加する整数であることに注意してください。
• 任期番号: このログエントリを作成したリーダーの任期番号。

ログ複製プロセス

Raft のレプリケーション プロセスは、おおよそ次のようになります。

リーダーはクライアントからの要求を受け取り、新しいログ エントリを作成し、それをローカル ログに追加します。次に、リーダーはエントリ追加 RPC 要求を通じて、新しいログ エントリをフォロワーのローカル ログにコピーします。リーダーは、ほとんどのフォロワーから正常な応答を受信すると、このログ エントリをステート マシンに適用します。これは、ログが正常に書き込まれたことを意味します。最後に、リーダーは、ログが正常に書き込まれたことを示すメッセージをクライアントに返します。このプロセスを次の図に示します。

Raft のレプリケーション プロセス中に、リーダーがほとんどのフォロワーから成功応答を受信し、ログ項目をステート マシンに適用した後、フォロワーに結果を返す必要がなく、成功メッセージでクライアントに直接応答することがわかります。これは最適化手法です。同時に、Raft は次の RPC ログ追加要求にこの時点のログ項目情報を添付します。

上記は、何の問題もないレプリケーション プロセスです。このプロセスでは、ノードのダウンタイムなどの問題が避けられません。この場合、Raft はどのように対処するのでしょうか。

ログの一貫性を確保するにはどうすればよいですか?

前述のように、通常の状況では、リーダーのログ追加 RPC 要求応答が成功すると、リーダー ログとフォロワー ログは一貫性を保ちます。ただし、リーダーが突然クラッシュした場合、リーダーとフォロワーのログに矛盾が生じる可能性があり、その後の一連のリーダーのクラッシュによって状況が悪化します。

注: 例は Raft 論文から引用したものです。

上記のように、リーダーが選出されると、フォロワーは次のようになります。

1. ab は、フォロワーのログ エントリが現在のリーダーより遅れていることを意味します。
2. cd はフォロワーの一部のログエントリがコミットされていないことを意味します。
3. ef の状況は、上記の両方の状況が存在するため、もう少し複雑です。

上の図に示す状況がどのように発生するかを再現してみましょう。

最初は e がリーダーだったとします。ターム 2 では、f がリーダーに選出されます。いくつかのログ項目を書き込んだ後、append RPC 要求中にクラッシュします。再起動後、再びリーダーに選出されます (ターム番号 3)。いくつかのログ項目を書き込んだ後、再びクラッシュします。この時点で、e がリーダーに再選出されます (ターム番号 4)。いくつかのログ項目を正常にコピーします。同時に、そのうちのいくつかはほとんどのフォロワーに正常に追加されず、再びクラッシュします。同時に、フォロワー b はいくつかのログ項目をコピーした後にクラッシュします。ターム 5 で a がリーダーに選出され、ターム 6 で c がリーダーに選出されますが、すべてのローカル ログを他のフォロワーにコピーする前に再びクラッシュします。ターム 7 では、d がリーダーに選択されます。いくつかのログ項目を書き込んだ後、append RPC 要求中にクラッシュし、上の図に示す状況になります。

上記の状況において、Raft はログの一貫性の問題をどのように解決するのでしょうか?

Raft ログ メカニズムでは、ログの一貫性の動作を簡素化するために、次の 2 つの非常に重要な機能があります。

1. 異なるログ内の 2 つのエントリが同じインデックスと用語番号を持つ場合、それらには同じ命令が格納されます。
2. 異なるログ内の 2 つのエントリのインデックスと用語番号が同じである場合、それらの前のすべてのログ エントリも同一になります。

1 つ目の特徴は、Raft ログ項目はログ内で変化しないため、ログ項目が同じインデックス値と項番号を持つ限り、同じ命令データ情報を格納しているとみなせることです。

2 つ目の機能は、リーダーが強制的に上書きすることでフォロワーに自身のログをコピーさせることで、ログの不整合の問題を解決することです。リーダーは、RPC 要求の追加プロセス中に、コピーするログと以前のログ項目の関連情報を添付します。フォロワーが同じインデックス位置とターム番号のログ項目に一致できない場合、新しいログ エントリの受け入れを拒否します。次に、リーダーは、同じインデックスとターム番号のログ項目が見つかるまで、コピーするログ項目のインデックス値を減算し続け、最終的にフォロワーの後のログ項目を直接上書きします。 2 つのエントリのインデックスと用語番号が同じである場合、それらの以前のログ エントリもすべて同じであると想定できます。

したがって、Raft のログの追加は、おおまかに 2 つのステップに分けられます。

リーダーは、フォロワーが自身と共通する最大のログ項目を見つけます。つまり、フォロワーの以前のログはすべてリーダーのログと同じであるということです。

リーダーは、ログの一貫性を実現するために、一貫性のないログの上書きを強制します。

以下では、ログ複製プロセス中に Raft が強制ログ上書きを実行する方法を例を使って詳しく説明します。

リーダーとフォロワーが存在し、それらのログ エントリが次のように複製されると仮定します。

フォロワーは、ターム番号が 3 のときにリーダーであったことがわかります。ログ追加プロセス中にクラッシュしました。再起動後、フォロワーになりました。その後、新しいリーダーがログを追加しました。この時点で、ターム番号は 3 であり、最後のログエントリが上書きされます。

まず、Raft 追加エントリ RPC のリクエスト パラメータを見てみましょう。

リーダーがフォロワーを追加してカバーするプロセスは次のとおりです。

リーダーは、ログ追加 RPC 要求を通じて、フォロワーに追加する最新のログ項目と、前のログ項目 prevLogIndex=7、prevLogTerm=3 をフォロワーに送信します。

フォロワーは、現在の最新ログの用語番号が prevLogTerm と一致していないと判断し、追加を拒否します。

リーダーは、コピーする必要があるログ項目のインデックス値を減らし続けます。この時点で、prevLogIndex=6、prevLogTerm=3;

フォロワーは、LogIndex=6 および LogTerm=3 のログ エントリを見つけ、追加要求を受け入れます。

リーダーは、フォロワーのログ エントリの後に LogIndex=6 および LogTerm=3 でログ エントリを追加して上書きします。

この記事はWeChatの公開アカウント「Backend Advanced」から転載したもので、以下のQRコードからフォローできます。この記事を転載する場合は、Backend Advanced Public Account にお問い合わせください。