因果整合性

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

因果整合性は「パーティションの下でも利用可能」であり、プロセス間のネットワーク接続が機能していなくても、プロセスがメモリを読み書きできる非同期モデルである。パーティションの下では安全性とライブ性を両立できず、同期を必要とするため応答が遅くなる逐次整合性や線形性などの強力な整合性モデルとは対照的である。

因果整合性は、1990年代に共有メモリモデルの弱い整合性モデルとして提案された。因果的整合性は、通信プロトコルにおける因果的ブロードキャストの概念と密接に関連している。これらのモデルでは、Lamportのhappened-beforeの概念に基づく潜在的な因果関係に基づいて、分散実行を部分的な順序として表現する。

因果的整合性は、プログラマの時間に関する直感に合致し、強力な整合性モデルよりも利用しやすく、かつ最終的な整合性よりも有用な保証を提供するため、有用な整合性モデルである。例えば分散データベースでは、結果一貫性とは対照的に、因果的一貫性は操作の順序付けをサポートしている。

時間と順序は我々の直感にとって非常に基本的なものであるため、因果整合性を保証しないシステムを推論することは困難である。しかし、多くの分散データベースは、直列化可能性を提供するものでさえ、この保証を欠いている。Spannerは因果一貫性を保証するが、強い一貫性も強制するため、パーティション下での可用性がない。因果関係の一貫性を保証するデータベースとしては、MongoDBやAntidoteDBなどがある。

1. 定義
-----

因果整合性とは、操作間の潜在的な因果関係を捉え、すべてのプロセスが因果関係のある操作を共通の順序で観察することを保証するものである。言い換えれば、システム内のすべてのプロセスは、因果関係のある操作の順序に同意する。因果関係のない操作の順序については、プロセス間で意見が異なることがある。

ここで、次のような関係を定義します。あるプロセスが書き込み操作Aを行い、Aを観測したプロセスが次に書き込み操作Bを行う場合、AがBの原因となる可能性があり、AがBを「潜在的に引き起こす」または「因果的に先行する」という。因果的整合性は、AがBを因果的に先行させる場合、システム内のすべてのプロセスがBを観察する前にAを観察することを保証する。逆に、2つの書き込み操作CとDが、どちらも因果的に先行していない場合、並行、または因果的に独立という。共有メモリにおける因果的先行関係は、メッセージベースの通信におけるhappens-before関係と関連している。

つまり、潜在的な因果関係がある書き込み操作が、システムの各プロセスによって因果関係のある優先順位で見られる、という条件が成立する場合に、システムは因果整合性を提供します。異なるプロセスでは、同時書き込みを異なる順序で見ることができる。

因果整合性モデルは、因果関係の有無にかかわらず、すべてのプロセスがすべての書き込み操作を共通の順序で観察することを保証する逐次整合性よりも弱い。しかし因果整合性は、1つのプロセスが行う書き込み操作のみを他の各プロセスが共通の順序で観察することを要求するPRAM整合性よりも強い。このことから、システムが逐次的に一貫している場合は、因果的にも一貫していることになる。さらに、因果的整合性はPRAM整合性を暗示するが、その逆はない。

2. 事例
-----

因果関係の一貫性の例を挙げてみる。

因果関係は以下のイベントシーケンスで成り立つ。

プロセスP2は、プロセスP1が行った先の書き込みW1を観察、読み取る。したがって、2つの書き込みW1とW2は因果関係がある。因果整合性の下では、すべてのプロセスは、W2を観測する前に、まずW1を観測する。2つの書き込み操作W2とW3は、読み取り操作が介在していないため、同時進行しており、プロセスP3とP4は異なる順序でそれらを観察していることに注意すべきである。

3. セッション保証
----------

因果関係のある一貫性モデルは、4つのセッション保証に集約できる。それらは以下のようにまとめられる。

Read Your Writes：あるプロセスが書き込みを実行した場合、同じプロセスが後でその書き込みの結果を観測する。
Monotonic Reads：あるプロセスが観測した書き込みの集合は、単調に非減少することが保証されている。
Writes Follow Reads：あるプロセスがリードの後にライトを実行し、別のプロセスがライトの結果を観測した場合、そのプロセスもリードを観測できる。
Monotonic Writes: あるプロセスが書き込みを行い、しばらくしてから別の書き込みを行った場合、他のプロセスは同じ順序でそれらを観測する。Daudjee and Salemによって直列性とスナップショット分離のトランザクション・セッション保証が提示されている。

4. 実装
-----

システムは、通信可能なプロセスの集合として抽象化されている。あるプロセスが共有メモリに書き込むと、実装はこのイベントを他のプロセスに送信する。並行処理や障害のため、プロセスは任意の順序でイベントを受け取る可能性がある。実装は、イベントに因果的に先行するすべてのイベントが配信された場合にのみ、イベントを配信する、つまりプロセスに見えるようにする。このためには、メモリアクセス間の因果関係を表すメタデータを維持する必要がある。

簡単に言うと、この実装には以下のステップが含まれている。 現在の状態に因果的に先行する更新内容を要約するために、すべてのプロセスで因果関係のメタデータを維持する。 プロセスがメモリを更新する際、更新イベントにそのプロセスの因果関係をタグ付けし、この更新に因果的に先行する更新を要約する。 ある更新イベントを受け取ったプロセスは、そのイベントのタグが受け取ったプロセスの因果関係に因んで先行している場合に限り、そのイベントを配信することができる。。そうでなければ、更新の受信が早すぎて、イベントがコンテキストにマッチするまでバッファリングされたままでなければならない。その間、実装は欠落したイベントを受け取るのを受動的に待つか、ソースから積極的にフェッチする。

このアプローチにより，パーティション下での利用可能性が可能になる．

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

完全なピアツーピアシステムにおいて、どのイベントが依存していて、どのイベントが並行しているかを正確に判断するためには、メタデータのサイズは少なくともアクティブなライターの数に比例する。しかし、並行性を正確に判断することは、一般的にはやりすぎである。因果関係の一貫性は、因果関係に依存するイベントが順番に配信されることだけを必要とし、2つの同時イベントが最終的に順番になることは重要ではない。そのため、安全な近似技術を用いることで、サイズを任意に小さくすることができる。限界では、同時性を排除しても、単一のスカラで十分である。また通信トポロジーを制限することで、メタデータのサイズを小さくすることができる。例えば、スター型、ツリー型、リニア型のトポロジーでは、単一のスカラーで十分である。

5. 脚注
-----

6. 関連項目
-------

一貫性モデル 
結果整合性
線形化可能性
直列化可能性
逐次一貫性