分散システムが知っておくべきコンセンサスアルゴリズム: Raft-AI-php.cn

1. Raft の概要

Raft アルゴリズム は分散システム開発の最初の選択肢ですコンセンサスアルゴリズム 。たとえば、Etcd や Consul が今人気です。

このアルゴリズムをマスターすれば、フォールトトレランスとほとんどのシナリオの を簡単に処理できます。# 一貫性 要件。たとえば、分散構成システム、分散 NoSQL ストレージなどは、システムの単一マシンの制限を簡単に突破できます。 Raft アルゴリズムは、リーダーに基づいたすべての方法を通じて、各ノードの一連の値とログの一貫性についての合意を達成します。

#2. Raft の役割

2.1 役割

フォロワー：一般人

は、リーダーからのメッセージを静かに受け取り、リーダーの鼓動メッセージがタイムアウトすると、自ら率先して立ち上がり、自らを候補者として推薦します。

Candidate (Candidate): Candidate

は、他のノードからの投票 RPC メッセージを要求し、過半数の投票を獲得した場合に他のノードに投票するよう通知します。リーダーに昇進。

リーダー: 横暴な社長

、すべては私の支配下にあります。書き込みリクエストを処理し、ログのレプリケーションを管理し、ハートビート情報を継続的に送信して、他のノードに「私がリーダーであり、私はまだ生きているので、あなたは望んでいない」ことを通知します。置き換える新しいリーダーを見つけることなく、新しい選挙を開始します。自分。

下の図に示すように、フォロワー、候補者、リーダーを表すために 3 種類の数字が使用されます。 役割

3. 単一ノードシステム

3.1 データベースサーバー

次に想像してみましょう。単一ノードシステムがあり、このノードはデータベースサーバーとして機能し、X の値を保存します。

データベースサーバー

3.2 クライアント

左側の緑の実線の円はクライアント、右側の青の実線の円はノード a です。 (ノード a )。 Term は後述する任期を表します。

クライアント

分散システムが知っておくべきコンセンサスアルゴリズム: Raft 3.3 クライアントはサーバーにデータを送信します

クライアントはデータを単一のサーバーに送信します。ノードサーバー更新操作により、データベースに格納されている値が 8 に設定されます。スタンドアロン環境 (単一サーバーノード) では、クライアントがサーバーから取得する値も 8 です。一貫性を確保するのは非常に簡単です。

クライアントはサーバーにデータを送信します

分散システムが知っておくべきコンセンサスアルゴリズム: Raft 3.4 複数のノードはどのように一貫性を確保しますか?

しかし、複数のサーバーノードがある場合、整合性を確保するにはどうすればよいでしょうか?たとえば、a、b、c という 3 つのノードがあるとします。以下に示すように。これら 3 つのノードはデータベースクラスターを形成します。クライアントがこれら 3 つのノードで更新操作を実行する場合、3 つのノードに格納されている値が一貫していることを確認するにはどうすればよいでしょうか?これは分散一貫性の問題です。 Raft アルゴリズムは、この問題を解決するために登場しました。もちろん、これを保証できるプロトコルは他にもありますが、この記事では Raft アルゴリズムのみに焦点を当てます。

分散システムが知っておくべきコンセンサスアルゴリズム: Raft

マルチノードクラスターでは、ノード障害やパーティションエラーなどの異常な状況下で、Raft アルゴリズムはクラスター内に同時にリーダーが 1 つだけ存在することをどのように保証しますか? Raft アルゴリズムによるリーダー選出のプロセスを説明しましょう。

4. リーダー選出プロセス

4.1 初期状態

初期状態では、クラスター内のすべてのノードがフォロワーです。状態。

下図に示すように、3つのノード(Node) a、b、cがあり、項(Term)は0です。

分散システムが知っておくべきコンセンサスアルゴリズム: Raft

初期状態

4.2 候補者になる

Raft アルゴリズムは、毎回ランダムなタイムアウトの特性を実装しています。各ノードがリーダーノードからのハートビート情報を待つタイムアウト間隔はランダムです。たとえば、ノード A の待機タイムアウト間隔は 150 ミリ秒、ノード B の待機タイムアウト間隔は 200 ミリ秒、ノード C の待機タイムアウト間隔は 300 ミリ秒です。すると、aが先にタイムアウトになりますが、まずリーダーの心拍情報を待たずにタイムアウトしてしまいます。次の図に示すように、3 つのノードのタイムアウトタイマーが実行を開始します。

タイムアウト時間

ノード A のタイムアウト時間が経過すると、ノード A は候補となり、期間番号が増加し、期間値は 0 から 1 に更新されます。そして私自身に一票を投じました。

ノード A: 期間 = 1、投票数 = 1。
ノード B: 期間 = 0。
ノード C: 期間 = 0。

分散システムが知っておくべきコンセンサスアルゴリズム: Raft

候補者になる

4.3 投票

候補者がリーダーになれる方法を見てみましょうの。

分散システムが知っておくべきコンセンサスアルゴリズム: Raft

リーダー選挙

ステップ 1: ノード A が候補になったら、RPC 投票リクエストを他のノードに送信します。ノードはメッセージを送り、自分たちをリーダーに選出するよう依頼します。
ステップ 2: ノード B とノード C は、ノード A から送信された投票要求情報を受信した後、番号 1 の期間中は投票せずに投票します。投票はノード A に投じられ、その項数が増加します。
第 3 ステップ : ノード A は 3 票を獲得し、過半数のノードの票を獲得し、候補者から今期中の新しいリーダーになりました。
ステップ 4: ノード A はリーダーとして、ハートビート情報をノード B とノード C に一定の間隔で送信し、自分がリーダーであり、他のメンバーが従うように組織していることをノード B とノード C に伝えます。 . 新しい選挙を開始する。
ステップ 5: ノード B とノード C は応答情報をノード A に送信し、ノード A に私が正常であることを伝えます。

4.4 任期

英語ではタームと呼ばれ、リーダーには任期があります。

自動増加: フォロワーは、リーダーのハートビート情報を待ってタイムアウトになった後、自分自身を候補として推薦し、ターム番号を増やします。 A は 0 です。自分を候補者として推薦すると、任期番号は 1 に増加します。
より大きな値に更新: ノードは、その項番号が他のノードの項番号よりも小さいことを検出すると、より大きな値に更新します。たとえば、ノード A の期間は 1 で投票を要求します。投票メッセージにはノード A の期間番号が含まれており、その番号は 1 です。ノード B はメッセージを受信すると、その期間番号を 1 に更新します。
フォロワーに戻る: 候補者またはリーダーが自分の任期番号が他のノードよりも小さいことに気付いた場合、すぐにフォロワーのステータスに戻ります。このシナリオは、パーティションエラーの回復後に発生します。期間 3 のリーダーが期間 4 のハートビートメッセージを受信すると、リーダーはすぐにフォロワー状態に戻ります。
拒否メッセージ: ノードがより小さい用語番号値のリクエストを受信した場合、そのリクエストは直接拒否されます。たとえば、用語番号 6 のノード A は用語番号を受け取ります。ノード B が 5 つの RPC メッセージに投票するよう要求すると、ノード A はメッセージを拒否します。

4.5 選挙ルール

任期中、問題 (ダウンタイムなど) が発生するか、問題が発生するまで、リーダーは常にリーダーであり続けます。ネットワークの問題 (遅延) がある場合、他のノードが新しいラウンドの選挙を開始します。
選挙では、各サーバーノードは任期番号に対して最大 1 票を投じ、投票が完了すると投票はなくなります。

4.6 最多

クラスターが N 個のノードで構成されていると仮定すると、過半数は少なくとも N/2 1 です。たとえば、3 ノードのクラスターの場合、ほとんどは 2 ノードです。

4.7 ハートビートタイムアウト

複数のノードが同時に投票を開始するのを防ぐために、各ノードにはランダムな選出タイムアウトが割り当てられます。この間、ノードは候補になることができず、タイムアウトになるまで待つことしかできません。たとえば、上記の例では、ノード A が最初にタイムアウトし、最初に候補になります。この賢い設計により、ほとんどの場合、同時に選挙を開始するのではなく、1 つのサーバーノードだけが最初に選挙を開始するため、投票分割による選挙失敗の数が減少します。

分散システムが知っておくべきコンセンサスアルゴリズム: Raft

候補者になる

5. リーダーの失敗

リーダーノードが失敗すると、新しい選挙ラウンド。次の図に示すように、リーダーノード A に障害が発生した場合、ノード B とノード C がリーダーを再選出します。

分散システムが知っておくべきコンセンサスアルゴリズム: Raft

リーダーの障害

ステップ 1 : ノード A 障害、ノード B およびノード CリーダーノードAからハートビート情報を受信できず、待ち時間がタイムアウトしてしまいます。
2 番目のステップ : ノード C が最初にタイムアウトし、ノード C が候補になります。
ステップ 3: ノード C は、ノード A とノード B への投票情報の要求を開始します。
ステップ 4: ノード C は投票に応答し、C に投票しましたが、ノード A は障害のため C の投票リクエストに応答できませんでした。
ステップ 5: ノード C が 2 票 (過半数の票) を獲得し、リーダーになります。
ステップ 6: ノード C はノード A とノード B にハートビート情報を送信します。ノード B はハートビート情報に応答します。ノード A は障害があるため、ハートビート情報に応答しません。