グラフィカル分散コンセンサスアルゴリズム

本日の記事では、グラフを使用して分散一貫性の実装原則を深く研究し、理解します。

まず、自己を見つめ直す質問をしてみましょう。分散一貫性とは何でしょうか?

アプリケーションは単一ノードですか?
あなたのシステムには多くのユーザーがいますか? 拡張をサポートしていますか?
システム拡張後もデータの一貫性は維持できますか?
あなたのシステムは Raft または Paxos を使用していますか?
…

理解しているかどうかは問題ではありません。後で例を示し、図を使って一貫性がどのように機能するかを説明しましょう。

[[278855]]

1. 序曲

あるシステムがあるとします。これは単一ノードシステムであり、1 つのインスタンスにのみデプロイされます。これはデータベースサービス (データベースサーバー) として理解できます。インスタンスにはデータ X が 1 つだけ存在し、以降のストーリーはすべて X の値を変更する操作を中心に展開されます。

[[278856]]

また、クライアント（Client）があり、ノード（Server）にデータを書き込む必要があります。このとき、アプリケーションコードも簡単に記述でき、データの一貫性を簡単に確保できます。

書き込み要求が実行されると、クライアントとサーバーの両方の X データは 8 になります。

ユーザー数が少なかった頃は、ユーザーが数百万人、数千万人になったときにどうなるか心配していました。ユーザー数が少し増えると、元のインスタンスではワークロードを処理できないことがわかりました。今回、より多くのユーザーアクセスをサポートするために、インスタンスをさらに拡張しました。

ここで問題となるのは、複数のインスタンスノードがある場合、クライアントがいずれかのノードにデータを書き込むと、それを他のノードとどのように同期するかということです。ノード間のデータの一貫性を確保するにはどうすればよいでしょうか。これが分散一貫性の問題です。

2. Raftプロトコルの概要

Raft は、前述の分散一貫性問題を解決するプロトコルです。同様のプロトコルには、Paxos、Zab などがあります。 Paxos と比較すると、Raft は理解しやすく実装も簡単です。

今回は、Raft の仕組みを理解するために、Raft を俯瞰してみます。

Raft では、ノードは次の 3 つの状態で存在します。

フォロワー
候補者
リーダー

以下の図では、上記の 3 つの状態がそれぞれ次の 3 つの図に対応しています。

いつでも、上記の 3 つの状態のいずれかになります。最初は、すべてのノードがフォロワー状態にあります。

フォロワーノードがリーダーノードからのメッセージを受信できなくなった場合、そのステータスは「候補」に変わります。

候補者ノードは他のノードへの投票リクエストを開始します。

他のノードも応答に投票します。

候補ノードが大多数のノードから投票を獲得した場合、そのノードがリーダーになります。

上記のプロセスは、分散コンセンサスプロトコルにおける「選挙」（リーダー選挙）です。

システムに対するその後のすべての変更はリーダーを通じて行われます。次に、リーダーを通じて他のノードに到達します。

クライアントからの変更要求がリーダーに到達するたびに、それはエントリと見なされ、最初にノードのログに追加されます。この新しく追加されたログエントリはまだ送信されていないため、ノード内の X の値は実際には更新されません。

リーダーはまず、ログエントリをすべてのフォロワーノードにコピーします。

リーダーは、ほとんどのノードがエントリを書き込むまで待機します。

リーダーノードは大多数のノードから書き込み応答を受信するとエントリをコミットし、リーダーノードの値は 5 になります。

次に、リーダーはフォロワーノードにエントリが送信されたことを通知します。

このとき、各フォロワーノードも、以前に受信したエントリを送信します。

システム全体のすべてのクラスターノードが一貫した状態に達しました。このプロセスは一般にログレプリケーションと呼ばれます。

3. リーダー選挙

Raft には、選出を制御するタイムアウト設定があります。選挙タイムアウトは、フォロワーが候補者になるまでの待機時間です。値は 150 ミリ秒から 300 ミリ秒の間のランダムな値です。

選挙がタイムアウトすると、フォロワーは候補者となり、新しい選挙サイクル (任期) を開始し、自分自身に投票します。

そして、他のノードに投票を要求するメッセージを送信します。

メッセージを受信したノードがこのサイクルで投票していない場合、そのノードは候補者に投票する必要があり、そのノードは選挙タイムアウトをリセットします。

候補者がノードの過半数から投票を獲得した場合、その候補者がリーダーになります。

リーダーは、ハートビート検出サイクル中にすべてのフォロワーにエントリ追加メッセージを送信するようになりました。検出頻度はハートビートタイムアウトによって設定されます。

その後、各フォロワーもエントリ追加メッセージに応答を送信します。

この選挙サイクルは、フォロワーがハートビートメッセージの受信を停止して候補者になるまで継続されます。

リーダーを止めて再選の状況を見てみましょう。

この時点でノード B は停止しているため、ノード A とノード C はハートビートメッセージを受信できません。先ほど、ハートビートメッセージが受信されない場合、ノードのステータスがフォロワーから候補に変更されるので、A と C はそれぞれの選出タイムアウト設定内でステータスが変更されると述べました。

この時点で、ノード A と C は両方とも待機中です。ノード C が最初にタイムアウトするため、最初に選挙ラウンドが開始されます。上記の選挙プロセスと同様に、最初に新しい用語を追加し、自分自身に投票し、次に他のノードに投票リクエストを送信します。

ノード A からの投票を受け取った後、ノード C がターム 2 のリーダーに昇格します。

私たちはこれまで常に「過半数の投票」について話してきました。これにより、投票サイクル内でリーダーが 1 人だけ生成されるようになります。

2 つのノードが同時にフォロワー状態から候補状態に変わると仮定します。このとき、両方のノードは自分の Term をアップグレードし、他のノードに自分に投票しないように要求します。

この時点で、2 つの任期は実際には同じです。同じ任期では、他のノードは 1 票しか投じないため、各候補者は 1 つのノードからのみ投票を受け取ります。

彼らは「多数派」以上のものを持っていないので、リーダーになることはできません。これらのノードは、新しい選挙ラウンドを待ちます。この時点で、ノード D が最初に投票を開始し、過半数の票を獲得し、最終的に第 5 期のリーダーになります。

4. ログのレプリケーション

リーダーが選出された後、すべての変更をシステム内のすべてのノードに複製する必要があります。これは、ハートビート検出と同じエントリ追加メッセージを介して実行されます。

このプロセスを見てみましょう。最初に、クライアントはリーダーにミューテーションを送信します。

この変更はリーダーのログに追加され、次のハートビートチェック中にフォロワーに送信されます。

メッセージを受信した後、フォロワーはリーダーに応答 ack メッセージを送信します。

ほとんどのフォロワーから応答を受け取った後、リーダーはエントリをコミットし、クライアントに応答を送信します。