Pacxアルゴリズム。 分散システムにおけるコンセンサスに関する明確な記事

この記事では、Paxosコンセンサスアルゴリズムを分析し、なぜそれが必要なのか、なぜ機能するのか、その正確性を証明し、実際のアプリケーションの問題について少し話します。 多くの点で、これはレスリーランポートによる記事「Paxos Made Simple」の無料の語り直しです

分散コンセンサスが必要な理由とその内容

多くの場合、分散システムの実行中（ユーザーリクエストや分散ストレージシステムなどを処理するサーバーが複数あるだけ）、一般的な決定を下す必要があります。たとえば、クラスターレベルのシングルトンサービスを実行するサーバーと、それが落ちたときに移行する場所サーバー。 このタスクは、決定の調停者（管理サーバー）の存在下で単純に解決されます。 問題は、アービターが単一の崩壊点になり、アービターの障害がシステムの完全または部分的な動作不能につながる可能性があり、システムのパフォーマンスの復元と復元には手動の介入が必要になることです。 明らかに、問題に耐性のあるシステムは、共通の問題について合意することができる平等な参加者で構成されるべきです。 通常、交渉の結果として、アービターが選ばれ（リーダー、マスターという用語を使用します）、作業中に彼を通してさらなる問題が決定されます。



レスリーランポートはもともと、信頼性の低い通信を伴う分散システムではコンセンサスが不可能であることを数学的に厳密に証明したかったのですが、そのようなコンセンサスを達成するためにPaxosアルゴリズムを発明し、証明しました。 たとえば、 ウィキペディアにあるアルゴリズムの説明は、一見単純で短く見えますが、理解するのは容易ではなく、実践するのはさらに困難です。



このアルゴリズムには重要な制限があります。1つの値のみを選択するプロセスについて説明します。実際には、多くの決定を行う必要があり、次の各ケースではアルゴリズムの新しいインスタンスを作成する必要があります。 また、システムの参加者はビザンチン様式で行動しないと想定されます。 約束を守り、虚偽のデータを提供しないでください（ストーリーはわかりませんが、ビザンチンの評判はまあまあだったと感じています）

選択と役割について

コンセンサスアルゴリズムのコンテキストでの「選択」（ソリューションの選択、価値の選択）の概念は、日常とは異なります。 実生活で長所と短所を比較する場合、コンセンサスアルゴリズムの場合、同等のオプションから選択が行われます。 任意の値/ソリューションが適切であり、主なことは、多くの提案されたもののどれを決定することです。



これは、3人とあなたの友人がピッツェリアに来て、ピザ全体が同じくらい（または悪い）であり、3つ注文する大きなピザを選択しようとすると、ウェイターだけがあなたに近づき、メニューを困惑して見続けるのと比較できます。 隣接するテーブルがあるため、「ペペローネをもう持って、遅らせないで、他のすべてよりも悪くない」-これは提案であり、提案者を提案しました。 あなたの一人が彼の話を聞いて、「OK、ペパロニにしましょう」と考えています。 彼は受け入れ者であり、 申し出を 受け入れたところです。 別のテーブルの後ろから彼らは叫ぶ：「彼らはあなたに三度目のことを言う-マルガリータを取り、私たちにすでに注文を受け取らせる」-これはもう一つの申し出であり、そして「三度目のあなた」は提案番号であり、マルガリータは文の値（値）。 その後、ウェイターは、オファーを受け入れた人に質問し始めます。 彼はよりleanせており、あなたの大多数が同じ申し出を受け入れた場合（「私はあなたに3回目を言います—マルガリータ」）、この申し出は選ばれたと呼ばれ 、大多数がウェイターに通知した場合、ウェイターは知っています （選択した値について学習し、注文を受け入れることができるようになります。 しかし、3番目の文を受け入れた人の1人がスマートフォンに引っかかっており、ウェイターの質問に応答しません。



値が選択されましたが、それを認識することは不可能です-現実の世界に残っている2人の友人は矛盾した答えを与えます。 次の交渉ラウンドが始まり、おそらく新しい提案が受け入れられ、スマートフォンにこだわった参加者はHabrを読み続けます。 したがって、正しいコンセンサスアルゴリズムは、次に選択された値が選択された値と初めて一致するようなネゴシエーションルールを定義します。

もう一度見てください、これは非常に重要で絶対に素晴らしい瞬間です：システムの状態（受け入れられた値）はノード間で分配されます-各受信者は受け入れた提案についてのみ知っており、一般的な値が選択されていますが、知ることが不可能であり、知ることさえできない状況が発生する可能性があります何かが選択されているかどうか。 この場合、交渉は継続されます。 しかし、Paxosは、受け入れ値のほとんどによって選択された次の値が、選択された最初の値と一致するようなものです。 一度選択すると、選択は変更されません。

そこで、用語と役割を理解しました。

1. 提供 - 提案を行います。
2. Acceptors-オファーを受け入れ、受け入れられたもの（ numberとvalue ）を記憶します。 この場合、ホストは最初に受け取った提案を受け入れ、選択がすでに行われていても後続の提案を受け入れます。
3. 認識 -どの提案が選択されたかを確認します（ほとんどの参加者に受け入れられました）。

実際には、役割を組み合わせることができます。たとえば、サーバーを相互にリーダーとして選択することについて話し合う場合、各サーバーはリーダーとして自らを提供し、オファー（独自のオファーを含む）を受け入れ、最終的に誰を見つける必要があります選ばれました。

ほとんどについて

過半数は「半分以上」、つまり 2N + 1からのN + 1（および2Nからも）以上。



多数による受け入れの要件は明らかです：値の選択が少数の受け入れ者（正確には半分以下）による受け入れを必要とする場合、同時に複数の異なる値を選択するのを妨げるものはありません。 コンセンサスは得られません。 多数派を構成する2つのセットが空でない交差点を持っていると便利です。



この場合、すべての受信者が選択に参加する必要はありません。残りの受信者が誤動作している可能性があり、受信者との通信が切断されている可能性があります。 したがって、2N + 1人の参加者のシステムは、N人の失敗に耐えることができます。

グローバル時間分散システム

オファー番号についてはすでに言及しました。 各提案には番号があります。 ランポートの説明では、これは次のような自然数です。

1. 番号は一意であり、各オファーには独自の番号があります。
2. 入札者は、後続のオファーごとに大きな数値を使用します。

次の例えは、アルゴリズムを理解するのに役立ちました：番号は基本的に提案のタイムスタンプであり、タイムスタンプはa）同時に2つの文を作成（発行）できないように設計された分散システムのグローバル合成時間を設定します、b）2つの提案のどちらが「後で」行われたかを理解できます。 いくつかの提案を受け入れたホストは、受け入れられた提案より「早い」（「過去から」の提案）された提案を無視します。



実際には、オファー番号は、特定のサーバーのオファーカウンターの値とサーバー識別子のペアで構成されます。

正しいアルゴリズムを構築します

番号mおよび値vの提案が大多数のホストによって受け入れられた場合、値vが選択されます。 その後、後続の選択値（ほとんどの受信者が受け入れる）は、選択されたvと一致するはずです。



この要件は、 vの値が選択された後、アクセプターがvに等しい値のオファーのみを受け入れる場合に満たすことができます。



アクセプターは、オファー側が提供するものを受け入れます。したがって、番号n> mのすべてのオファーのすべてのオファー側が以前に選択した値vのみを提供する場合、前述の要件が順番に満たされます。



帰納法によって最後のステートメントを証明していると仮定し、帰納遷移を行うために何が欠けているかを理解しようとします。

文（m、v） -が選択されました。 大多数のホストで構成されるCが多数あり、これらの各ホストはオファー（m、v）を受け入れました。 また、帰納法の仮説から、 mからn-1までの範囲の数字を持つすべての文の値はv （*）であることがわかります。 次に、数値nの文の値もvにする必要があります。



ホストの大部分で構成されるセットSが存在し、このセットからホストが受け入れる最後の文（最大数がn未満）の意味を見つけることができると仮定します。 この「最大」文の数をkとしましょう。 セットSには、セットCから少なくとも1つの受信aが含まれているため、数kは、受信aによって最後に受け入れられたオファーの数以上になり、受け入れられたaの最後の文の数は、 m （値が選択された瞬間）以上になります。 。 k> = mであるため、（*）により、文kの値は以前に選択されたvであり 、これを使用して文（n、v）を生成します。 したがって、集合Sの存在を保証できる場合、これは誘導遷移を提供します。

厳密な数学言語では、Lamportによって次のように定式化されました。誘導遷移が発生するには、次の不変式が満たされる必要があります。

任意のvおよびnについて、文（n、v）が作成（発行）されると、受信者の過半数で構成されるセットSが存在し、2つのうちの1つが真になります。（a）セットSの受信者は、 n未満の数または（b） vは、セットSからの受信者によって受け入れられたすべてのオファーの中で、 n未満の最大数を持つオファーの値です。

上記のセットSの存在を保証するために、提案nを行うことを計画している人は、瞬間nまでに受け入れる最後の文の数と値を受け入れる人の大多数から見つけなければなりません。



問題が何であるかを確認してください：申し出人は、最後に受け取った申し出の数と意味を受け入れる人に尋ねることができますが、回答を送信することにより、受信者が次の申し出を受け入れ、申し出人が受け取った回答が古くて役に立たなくなる可能性があります これを避けるために、Lamportはこれを考え出しました。入札者に最後に受け入れられたオファーの意味を尋ねるだけでなく、 nより小さい数のオファーを受け入れないように依頼してください。 受信者からの応答として、オファー側は、1）最後に受け入れられたオファーの値と数、2） n未満の数のオファーを受け入れないという約束を受け取ります。 その後、応答として受信した最後に受け入れられた提案に関する情報は古くならず、回答が大多数の受信者から受信される場合、これらの受信者は所望のセットSを形成します。 セットSが形成されるとすぐに、オファー側はオファー（n、v）を作成します （ここでvは、上記で説明したように、セットSから瞬間nまでホストによって受け入れられた最後の文（最大数のオファー）の値です）。



したがって、正しいコンセンサスアルゴリズムを取得しました。提案は2段階で行われます。

1. 準備段階：
   1. 申し出人は、（時間nで ） nを申し出ることを計画しているという発表を送信します。
   2. アナウンスを受信した受信者は、 n未満の番号（最大n ）のオファー、および最後に受け入れられたオファー（数と値）を受け入れない、または最後に受け入れられたオファーの数がnより大きい場合、またはnがホストが別の入札者を受け入れないことをすでに約束しているという提案。
2. 提案：
   1. 大多数の受信者から回答を受け取った提案者は、最大オファー番号を持つ応答から値をオファー値vとして選択し、オファー（n、v）を送信します。
   2. 申し出（n、v）を受け取った受信者は、もちろん、他の申し出人がn *より小さい番号の申し出を受け入れないことを約束していない場合、それを受け入れる義務があります（ n *> n） 。

値が選択されたことを知るためには、認識している人は、同じオファー（数と値）がほとんどの受信者によって受け入れられたことを確認する必要があります。

実用的な問題

メッセージングは​​非同期であり、通信は信頼できないため、オファー側が必要な数の約束を待たずに少なくともいくつかの回答を受け取るかどうかは不明であり、オファー側は次のオファーを行うことで再試行します。 これはすべて長い間繰り返すことができます。



アルゴリズムは、合意に達することを保証しません。 たとえば、ある提供者は多数派から1未満の数のオファーを受け入れないという約束を受け取り、2番目の提供者は多数派から2未満の数のオファーを受け入れないという約束を受け取ります。 最初の文は選択できなくなりました。 彼のオファーが選択されないことを理解すると、最初の入札者は、3未満のオファーを受け入れないという約束を大多数から受け取ろうとします。現在、2番目のオファーは受け入れられません。 そのため、2つの申し出人が無限に、大多数の受信者を一方または他方に説得して、コンセンサスに達する可能性をブロックすることができます。 これは、アルゴリズムにランダムな遅延を導入することで修正できます。もちろん、提供するサービスが1つだけであることを確認することをお勧めします。 これを行うには、複数の決定を行う必要がある場合、提案として次の値を選択するときに、前のステップ（アルゴリズムの前のインスタンス）で選択したリーダーを使用します。



しかし、ここで新たな問題が発生します。リーダーを選択した場合、背後にある残りのノードが新しい選挙を開始し、他のリーダーを選択することを妨げるものは何もありません。 さらに、前のリーダーはこれについて何も知らないかもしれず、彼がここで担当しているという仮定に基づいて行動し続けるでしょう。



別の複雑な問題は、不正なビザンチン様式の振る舞いであり、このためにシステムの要素にマルウェアを含める必要はありません。 たとえば、受信者は約束を覚えておく必要があります。これにより、ディスクに保存されるため、ディスク上のデータ破損（オペレータによるファイルの失敗または不正確な削除による）がビザンチンの動作につながります。 実際には、メモリ内のデータでさえ破損する可能性があり、同じ悲しい結果になります。 コードのエラーは、ビザンチンの動作を引き起こす可能性もあります。



Google開発者による「Paxos Made Live-An Engineering Perspective」というPaxosアルゴリズムのこれらの問題やその他の問題について、Chubbyプロジェクト（Zookeeperの企業内類似物）での分散コンセンサスの実装経験について語るエキサイティングな記事で読むことができます。



したがって、Paxosアルゴリズムは特効薬ではなく、フォールトトレラントな分散システムに関する知識のほんの小さな素晴らしい基本的なブリックです。