GIF で Distributed Raft を説明する

[[378468]]

1. いかだの概要

Raft アルゴリズムは、分散システム開発に適したコンセンサスアルゴリズムです。たとえば、Etcd や Consul が現在人気があります。

このアルゴリズムを習得すれば、ほとんどのシナリオのフォールトトレランスと一貫性の要件を簡単に処理できます。たとえば、分散構成システム、分散 NoSQL ストレージなどは、システムの単一マシンの制限を簡単に突破できます。

Raft アルゴリズムは、リーダーを基準として一連の値と各ノードのログの一貫性に関するコンセンサスを実現します。

2. いかだの役割

2.1 役割

フォロワー: リーダーからのメッセージを黙って受け取る一般人。リーダーのハートビートメッセージがタイムアウトすると、リーダーは率先して立ち上がり、自分自身を候補者として推薦します。

候補者: 候補者は他のノードに投票を通知するために、他のノードからの投票 RPC メッセージを要求します。過半数の票を獲得すれば、リーダーに昇格する。

リーダー：私は横暴な大統領です。すべては私次第です。書き込み要求を処理し、ログのレプリケーションを管理し、ハートビートメッセージを継続的に送信して、他のノードに「私はリーダーです。まだ生きています。私に代わる新しいリーダーを探すことなく、新しい選挙を開始しないでください」と通知します。

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

役割

3. シングルノードシステム

3.1 データベースサーバー

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

データベースサーバー

3.2 クライアント

左側の緑の実線円はクライアント、右側の青の実線円はノード a です。 Term は任期を表します。これについては後で説明します。

クライアント

3.3 クライアントがサーバーにデータを送信する

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

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

3.4 複数のノード間の一貫性を確保するにはどうすればよいですか?

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

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

IV.リーダーを選出するプロセス

4.1 初期状態

最初は、クラスター内のすべてのノードがフォロワー状態にあります。

下の図に示すように、3 つのノード a、b、c があり、それらの項はすべて 0 です。

初期状態

4.2 候補者になる

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

タイムアウト

ノード A のタイムアウト期間に達すると、ノード A は候補となり、その用語番号を増やし、用語値が 0 から 1 に更新され、自身に投票します。

ノード A: 用語 = 1、投票数 = 1。
ノード B: 項 = 0。
ノード C: 項 = 0。

候補者になる

4.3 投票

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

リーダー選挙

ステップ 1: ノード A が候補になると、他のノードに投票 RPC メッセージを送信し、自身をリーダーとして選出するよう依頼します。
ステップ 2: ノード A から送信された投票要求情報を受信した後、ノード B とノード C はノード A に投票し、番号 1 の期間にまだ投票していない場合は自身の期間番号を増やします。
ステップ 3: ノード A は 3 票を獲得し、大多数のノードから投票を獲得し、候補者からこの任期の新しいリーダーになります。
ステップ 4: リーダーであるノード A は、一定の時間間隔でノード B と C にハートビートメッセージを送信し、自分がリーダーであることをノード B と C に伝え、他のフォロワーを組織して新しい選出を開始します。
ステップ 5: ノード B とノード C はノード A に応答情報を送信し、正常であることをノード A に伝えます。

4.4 任期

英語では「term」であり、リーダーには任期があります。

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

4.5 選挙ルール

任期中、リーダーは、リーダー自身に問題 (ダウンタイムなど) またはネットワークの問題 (遅延) が発生し、他のノードが新しい選挙ラウンドを開始するまで、常にリーダーのままです。

選挙では、各サーバーノードは任期番号に対して最大 1 票を投じますが、一度投じられると無効になります。

4.6 最も

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

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

候補者になる

5. リーダーの失敗

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

リーダーの失敗

ステップ 1: ノード A に障害が発生し、ノード B とノード C はリーダーノード A からハートビート情報を受信せず、待機タイムアウトが発生します。
ステップ 2: ノード C が最初にタイムアウトし、その後候補になります。
ステップ 3: ノード C は、投票情報についてノード A とノード B に要求を送信します。
ステップ 4: ノード C は投票に応答し、C に投票しますが、ノード A は失敗し、C の投票要求に応答できません。
ステップ 5: ノード C は 2 票 (過半数) を獲得し、リーダーになります。
ステップ 6: ノード C はハートビート情報をノード A と B に送信します。ノード A はハートビート情報に応答しますが、ノード B はハートビート情報に応答しません。

要約する

Raft アルゴリズムは、次の方法でリーダーを選出し、1 期につきリーダーが 1 人だけになるようにすることで、選出の失敗数を大幅に削減します。