因果整合性
因果整合性または因果一貫性 （英: Causal Consistency）は、主要なメモリ一貫性モデルの1つである。並行プログラミングでは、並行プロセスが共有メモリにアクセスする場合、整合性モデルによって、どのアクセスが合法であるかを制限する。分散共有メモリや分散トランザクションにおける正しいデータ構造を定義するのに役立つ。
因果整合性は可用性と分断耐性を両立した上で構築可能である[1]。すなわち、プロセス間のネットワーク接続が機能していなくても（ネットワーク的に分断されていても）、プロセスがメモリを読み書きできる（メモリが利用可能な）非同期モデルである。パーティションの下では安全性とライブ性を両立できず、同期を必要とするため応答が遅くなる逐次整合性や線形性などの強力な整合性モデルとは対照的である。
因果整合性は、1990年代[2]に共有メモリモデルの弱い整合性モデルとして提案された。因果的整合性は、通信プロトコルにおける因果的ブロードキャストの概念と密接に関連している。これらのモデルでは、Lamportのhappened-beforeの概念に基づく潜在的な因果関係に基づいて、分散実行を部分的な順序として表現する[3]。
因果整合性による一貫性はプログラマの時間に関する直感に合致する。この意味で因果一貫性は結果一貫性よりも有用な保証を提供し、また強い整合性モデルと比較して利用可能な条件は緩くなっている。例えば分散データベースでは、結果一貫性とは対照的に、因果的一貫性は操作の順序付けをサポートしている[4]。
時間と順序は我々の直感にとって非常に基本的なものであるため、因果整合性を保証しないシステムを推論することは困難である。しかし、多くの分散データベースは、直列化可能性を提供するものでさえ、この保証を欠いている[5]。Spannerは因果一貫性を保証するが、強い一貫性も強制するため、分断下での可用性喪失を許容している。因果整合性を保証するデータベースとしては、MongoDBやAntidoteDBなどがある。
定義
[編集]因果整合性（因果一貫性）とは、操作間の潜在的な因果関係を捉え、すべてのプロセスが因果関係のある操作を共通の順序で観察することを保証するものである。言い換えれば、システム内のすべてのプロセスは、因果関係のある操作の順序に同意する。因果関係のない操作の順序については、プロセス間で意見が異なることがある。
ここで、次のような関係を定義する。あるプロセスが書き込み操作Aを行い、Aを観測した（同じまたは別の）プロセスが次に書き込み操作Bを行う場合、AがBの原因となる可能性があり、AがBを「潜在的に引き起こす」または「因果的に先行する」という。因果整合性は、AがBを因果的に先行させる場合、システム内のすべてのプロセスがBを観察する前にAを観察することを保証する。逆に、2つの書き込み操作CとDが、どちらも因果的に先行していない場合、並行、または因果的に独立という。共有メモリにおける因果的先行関係は、メッセージベースの通信におけるhappens-before関係と関連している。
つまり、潜在的な因果関係がある書き込み操作が、システムの各プロセスによって因果関係のある優先順位で見られる、という条件が成立する場合に、システムは因果整合性を提供する。異なるプロセスでは、同時書き込みを異なる順序で見ることができる。
因果整合性(因果一貫性)モデルは、因果関係の有無にかかわらず、すべてのプロセスがすべての書き込み操作を共通の順序で観察することを保証する逐次整合性（逐次一貫性）よりも弱い。しかし因果整合性は、1つのプロセスが行う書き込み操作のみを他の各プロセスが共通の順序で観察することを要求するPRAM整合性よりも強い。このことから、システムが逐次的に一貫している場合は、因果的にも一貫していることになる。さらに、因果整合性はPRAM整合性を暗示するが、その逆はない。
事例
[編集]因果関係の一貫性の例を挙げてみる。
因果関係は以下のイベントシーケンスで成り立つ。
| P1 : | W(x)1 | W(x)3 | |||
| P2 : | R(x)1 | W(x)2 | |||
| P3 : | R(x)1 | R(x)3 | R(x)2 | ||
| P4 : | R(x)1 | R(x)2 | R(x)3 |
プロセス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つのセッション保証に集約できる。それらは以下のようにまとめられる。
- Read Your Writes：あるプロセスが書き込みを実行した場合、同じプロセスが後でその書き込みの結果を観測する。
- Monotonic Reads：あるプロセスが観測した(読んだ)書き込みの集合は、単調に非減少することが保証されている。
- Writes Follow Reads：あるプロセスがリードの後にライトを実行し、別のプロセスがライトの結果を観測した場合、そのプロセスもリードを観測できる（上書きされていない限り）。
- Monotonic Writes: あるプロセスが書き込みを行い、しばらくしてから別の書き込みを行った場合、他のプロセスは同じ順序でそれらを観測する。
Daudjee and Salemによって直列性とスナップショット分離のトランザクション・セッション保証が提示されている。
実装
[編集]システムは、通信可能なプロセスの集合として抽象化されている。あるプロセスが共有メモリに書き込むと、実装はこのイベントを他のプロセスに（共有メモリ経由またはメッセージとして）送信する。並行処理や障害のため、プロセスは任意の順序でイベントを受け取る可能性がある。実装は、イベントに因果的に先行するすべてのイベントが配信された場合にのみ、イベントを配信する、つまりプロセスに見えるようにする。このためには、メモリアクセス間の因果関係を表すメタデータを維持する必要がある。
簡単に言うと、この実装には以下のステップが含まれている。(1) 現在の状態に因果的に先行する更新内容を要約するために、すべてのプロセスで因果関係のメタデータを維持する。(2) プロセスがメモリを更新する際、更新イベントにそのプロセスの因果関係をタグ付けし、この更新に因果的に先行する更新を要約する。(3) ある更新イベントを受け取ったプロセスは、そのイベントのタグが受け取ったプロセスの因果関係に因んで先行している場合に限り、そのイベントを配信することができる。(配信の副作用として、新しいイベントを受信プロセスの因果関係に追加する)。そうでなければ、更新の受信が早すぎて、イベントがコンテキストにマッチするまでバッファリングされたままでなければならない。その間、実装は欠落したイベントを受け取るのを受動的に待つか、ソースから積極的にフェッチする。
このアプローチにより，パーティション下での利用可能性が可能になる．
因果関係のメタデータには2つの一般的な表現方法がある。1つは、因果関係の依存関係グラフを明示的に保持する方法である。このようなグラフは恣意的に大きくなる可能性があるため、イベントにはその直前の前任者のみがタグ付けされることが多い。もう1つの方法は、プロセス（またはプロセスグループ）ごとに1つのエントリを持ち、そのプロセスまたはグループが生成したイベントの数をカウントするベクトルクロックを維持することである。この表現は固定サイズであり、イベントの順序はベクトルの単純な比較によって推測できる。
完全なピアツーピアシステムにおいて、どのイベントが依存していて、どのイベントが並行しているかを正確に判断するためには、メタデータのサイズは少なくともアクティブなライターの数に比例する。しかし、並行性を正確に判断することは、一般的にはやりすぎである。因果関係の一貫性は、因果関係に依存するイベントが順番に配信されることだけを必要とし、2つの同時イベントが最終的に順番になることは重要ではない。そのため、安全な近似技術を用いることで、サイズを任意に小さくすることができる。限界では、同時性を排除しても、単一のスカラ（ランポート・クロック）で十分である。また通信トポロジーを制限することで、メタデータのサイズを小さくすることができる。例えば、スター型、ツリー型、リニア型のトポロジーでは、単一のスカラーで十分である。
脚注
[編集]- ^ Zennou, R., Biswas, R., Bouajjani, A. et al. Checking causal consistency of distributed databases., Computing 104, 2181–2201 (2022). https://doi.org/10.1007/s00607-021-00911-3
- ^ Ahamad, M., Neiger, G., Burns, J. E., Kohli, P., & Hutto, P. W. (1995). Causal memory: Definitions, implementation, and programming. Distributed Computing, 9(1), 37-49.
- ^ Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558-565.
- ^ Perrin, M., Mostefaoui, A., & Jard, C. (2016, February). Causal consistency: beyond memory. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (p. 26). ACM.
- ^ K. Daudjee and K. Salem. Lazy database replication with ordering guarantees. In Int. Conf. on Data Engineering, pp. 424–435, Apr. 2004.