概要
Eventual Consistency（結果整合性）はレプリケーションラグにより「自分が書き込んだデータが読めない」といったような因果関係がおかしくなるケースがあります。
そこでより一貫性の強いものとしてCausal Consistency（因果一貫性）があります。
※Casual（カジュアル）ではなくCausal（コーザル）です
文字通り因果関係に対する一貫性を保証するもので、以下の４つに分類されます。
- Read your writes
- Monotonic read
- Monotonic write
- Write follow reads
これらについて図を交えて説明していきます。
Causal Consistency
Read your writes (read after write)
読んで字のごとく、自身の書き込みを読み取る際の一貫性の保証です。
保証されていないケース
以下のように書き込んだ（プロフィールの更新）もののレプリケーションラグで反映が遅れたノードから読み取ってしまうと矛盾が発生します。
対応方法
よくある対応方法としては、Primaryで読み取ることで一貫性を保証します。
ただしこの方式の場合はレプリカによる負荷分散ができないため、上図のように自身のデータ(userA->userA)はPrimaryから/他ユーザのデータ(userB->userA)はSecondaryから、などの考慮が必要です。
userBは最新のデータを取得できませんが、userB自体が書き込んではいないので混乱はしません（＝一貫性は保証できている）。
Monotonic Read
Monotonicは単調増加 or 単調減少のことをいいます。イメージとしては以下で、
ref: https://en.wikipedia.org/wiki/Monotonic_function
３次関数のようにyの値が巻き戻るものはMonotonicとはいいません。
ref: https://en.wikipedia.org/wiki/Monotonic_function
Monotonic Readというのは誰かが連続して行った複数の読み取りにおいて、時間が巻き戻らないことを保証します。
保証されていないケース
レプリケーションラグによって１回目の読み取りと２回目の読み取りで因果関係が崩れることがあります。
２回目の方が未来に実行しているのに関わらず、レプリケーションラグによって１回目よりもデータが過去の状態になってしまっています。
対応方法
よくある対応方法としては、同じノードから取得することで一貫性を保証します。
Monotonic Write
Monotonic Writeは誰かが連続して行った複数の書き込みにおいて、時間が巻き戻らないことを意味します。
保証されていないケース
レプリケーションラグとノード障害によって１回目の書き込みが反映されないケースがあります。
この図では書き込み後、データがSecondaryに反映される前にPrimaryが落ち、未反映のノードがPrimaryに昇格したケースです。
本来+50、+100としたので合計で250になるはずですが、１回目の書き込みが消えてしまい200となっています。
対応方法
対応方法の１つとしては
MongoDB Write Concern - Carpe Diem
で説明したw: "majority"のようにデータをdurableにすることです。
仮にack前にPrimaryが落ちた場合はエラーが返るので、クライアントとしては書き込みが失敗したので一貫性を保証できていると言えます。
Writes follow reads
Writes follow readsは読み取ったデータが書き込む際のデータに対して一貫性を持っているかどうかです。
保証されていないケース
例えば上図ではPrimaryが落ちたことで最初にreadした際にあったコメントが消え、writeした返信のみが残り矛盾が発生してしまうケースです。
対応方法
こちらもノードのダウンのケースであれば、データをdurableにすることで解消できるでしょう。
より汎用的なソリューション
それぞれのケースで対応方法を紹介しましたが、どれもサービス側でケースに応じた１つ１つの対応が求められます。
また挙げた例以外にもネットワーク分断などによって因果関係が狂うケースがあり、その場合は異なる対応が求められます。
安直に考えると物理時間(timestamp)で比較することで因果関係を保証しようとしますが、分散システムでは各ノードの物理時間を完全に一致させることは困難で因果関係の保証はできません。
そこでより汎用的な解決策としてLamport ClockやVector Clockがあります。
以下の筑波大の講義資料で分かりやすく説明されています。
Lamport Clockを適用してみる
簡単のため単純化した上でLamport Clockを各ケースに適用してみます。
- WriteイベントでclusterTimeを単調増加させる
- プロセス間（今回はノード間）を移動するメッセージと比較してclusterTimeを増加させる
というLamport Clockを使い、
- クライアントは受け取ったclusterTimeをそのセッションの間渡し続ける
- read時はclusterTimeがクライアントの渡す時間より大きくなるまでブロックする
- write時はclusterTimeがクライアントの渡す時間より小さければエラーにする
というロジックを組み合わせます。
Read your writeの場合
Read your writeに適用すると以下のようになります。
レプリケーションが反映されるまで待つ（ブロックされる）ことで因果関係を保証できています。
Monotonic readの場合
Monotonic readに適用すると以下のようになります。
こちらもレプリケーションが反映されるまで待つ（ブロックされる）ことで因果関係を保証できています。
Monotonic writeの場合
Monotonic writeに適用すると以下のようになります。
因果関係がおかしいことが検知できたのでエラーとし、新しいセッションで正しい因果関係で実行し直しています。
durableであれば
データがすでに伝播されていればclusterTimeのインクリメントも伝播しており、セッションの条件を満たすのでエラー無く実行されます。
Writes follow readsの場合
Writes follow readsに適用すると以下のようになります。
こちらも因果関係がおかしいことが検知できたのでエラーとし、新しいセッションで実行し直しています。
新しいセッションではコメントAが無くなっていることに気づくので、それの返信を書くことはなくなり因果関係の矛盾は起きません。
まとめ
Causal Consistencyが保証されないケースとその対策について説明しました。
Lamport ClockやVector Clockについては分散システム側が対応している必要がありますが、対応していればCausal Consistencyを保証できるのでデータ一貫性を保ちたい場合は積極的に使っていくと良いでしょう。
