因果整合性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/20 16:50 UTC 版)
因果整合性は可用性と分断耐性を両立した上で構築可能である[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は異なる順序でそれらを観察（読み取り）していることに注意すべきである。
- ^ 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.
- 因果整合性のページへのリンク
