コンセンサスアルゴリズムについて学ぶ - 8分でRaftアルゴリズム

写真

分散一貫性

分散環境における一貫性とは、データが複数のコピーにわたって一貫性を維持できるかどうかを指します。

分散コンセンサスアルゴリズム

一般的なコンセンサスアルゴリズムには、Paxos アルゴリズム、Raft アルゴリズム、ZAB アルゴリズムなどがあります。

• Paxos は、Leslie Lamport が提案したメッセージパッシングに基づく分散コンセンサスアルゴリズムです。多くの分散一貫性アルゴリズムは Paxos から進化しましたが、その最大の特徴は理解と実装が難しいことです。
• Raft は比較的新しい分散コンセンサスアルゴリズムであり、理解しやすく実装も簡単です。リーダー選出やその他の方法による紛争解決において、非常に単純で明確な解決策を選択します。
• ZAB プロトコルの正式名称: Zookeeper Atomic Broadcast (Zookeeper Atomic Broadcast Protocol) は、Zookeeper 用に設計された分散一貫性プロトコルです。

写真

Raft アルゴリズムの使用シナリオ

一般的に、次の 2 つのシナリオで使用されます。
メタデータ管理: 例えば、etcd はデータサイズが小さいのが特徴で、主にデータの一貫性とクラスターの高可用性 (ラフトリーダーの選択) を確保するため、ラフトクラスターで十分です。
分散データベース: このタイプはパーティショングループを使用し、各グループにはラフトクラスターがあり、データが大きくなると拡張されます。

🚩 Raft はデータの一貫性を確保するためのコンセンサスアルゴリズムであり、データベース、クライアント、トランザクションとは一切関係ありません。

ラフトアルゴリズムの基礎

Raft はアルゴリズムのプロセスを、リーダー選出、ログ複製、安全性の 3 つのサブ問題に分割します。

役割

• リーダー: クライアントのリクエストを受信して処理し、フォロワーとログを同期します。一度に実行可能なリーダーは 1 人だけです。
• フォロワー: リーダーによって同期されたログを受け入れて保存します。リーダーがログを送信できることを伝えると、ログが送信され、完全にパッシブな状態になります。
• 候補者: リーダーとフォロワーの間の一時的な役割

写真

Raft アルゴリズムでは、一度に最大 1 人のリーダーが存在し、通常の操作中にはリーダーとフォロワーのみ存在します。

状態遷移

写真

状態切り替えプロセス:

1. Raft を初めて起動すると、すべてのノードは最初は Follower 状態になります。
2. タイムアウト期間内にリーダーからのリクエストが受信されない場合、役割は候補者の役割に変更され、リーダーの選出が開始されます。
3. 候補者がノードの過半数から投票を獲得した場合、リーダーに転換されます。
4. 選挙中にすでにリーダーが見つかった場合、またはより高い任期の要求があった場合は、フォロワーに変換されます。
5. リーダーは、より高い条件のリクエストを受け取った後、フォロワーに変わります。

任期

任期: ノードがリーダーとして機能する期限として理解できます。

Raft は時間を用語に分割します。各用語は単調に増加する番号 (用語番号) によって識別されます。労働期間は長くても短くても、あるいはまったくない場合もあります。

🚩 任期時間 = 選挙時間 + 稼働時間

写真

コミュニケーション

Raftのサーバーノード間の通信は、次の 2 つの RPC 呼び出しを通じて行われます。

• RequestVote: 選挙中に候補者が開始する
• ログレプリケーションAppendEntries: リーダーによって開始され、ログを複製してハートビートを送信するために使用されます。

写真

リーダー選挙

初期状態

初期状態では、各ノードの役割はフォロワーであり、ターム番号は1です（ターム番号は1から始まると仮定）

写真

ただし、選挙をトリガーする状況が 2 つあります。

• Raft が最初に起動されたときは、リーダーが存在しないため、リーダーの選出がトリガーされます。
• フォロワーが自身のタイムアウト期間内にリーダーのハートビートを受信せず、選出タイムアウトがトリガーされ、フォロワーの役割が候補者に切り替わり、選出が開始されます。

選挙

選挙は 2 つの状況でトリガーされます。1 つは初期起動時、もう 1 つはリーダーがフォロワーにハートビートを送信できないときです。5 つのノードがあると仮定し、図を使用して選挙がどのように実行されるかを見てみましょう。

🚩図面のスペースをあまり取らないように、一時的に3つのノードで表し、残りのノードは「...」で表します。

初回起動時:

ノードを初めて起動する場合の通常のプロセスは次のとおりです。

写真

リーダーが失敗した場合:

この時点ではノード 2 がリーダーノードですが、失敗したため、選挙に参加するノードは 4 つになります。

写真

選挙条件

任期中は 1 つのノードにのみ投票でき、過半数の票を獲得したノードのみがリーダーになることができるため、任期中に生成されるリーダーは 1 人だけになります。

ログ同期

一言でまとめると、リーダーのログがまったく同じ方法で複数のフォロワーサーバーにコピーできることを確認します。

わかりました！同期する方法を見てみましょう

ログ構造

Raft アルゴリズムでは、各ノードはシステム内のすべての状態変化の記録を含むログを保持します。それぞれの状態の変化はログエントリと呼ばれます。

まず、ログ構造と右側の説明を見てみましょう。

写真

グラフ内の各ノードにはログ (log) の独自のコピーが保存され、各ログレコードには次の内容が含まれます。

• インデックス（ログインデックス）：ログ内のレコードの位置。連続して単調に増加する整数。

• 任期: ログレコードが作成された時点のリーダーの任期。上の図には 3 つの項があります。

• コマンド: クライアント要求によって指定され、ステートマシンが実行する必要がある命令

実行プロセス

ログ構造を理解した後、ログ同期がどのように開始されるかを見てみましょう。

永続的なログ保存の条件

フォロワーノードは、リーダーノードに書き込み成功応答を返す前に、まずレコードをディスクに安全に書き込む必要があります。

ログレコードが半数以上のノードに保存されている場合、そのレコードはコミットされたとみなされます。これは Raft の非常に重要な機能です。レコードがコミットされると、ステートマシンがレコードを安全に実行できることを意味します。

プロセスは次のとおりです。

写真

1. クライアントは、コマンドがすべての状態マシンによって実行されることを期待して、リーダーにコマンドを送信します。
2. リーダーはまずコマンドを自身のログに追加します。
3. リーダーは他のノードに AppendEntries RPC を並行して送信し、応答を待ちます。
4. 半数以上のノードから応答が受信されると、新しいログレコードが送信されたとみなされます。
5. リーダーはコマンドを自身のステートマシンに渡し、クライアントに応答を返す
6. さらに、リーダーはレコードが送信されたことを知ると、後続のAppendEntries RPCでレコードを送信したフォロワーに通知します。
7. フォロワーは送信されたコマンドを自身のステートマシンに渡す
8. フォロワーがクラッシュ/タイムアウトした場合: リーダーは RPC を繰り返し送信しようとします。

🚩 注: リーダーはすべてのフォロワーが応答するのを待つ必要はなく、フォロワーの半数以上が正常に応答するだけで済みます (ログレコードが半数以上のノードに保存されていることを確認するため)。リーダーは待機する必要がないため、非常に遅いノードによってシステムが遅くなることがありません。

一貫性チェック

Raft は AppendEntries RPC メッセージを介してこれを検出します。

• 各 AppendEntries RPC には、新しいログレコードの前のレコードのインデックス (prevLogIndex) と用語 (prevTerm) が含まれます。
• メッセージを受信した後、フォロワーは自身のログインデックスと用語をチェックして、prevLogIndexとprevTermと一致するかどうかを確認します。
• 一致が成功した場合、レコードは受け入れられ、最新のログが追加されます。一致しない場合、メッセージは拒否されます。

写真