コミットされた分散フェールオーバートランザクションの到達可能性の下限

まえがき

最近、このシリーズの別の記事を読みました。「2フェーズコミットよりも優れています。」 ここでは、この記事の内容を分析しません（詳細な分析を行うことを考えていますが）。 私の仕事のタスクは、時間遅延の観点から最も効率的な分散コミットのバージョンを提案することです。 もちろん、このようなコミットには高い代償が伴います。 ただし、多くの人が信じているように、2フェーズコミットが抑制的ではないことを評価して示すことが目標です。

また、野外実験や偽の比較は行われないことに注意してください。 アルゴリズムと理論的分析を簡単に示します。 必要に応じて、実際に独立して実装および検証できます。 もちろん、これが現在の記事で説明されていればはるかに良いでしょうが、すべては自由時間とモチベーションに依存しています。 私の意見では、アルゴリズムを記述することはグラフを与えることよりも重要です。 ほぼ全員がアルゴリズムを使用してグラフを描画できますが、その逆は当てはまりません。

この紹介の後、次に進みます。

はじめに

定義 RTT-メッセージの往復時間。
定義 ホップとは、1回の出荷の時間です。

定理 時間1 RTTは2ホップの時間と同じです。
証明 。 これは明らかです。

定義 分散コミットとは、少なくとも2人の分散システム参加者間のアトミックな変更を受け入れるプロセスです。

定義 2フェーズコミットは2フェーズコミットです。 最初のフェーズは、トランザクションを開始してコミット参加者をブロックする可能性を検証するアトミック操作です。 2番目のフェーズは、参加者からの応答の収集と、ロックの解放を伴うトランザクションのアプリケーションです。

定理 2フェーズの分散コミットは、1 RTTより速く実行できません。
証明 。 2フェーズコミットを実行するには、少なくとも、クライアントからすべての参加者に要求を送信し、完了時に応答を受信する必要があります。 これには2ホップまたは1 RTTが必要です。

定義 フェイルセーフコミットとは、1人以上のコミット参加者が失敗した場合でも実行を継続するコミットです。

定理 1 RTTの2フェーズフォールトトレラント分散コミットが可能です。

この定理を証明するには、可能な場合に方法と条件を与えるだけで十分です。 これが常に可能であるとは限らないことは明らかです。 同じリソースへの分散トランザクションの同時アクセスの場合、そのようなトランザクションはこのリソースに並ぶ必要があります。 そして、それはそれらが順番に実行されることを意味します。 この場合、1 RTTについて話すのは少しおかしいでしょう。 ただし、有利な条件下での従来のアルゴリズムでさえ、1 RTTよりも著しく長い時間を与えます。

この定理の証明については、この記事の後の部分で説明します。

二相性コミット

コーディネーターを使用した2フェーズコミットの古典的なスキームを考えてみましょう。

シーケンスは次のとおりです。

最初のホップ 。 クライアントはコーディネーターにリクエストを送信します。
2ホップ目 。 トランザクションコーディネーターは、ブロックする要求を参加者に送信します-フェーズ1。
3ホップ目 。 参加者は正常にロックを取得し、トランザクションを実行する準備ができているという応答を送信します。
4ホップ目 。 コーディネーターは、すべての参加者に操作の適用に関するメッセージを送信します-フェーズ2。
5番目のホップ 。 参加者はコーディネーターに成功を報告します。
6ホップ目 。 コーディネーターはクライアントに責任があります。

合計3 RTT。

フォールトトレランスを追加します。 コーディネーターと参加者は、対応するコンセンサスグループの一部であると想定します。 また、好ましい条件、すなわち グループのリーダーは変わらず、コンセンサスは正常に終了します。 補題を証明しましょう：

補題 リーダーベースの分散コンセンサスは、1 RTTより速く完了することはできません。
証明 。 コンセンサスを得るには、リクエストをリーダーに送信する必要があります。 この場合：

最初のホップ 。 リーダーは、要求を他のコンセンサスメンバー（フォロワー）に送信します。
2ホップ目 。 参加者はリーダーに確認を送ります。
これらのフェーズがなければ、コンセンサスは得られません。

補題 1つのRTTでコンセンサスが可能です。
証明 ：Raftアルゴリズムを使用します。 リーダーと大多数のコンセンサス参加者の活気のある場合、リーダーに関する合意された決定の採択は、参加者からの回答を受け取った後に発生します。 1 RTT後。

定義 コンセンサスによって合意された決定を下すことは、合意と呼ばれます。

この時点で合意が他の当事者にまだ達していない場合でも、この後システムはこの合意がシステムに残ることを保証することに注意する価値があります。 リーダーが落ちた場合、フェールオーバーが発生し、その間に新しいリーダーがこれらの変更を調整する必要があります。 ただし、これは補題の検討対象ではありません。 潜在性、つまり 望ましい結果につながる可能性のある理想的な条件は、合意形成です。 考えられるすべての条件を考慮しませんか？ はい、 非同期システムではコンセンサスが得られないという定理があるためです 。 したがって、アルゴリズムの正確性を損なうことなく、これらの条件がどの段階で違反されても、不変式を維持するために必要な、最も有利な状況での最小可能時間を理解することが重要です。 これらの2つの補題は、可能な限り最短の合意時間を達成できることを示唆する包括的な答えを与えます。

この定理は、リーダーの条件を捨てて1 RTTよりも早くコンセンサスに達することは不可能であることを証明することによって一般化できます。 ただし、これはこの記事の範囲外です。 証明の考え方は、システムの他の参加者に関する知識の普及と、対応するメッセージの可用性を考慮することです：1ホップでは、データのみを送信できますが、到着したかどうかと受信者が何であったかはわかりません。

したがって、フォールトトレランスのために、1 RTTでコンセンサスを取り、2フェーズコミットに追加します。

最初のホップ 。 クライアントはコーディネーターリーダーにリクエストを送信します。
2番目と3番目のホップ 。 コーディネーターリーダーは、トランザクションの開始に同意します。
4ホップ目 。 トランザクションコーディネーターは、参加者のリーダーにブロックするリクエストを送信します-フェーズ1。
5番目と6番目のホップ 。 参加者は、コンセンサスグループの知識を維持しながら、正常にロックを取得します。
7ホップ目 。 参加者のリーダーは、取引を行う準備ができているという応答を送信します。
8番目と9番目のホップ 。 コーディネーターのリーダーは、システムのすべての参加者に関する情報を調整します。
10ホップ目 。 コーディネーターのリーダーは、参加者のすべてのリーダーに、運用の適用に関するメッセージを送信します-フェーズ2。
11ホップと12ホップ 。 リーダーはコミットに同意し、変更を適用します。
13ホップ 。 参加者は、アプリケーションの成功についてコーディネーターのリーダーに報告します。
14ホップ目 。 コーディネーターはクライアントに責任があります。

合計7 RTT。 悪くない。 フォールトトレランスのコストは4 RTTです。 それらは、コーディネーターと参加者が連続して2回ずつそれぞれ自分のコンセンサスに達するという事実のために発生します。

上の図では、いくつかの非最適性に気付くことができます。 それらを排除しましょう。

コミットの最適化

最初の明らかな最適化は、参加者から成功したロックの応答を収集した直後にクライアントに応答を送信することです。 なぜなら これらの回答はフォールトトレラントであり、参加者はそれらのことを決して忘れません。つまり、ノードの損失、リーダーの再選などの場合でも、遅かれ早かれトランザクションは完了します。 ただし、ここでは、滑りやすい瞬間が1つあります。

実際には、コーディネーターが最終トランザクションをコミットするかどうかについて最終決定を下すという事実にあります。 つまり すべての参加者が「OK」と言ったが、リーダーの変更などで参加者が鈍くなった場合でも、コーディネーターはトランザクションをロールバックする完全な権利を持っています。 もしそうなら、あなたは10-13の希望だけを削除できますが、8日と9日は削除できません。 しかし、2 RTTの減少があるため、これはすでに悪くありません。 7ではなく5 RTT。

同時に、10-13の希望は消えず、クライアントはそれらを待つ必要はありません。 コーディネーターと参加者は、クライアントと並行して作業を終了します。 そして、クライアントは少し早く確認を受け取ります。 この知識は、ほんの少し後にシステムに確実に反映されます。 ここでは、非同期、コンセンサス、および外部の参加者に少し不正行為をしてコーナーをカットしたことを証明できないという魔法を使用します。 つまり クライアントが私たちがコミットしたばかりのデータをすぐに読み、参加者に直行したい場合、ロックにつまずくでしょう（それまでに第2フェーズで削除されなかった場合）、このリクエストは取り消されるまでフリーズします。 しかし、理論研究の枠組みでは、この事実は私たちにとって絶対に重要ではありません。 私たちは自分たちにとって理想的な条件を準備しています。 そして、不完全なものの場合、上記のように、私たちはいくつかの永遠を待ちます（コンセンサスには永遠が必要であり、さらにそれらのいくつかを連続して使う必要があるため）。

騎士との次の動きはやや複雑でエレガントです。

トランザクションの最初の部分を検討してください。 そこで、クライアントはコーディネーターにリクエストを送信し、2フェーズコミットを開始して、これらのリクエストを他の参加者に送信します。 そのような要求を同時に満たすというアイデアがすぐに生まれます。 コーディネーターと参加者の両方に並行してリクエストを送信します。 途中で陰湿なtrapが私たちを待っています。

実際、クライアントはフォールトトレラントなエンティティではありません。 彼は落ちるかもしれません。 彼が参加者にリクエストを送信し、ロックを取得して待機したが、何らかの理由でコーディネーターへのリクエストが届かず、クライアントが落ちたと想像してください。 したがって、2フェーズコミットを開始する人や、競合/問題などが発生した場合にロールバックする人はいません。 参加者は記録を永久にブロックし、誰も彼らを助けません。 したがって、このような最適化は正しくありません。 参加者は、トランザクションを担当し、必要に応じてロールバックするコーディネーターの決定後にのみコミットする権利を持ちます。

さらに進むには、まったく別の方法で問題を調べる必要があります。 そして、このために、奇妙なことに、コンセンサスから始めます。

コンセンサス最適化

ここで最適化できると思われますか？ 結局、Raftと私は最短のリードタイムである1 RTTを達成しました。 実際には、RTTが0の場合、より高速です。

このため、クライアントからリーダーにリクエストを送信して応答を受信するには、コンセンサス自体に加えて、別の1 RTTが必要であることを思い出してください。 つまり この場合、リモートコンセンサスグループには2つのRTTが必要です。これは、コーディネーターでの送信とコミット、参加者での送信とコミットの2つの例の2フェーズコミットで確認できます。 すぐに合計4 RTT、および別の1 RTT-コーディネーターに第2フェーズをコミットします。

リモートクライアントのリーダーに基づくコンセンサスが2 RTTよりも速くなることはありません。 実際、最初にリーダーにメッセージを配信する必要があります。次に、リーダーはグループメンバーを既に転送し、それらから回答を取得する必要があります。 オプションなし。

唯一のオプションは、弱いリンク（リーダー）を取り除くことです。 実際、すべての記録がそれを通過するだけでなく、その落下の場合、グループは非常に長い間アクセスできなくなります。 コンセンサスリーダーは最も弱いリンクであり、リーダーの回復はコンセンサスの最も脆弱で重要な部分です。 したがって、あなたはそれを取り除く必要があります。

定義 メッセージブロードキャストは、グループのすべてのメンバーに同じメッセージを送信しています。

これを行うには、狭い円で広く知られているマスターなしでコンセンサスを取ります。 主なアイデアは、ブロードキャストが参加者に対して同じ状態を達成することです。 これを行うには、2回ブロードキャストすれば十分です。 わずか1 RTT。 システム参加者への最初のブロードキャストは、クライアント自身が行うことができます。 参加者からの応答ブロードキャストはクライアントに到達できます。 クライアントが同じ状態を見ると（たとえば、競合する要求がない場合にこれを見る）、応答ブロードキャストの内容を分析することで、要求が遅かれ早かれ通信されることを理解できます。 実際、このようなアルゴリズムを使用すると、クライアントを含むすべてのコンセンサス参加者は、リクエストが通信されたことを同時に認識します。 そして、これは2回のブロードキャストの後に発生します。 1 RTT。 なぜなら クライアントはグループへのメッセージの送信と応答の受信に1 RTTを費やす必要があるため、0 RTTでコンセンサスが効果的に発生したという逆説的な結論が得られました。

アナロジー

さらに進むには、強力な分析ツールを使用します-類推。 Raftアルゴリズムに戻ります。 それで何が起こっていますか？ 次の2つのフェーズで構成されます。

第1段階 ：リーダーは参加者にリクエストを送信し、応答を待ちます。
第2段階 ：回答後、リーダーは合意された決定を個別に受け取り、システムの参加者に送信します。

何にも似ていませんか？ そうです、これは2フェーズコミットであり、注意点がいくつかあります。

1. Raftアルゴリズムは、すべての参加者からの応答を待つ必要はありません。 2フェーズコミットでは、トランザクションを成功させるために、すべての参加者からの成功した応答を待つ必要があります。
2. Raftアルゴリズムでは、参加者はneoとは言えません。 より正確に、理論的には、彼はこれを行うことができます（たとえば、場所がなくなった）が、このneoKは回答がないことに似ています。 2フェーズコミットでは、すべてがより厳密になります。参加者の少なくとも1人がneo-OKを言った場合、トランザクション全体が悪化してロールバックするはずです。 これは、2フェーズの本質です。最初にすべての人の同意を求め、全会一致の承認を得てから変更をロールオーバーします。 この意味でのコンセンサスはより民主的です。なぜなら、 多数決が必要です。

さらに、ソリューションには専用のドライバー（リーダーまたはコーディネーター）があり、予備段階と最終段階の2つのフェーズがあるという共通点があります。

したがって、必要なのは、2フェーズコミットでコーディネーターを放棄することです。 リーダーを放棄することでコンセンサスのために行ったのとまったく同じことを行う。

しばらくの間、フォールトトレランスについて忘れて、この場合のコミットの様子を見てみましょう。

自己調整

定義 コーディネーターを使用しない2フェーズコミットは、2つのフェーズで構成されます。

1. すべての参加者は、決定を他のすべての参加者に送信します：OKまたは非OK。
2. 全員からOKを受け取った各参加者は、少なくとも1人がOKに返信した場合、変更をコミットするかロールバックします。

その後、信頼性のために、各参加者はコミットが発生し、ロックを解除できるという情報を他の全員に送信できますが、これは必須ではありません。

突然コーディネーターが必要なくなったのはなぜですか？ 実際には、コーディネーターは、ノードが稼働しているかどうかなど、トランザクションプロセスを監視しました。 つまり 参加者に問題がある場合、コーディネーターはトランザクションをロールバックしました。 問題はコーディネーターだけにありました、なぜなら 彼は自分の面倒を見ることができませんでした。 したがって、多くの場合、 2フェーズコミットはブロッキングと呼ばれます。

定義 自己調整トランザクション -専用のコーディネーターを必要としないトランザクション。

ただし、フォールトトレランスを追加すると、コーディネーターの役割は次のように冗長になります。 各コンセンサスメンバーは、自ら立ち上がることができます。 したがって、専用のコーディネーターを必要とせずに、自己調整トランザクションになります。 コーディネーターを使用した通常の2フェーズコミットとの重要な違いは、コーディネーターがすべての参加者から肯定的な回答があったとしても、いつでもトランザクションをロールバックすることを決定できることです。 自己調整トランザクションでは、そのような非決定的な動作は受け入れられません。 各参加者は、他の参加者の応答に基づいて決定を行いますが、この決定は同じでなければなりません。

定理 自己調整トランザクションは、厳密な一貫性を提供します（厳密な一貫性=線形化可能性+直列化可能性）。
証明 。 実際、この証明は、2フェーズコミットもこのような保証を提供するという単純な事実に基づいています。 実際、コーディネーターなしのスキームでは、各参加者はそれ自体がコーディネーターです。 最も重要であるかのように、2フェーズコミットがあります。 これは、2フェーズコミットのすべての不変式を保持することを意味します。 これは、各参加者が他の全員にブロードキャストの回答を送信することを覚えていれば簡単に確認できます。 つまり 全員が他の全員からOK応答を受け取り、トランザクションをコミットするコーディネーターとして機能します。

有利な状況下での希望の最小数を説明しましょう。
最初のホップ 。 クライアントは、トランザクションのすべての参加者にメッセージを送信します。
2ホップ目 。 すべての参加者は、クライアントとお互いに応答を送信します。

2番目のホップの後、クライアントには、コミットに関する決定を下すために必要なすべての情報があります。 したがって、コミットに必要なRTTは1つだけです。

耐障害性と可用性

気配りのある読者が尋ねる場合があります：クライアントがクラッシュした場合に何をすべきか？ 実際、システムの参加者をフォールトトレラントにすることができる場合、クライアントにそのような要求を行うことはできません。 彼はいつでも倒れるかもしれません。 クライアントがシステム内のすべての参加者にリクエストを転送した後、クライアントの参加なしで分散コミットが完了することは明らかです。 そして、クライアントがそれらの一部にのみ送信し、安全に落ちた場合はどうなりますか？

この場合、クライアントは次のことを行う必要があります。クライアントは各参加者に、トランザクションの他のすべての参加者に関する情報を転送する必要があります。 したがって、各参加者は他のすべての参加者を知っており、結果を送信します。 さらに、参加者は、クライアントからリクエストを受け取っていない場合、次の動作のいずれかを選択できます。

1. 彼は取引を受け入れない、つまり即座に答えます neokを送信します。 この場合、ロックはロールバックされます。 参加者は、いつものように、他の参加者に他の回答を送信します。
2. 別の参加者からの要求に、この参加者のトランザクションコミットを完了するために必要なすべての情報が含まれている場合、関連するレコードを正常にブロックし（フェーズ1）、OKを転送することを決定できます。 これを行うには、クライアントは、他のすべての参加者および分散コミットを完了するために必要なすべてのデータに関するトランザクション情報の各参加者を送信する必要があります。

いずれの場合でも、すべての参加者がOKを受け取るか、必要な情報がない場合、誰かがOKを通知し、トランザクションがロールバックされます。 つまり クライアントがクラッシュした場合、各参加者は開始された内容を完了するか、クライアントのアクションを正しくロールバックできます。

システム参加者に耐障害性を持たせることは残っています。 これを行うには、専任のリーダーなしでグループのコンセンサスに入れてください。 つまり 各参加者は個別のノードではなく、コンセンサスグループ内のノードのセットを表します。

コミットアルゴリズムは次のようになります。

1. クライアントは、各要求をトランザクションの参加者のグループに属するノードに送信します。
2. 各ノードは、リクエストを受信すると、他のすべてのノードとクライアントに、現在の合意ステップで実行されるかのように、コミットの最初のフェーズの投機的実行に関する回答を送信します。 現実には、これが実際に起こるかどうかはわかりません。なぜなら、 他のクライアントから競合するリクエストがある場合、コンセンサスは現在適用されていないアクションを並べ替えることがあります。
3. クライアントは、すべての参加者のすべてのノードからすべての要求を受け取ります。 投機的実行中のすべてのノードがOKと回答し、コンセンサスグループの各ノードでコンセンサスステップが同じであった場合、これは最初のフェーズの投機的実行が実際に行われ、コミットを決定できることを意味します。

実際、各グループのすべてのノードから応答を受信する条件は冗長です。 ただし、この要件を緩和するためのより詳細な考慮事項は、この記事の範囲外です。

結論

合計2ホップまたは1 RTTを取得します。 クライアントとサーバー間のメッセージを削除できないことを考慮すると、サーバー側でのコミットの有効な処理時間はゼロです。 サーバーが分散高可用性フェイルセーフトランザクションを即座に処理し、クライアントに応答を送信したかのように。

このように、重要な理論的および適用された事実があります：分散フェイルセーフコミットの実行時間の下限は達成可能です。

文学

マイケル・J・フィッシャー、ナンシー・A・リンチ、マイケル・S・パターソン、1983年、
1つの障害のあるプロセスによる分散コンセンサスの不可能性

G. デムチェンコ 、2016年、 マスターレスコンセンサスアルゴリズム

ジムグレイ、レスリーランポート、2003年、 トランザクションコミットに関するコンセンサス