分散システムでは、Paxosアルゴリズムの簡単な説明は何ですか？

決して 異なる値について合意することはありません。プロトコルは、合意が必ず行われるように設計されています。成功した場合、今後の合意の試みは、これらのノードの少なくとも1つも通過する必要があります。したがって、決定に達した後に提案するノードは、大多数のノードと通信します。プロトコルは、以前のagを学習することを保証します。その過半数からの価値に基づいてリードします。

その仕組みは次のとおりです。

A、B、Cの3つのノードがあるとします。Aが提案したいのは値 “Foo。”

アルゴリズムは3つのフェーズで動作します。各フェーズで、大多数のノードからの確認に到達する必要があります。

最初に、準備フェーズがあります。 A は準備リクエストをA、B、Cに送信します。Paxosはシーケンス番号に依存してその保証を達成します。準備リクエストは、ノードに「準備リクエストのシーケンス番号よりも小さいシーケンス番号の提案を受け入れることはありません」と約束するように要求します。 ノードは、以前に同意した値（存在する場合）で応答します。（これは非常に重要です）：ノードAは、受け取った値を最大のシーケンス番号で提案する必要があります。このアクションにより、以前に合意した値が保持されることが保証されます。

次に、受け入れフェーズがあります。 A は、承認リクエストをA、B、Cに送信します。承認リクエストの状態は次のとおりです。 ” fooを受け入れますか？」 付随するシーケンス番号が、ノードが以前に約束したもの、またはノードが以前に受け入れた要求を下回っていない場合、新しい値とシーケンス番号を受け入れます。

ノードAがからの受け入れを受け取った場合大多数のノード、値が決定されます。 このラウンドのPaxosは別の値に同意することはありません。

第3フェーズは厳密には必要ありませんが、重要です。生産されたPaxos実装での最適化。 A は、大部分の承認を受信した後、決定済みメッセージを A、B、C。これらのメッセージは、値が選択されたことをすべてのピアに通知し、決定プロセスの終了を加速します。

このメッセージがないと、他のピアは合意を知るために価値を提案しようとする必要があります。準備段階で、彼らは以前に合意された価値を知りました。その合意が締結に至ると、ノードは合意を認識します。

ここでいくつかの重要な問題について説明しました。

1. すべてのシーケンス番号は単調に増加し、ノードごとに一意である必要があります。つまり、 A と B の両方がシーケンス番号kのメッセージを送信することはできません。プロトコルで送信されるすべてのメッセージには、シーケンス番号が含まれています。ノードは、確認した最高の受け入れ要求と、準備フェーズで約束した最高の値を追跡する必要があります。
2. 障害状態。 Paxosのラウンドが失敗する可能性は十分にあります。障害が発生した場合、1つのノードがより高いシーケンス番号で再度提案を試みます。
3. 終了条件。私が説明したバージョンのPaxosは、必ずしも終了するわけではありません。終了の正式な証明には、いくつかの調整が必要です。

回答

Paxosはコンセンサスを達成しているため、分散データベースへの書き込みを複製するためにも使用できます。グループ内のすべてのノード間でイベントの一貫した順序を保証できます。 Chubby by Googleは、一貫性の高いファイルを提供するためにPaxosを使用しています。これが混乱の原因です。では、ビューの同期とpaxosの両方をレプリケーションに使用できる場合、その関係はどうなりますか？

小さな歴史： Lamportは、80年代初頭に状態機械複製の概念を導入しました。状態マシンレプリケーションとは、システムがすべてのノードに同じ順序でイベントを配信し、それらが決定論的に処理されて、グループ内のすべてのノードで一貫した状態が保証されることを意味します。ただし、この概念が導入された時点では、ネットワークが同期していることを含め、あらゆる種類の仮定が必要でした。したがって、状態マシンレプリケーションは、実用化されていない理論的なツールのままでした。ビューの同期はこの時点で導入され、そのような仮定を行わずに一貫性を実現することを目的としています。目標は、そのような保証を提供する実用的なシステムを持つことでした。

Paxosの公開は、ビューの同期に関する作業の進行中に行われました。レプリカがこのコンセンサスアルゴリズムを使用してクライアント要求の実行順序について合意できるようになったため、Paxosは状態マシンレプリケーションを実現できました。 Paxosは、同期ネットワークや障害を想定していませんでした。 Paxosは、グループメンバーシッププロトコルも提供しました。ビューの同期とPaxosの間に残った違いは、抽象化が定式化された方法だけでした。どちらも動的メンバーシップを提供し、同様に障害を処理します。違いは実際にはモデルにのみあります。強調できるいくつかの違いは次のとおりです。

• Virtual Synchronyは、Paxosと比較して単純なグループメンバーシッププロトコルを備えています。 Virtual Synchronyは、グループメンバーシップを個別のサービスとして実行します。
• 仮想同期がブロックされるパーティションの特定のケースでは、Paxosが進行する場合があります。
• VirtualSynchronyは現在のPaxosよりも高速です。

どちらのシステムも進化して収束しています。 現在のところ、2つの間に大きな違いを描くことは非常に困難です。

Lalithは、仮想同期プロトコルを明確に説明し、Paxosまたはその他のコンセンサスバリアントをビュー同期で使用できることを正しく指摘しています。コンセンサスとは別に、Paxosは、仮想同期がすでに提供しているグループメンバーシップおよびその他の機能を提供します。仮想同期とPaxosはどちらも同じ保証を提供し、ほぼ同時に開発されたため、仮想同期の仕様では、コンセンサスにPaxosを使用していません。ただし、仮想同期モデルは、完全に順序付けられた送信プロトコル（ABCASTとも呼ばれます）を使用してアトミックブロードキャストを実現し、別のプロトコルを使用してグループビューを更新します。これらは、コンセンサスバリアントと見なすことができます使用します。

ISIS-2ランタイムモデルは、コンセンサスのためではなく、Paxosの個別のサービスとしてグループメンバーシップを除外するために、Paxosモデルと仮想同期モデルを組み合わせていることに注意してください。これにより、メンバーシップが動的に変更されない場合にPaxosが高速になります。 Virtual SynchronyとPaxosを組み合わせることにより、ISIS2は通常のPaxosが実行する必要のある特定のステップをスキップできます。本質的に、PaxosとVirtual Synchronyは、同じ機能を実現するための異なるモデルであり、互いに組み合わせてバリアントまたは最適化を実現できます。