コンセンサスアルゴリズムについて学ぶ - 8分でRaftアルゴリズム

コンセンサスアルゴリズムについて学ぶ - 8分でRaftアルゴリズム

写真

分散一貫性

分散環境における一貫性とは、データが複数のコピーにわたって一貫性を維持できるかどうかを指します。

分散コンセンサスアルゴリズム

一般的なコンセンサス アルゴリズムには、Paxos アルゴリズム、Raft アルゴリズム、ZAB アルゴリズムなどがあります。

  • • Paxos は、Leslie Lamport が提案したメッセージ パッシングに基づく分散コンセンサス アルゴリズムです。多くの分散一貫性アルゴリズムは Paxos から進化しましたが、その最大の特徴は理解と実装が難しいことです。
  • • Raft は比較的新しい分散コンセンサス アルゴリズムであり、理解しやすく実装も簡単です。リーダー選出やその他の方法による紛争解決において、非常に単純で明確な解決策を選択します。
  • • ZAB プロトコルの正式名称: Zookeeper Atomic Broadcast (Zookeeper Atomic Broadcast Protocol) は、Zookeeper 用に設計された分散一貫性プロトコルです。

写真

Raft アルゴリズムの使用シナリオ

一般的に、次の 2 つのシナリオで使用されます。
メタデータ管理: 例えば、etcd はデータサイズが小さいのが特徴で、主にデータの一貫性とクラスターの高可用性 (ラフトリーダーの選択) を確保するため、ラフトクラスターで十分です。
分散データベース: このタイプはパーティション グループを使用し、各グループにはラフト クラスターがあり、データが大きくなると拡張されます。

🚩 Raft はデータの一貫性を確保するためのコンセンサス アルゴリズムであり、データベース、クライアント、トランザクションとは一切関係ありません。

ラフトアルゴリズムの基礎

Raft はアルゴリズムのプロセスを、リーダー選出、ログ複製、安全性の 3 つのサブ問題に分割します。

役割

  • • リーダー: クライアントのリクエストを受信して​​処理し、フォロワーとログを同期します。一度に実行可能なリーダーは 1 人だけです。
  • • フォロワー: リーダーによって同期されたログを受け入れて保存します。リーダーがログを送信できることを伝えると、ログが送信され、完全にパッシブな状態になります。
  • • 候補者: リーダーとフォロワーの間の一時的な役割

写真

Raft アルゴリズムでは、一度に最大 1 人のリーダーが存在し、通常の操作中にはリーダーとフォロワーのみ存在します。

状態遷移

写真

状態切り替えプロセス:

  1. 1. Raft を初めて起動すると、すべてのノードは最初は Follower 状態になります。
  2. 2. タイムアウト期間内にリーダーからのリクエストが受信されない場合、役割は候補者の役割に変更され、リーダーの選出が開始されます。
  3. 3. 候補者がノードの過半数から投票を獲得した場合、リーダーに転換されます。
  4. 4. 選挙中にすでにリーダーが見つかった場合、またはより高い任期の要求があった場合は、フォロワーに変換されます。
  5. 5. リーダーは、より高い条件のリクエストを受け取った後、フォロワーに変わります。

任期

任期: ノードがリーダーとして機能する期限として理解できます。

Raft は時間を用語に分割します。各用語は単調に増加する番号 (用語番号) によって識別されます。労働期間は長くても短くても、あるいはまったくない場合もあります。

🚩 任期時間 = 選挙時間 + 稼働時間

写真

コミュニケーション

Raftのサーバー ノード間の通信は、次の 2 つの RPC 呼び出しを通じて行われます。

  • • RequestVote: 選挙中に候補者が開始する
  • • ログレプリケーションAppendEntries: リーダーによって開始され、ログを複製してハートビートを送信するために使用されます。

写真

リーダー選挙

初期状態

初期状態では、各ノードの役割はフォロワーであり、ターム番号は1です(ターム番号は1から始まると仮定)

写真

ただし、選挙をトリガーする状況が 2 つあります。

  • • Raft が最初に起動されたときは、リーダーが存在しないため、リーダーの選出がトリガーされます。
  • • フォロワーが自身のタイムアウト期間内にリーダーのハートビートを受信せず、選出タイムアウトがトリガーされ、フォロワーの役割が候補者に切り替わり、選出が開始されます。

選挙

選挙は 2 つの状況でトリガーされます。1 つは初期起動時、もう 1 つはリーダーがフォロワーにハートビートを送信できないときです。5 つのノードがあると仮定し、図を使用して選挙がどのように実行されるかを見てみましょう。

🚩図面のスペースをあまり取らないように、一時的に3つのノードで表し、残りのノードは「...」で表します。

初回起動時:

ノードを初めて起動する場合の通常のプロセスは次のとおりです。

写真

リーダーが失敗した場合:

この時点ではノード 2 がリーダー ノードですが、失敗したため、選挙に参加するノードは 4 つになります。

写真

選挙条件

任期中は 1 つのノードにのみ投票でき、過半数の票を獲得したノードのみがリーダーになることができるため、任期中に生成されるリーダーは 1 人だけになります。

ログ同期

一言でまとめると、リーダーのログがまったく同じ方法で複数のフォロワー サーバーにコピーできることを確認します。

わかりました!同期する方法を見てみましょう

ログ構造

Raft アルゴリズムでは、各ノードはシステム内のすべての状態変化の記録を含むログを保持します。それぞれの状態の変化はログ エントリと呼ばれます。

まず、ログ構造と右側の説明を見てみましょう。

写真

グラフ内の各ノードにはログ (log) の独自のコピーが保存され、各ログ レコードには次の内容が含まれます。

• インデックス(ログインデックス):ログ内のレコードの位置。連続して単調に増加する整数。

• 任期: ログ レコードが作成された時点のリーダーの任期。上の図には 3 つの項があります。

• コマンド: クライアント要求によって指定され、ステートマシンが実行する必要がある命令

実行プロセス

ログ構造を理解した後、ログ同期がどのように開始されるかを見てみましょう。

永続的なログ保存の条件

フォロワー ノードは、リーダー ノードに書き込み成功応答を返す前に、まずレコードをディスクに安全に書き込む必要があります。

ログ レコードが半数以上のノードに保存されている場合、そのレコードはコミットされたとみなされます。これは Raft の非常に重要な機能です。レコードがコミットされると、ステート マシンがレコードを安全に実行できることを意味します。

プロセスは次のとおりです。

写真

  1. 1. クライアントは、コマンドがすべての状態マシンによって実行されることを期待して、リーダーにコマンドを送信します。
  2. 2. リーダーはまずコマンドを自身のログに追加します。
  3. 3. リーダーは他のノードに AppendEntries RPC を並行して送信し、応答を待ちます。
  4. 4. 半数以上のノードから応答が受信されると、新しいログ レコードが送信されたとみなされます。
  5. 5. リーダーはコマンドを自身のステートマシンに渡し、クライアントに応答を返す
  6. 6. さらに、リーダーはレコードが送信されたことを知ると、後続のAppendEntries RPCでレコードを送信したフォロワーに通知します。
  7. 7. フォロワーは送信されたコマンドを自身のステートマシンに渡す
  8. 8. フォロワーがクラッシュ/タイムアウトした場合: リーダーは RPC を繰り返し送信しようとします。

🚩 注: リーダーはすべてのフォロワーが応答するのを待つ必要はなく、フォロワーの半数以上が正常に応答するだけで済みます (ログ レコードが半数以上のノードに保存されていることを確認するため)。リーダーは待機する必要がないため、非常に遅いノードによってシステムが遅くなることがありません。

一貫性チェック

Raft は AppendEntries RPC メッセージを介してこれを検出します。

  • • 各 AppendEntries RPC には、新しいログ レコードの前のレコードのインデックス (prevLogIndex) と用語 (prevTerm) が含まれます。
  • • メッセージを受信した後、フォロワーは自身のログインデックスと用語をチェックして、prevLogIndexとprevTermと一致するかどうかを確認します。
  • • 一致が成功した場合、レコードは受け入れられ、最新のログが追加されます。一致しない場合、メッセージは拒否されます。

写真

写真

ログの一貫性

Raft アルゴリズムの目的は、すべてのノードの一貫性を確保することです。つまり、特定のノードでログ エントリが送信された場合、このログ エントリはすべてのノードでも送信されなければなりません。

🚩 ログの一貫性のこれら 2 つのポイントは、[一貫性チェック] によって保証されます。

  • • 2つのノードのログが同じインデックス位置に同じ用語番号を持つ場合、それらは同じコマンドを持つとみなされ、最初からこのインデックス位置までのログはまったく同じです。
  • • 特定のレコードがコミットされると、それ以前のすべてのレコードもコミットされます。

要約する

Raft アルゴリズムは、リーダー選出とログ複製のメカニズムを導入することで分散システムのコンセンサスと一貫性を保証する、簡潔で効率的な分散一貫性アルゴリズムです。

<<:  Kubernetes Pod の構成: 基礎から高度な実践スキルまで

>>:  CIO 分析: クラウド投資を最大限に活用する 5 つの方法

推薦する

調査:アプリケーションはクラウドへの移行が加速しているが、データはそうではない

パブリック クラウド市場は成長を続け、ローカル データ センター ビジネスは縮小していますが、クラウ...

パスワード保護: #限定版# BandwagonHost「11.11」CN2ラインKVM特別提供、在庫限り

このコンテンツはパスワードで保護されています。アクセスするには、下のフィールドにパスワードを入力して...

Kuaiboの王欣とMomoが地図ソーシャルネットワーキング市場に参入、新たなトレンドか?

MaToilet MTの失敗後も、王欣はソーシャルネットワーキングの探求をやめなかった。 Tech ...

初心者コピーライターを上級コピーライターに変える 4 つのライティング スキル

月給5,000~50,000のこれらのプロジェクトはあなたの将来ですコピーライティングの敷居は比較的...

iPaaS: クラウド アプリケーション展開の聖杯?

コンポーネント化されたアプリケーションを展開するときは常に、それらのコンポーネントが互いを検出し、ス...

Mofang Cloud-Simple 韓国 VPS/gcore 韓国 1Gbps サーバーのレビュー

Magic Cube Cloud は韓国のサーバーにあります。先週、Magic Cube Cloud...

BeastNode - 7 ドル / 1g メモリ / 35g SSD / 2T トラフィック / シングルホップ / シカゴ / アムステルダム

BeastNode.com はカリフォルニアに登録された会社です。主に MINECRAFT ゲームに...

ウェブマスターネットワークレポート:WeChat iOS 5.0ベータ版が公開され、Baidu Weigouが電子商取引を混乱させる

1. Android トロイの木馬は管理者権限を乗っ取り、権限を削除できない北京時間6月7日のニュー...

インドに海外進出するクラウド コンピューティング企業が知っておく必要があるポリシーは何ですか?

インドにおけるクラウドコンピューティングのブームクラウド コンピューティングにより、政府、企業、消費...

首都の冬が近づくにつれ、グループ購入業界では新たな一連のレイオフが起こっている。

半年が経ち、共同購入業界は復活しつつあるようだ。昨日、Meituan.comが最近、秘密裏に大規模な...

競合他社よりも外部リンクが多いにもかかわらず、ランキングが向上しないのはなぜですか?

昨日、あるネットユーザーから、自分の外部リンクは質も量も競合他社より優れており、リンク数も競合他社よ...

企業ウェブサイト向けのオリジナル記事リソースをより適切に見つける方法

最近、ウェブサイトの構築と最適化に忙しく、ブログの更新が遅くなってしまいました。この間、多くの企業サ...

Tencent Cloud + クラウドデータベース、WordPress ブログの構築

ここでは、スクリーンショットと詳細な手順とともに、Tencent Cloud + Tencent C...

Baidu が SEO を廃止、その製品は外部リンクをブロック

一方で、百度は積極的に新しい百度最適化ガイドを編纂しており、他方では、百度は自社製品の脱SEO化を強...