分散コンセンサスアルゴリズムの実装 - 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: リーダーノードは、日記の複製要求、ハートビート要求、日記の送信要求を他のフォロワーノードに送信します。

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

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

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

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

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

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

リーダー選出プロセス

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

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

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

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

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

パブリッククラスRequestVoteResp {
    プライベート長期;
    プライベートブール値 voteGranted;
 }

任期: 投票者の現在の任期番号。任期値を更新するよう選挙運動者に通知するために使用されます。
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 呼び出しを非同期的に開始して、ログが送信されたことを他のフォロワーノードに通知します。送信要求を受信した後、フォロワーノードは最初にログを送信された状態に変更し、次にログを状態マシンに適用します。

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

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

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

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

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

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

success: 受信者 (フォロワー) が 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 クラスターのリーダーノードを複数のマシンに均等に分散できます。例えば：

機械	`Raft`	`Raft`	`Raft`
マシン`1`	`Raft`サービス`A`ノード`1` （ `Leader` ）	`Raft`サービス`B`ノード`1` （ `Follower` ）	`Raft`サービス`C`ノード`1` （ `Follower` ）
マシン`2`	`Raft`サービス`A`ノード`2` （ `Follower` ）	`Raft`サービス`B`ノード`2` （ `Leader` ）	`Raft`サービス`C`ノード`2` ( `Follower` )
マシン`3`	`Raft`サービス`A`ノード`3` （ `Follower` ）	`Raft`サービス`B`ノード`3` （ `Follower` ）	`Raft`サービス`C`ノード`3` （ `Leader` ）