パクソス&いかだコンセンサスプロトコル

パクソス そして ラフト は、長い間存在しており、分散コンピュータシステムでの状態マシンレプリケーションを理解するために不可欠な2つのよく知られたコンセンサスプロトコルです。 Paxosは実際には、システムに応じて異なる仮定のグループに依存するプロトコルのファミリーですが、Raftは、より理解しやすいように設計されたPaxosの代替コンセンサスです。.

PaxosとRaftの両方を理解することは、プルーフオブワークや実用的なビザンチンフォールトトレランスなどの暗号通貨で分散コンセンサスプロトコルがどのように機能するかについての知識を深めるのに非常に役立ちます.

パクソス&いかだコンセンサスプロトコル

パクシ島といかだの背景

Paxosは1989年に最初に提案され、フォールトトレラントな分散コンセンサスの安全性を証明する特に洗練された方法として際立っていました。最初の目新しさにもかかわらず、Paxosは、その幅広い仮定と複雑な動作のために、理解するのが難しいと見なされることがよくあります。.

Raftは、パフォーマンスとフォールトトレラントの保証においてPaxosと本質的に同等である、Paxosのより理解しやすい代替手段として開発されました。 PaxosとRaftの両方で利用可能な広範なリソースがあり、それらは今日のさまざまなアプリケーションやシステムで広く研究され、使用されています。.

Paxosのよりよく知られている実用的な使用法のいくつかは、GoogleのNewSQLデータベース内にあります スパナ そしてその IBMSANボリュームコントローラー ストレージ視覚化サービス用.

Raftにはいくつかのオープンソースがあります リファレンス実装 Go、Java、C ++、Rustなどの複数の言語で.

Paxosとは?

分散型フォールトトレラントシステムのコンセンサスは、信頼性の低い参加者のグループ間で1つの結果に同意しています。 Paxosは、特定のシステムのプロセッサ、参加者、およびメッセージに関する仮定の間でさまざまなトレードオフを行うコンセンサスアルゴリズムのファミリです。このプロトコルは安全性を保証し、大規模なデータセットの耐久性が必要な場合によく使用されます.

非同期コンセンサスプロトコルは、安全性と活性の両方を保証できないため、すべてに固有のトレードオフがあります。 Paxosは、安全性を保証し、提案された値が最終的にコンセンサスラウンドの参加者グループによって選択されることを保証することにより、活気を生み出そうとする最初の分散型フォールトトレラントコンセンサスプロトコルの1つでした。.

Paxosコンセンサスには、エージェントとして知られる3つの役割があります。

  1. 提案者
  2. アクセプター
  3. 学習者

コンセンサスの目標は、参加者のグループが各ラウンドごとに1つの値について合意に達することです。コンセンサスのラウンドは、提案者が提案された値をアクセプターのグループに送信したときに始まります。アクセプターは、特定の提案者によって提案された値を受け入れることができ、特定のしきい値に達すると、その値はネットワークによって承認されます.

ただし、コンセンサスが正しく機能するためのPaxosの最初の条件は次のとおりです。

「アクセプターは、最初に提案された価値を受け入れる必要があります。」

これは、いくつかの提案者が受け入れ者によって受け入れられる提案された値を送信するという問題につながりますが、最初の提案された値を受け入れているため、すべての提案者は過半数の値を受け入れません。 Paxosは、アクセプターが受け取る提案された各値に一意のインデックスを付けて、複数の提案を受け入れることでこれを解決します。.

一意の番号が各提案を定義し、特定の提案された値が大多数のアクセプターによって受け入れられると、ネットワークは値を選択します。 選ばれた 値。複数の提案を選択できますが、これらの提案がすべて同じ値であることを保証することにより、安全性を検証する必要があります。安全性を確保するために必要なパクシ島の2番目の条件に関するレスリーランポートの定義によると、

「値vのプロポーザルが選択された場合、選択された番号の大きいプロポーザルはすべて値vになります。」

ネットワーク内の通信は非同期であるため、特定のアクセプターが選択された値を受信して​​いない可能性があります。これは、条件1と2に違反しない限り問題ありません。.

提案者は、値とともに一連のアクセプターへのメッセージとして特定の制限を採用します。これらは呼ばれます リクエストの準備 2つの主要なリクエストが含まれています:

  1. 未満の提案を決して受け入れないことを約束する n (nは新しい提案番号です)
  2. 最大数が以下の提案で応答する n アクセプターが受け入れたこと.

ランポートによると:

「提案者が大多数の承認者から要求された回答を受け取った場合、番号nと値vの提案を発行できます。ここで、vは回答の中で最も番号の大きい提案の値、または提案者が選択した任意の値です。回答者が提案を報告しなかった場合。」

その後、提案者は、承認者によって承認された承認要求を送信します。次に、提案者は、(安全性を損なうことなく)無視するか、値のコミットの成功を示すことができるアクセプターにコミットメッセージを送信します。アクセプターの特定のしきい値が値をコミットすると、そのコンセンサスラウンドのプロトコルは終了し、値を外部化します.

Paxosの複雑な設計は、他のノードが提案された値を無視または拒否しているにもかかわらず、ノードの大部分が同意したときに値を受け入れることができるというものです。これは、すべてのノードが同意する必要があり、単一ノードの障害によるプロトコルのブロックの対象となった以前のコンセンサスの反復とは異なります。.

提案番号が一意である限り、Paxosは安全性を保証する値を選択できます。承認者は、承認した最大番号の提案のみを覚えておく必要があることに注意することが重要です。逆に、提案者は、同じ一意の番号で提案を再発行しない限り、いつでも提案を放棄できます。.

プロトコルにおける提案者と承認者の役割の内訳は次のとおりです。

提案者

  • 提案を提出する n 準備リクエストと一緒にアクセプターに、過半数が返信するのを待つ.
  • アクセプターの過半数が同意した場合、同意した値で返信します。大多数が拒否した場合は、プロセスを中止して再開します.
  • その後、提案者はコミットメッセージを送信します。 n 過半数が受け入れる場合の価値.
  • アクセプターの大多数がコミットメッセージを受け入れると、プロトコルラウンドが完了します.

アクセプター

  • 提案を受け取り、すでに合意されている最大番号の提案と比較します.
  • 場合 n が高い場合は提案を受け入れ、nが低い場合は提案を拒否します.
  • その値が以前に受け入れられた提案と同じであり、そのシーケンス番号が合意された最大の番号である場合、後続のコミットメッセージを受け入れます.

プロポーザルは複数のプロポーザルを作成できますが、各プロポーザルのアルゴリズムに個別に従う必要があります.

最後に、の役割 学習者 受け入れ者の大多数が提案者からの提案を受け入れたことを発見することです。選択された値をネットワーク内の他の学習者に伝播する、著名な学習者が選択されます。このプロセスのバリエーションは、すべてのアクセプターが対応する学習者に決定を通知するか、アクセプターが個別の学習者セットに応答して、残りの学習者にメッセージを伝播する場合に使用できます。.

正式には、Paxosアルゴリズムは、進行するために必要な各ラウンドのリーダー(提案者)を区別します。アクセプターは、ノードのクラスター内でリーダーを選択するためにPaxosを使用できるようにする提案者のリーダーシップを認めることができます。ただし、2人の提案者がどちらがリーダーであるかについて合意がなく、リーダーの地位を争っている場合、Paxosは失速する可能性があります。ただし、この非終了状態が続く可能性は低いです。.

いかだとは?

Raftは、同じフォールトトレランスとパフォーマンス保証を備えた、より理解しやすいバージョンのPaxosとして作成されました。 Raftは、その上にプロトコルの実用的な実装を構築することも改善します。 Paxosは複雑であるため、その上に開発するための強固な基盤を提供するのには役立ちません。 RaftはPaxosに似ているため、2つを比較するには、RaftがPaxosプロセスをどのように簡素化するかを簡単に説明する必要があります。.

Raftは、ノードのクラスターに選択されたリーダーが1つしかないという仮定に基づいて、リーダーとフォロワーのモデルを採用しています。リーダーは、参加しているノード間のログレプリケーションを管理し、障害が発生するか切断されると置き換えられます.

アルゴリズムの開始時にリーダーも選出されます。リーダーの選択に何らかのコンテキストを与えるために、それはコンセンサスにおいて重要な役割を果たし、特定のアルゴリズムで区別できます。たとえば、ナカモトのプルーフオブワークでは、リーダーの選択は、各ラウンドの宝くじのようなマイニングプロセス(約10分ごと)によって行われます。実用的なビザンチンフォールトトレランス(pBFT)では、リーダーの選択はラウンドロビンスタイルの形式で実行されます。.

ナカモトコンセンサスとは

読む:ナカモトコンセンサスとは?

Raftは、候補ノードによって開始されたプロセスを通じてリーダーを選択します。候補者がとして知られているフェーズ中に通信を受信しない場合 選挙タイムアウト, それから彼らは彼らの増加した後に彼ら自身に投票します タームカウンター そしてそれを他のノードにブロードキャストします。候補は、少なくとも自分と同じくらいの期間数を持つ他の候補のフォロワーになり、この波及効果は、1人の候補がフォロワーの過半数を受け取るまでノード間で継続します。.

リーダーは、クライアント要求コマンドをフォロワーに送信するノード間のログレプリケーションを制御します。フォロワーの過半数がレプリケーションを確認した場合、リクエストはコミットされます。フォロワーは、ローカルのステートマシンにもコミットを適用します.

Raftは、新しいリーダーがフォロワーに自身のログを複製するように強制することにより、障害またはリーダー障害の対象となるノードからのフォールトトレランスを保持します。互いに一致しないエントリはすべて削除され、ログレプリケーションの一貫性が維持されます.

リーダー候補者は、フォロワーログよりも最新のログを持っている必要があります。候補者のログが潜在的なフォロワー(このコンテキストでは有権者)よりも最新でない場合、候補者は拒否されます.

全体として、Raftはコンセンサスを3つの個別のサブ問題に分解します。

  1. リーダー選出
  2. ログレプリケーション
  3. 安全性

コンセンサスプロトコルは、 強力なリーダー, つまり、Raftのリーダーノードは、プロトコルの制限によって制限されたまま、プロセスに実質的な影響を及ぼします。その結果、RaftはPaxosよりも設計が簡単です。.

結論

PaxosとRaftは、より大規模な分散型フォールトトレランスエコシステムのコアコンポーネントである重要なコンセンサスプロトコルです。暗号通貨で直接採用されていませんが、暗号通貨ネットワークで使用されるコンセンサスプロトコルは、PaxosとRaftの両方の設計からそれらの特徴的な仮定の多くを導き出します.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me