諸葛亮 vs. 龐統、Distributed Paxos の勝利

[[375586]]

序文

配布は確かに興味深いトピックです。注意して見ていれば、生活のいたるところに分配があることに気づくでしょう。

悟空兄さんは、自分が丹念に書いた技術論文から流通について学び始め、その論文が論文コンテストで一位を獲得しました。このプラットフォームを提供してくれたナゲッツコミュニティに感謝します。

この記事から、8 つの主要な分散プロトコル/アルゴリズムについて説明します。この記事では主に Paxos コンセンサスアルゴリズムについて説明します。

この記事の主な内容は次のとおりです。

この記事の主な内容

Paxosアルゴリズム

Paxos は分散アルゴリズムの兄貴分です。 Paxos は分散コンセンサスの代名詞であると言えます。最も一般的に使用される分散コンセンサスアルゴリズムは、これに基づいて改良されています。たとえば、Raft アルゴリズム (後で紹介します)。したがって、分散アルゴリズムを学習するには、まず Paxos アルゴリズムを学習する必要があります。

Paxos アルゴリズムは主に 2 つの部分で構成されます。

基本的な Paxos アルゴリズム: 複数のノード間で値について合意に達する方法。（この値は提案値と呼ばれます）

マルチ Paxos アルゴリズム: 複数の Basic Paxos インスタンスを実行して、一連の値について合意に達します。

基本 Paxos アルゴリズムは、Multi-Paxos コンセプトの中核です。 Multi は複数回、つまり Basic Paxos アルゴリズムを複数回実行することを意味します。したがって、基本的な Paxos アルゴリズムは非常に重要です。

三国志におけるパクソス

三国志では、劉備のグループには諸葛亮と龐統という二人の偉大な軍事顧問がおり、二人とも非常に強力でした。複数の将軍がそれぞれ異なる作戦を立てていたとき、どうやって合意に達したのでしょうか?

役割

Paxos には、提案者、受け入れ者、学習者の 3 つの役割があります。

Paxos アルゴリズムをもっと一般的な方法で説明しましょう。東漢末期に遡り、劉備陣営の曹操を攻撃するために Paxos アルゴリズムがどのように使用されたかを学びましょう。

劉備陣営の登場人物紹介:

一人の君主：劉備、依頼者または依頼人として。
提案者には諸葛亮と龐統という二人の軍事顧問がいた。
受賞者は関羽、張飛、趙雲の三将軍。
二人の文官：法正と馬良が弟子として登場。

劉備グループ

提案者

投票する値を提案します。
アクセスと調整では、クライアントの要求を受信した後、コンセンサスネゴシエーションのために 2 フェーズコミットを開始できます。
上記のストーリーに当てはめると、軍事顧問は戦闘計画を展開するために使用されます。

アクセプター

提案された各値に投票し、承認された値を保存します。
データの投票、交渉、保存、提案された値への投票、保存のためのコンセンサス値の受け入れ。
上記のストーリーに当てはめると、将軍は軍事顧問から戦闘計画を受け取る責任があります。

実際、クラスター内のすべてのノードは受信者の役割を果たし、コンセンサス交渉に参加し、データを受信して保存します。

学習者

投票結果を通知し、合意値を受け入れ、データを保存する。
投票プロセスに参加しないということは、合意交渉に参加しないことを意味します。
上記の物語に当てはめると、2 人の文官は戦闘計画の記録のバックアップとして機能しました。

受諾者または提案者

ノードがアクセプターとプロポーザーの両方の役割を果たせるとされるのはなぜでしょうか?

前回の記事では、BASEプロトコルについて説明した際に、2フェーズコミットプロトコルについてお話しました。受け入れ側と提案側の両方になれるコーディネーターがいます。

受信機として、クライアントからのメッセージを受信します。たとえば、諸葛亮は劉備の戦闘要件を受け取る必要があります。
提案者として、第 2 フェーズのコミットを開始します。次に、このノードと他のノードが受信者としてコンセンサス交渉を実行します。例えば、諸葛亮は劉備のために最終的な戦闘計画をまとめなければなりませんでした。

下の図に示すように、ノード 1 は提案者と受容者として機能し、ノード 2 と 3 は受容者として機能します。

ノードは提案者と受容者の両方である

諸葛亮 VS 龐統

三国時代には、劉備軍（西蜀を占領）、曹操軍（北方を占領）、孫権軍（江南を占領）がありました。

諸葛亮と龐統は発議者として、3人の受益者に作戦を提案した。提案には 2 つのプロパティがあります。

提案番号。軍事顧問が提案を行うたびに、番号が与えられます。ここでは、番号は n で表されます。

提案された価値、つまり戦闘計画は、ここでは v で表されます。したがって提案は[n, v]です。

諸葛亮の作戦は北から曹操を攻撃することであり、龐統の作戦は南から曹操を攻撃することであった。関羽、張飛、趙雲は次々と作戦を受け取った。誰の言うことを聞くべきでしょうか?これは合意の問題です。 Paxos アルゴリズムは 2 段階で合意に達します。準備フェーズと承認フェーズ。

準備

提案者として、諸葛亮と龐統は、作戦番号（提案番号）を含む準備要求をすべての受信者（関羽、張飛、趙雲）に送信しますが、作戦番号（提案値）は送信しません。

準備リクエストの送信

発案者の諸葛亮はまず作戦番号１の準備要請を送り、龐統は作戦番号２の準備要請を送ります。
受信側関羽（ノードX）は、8時に諸葛亮から作戦準備依頼を受信し、10時に龐統から作戦準備依頼を受信します。
受信側張飛（ノードY）は9時に諸葛亮からの戦計準備依頼を受信し、11時に龐統からの戦計準備依頼を受信します。
受信側の趙雲（ノードZ）は、12時に龐統からの戦計準備依頼を受信し、13時に諸葛亮からの戦計準備依頼を受信します。

準備フェーズ - 準備リクエストを送信する

注意: 準備フェーズでは特定の戦闘計画を持参する必要はないため、戦闘計画は空でも構いませんが、提案番号は必ず含める必要があります。

準備リクエストを受信（初回）

依頼を受けた順番は、関羽と張飛が諸葛亮の依頼[1、空欄]を受け、趙雲が龐統の依頼[2、空欄]を受けた。

準備フェーズ - 準備リクエストを受信する (初回)

関羽と張飛はこれまで提案を受けたことがなかったため、まだ提案がないことを示す応答が返されます。これは、諸葛亮が 1 以下の数字の準備要求には応答せず、1 未満の数字の提案を承認しないことを意味します。応答時刻は 14:00 と 15:00 です。

趙雲はこれまで提案を受けたことがなかったため、提案がない旨の返答が返されました。それは、Pang Tong に、2 以下の数字の準備要求には応答せず、2 未満の数字の提案も承認しないことを伝えることです。応答時間は 16 時です。

準備リクエスト受信（2回目）

準備フェーズ - 準備リクエストの受信（2回目）

龐統の準備要請については、関羽と張飛は以前受け取った1番よりも大きい2番の準備要請を受け取りました。なお、関羽と張飛は提案を通さなかったため、龐統に提案なしの返答が返されました。つまり、Pang Tong は、番号が 2 以下の準備リクエストには応答せず、番号が 2 未満の提案も承認しません。応答時刻は 14:00 と 15:00 です。

趙雲は最終的に諸葛亮の準備要求番号 1 を受け取りましたが、番号 1 は以前応答した準備要求の提案番号 2 よりも小さいため、図に示すように、準備要求を直接破棄し、応答しません。上の図のアイコン。

受け入れ段階

承認リクエストを送信

諸葛亮と龐統は準備応答を受け取った後、次の図に示すように、それぞれ承認要求を送信します。

承認フェーズ - 承認リクエストの送信

諸葛亮は、大多数の受諾者 (関羽と張飛) から準備応答を受け取った後、応答内の提案番号が最も大きい提案の値に従って、受諾要求の値を設定します。関羽と張飛から返された準備応答はどちらもまだ提案がないことを示すため、提案番号 1 と提案値 North (曹操を北から攻撃することを意味する) を指定して承認要求が送信されます。送信時間は15:00と16:00の1分後となります。

なぜ15時1分なのですか？ほとんどの受信者の準備要求が満たされると、承認要求を送信できるためです。関羽と張飛はそれぞれ14:00と15:00に返信したので、15:00以降に送信できます。

龐統は、ほとんどの受け入れ側 (関羽、張飛、趙雲) から準備応答を受け取った後、応答内の提案番号が最も大きい提案の値に従って、受け入れ要求の値を設定します。 Guan Yu、Zhang Fei、Zhao Yun から返された準備応答はすべて、まだ提案がないことを示しているため、提案番号 2 と提案値 South の承認要求が送信されます。南は曹操を南から攻撃することを意味します。発送時間は18:00、19:00、20:00となります。

承認リクエストを受け取りました

関羽、張飛、趙雲が諸葛亮と龐統からの受諾要請を受け取ると、下図のように次のように進めます。

承認フェーズ - 承認リクエストの受信

関羽、張飛、趙雲が諸葛亮から送られた提案[1、北]を受け取ったとき、提案番号1が彼らが通過すると約束した最小の提案番号2よりも小さかったため、諸葛亮の提案は拒否されました。

龐統が送った提案[2、南]を受け取ったとき、その2の数字は以前に約束された2の数字より小さくなかったため、彼らは龐統の提案[2、南]を可決した。そのため、関羽、張飛、趙雲の作戦は南から曹操を攻撃することだった。合意に達した。

学習者がステージに登場

承認者が提案を承認すると、すべての学習者に通知されます。学習者は、ほとんどのアクセプタが提案を承認したことに気付いた場合、その提案も承認し、提案の値を受け入れます。

つまり、関羽、張飛、趙雲が合意に達した後、学生の法正と馬良も南から攻撃するという作戦を可決したのです。

要約する

基本的な Paxos も、2 フェーズコミットプロトコルを通じて合意に達します。準備段階と受け入れ段階。 2 フェーズコミットプロトコルを知らない場合は、以前の記事を読んでください。「太極拳を使って分散理論を説明すると、快適！」

基本的な Paxos はコンセンサスを実現するだけでなく、フォールトトレランスも実現します。半分未満のノードに障害が発生しても、クラスターは正常に機能します。この記事では、Basic Paxos にフォールトトレランスを与える原則である多数ノード合意の原則についても繰り返し強調しています。

提案番号は優先度を表し、次の 3 つのコミットメントを保証します。