コンセンサスアルゴリズムについて学ぶ - 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 つの方法

推薦する

サイン会第一弾! EasyStackはPKCをコアとして「Chain Hainan」をサポート

12月4日、海南自由貿易区(香港)ブロックチェーン実験区主催のデジタル文明会議記者会見が海南生態ソ...

asmallorange - $75/年/4CPU/4g メモリ/100g ハードディスク/2T トラフィック/無料 cpanel ライセンス

asmallorange.com はサイバー マンデー セールを実施しており、仮想ホスト、VPS な...

yalo-$5/1g メモリ/200g ハードディスク/10T トラフィック/ノースカロライナ

yaloがホストキャットに登場するのは2回目。昨年設立され、openvz仮想化をベースにしている。最...

Baidu の不正行為防止アップデート後に高品質な記事を作成する方法

6月22日と6月28日のBaiduの不正行為対策の大規模なアップデートは、多くのウェブマスターにとっ...

ウェブマスターネットワークからの毎日のレポート:Twitter の電子商取引企業への転換は、価格戦争の早期終結につながる可能性がある

1. 草の根は儲かる、新浪は損をする、微博は2つの異なる状況に直面中国国際放送、北京、8月20日。経...

scalahosting: 月額 10 ドル、ダラス VPS、2GB RAM/50GB SSD/無制限帯域幅

scalahosting を紹介します。2007 年に設立され、主に米国とヨーロッパで仮想ホスト (...

2019 年のデータセンターの 5 つのトレンド: エッジ コンピューティングが変化を推進

2019 年を迎えても、ネットワーク エッジはデータ センター分野におけるイノベーションのテクノロジ...

簡単にウェブサイトを構築できる、PHP オープンソース コンテンツ管理システム (CMS) 20 選

2018年最もホットなプロジェクト:テレマーケティングロボットがあなたの参加を待っていますコンテンツ...

Baidu が新しいウェブマスター プラットフォームを立ち上げ、ウェブサイト運営コンベンションを開始

Admin5 Webmaster Network ニュース: 「千の峰が十年を競う」をテーマにした第...

正確で柔軟なWeiboプロモーション、高品質のコンテンツ、高いタイムリーさ

ショートビデオ、セルフメディア、インフルエンサーのためのワンストップサービスWeiboは、インターネ...

分散トランザクション - 信頼性の高いメッセージ最終一貫性ソリューション

[[405809]]みなさんこんにちは。私はバスケットボールが大好きなプログラマーのウルフキングです...

業務再開が迫る中、伝統的な産業は4つの戦略でオンライン販売の成長を達成するためにデジタルマーケティングを採用しています。

ショートビデオ、セルフメディア、インフルエンサーのためのワンストップサービス突然の疫病の発生により、...

Kubernetes ロードバランサー MetalLB

導入Kubernetes では、Loadbalancer を使用して外部サービスを提供できます。一般...

スパムコンテンツはウェブサイトに悪影響を及ぼす可能性がある

SEO オペレーターの多くは、一般的に、Web サイトのコンテンツの更新と外部リンクの投稿という 2...

スーパーマーケットでの買い物から見るWeiboマーケティング、O2O、モバイルインターネット

2013年はWeiboマーケティング、O2O、モバイルインターネットがホットワードになるだろう。今日...