因果整合性 セッション保証

ウィキペディア

因果整合性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/20 16:50 UTC 版)

セッション保証

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

1. Read Your Writes：あるプロセスが書き込みを実行した場合、同じプロセスが後でその書き込みの結果を観測する。
2. Monotonic Reads：あるプロセスが観測した(読んだ)書き込みの集合は、単調に非減少することが保証されている。
3. Writes Follow Reads：あるプロセスがリードの後にライトを実行し、別のプロセスがライトの結果を観測した場合、そのプロセスもリードを観測できる（上書きされていない限り）。
4. Monotonic Writes: あるプロセスが書き込みを行い、しばらくしてから別の書き込みを行った場合、他のプロセスは同じ順序でそれらを観測する。

Daudjee and Salemによって直列性とスナップショット分離のトランザクション・セッション保証が提示されている。

実装

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

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

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

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

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