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

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

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

• アプリケーションは単一ノードですか?
• あなたのシステムには多くのユーザーがいますか? 拡張をサポートしていますか?
• システム拡張後もデータの一貫性は維持できますか?
• あなたのシステムは 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 メッセージを送信します。

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

そして次のハートビートで、フォロワーに送信操作を実行するように通知されます。

書き込みが完了すると、フォロワーはリーダーに応答を送信します。

このとき、クライアントはリーダーにメッセージを送信し、X に 2 を加算する操作を実行するように要求します。リーダーはメッセージをログに追加した後、各フォロワーにハートビートを送信します。

それを受け取ったフォロワーは、引き続きレスポンスを返します。

リーダーは ack を受信した後、この実行のコミットを確認し、クライアントに応答を返します。そして次のハートビートで、書き込みが各フォロワーに送信されます。

この時点で、システム内の X は 7 になり、各ノードのデータは一貫したままになります。

5. 「多数派」とは何ですか?

これまでのシナリオの多くで「ほとんど」について言及しました。それで、多数派は何人ですか?

たとえば、ログを選択または複製する場合、大多数のフォロワーが応答メッセージを送信する必要があります。

ここでの大多数は、基本的に私たちの日常生活と同じ、つまり半分以上です。たとえば、合計 5 つのノードがあり、候補者がリーダーになりたい場合は、投票プロセス中に少なくとも 3 票を獲得する必要があります。

公式サイトには、ユーザーが交流する時間をカスタマイズできる動的な画像があります。興味のある友人は自分で確認することができます。

[この記事は51CTOコラムニスト「侯樹成」によるオリジナル記事です。転載する場合は著者のWeChat公開アカウント「Tomcat Things」から許可を得てください]

この著者の他の記事を読むにはここをクリックしてください