Highly Available Transactions Virtues and Limitations (2013)
January 30, 2025概要
CAP定理の一貫性、可用性、ネットワークの分断耐性のトリレンマは、1つを完全に切り捨てるのではなく、現実には、3つの性質の優先順位をつける問題になる。 システムの一貫性と可用性の均衡を設計するときは、求める一貫性に対して実現できる可用性を知らないといけない。 Highly Available Transactions Virtues and Limitations は、既存の一貫性を両立できる可用性の水準と対応させ、両性質の強さで一貫性と可用性のペアを半順序関係に整理した。
可用性
可用性をhigh availabilityとsticky availabilityの二種類に分け、この2つを一貫性と対応させる。 どちらの可用性も無期限のネットワーク分断を想定する。
High availabilityは、サーバー間で任意かつ無期限のネットワークの分断がありえる場合でも、すべてのクライアントがリクエストの送り先の正常なサーバから応答を受けとれることを保証する。 応答にかかる時間は問わない。また、この定義は過去に紹介したBrewer’s conjecture and the feasibility of consistent, available, partition-tolerant web servicesに由来する。
Sticky availabilityは、あるクライアントによる以前の全操作を反映したレプリカがあり、そのレプリカにトランザクションを実行したとき、やがてクライアントに応答が返ることを保証する。 Sticky availabilityをみたすために、クライアントに読み書きをキャッシュさせて、クライアントをサーバーとみなしてもよい。
一貫性と可用性のペアの半順序関係
High availabilityとsticky availabilityには順序関係がある。
High availabilityを備えるシステムは、sticky availabilityも満たす。
しかし、逆は成立するとは限らない。
以下に文献から引用した半順序関係の図を示す。
単語は一貫性を、枠は可用性を意味する。
枠がない一貫性はhigh availabilityを満たし、 四角で囲まれた一貫性はsticky availabilityを意味する。
楕円の一貫性はavailabilityを保証しない。
一貫性と可用性はトレードオフの関係にあるので、より上にあるほど一貫性は強いが可用性は低く、下にあるほど高可用性はあるが一貫性は弱い。
文献よりも、分散システム向けのフォールトインジェクションフレームワークjepsenのウェブサイトにある半順序関係と一貫性の非形式的な説明が参考になるかもしれない。
文献にも以下の表や一貫性の説明はあるが、ウェブサイトほど解説に紙面が割かれておらず、また、解説を原典の文献にゆずる箇所が多い。
ウェブサイトが更新されたときのために、1段階ごとに可用性が上下するパス、WFR (Writes Follow Reads), causal, linearizableで半順序関係の簡潔な説明を残す。 WFRは、プロセスがトランザクション\(T_1\)の後にトランザクション\(T_2\)をコミットした場合に、別のプロセスは、\(T_2\)の結果を\(T_1\)の結果よりも先に参照できないことを保証する。 causal consistencyは、すべてのプロセスが因果関係のあるの操作の同一な前後関係を観察していることを保証する。 一方、因果関係のない操作間はプロセスごとに異なる順序で観測されうる。 線形化可能性は、読み書き操作がアトミックであるように観測でき、かつ、すべてのプロセスの実行を仮に直列化したときと同じ実行結果になることを保証する。