因果関係の一貫性

因果的一貫性は、主要なメモリ一貫性モデルの 1 つです。並行プロセスが共有メモリにアクセスする並行プログラミングでは、一貫性モデルによってどのアクセスが合法であるかが制限されます。これは、分散共有メモリまたは分散トランザクションで正しいデータ構造を定義するのに役立ちます。

因果的一貫性は「分割下でも利用可能」です。つまり、プロセス間でネットワーク接続が機能していない（ネットワークが分割されている）場合でも、プロセスはメモリの読み取りと書き込みができます（メモリは利用可能）。これは非同期モデルです。シーケンシャル一貫性や線形化可能性などの強力な一貫性モデルとは対照的です。これらのモデルは、分割下でも安全かつ存続することはできず、同期が必要なため応答が遅くなります。

因果一貫性は、共有メモリモデルのための弱い一貫性モデルとして1990年代に提案されました^{[1] 。因果一貫性は、通信プロトコルにおける因果ブロードキャストの概念と密接に関連しています。 [2]} これらのモデルでは、分散実行は、潜在的な因果関係のLamportの事前発生 概念に基づいて、部分的な順序として表現されます。^[3]

因果一貫性は、プログラマの時間に関する直感に一致し、強い一貫性モデルよりも利用可能でありながら、結果的一貫性よりも有用な保証を提供するため、有用な一貫性モデルです。たとえば、分散データベースでは、因果一貫性は結果的一貫性とは対照的に、操作の順序付けをサポートします。^[4]また、因果一貫性は、キューやカウンターなどの抽象データ型の開発にも役立ちます。 ^[5]

時間と順序は私たちの直感にとって非常に基本的なため、因果一貫性を強制しないシステムについて推論することは困難です。しかし、多くの分散データベースは、直列化可能性を提供するものであっても、この保証がありません。^[6] Spannerは因果一貫性を保証しますが、強い一貫性も強制するため、パーティション化による可用性を回避します。因果一貫性を保証する利用可能なデータベースには、MongoDB やAntidoteDBなどがあります。

因果一貫性は、操作間の潜在的な因果関係を捉え、すべてのプロセスが因果的に関連する操作を共通の順序で実行することを保証します。言い換えれば、システム内のすべてのプロセスは因果的に関連する操作の順序に同意します。因果的に関連のない操作の順序については、同意しない場合があります。^[1]

以下の関係を定義しましょう。あるプロセスが書き込み操作 A を実行し、A を観察したある (同じまたは別の) プロセスが書き込み操作 B を実行した場合、A が B の原因である可能性があります。A は「潜在的に B を引き起こす」または「因果的に先行する」と言います。因果一貫性は、A が因果的に B に先行する場合、システム内のすべてのプロセスが B を観察する前に A を観察することを保証します。逆に、2 つの書き込み操作 C と D は、どちらも因果的に他方に先行しない場合は同時または因果的に独立していると言われます。この場合、プロセスは C を D の前に観察することも、D を C の前に観察することもできます。共有メモリの因果先行関係は、メッセージベースの通信のhappened-before 関係に関連しています。^[3]

したがって、システムが因果一貫性を提供するには、次の条件が満たされる必要があります。潜在的な因果関係によって関連付けられている書き込み操作は、システムの各プロセスによって因果関係の優先順位で認識されます。異なるプロセスは、異なる順序で同時書き込みを観察する場合があります。^[7]

因果一貫性モデルは、因果関係があるかどうかに関係なく、すべてのプロセスがすべての書き込み操作を共通の順序で観察することを保証する順次一貫性よりも弱い。 ^[8]しかし、因果一貫性は、単一のプロセスによって行われた書き込み操作のみが他の各プロセスによって共通の順序で観察されることを要求するPRAM一貫性よりも強い。 ^[9]したがって、システムが順次一貫性を持っている場合、因果的に一貫しているということになる。さらに、因果一貫性はPRAM一貫性を意味するが、その逆は当てはまらない。

因果一貫性の例を次に示します。^[10]

次のイベントシーケンスでは因果関係が尊重されます。

プロセス P2 は、プロセス P1 によって行われた以前の書き込み W(x)1 を観察し、読み取ります。したがって、2 つの書き込み W(x)1 と W(x)2 は因果関係があります。因果関係の一貫性のもとでは、すべてのプロセスは、W(x)2 を観察する前に、まず W(x)1 を観察します。2 つの書き込み操作 W(x)2 と W(x)3 は、読み取り操作が介在しないため同時実行され、プロセス P3 と P4 は異なる順序でそれらを観察 (読み取り) することに注意してください。

因果一貫性モデルは4つのセッション保証に細分化することができる。^[11]それらは以下のように要約できる。

• 書き込みの読み取り: プロセスが書き込みを実行すると、同じプロセスが後でその書き込みの結果を確認します。

• 単調な読み取り: プロセスによって観察される (読み取られる) 書き込みのセットは、単調に減少しないことが保証されます。

• 書き込みは読み取りに続く: あるプロセスが読み取りに続いて書き込みを実行し、別のプロセスが書き込みの結果を監視する場合、そのプロセスは読み取りも監視できます (上書きされていない限り)。

• 単調な書き込み: あるプロセスが書き込みを実行し、しばらくしてから別の書き込みを実行すると、他のプロセスは同じ順序でそれらを観察します。

シリアル化可能性とスナップショット分離のためのトランザクションセッション保証は、DaudjeeとSalemによって提案されています。^[12]

システムは、通信するプロセスのセットとして抽象化されます。プロセスが共有メモリに書き込むと、実装は、このイベントを他のプロセスに送信します (共有メモリ経由またはメッセージとして)。同時実行と障害のため、プロセスは任意の順序でイベントを受信する可能性があります。実装は、因果的にその前に発生するすべてのイベントが配信された場合にのみ、イベントを配信します (つまり、イベントをプロセスに表示します)。これには、メモリ アクセス間の因果関係を表す メタデータを実装で維持する必要があります。

簡単に言うと、実装には次の手順が含まれます。(1)すべてのプロセスで因果コンテキストメタデータを保持し、現在の状態に因果的に先行する更新を要約します。(2) プロセスがメモリを更新すると、更新イベントにそのプロセスの因果コンテキストのタグを付け、この更新に因果的に先行する更新を要約します。(3)更新イベントを受信したプロセスは、イベントのタグが受信側プロセスの因果コンテキストに因果的に先行する場合にのみ、そのイベントを配信できます。(配信の副作用として、受信側プロセスの因果コンテキストに新しいイベントを追加します。) それ以外の場合は、更新の受信が早すぎたため、イベントがコンテキストと一致するまでバッファリングされたままにする必要があります。その間、実装は不足しているイベントを受信するまで受動的に待機するか、ソースから能動的にフェッチします。

このアプローチにより、パーティション分割下でも可用性が実現します。^[13]

因果コンテキスト メタデータには、2 つの一般的な表現があります。1 つは、因果依存関係の明示的な依存関係グラフを維持することです。このようなグラフは任意の大きさに成長する可能性があるため、イベントは、その直前のイベントのみでタグ付けされることが多く、その推移的なイベントを特定するには、分散グラフ トラバーサルが必要です。もう 1 つは、プロセス (またはプロセス グループ) ごとに 1 つのエントリを持つベクトル クロックを維持し、プロセスまたはグループによって生成されたイベントの数をカウントすることです。この表現は固定サイズで、イベントの順序はベクトルの単純な比較によって推測できます。

完全なピアツーピアシステムでどのイベントが依存しており、どのイベントが同時実行されているかを正確に判断するには、メタデータのサイズがアクティブなライターの数に少なくとも比例する必要があります。^[14] しかし、同時実行性を正確に判断することは、一般的にやり過ぎです。因果一貫性は、因果的に依存するイベントが順番に配信されることのみを必要とします。2つの同時イベントが最終的に順序付けられるかどうかは問題ではありません。したがって、安全な近似技術を使用することで、サイズを任意に削減できます。^[15] 極限では、同時実行性を削除するというコストで、単一のスカラー（Lamportクロック^[3]）で十分です。メタデータのサイズは、通信トポロジを制限することによっても削減できます。たとえば、スター、ツリー、または線形トポロジでは、単一のスカラーで十分です。

因果一貫性の効率的な実装の探求は、非常に活発な研究分野です。