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

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

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

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

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

[[278855]]

1. 序曲

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

[[278856]]

また、ノード (サーバー) にデータを書き込む必要があるクライアント (クライアント) もあります。このとき、アプリケーションコードも簡単に記述でき、データの一貫性も確保しやすくなります。

書き込み要求が実行されると、クライアントとサーバーの両方の 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 つのノードが同時に Follower 状態から Candidate 状態に変化すると仮定します。この時点で、両方のノードは自分の Term をアップグレードし、他のノードに投票しないように要求します。

現時点では、両者の条件は実際には同じです。同じ期間に、他のノードは 1 票しか投じないので、各候補者は 1 つのノードからのみ投票を受け取ります。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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