分散コンセンサスアルゴリズムの実装 - Raft アルゴリズム

[[385285]]

著者は、Raftアルゴリズムフレームワークraft-coreの独自のJavaバージョンをオープンソース化しました。

プロジェクトリンク: https://github.com/wujiuye/delay-scheduler/tree/main/raft/raft-core

このプロジェクト コードは、delay-scheduler (分散遅延スケジューリング ミドルウェア) のサブモジュールです。レベルが限られているので、学習して使用することだけをお勧めします。

CAP原則について

C (一貫性)、A (可用性)、P (パーティション耐性) の原則は、分散システムでは避けて通れないトピックです。どの分散システムでも、可用性、一貫性、およびパーティション耐性は互いに矛盾しています。 3 つすべてを同時に持つことはできず、最大で 2 つしか持つことができません。

AP: システムに高可用性 (A) とパーティション耐性 (P) が求められる場合、一貫性 (C) は放棄する必要があります。

CP: 強力なデータ一貫性 (C) が必要な場合、ネットワーク パーティションによって同期時間が無限に延長されるため (P)、可用性を保証できず、可用性を放棄する必要があります (A)。

CA: ネットワーク パーティション (パーティションは異なるデータ センター/国/地域を指します) (P) がない場合、強力な一貫性 (C) と可用性 (A) を同時に満たすことができます。

Raftコンセンサスアルゴリズムの紹介

Raft クラスターでは、各ノードはリーダーまたはフォロワーのいずれかの役割に対応します。リーダーが選出される前は、各ノードが候補者になることができます。

Raft アルゴリズムでは、Raft クラスターにはリーダー ノードが 1 つだけ存在でき、リーダー ノードのみがクライアントの読み取りおよび書き込み要求を処理し、書き込み要求を操作ログに変換し、リーダー ノードが操作ログを他のフォロワー ノードにコピーできることが規定されています。リーダー ノードが操作ログを大多数のノード (自分自身を含む) に正常に同期すると、操作ログをステート マシンに適用でき、ステート マシンは書き込み操作 (コマンドの実行) を実行して、データの最終的な一貫性を確保します。

Binlog は、MySQL データベースによって実行される書き込み操作コマンドと考えることができます。また、MyISAM ストレージ エンジンは、コマンドを実行するために使用される Binlog のステート マシンです。

Raft アルゴリズムを実装するには、次の 2 つの RPC インターフェースを実装する必要があります。

• RequestVoteRpc: 選挙中、現在の候補ノードは他のノードからの投票要求を開始します。
• AppendEmtriesRpc: リーダー ノードは、日記の複製要求、ハートビート要求、日記の送信要求を他のフォロワー ノードに送信します。

定期的なハートビートタイマー

リーダー ノードは、他のフォロワー ノードの選択タイムアウトを更新するために、他のフォロワー ノードに定期的にハートビート パケットを送信する必要があります。

ハートビート タイマーは、ノードがリーダーになると開始され、ノードがフォロワーになると停止します。ハートビート タイムアウト間隔は、選出タイムアウト間隔よりも長くする必要があります。つまり、ハートビート タイムアウト (ハートビート パケットのブロードキャスト時間) < 選出タイムアウト (選出タイムアウト) です。

タイムアウト選挙タイマー

タイミングがタイムアウト (Election Timeout) しきい値に達すると、リーダー選出がトリガーされます。現在のノードは、その任期番号を 1 増やし、自分自身に投票しようとします (まだ他の候補者に投票していない場合)。自分自身に投票することに成功した場合、そのノードは候補者となり、他のノードに対して投票要求を開始します。

タイムアウト選択タイマーの現在のカウントは、AppendEntriesRPC (ハートビート要求を含む) 要求を受信するとリセットされ、再開されます。複数の選挙ラウンドの後にリーダーを選出できない状況が発生する可能性がある同時選挙要求を回避するために、各ノードのタイムアウトしきい値が異なる必要があります。

リーダー選出プロセス

リーダーは投票メカニズムを通じて選出されます。各ノードは、各用語番号に対して 1 票のみを持つことができます。各ノードは、自分自身への投票を優先します。過半数の票を獲得したノードがリーダーノードになります。したがって、Raft クラスターには少なくとも 3 つのノードが必要であり、Raft クラスター内のノードの合計数は奇数であることが望ましいです。

RequestVoteRpc 要求データ パケット (投票集計データ パケット):

パブリッククラスRequestVote {
    プライベート長期;
    プライベートint候補ID;
    プライベート長いlastLogIndex;
    プライベート長いlastLogTerm;
 }

• 任期: 選挙運動当事者（候補者ノード）の現在の任期番号。
• candidateId: 選挙運動を行う政党のノード ID。
• lastLogIndex: 調査員の最新のログエントリのインデックス値。
• lastLogTerm: 選挙運動員の最新の日記エントリに対応する学期番号。

RequestVoteRpc 応答データ パケット (投票データ パケット):

パブリッククラスRequestVoteResp {
    プライベート長期;
    プライベートブール投票許可;
 }

• 任期: 投票者の現在の任期番号。任期値を更新するよう選挙運動者に通知するために使用されます。
• voteGranted: 投票政党が選挙運動政党に投票した場合、voteGranted は true になります。それ以外の場合は false になります。

選挙タイマーがタイムアウトしたときに選挙運動要求を開始するプロセスは次のとおりです。

1) ローカルに保持されている現在の用語番号 (term) を 1 増やします。

2) 自分自身に投票する。投票が成功した場合は、ステータスを候補ノード（候補者）に切り替えます。したがって、各候補ノードの最初の投票は、そのノード自身から行われます。

3) クラスター内の他のノードに RequestVoteRPC リクエスト (投票リクエスト) を送信し、自分自身に投票するよう依頼します。

各ノードが他の候補ノードから投票要請要求を受信すると、ノードの現在の任期番号、ログ同期ステータス、および他のノード (自分自身を含む) に現在の任期の投票をすでに投じているかどうかに基づいて、次のように応答する必要があります。

1) 選挙運動員の任期が現在の任期よりも短い場合は、false を返して選挙運動員に任期が期限切れであることを思い出させ、選挙運動員にこの投票は行われないことを明確に伝えます。

2) 選挙運動員の任期が現在の任期よりも長く、かつ選挙運動員がこれまで誰にも投票したことがない場合（自分自身を含む）、選挙運動員はノードに投票し、選挙運動員の任期と true を返します。

3) それ以外の場合、選挙運動員の任期が現在の任期と同じで、選挙運動員に投票が行われており (繰り返し要求のシナリオ)、要求者の日記が自身の日記と同じくらい新しい場合は、選挙運動員の任期と true を返します。

4) そうでない場合、以前に投票が他の人に投じられたことがある場合、この投票は請求当事者に投じられず、請求当事者にはこの投票は投じられないことが明確に伝えられます。

候補者ノードが選挙運動要求をブロードキャストした後、最終投票結果に基づいて次のように応答する必要があります。

1) 大多数のノードが異常に接続している場合は、現在の期間に引き続き調査を再開します。つまり、大多数のノードがダウンしており、選挙が異常です。

2) 自分自身への 1 票を含め、ほとんどのノードの投票を獲得してリーダーになる。ただし、各ノードには 1 票しかありません。自分自身に投票した場合、他のノードに投票することはできません。

3) 他のノードが選挙に勝ったことが判明した場合（選挙要求応答の期間が現在の候補ノードの期間よりも長い場合、他のノードが選挙に勝ったとみなされます）、積極的にフォロワーに戻ります。

4) タイムアウト選出タイマーが再度タイムアウト選出をトリガーした場合、リーダーのハートビート パケットが受信されておらず、前回の選出でリーダーになるための選出に勝利したノードがなかったことを意味し、引き続き選出を開始します。

別のノードが現在の期間のリーダーになった場合、リーダーはハートビート パケットを送信して自身に通知します。リーダーにハートビート パケットを自分自身に送信するのに十分な時間を与える必要があります。したがって、選出タイムアウトはハートビート タイムアウトよりも大きくする必要があります。つまり、ハートビート タイムアウト (ハートビート パケットのブロードキャスト時間) < 選出タイムアウト (選出タイムアウト) です。

選出後、各フォロワー ノードは現在のリーダー ノードがどれであるかを記録し、リーダー ノードは他のすべてのフォロワー ノードを記録する必要があります。リーダー ノードは、ハートビート パケットと日記同期要求を他のフォロワー ノードに送信する必要があり、他のフォロワー ノードは、クライアント要求を受信したときに、要求をリーダー ノードにリダイレクトするようにクライアントに通知する必要があります。

Raftログ複製プロセス

Raft クラスターでは、リーダー ノードがクライアントからの読み取りおよび書き込み要求を受信する役割を担います。フォロワーがリクエストを受信した場合、そのリクエストをリーダー ノードにリダイレクトする必要があります。

リーダーノードが読み取り要求を受信すると、リーダーノードはデータを直接照会し、クライアントに応答できます。リーダーノードが書き込み要求を受信すると、リーダーノードはまず書き込み要求を操作ログに変換し、その操作ログをローカルノードに追加します。同時に、他のノードへの AppendEntriesRPC 呼び出しを開始し、操作ログを他のノードにコピーします。ほとんどのノードのコピーが正常に完了すると、リーダー ノードは操作ログを送信します。送信が成功した場合、それはステート マシンに適用され、他のノードへの AppendEntriesRPC 呼び出しを非同期的に開始して、ログが送信されたことを他の Follower ノードに通知します。送信要求を受信すると、フォロワー ノードはまずログを送信済み状態に変更し、次にログをステート マシンに適用します。

AppendEntriesRPC 要求データ パケット (リーダー ノードは他のフォロワー ノードに対して RPC 要求を開始し、他のフォロワー ノードにこの日記エントリをコピーするよう要求します):

パブリッククラスAppendEntriesはCloneableを実装します{
    プライベート長期;
    プライベートintリーダー ID;
    プライベート長いprevLogIndex;
    プライベート長いprevLogTerm;
    プライベートな長いリーダーコミット;
    プライベートCommandLog[]エントリ;
 }

• term: リーダーノードが日記エントリを作成した時点のターム番号。
• leadersId: リーダー ノードの ID。これにより、他のフォロワー ノードはクライアント要求をリーダー ノードにリダイレクトできます。
• prevLogIndex: リーダーノードによって送信されたログ内の最新のログエントリのインデックス。
• prevLogTerm: リーダーノードによって送信されたログ内の最新のログエントリの用語番号。
• leaderCommit: リーダー ノードは、フォロワーごとに leaderCommit を維持します。これは、リーダー ノードがフォロワーが送信したと信じている日記エントリのインデックス値を示します。
• エントリ: フォロワーに追加される日記エントリ。ハートビート パケットの場合、エントリは空になります。

AppendEntriesRPC 応答パケット (AppendEntries RPC 応答):

パブリッククラスAppendEntriesResp {
    プライベート長期;
    プライベートブール値の成功;
 }

term: 現在の用語番号、これは Max です (AppendEntries リクエストで運ばれる用語と Follower によってローカルに維持される用語)。リーダー ノードが自身のターム番号を更新するために使用されます。リーダー ノードは、ターム番号が自身の番号より大きいことを検出すると、古いリーダーであることを示すため、ハートビート パケットの送信を停止し、フォロワーに積極的に切り替える必要があります。

success: 受信者 (Follower) が prevLogIndex と prevLogTerm を一致できるかどうか。一致する場合、リクエストは成功します。

リーダー ノードがクライアントの書き込み要求を処理し、書き込み要求ログをフォロワーにコピーするプロセス:

0) クライアントはリーダーに書き込み要求を送信します。

1) リーダーは書き込み要求を操作指示ログに解析し、それをローカル ログ ファイルに追加します。

2) リーダーは他のフォロワーノードに AppendEntriesRPC リクエストを非同期的に送信します。

3) ブロックして、大多数のノードが正常に応答するのを待ちます。ノードの大多数は、少なくともノードの総数を 2 で割った数に 1 を加えた数です。リーダー ノード自体も 1 としてカウントされるため、正常に応答するには、ノードの総数を 2 で割った数だけが必要です。

4) 大多数のノードが正常に応答した場合: リーダーはログエントリを送信してローカルステートマシンに適用し、ログが送信されたことを他のフォロワーノードに非同期的に通知し、操作結果をすぐにクライアントに返します。

5) それ以外の場合: クライアントに失敗を応答します。

フォロワー ノードはログ複製要求プロセスを処理します。

0) 任意の AppendEntriesRPC 要求 (ハートビート パケット要求、日記送信要求、日記追加要求を含む) を受信すると、選出タイムアウト タイマーの現在の時刻がリセットされます。

1) 自身の任期がリクエストパラメータの任期より長く、ローカルに記録されたリーダーの任期番号が自身の任期より小さい場合、自身の任期が返され、成功は false になります (要求者に期限切れのリーダーであることを通知します)。

2) それ以外の場合、prevLogIndex ログ内の Follower 自体のターム番号がリクエストパラメータ prevLogTerm と一致しない場合は、自身のタームが返され、成功は false になります (現在の Follower ノードのログが遅れています)。

3) そうでない場合、現在ハートビート パケットが 1 つしかない場合は、リーダーのハートビートが受信されたことを意味し、すでにフォロワーであることを意味します。必要に応じて、候補ノードからフォロワーノードに切り替え、独自の用語を返し、成功は true になります。

4) それ以外の場合、Follower は日記の一貫性チェックを実行し、既存の不一致な日記を削除し、既存の日記に存在しないエントリを追加し、冗長なエントリを削除し、すでにコミットされたエントリをコピーする場合は、コピーが成功したら直接コミットします。

5) リクエストパラメータの LeaderCommit が現在の commitIndex より大きい場合、commitIndex は Max(leaderCommit, commitIndex) に更新され、ローカルコミットされたダイアリーの commitIndex は、フォロワーが追跡するためにリーダーが記憶している値に楽観的に進められます。これは、フォロワーが障害から回復したばかりのシナリオで使用されます。

フォロワー ノードがリーダー ノードに、ログ追加が失敗し、フォロワー ノードの現在の期間番号がリーダーの現在の期間番号以下であると応答した場合、リーダー ノードはパラメーター prevLogIndex の減少を要求し、AppendEntriesRPC が成功を返すまで AppendEntriesRPC 要求を再開します。成功は、リーダーとフォロワーが prevLogIndex 位置のログ エントリで一貫していることを示します。このとき、フォロワー ノードの prevLogIndex 位置より前のすべてのログ エントリは保持され、prevLogIndex 位置より後のすべてのログ エントリ (リーダーと競合する) はフォロワーによって削除され、リーダーの prevLogIndex 位置より後のすべてのログ エントリはその位置から追加されます。したがって、AppendEntriesRPC が正常に返されると、リーダーとフォロワーのログの一貫性が保たれます。

一貫性

候補ノードがリーダーになるには、ノードの過半数によって投票される必要があり、ノードは独自のログを持たない新しい候補ノードには投票しません。さらに、リーダーは、ログを大多数のノード（リーダー自身を含む）に正常に同期した後にのみ、ログを送信します（ログを送信された状態に変更し、それをステート マシンに適用します）。したがって、毎回選出されるリーダーは、送信されたすべてのログを含むノードになります。

新しいリーダー ノードが新しい日記をフォロワー ノードに同期するときに、フォロワー ノードの日記が大幅に遅れている場合、フォロワー ノードはリーダーにない日記を積極的に削除し、リーダー ノードの日記をフォロワーに同期します。リーダー ノードが送信済みとしてマークした日記については、フォロワーはそれを受信したときにそれをステート マシンに直接適用して、データの最終的な一貫性を維持できます。

マルチラフト

3 台のマシンがあり、各マシンが Raft ノード サービスをデプロイしているとします。読み取りおよび書き込み要求はリーダー ノードによって処理されるため、動作できるのは 1 台のマシンだけでしょうか?

ノード サービスに対して複数の Raft サービス (複数のプロセスではないことに注意してください) を開始して、複数の Raft クラスター (つまり、Multi Raft) を構築できます。このようにして、各 Raft クラスターのリーダー ノードを複数のマシンに均等に分散できます。例えば：

分散データベース TiDB では、Multi Raft を使用してデータを分割し、各 Raft クラスターがデータの一部を担当するようにします。

参考文献

Huawei クラウド コンテナ サービス チーム。 「クラウドネイティブ分散ストレージの基礎: etcd の詳細な分析」(クラウド コンピューティング テクノロジー シリーズ)

ラフト紙の住所

Raft 論文の中国語版: https://github.com/maemual/raft-zh_cn

画像ソース

画像ソース: https://github.com/maemual/raft-zh_cn/tree/master/images

この記事はWeChatの公開アカウント「Java Art」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合はJava Art公式アカウントまでご連絡ください。