箱のないシュレディンガーの猫: 分散システムにおける合意の問題

それでは、想像してみましょう。 部屋には5匹の猫が閉じ込められており、飼い主を起こしに行くには、猫全員がこれに同意する必要があります。XNUMX匹が寄りかかっていないとドアを開けることができないためです。 猫のうちの XNUMX 匹がシュレーディンガーの猫で、他の猫がシュレディンガーの決断を知らなかった場合、「どうやってそんなことができるのでしょう?」という疑問が生じます。

この記事では、分散システムの世界の理論的構成要素とその動作原理について簡単に説明します。 また、Paxos の根底にある主なアイデアを表面的に調べます。

開発者がクラウド インフラストラクチャやさまざまなデータベースを使用し、多数のノードからなるクラスターで作業する場合、データは完全で安全で、常に利用可能であると確信します。 しかし、保証はどこにあるのでしょうか？

基本的に、当社の保証はサプライヤー保証です。 ドキュメントでは次のように説明されています。「このサービスは非常に信頼性が高く、所定の SLA が定められています。心配しないでください。すべてが期待どおりに分散して機能します。」

大企業の賢い人たちがすべてうまくいくと保証してくれたので、私たちは最善のものを信じる傾向があります。 私たちは、実際になぜこれが機能するのかという質問をしません。 このようなシステムが正しく動作することを正当化する正式な根拠はあるのでしょうか?

最近行ったのは 分散コンピューティング学部 そしてこのテーマにとても刺激を受けました。 学校の講義はコンピュータシステムに関するものというよりは微積分の授業に近いものでした。 しかし、これはまさに、私たちが毎日無意識に使用している最も重要なアルゴリズムが、かつて証明された方法です。

最新の分散システムのほとんどは、Paxos コンセンサス アルゴリズムとそのさまざまな修正を使用しています。 最も素晴らしいことは、このアルゴリズムの有効性、そして原理的にはその存在の可能性そのものが、紙とペンで簡単に証明できることです。 実際には、このアルゴリズムはクラウド内の膨大な数のノードで実行される大規模システムで使用されます。

次に説明する内容の簡単な説明: XNUMX 人の将軍の任務ウォーミングアップのつもりで見てみましょう 二人の将軍の任務.

私たちには赤軍と白軍の 1 つの軍隊があります。 白軍は包囲された都市に拠点を置いている。 将軍 A2 と AXNUMX が率いる赤軍が都市の両側に配置されています。 赤毛の使命は、白い都市を攻撃して勝つことです。 ただし、赤軍の各将軍の個別の軍隊は白軍よりも小規模です。

赤側の勝利条件: 白側に対して数的優位性を得るには、両方の将軍が同時に攻撃する必要があります。 これを行うには、将軍 A1 と A2 が互いに合意する必要があります。 全員が別々に攻撃すると、赤毛は負けます。

合意に達するために、将軍 A1 と A2 は白い都市の領土を通じて互いに使者を送ることができます。 使者は味方の将軍に無事到達することもあれば、敵に妨害されることもあります。 質問: 赤毛の将軍たちの間に、X 時間の攻撃に同意することが保証されるような一連の通信 (A1 から A2 へ、またはその逆に A2 から A1 へ使者を送る一連のこと) はあるのでしょうか。 ここでは、保証とは、同盟国 (別の将軍) が指定時間 X に確実に攻撃するという明確な確認を両将軍が持つことを意味します。

A1 が A2 に「今日の午前 1 時に攻撃しましょう!」というメッセージを含むメッセンジャーを送信したとします。 将軍A2は将軍A1の確認がなければ攻撃できません。 A2 からの使者が到着した場合、A2 将軍は「はい、今日白人を殺しましょう」というメッセージを含む確認を送信します。 しかし現在、将軍 A2 は自分の使者が到着したかどうかを知りません。攻撃が同時であるかどうかの保証もありません。 さて、一般 AXNUMX は再度確認が必要です。

彼らの通信を詳しく説明すると、次のことが明らかになります。メッセージ サイクルがどれほど多くても、両将軍がメッセージを受信したことが通知されたことを保証する方法はありません (どちらかのメッセンジャーが傍受できると仮定すると)。

Two Generals 問題は、通信の信頼性が低い 100 つのノードが存在する非常に単純な分散システムをよく示しています。 これは、それらが同期しているという XNUMX% の保証がないことを意味します。 同様の問題については、この記事の後半でより大規模にのみ説明します。

分散システムの概念を導入します

分散システムとは、メッセージを交換できるコンピュータ (以下、ノードと呼びます) のグループです。 個々のノードはそれぞれ、ある種の自律的なエンティティです。 ノードは単独でタスクを処理できますが、他のノードと通信するにはメッセージを送受信する必要があります。

メッセージがどのように正確に実装されるか、どのようなプロトコルが使用されるか - この文脈では、これは私たちには関係ありません。 分散システムのノードがメッセージを送信することによって相互にデータを交換できることが重要です。

定義自体はそれほど複雑ではありませんが、分散システムには重要な属性が多数あることを考慮する必要があります。

分散システムの属性

1. 並行性 – システム内で同時または同時に発生するイベントの可能性。 さらに、XNUMX つの異なるノードで発生するイベントは、これらのイベントの発生順序が明確でない限り、同時発生する可能性があるとみなします。 しかし、原則として、私たちにはそれがありません。
2. グローバルクロックがありません。 世界時計がないため、イベントの明確な順序はわかりません。 普通の人々の世界では、私たちは時計と時間が絶対にあるという事実に慣れています。 分散システムになるとすべてが変わります。 超高精度の原子時計にも誤差があり、XNUMX つの出来事のどちらが先に起こったかを判断できない状況が発生する可能性があります。 したがって、時間も当てにできません。
3. システムノードの独立した障害。 もう XNUMX つ問題があります。ノードが永久に持続するわけではないというだけの理由で、何か問題が発生する可能性があります。 ハードドライブに障害が発生し、クラウド内の仮想マシンが再起動し、ネットワークが点滅し、メッセージが失われる可能性があります。 さらに、ノードが機能しているにもかかわらず、同時にシステムに悪影響を及ぼしている状況も考えられます。 最後のクラスの問題には、問題という別の名前が付けられました。 ビザンチンの将軍。 この問題を抱えた分散システムの最も一般的な例はブロックチェーンです。 しかし、今日はこの特別な種類の問題については考慮しません。 単に XNUMX つ以上のノードに障害が発生する可能性がある状況に注目します。
4. ノード間の通信モデル（メッセージングモデル）。 ノードがメッセージを交換することによって通信することはすでに確立しています。 よく知られているメッセージング モデルには、同期と非同期の XNUMX つがあります。

分散システムにおけるノード間の通信モデル

同期モデル – メッセージがあるノードから別のノードに到達することが保証される、有限の既知の時間デルタが存在することは確実にわかっています。 この時間が経過してもメッセージが到着しない場合は、ノードに障害が発生していると言って間違いありません。 このモデルでは、待ち時間が予測可能です。

非同期モデル – 非同期モデルでは、待機時間は有限であると考えられますが、ノードの障害が発生したことを保証できるような時間の差はありません。 それらの。 ノードからのメッセージの待機時間は任意に長くすることができます。 これは重要な定義なので、さらに詳しく説明します。

分散システムにおけるコンセンサスの概念

コンセンサスの概念を正式に定義する前に、それが必要となる状況の例を考えてみましょう。 ステート マシンのレプリケーション.

分散ログがいくつかあります。 これには一貫性があり、分散システムのすべてのノード上で同一のデータが含まれることが必要です。 いずれかのノードがログに書き込む新しい値を学習すると、そのタスクはこの値を他のすべてのノードに提供して、すべてのノードでログが更新され、システムが新しい一貫した状態に移行するようにします。 この場合、ノード間で合意することが重要です。提案された新しい値が正しいことにすべてのノードが同意し、すべてのノードがこの値を受け入れます。この場合にのみ、誰もが新しい値をログに書き込むことができます。

言い換えれば、どのノードも、より関連性の高い情報があり、提案された値が正しくないことに反対しませんでした。 分散システムでは、ノード間の合意、および単一の正しく受け入れられる値に関する合意がコンセンサスとなります。 次に、分散システムが確実に合意に達することを可能にするアルゴリズムについて説明します。

より正式には、コンセンサス アルゴリズム (または単にコンセンサス アルゴリズム) を、分散システムを状態 A から状態 B に遷移させる特定の関数として定義できます。さらに、この状態はすべてのノードによって受け入れられ、すべてのノードがそれを確認できます。 結局のところ、このタスクは一見したほど簡単ではありません。

コンセンサスアルゴリズムのプロパティ

システムが存続し、状態から状態への移行をある程度進めるためには、コンセンサス アルゴリズムには XNUMX つのプロパティが必要です。

1. 契約 – 正しく動作しているすべてのノードは同じ値を取る必要があります (記事では、このプロパティは安全プロパティとも呼ばれます)。 現在機能している (障害が発生していないか、他のノードとの接続が失われていない) すべてのノードは合意に達し、何らかの最終的な共通値を受け入れる必要があります。

   ここで、私たちが検討している分散システム内のノードは合意を望んでいることを理解することが重要です。 つまり、私たちは今、何かが単純に失敗する可能性があるシステムについて話していますが（たとえば、一部のノードが失敗するなど）、このシステムには、意図的に他のノードに対して機能するノード（ビザンチンの将軍の任務）は絶対に存在しません。 この特性により、システムの一貫性が保たれます。

2. 統合性 — 正しく動作しているすべてのノードが同じ値を提供する場合 vこれは、正しく動作しているすべてのノードがこの値を受け入れる必要があることを意味します v.
3. 終了 – 正しく動作しているすべてのノードは最終的に特定の値 (活性プロパティ) を取得し、これによりアルゴリズムがシステム内で進歩することが可能になります。 正しく動作している個々のノードは、遅かれ早かれ最終値を受け入れ、「私にとって、この値は真実であり、システム全体に同意します。」と確認する必要があります。

コンセンサスアルゴリズムがどのように機能するかの例

ただし、アルゴリズムの特性は完全には明らかではないかもしれません。 したがって、同期メッセージング モデルを備えたシステムで、最も単純なコンセンサス アルゴリズムがどの段階を通過するかを例で説明します。この場合、すべてのノードが期待どおりに機能し、メッセージは失われず、何も中断されません (これは本当に起こりますか?)。

1. すべてはプロポーズ（プロポーズ）から始まります。 クライアントが「ノード 1」というノードに接続してトランザクションを開始し、新しい値 - O をノードに渡したとします。今後は「ノード 1」と呼びます。 提供。 プロポーザーとして、「ノード 1」はシステム全体に新しいデータがあることを通知する必要があり、他のすべてのノードにメッセージを送信します。 「O」の意味が思い浮かんだので書きたいと思います！ ログに「O」も記録されることを確認してください。」

   

2. 次の段階は、提案された値に対する投票です (投票)。 それはなんのためですか？ 他のノードがより新しい情報を受信し、同じトランザクションに関するデータを持っている場合があります。

   
   
   ノード「ノード 1」がプロポーザルを送信すると、他のノードはこのイベントに関するデータのログをチェックします。 矛盾がない場合、ノードは次のように通知します。「はい、このイベントに関するデータは他にありません。 「O」の値は、私たちが受け取るべき最新情報です。」

   それ以外の場合は、ノードは「ノード 1」に応答できます。 この取引に関する最新のデータがあります。 「O」ではなく、もっと良いものです。」

   投票段階では、ノードはすべて同じ値を受け入れるか、またはそのうちの XNUMX つが反対票を投じて、そのノードがより新しいデータを持っていることを示すかのいずれかの決定を下します。

3. 投票ラウンドが成功し、全員が賛成した場合、システムは新しい段階、つまり値を受け入れる段階に移行します。 「ノード 1」は他のノードからのすべての応答を収集し、「全員が値 "O" に同意しました!」と報告します。 今、私は「O」が私たちの新しい意味であり、誰にとっても同じであることを正式に宣言します。 小さな本に書き留めてください、忘れないでください。 それをログに記録してください！」

   

4. 残りのノードは、値「O」を書き留めたことを示す確認 (Accepted) を送信します。この間、新しいものは何も到着しません (一種の XNUMX フェーズ コミット)。 この重要なイベントの後、分散トランザクションは完了したと見なされます。
   

したがって、単純な場合のコンセンサス アルゴリズムは、提案、投票 (投票)、受け入れ (受け入れ)、受け入れの確認 (受け入れ) の XNUMX つのステップで構成されます。

あるステップで合意に達できなかった場合、提案された値の確認を拒否したノードによって提供された情報を考慮して、アルゴリズムが再度開始されます。

非同期システムにおけるコンセンサスアルゴリズム

これまでは、同期メッセージング モデルについて話していたため、すべてがスムーズでした。 しかし、現代の世界では、すべてを非同期で行うことに慣れていることはわかっています。 同様のアルゴリズムは、ノードからの応答の待ち時間が任意に長くなる可能性があると考えられる非同期メッセージング モデルを備えたシステムでどのように機能しますか (ちなみに、ノードの障害も、次のような場合の例として考慮されます)。ノードは任意の長い時間応答できます)。

コンセンサス アルゴリズムが原理的にどのように機能するかがわかったので、ここまで読み進めた好奇心旺盛な読者への質問です。非同期メッセージ モデルを備えた N ノードのシステムで、システムがコンセンサスに達するためには何個のノードが障害を起こしても問題ありませんか?

正解と根拠はネタバレの裏にあります。正解は次のとおりです。 0。 非同期システムで 1985 つのノードでも障害が発生すると、システムは合意に達することができなくなります。 このステートメントは、特定の界隈ではよく知られている FLP 定理で証明されています (XNUMX 年、Fischer、Lynch、Paterson、原文へのリンクは記事の最後にあります)。 」

皆さん、問題が発生しました。私たちはすべてが非同期であることに慣れています。 そしてここにあります。 どうやって生き続けるのか？

私たちはただ理論について、数学について話していました。 「合意に達することができない」とは、数学的な言語から工学的な言語に置き換えると、何を意味するのでしょうか? これは、「常に達成できるとは限らない」ことを意味します。 コンセンサスが得られないケースもある。 これはどのようなケースですか?

これはまさに、上で説明した liveness プロパティの違反です。 共通の合意がなく、すべてのノードから応答がない場合、システムは進行できません（有限時間内に完了できません）。 なぜなら、非同期システムでは応答時間が予測できず、ノードがクラッシュしたのか、それとも単に応答に時間がかかっているだけなのかを知ることができないからです。

しかし、実際には解決策を見つけることができます。 アルゴリズムが失敗した場合でも長時間動作できるようにします (潜在的には無期限に動作する可能性があります)。 しかし、ほとんどの状況では、ほとんどのノードが正しく機能していれば、システムは進歩します。

実際には、部分同期通信モデルを扱います。 部分同期は次のように理解されます。一般的なケースでは、非同期モデルがありますが、特定の時点の「グローバル安定化時間」という特定の概念が正式に導入されます。

この瞬間は長くは来ないかもしれないが、いつか必ず来るはずだ。 仮想目覚まし時計が鳴り、その瞬間からメッセージが到着するまでの時間差を予測できます。 この瞬間から、システムは非同期から同期に変わります。 実際には、私たちはまさにそのようなシステムを扱います。

Paxos アルゴリズムはコンセンサス問題を解決します

パクシ は、一部のノードで障害が発生する可能性を条件として、部分同期システムのコンセンサス問題を解決するアルゴリズムのファミリーです。 パクソスの作者は レスリーランポート。 彼は 1989 年にアルゴリズムの存在と正しさの正式な証明を提案しました。

しかし、その証明は決して簡単なものではないことが判明した。 アルゴリズムを説明した最初の出版物 (1998 ページ) は 33 年にのみ発行されました。 結局のところ、それは非常にわかりにくく、2001年には14ページに及ぶ解説が出版されました。 出版物の量は、実際にはコンセンサスの問題がまったく単純ではなく、そのようなアルゴリズムの背後には最も賢い人々による膨大な量の研究が横たわっていることを示すために挙げられています。

興味深いのは、レスリー・ランポート自身が講義の中で、XNUMX 番目の説明記事には XNUMX つのステートメント、XNUMX 行 (彼はどのステートメントであるかは特定しなかった) があり、それはさまざまな方法で解釈できると指摘したことです。 このため、最新の Paxos 実装の多くは完全に正しく動作しません。

Paxos の仕事を詳細に分析するには複数の記事が必要になるため、アルゴリズムの主なアイデアを非常に簡単に説明することにします。 私の記事の最後にあるリンクには、このトピックをさらに深く掘り下げるための資料があります。

パクソスでの役割

Paxos アルゴリズムには役割の概念があります。 XNUMX つの主なものを考えてみましょう (追加の役割による変更があります)。

1. 提案者 (リーダーまたはコーディネーターという用語も使用される場合があります)。 ユーザーから新たな価値を学び、リーダーの役割を担う人たちです。 彼らの任務は、新しい値の一連の提案を開始し、ノードのさらなるアクションを調整することです。 さらに、Paxos では、特定の状況において複数のリーダーの存在が許可されています。
2. 承認者 (有権者)。 これらは、特定の値を受け入れるか拒否するかを投票するノードです。 これらの役割は非常に重要です。なぜなら、コンセンサス アルゴリズムの次の段階の後にシステムがどの状態に移行する (または移行しない) かという決定がそれらに依存するからです。
3. 学習者。 システムの状態が変化したときに、単に受け入れて、新しく受け入れられた値を書き込むノード。 彼らは決定を下すのではなく、データを受信して​​エンドユーザーに提供するだけです。

XNUMX つのノードで、さまざまな状況で複数の役割を組み合わせることができます。

定足数の概念

次のシステムがあると仮定します。 N ノードそしてその中で最大のものは F ノードが失敗する可能性があります。 F ノードが失敗した場合、少なくとも次のものが必要です。 2F+1 アクセプタノード。

これは、最悪の状況であっても、正しく動作する「良好な」ノードの大部分を常に確保するために必要です。 あれは F+1 同意した「良好な」ノード、および最終値が受け入れられます。 そうしないと、さまざまな地域グループが異なる意味を受け取り、グループ間で合意できない状況が発生する可能性があります。 したがって、投票を獲得するには絶対多数が必要です。

Paxos コンセンサス アルゴリズムがどのように機能するかについての一般的な考え方

Paxos アルゴリズムには XNUMX つの大きなフェーズが含まれており、それぞれが XNUMX つのステップに分割されます。

1. フェーズ 1a: 準備する。 準備フェーズ中に、リーダー (提案者) はすべてのノードに次のように通知します。 新しいラウンドが始まりました。 このラウンドの数は n です。 これから投票を始めます。」 現時点では、新しいサイクルの開始を報告するだけであり、新しい値は報告しません。 このステージのタスクは、新しいラウンドを開始し、その固有の番号を全員に通知することです。 ラウンド数は重要であり、これまでのすべてのリーダーによる以前のすべての投票数よりも大きな値でなければなりません。 システム内の他のノードがリーダーのデータがどれだけ新しいかを理解できるのは、概数のおかげだからです。 おそらく他のノードはかなり後のラウンドの投票結果をすでに持っており、単にリーダーに時代遅れであることを伝えるだけでしょう。
2. フェーズ 1b: 約束。 アクセプター ノードが新しい投票ステージの番号を受け取ると、次の XNUMX つの結果が考えられます。
   • 新しい投票の数 n は、アクセプタが参加した以前の投票の数よりも大きくなります。 次に、アクセプターは、n より小さい番号の投票にはこれ以上参加しないという約束をリーダーに送信します。 アクセプターがすでに何かに投票している場合 (つまり、第 XNUMX フェーズですでに何らかの値を受け入れている場合)、受け入れられた値と参加した投票の数をプロミスに添付します。
   • それ以外の場合、アクセプターがより高い番号の投票についてすでに知っている場合は、単に準備ステップを無視して、リーダーに応答しなくても構いません。
3. フェーズ 2a: 受け入れる。 リーダーはクォーラム (システム内の大部分のノード) からの応答を待つ必要があります。必要な数の応答が受信された場合、イベントの開発には XNUMX つのオプションがあります。
   • アクセプタの一部は、すでに投票した値を送信しました。 この場合、リーダーは投票の中から最大数の値を選択します。 この値を x と呼び、「Accept (n, x)」のようなメッセージをすべてのノードに送信します。最初の値は独自の提案ステップでの投票数、XNUMX 番目の値は全員が集まったものです。つまり私たちが実際に投票する価値。
   • アクセプタのどれも値を送信せず、単にこのラウンドで投票することを約束した場合、リーダーはその値、つまり最初にリーダーになった値に投票するよう招待することができます。 それをyと呼びましょう。 前の結果と同様に、「Accept (n, y)」のようなメッセージがすべてのノードに送信されます。
4. フェーズ 2b: 承認されました。 さらに、アクセプターノードは、リーダーから「Accept(...)」メッセージを受信すると、一部の(その他)ことを約束していない場合にのみ、それに同意します(新しい値に同意するという確認をすべてのノードに送信します)。リーダーはラウンドナンバー付きで投票に参加します n' > nそうでない場合、確認リクエストは無視されます。

   大多数のノードがリーダーに応答し、すべてのノードが新しい値を確認した場合、新しい値は受け入れられたとみなされます。 万歳！ 過半数に達していない場合、または新しい値の受け入れを拒否したノードがある場合は、すべてがやり直しになります。

これが Paxos アルゴリズムの仕組みです。 これらの各段階には多くの微妙な点があり、実際にはさまざまな種類の失敗、複数のリーダーの問題などを考慮していませんでしたが、この記事の目的は、読者に分散コンピューティングの世界を高いレベルで紹介することだけです。

Paxos がこの種の唯一のものではなく、他のアルゴリズムも存在することも注目に値します。たとえば、 Raft、しかしこれは別の記事で取り上げます。

さらなる学習のための資料へのリンク

ビギナーのレベル：

• 分散型コンセンサスはどのように機能するのでしょうか?、Preethi Kasireddy、Medium のブログ記事
• Paxos をシンプルにしました。 実際に、Adi Kancherla、Medium のブログ記事
• 分散思考、エイブラハム一体、ブログ
• 同期、非同期、部分同期、エイブラハム一体、ブログ記事

レスリー・ランポートのレベル:

• XNUMX つの欠陥のあるプロセスによる分散コンセンサスの不可能性 (FLP 不可能性)、フィッシャー、リンチ、パターソン、研究論文、1985
• 非常勤議会、レスリー ランポート、研究論文、1998 年
• Paxos をシンプルに、レスリー ランポート、研究論文、2001 年

出所： habr.com