# CAP定理 ## 定義 CAP 定理は、Eric Brewer によって定式化された、分散システムにおける一貫性(Consistency)・可用性(Availability)・分断耐性(Partition tolerance)の3特性の間のトレードオフを扱う定理である。ネットワークが分割され一部のメッセージが宛先に到達しなくなる状況(ネットワーク分断)が存在する中で、一貫性と可用性の両方を同時に保証するシステムを実装することはできない。実現できるのは、強力な一貫性を保証しベストエフォートの可用性を提供する **CP システム**(一貫性が失われた可能性のあるデータを提供する場合にはリクエストを失敗させる)、または可用性を保証しベストエフォートの一貫性を提供する **AP システム**(一貫性の条件を緩和しリクエストに応じる)のいずれかである。ここでのベストエフォートとは、正常時には意図的に保証を侵害しないが、ネットワーク分断発生時には保証を弱めたり違反したりすることが許容される、という意味である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2) CAP 定理が扱う一貫性・可用性は、それぞれもっとも強力な形(線形化可能性、およびすべてのリクエストに最終的に応答する能力)に限定される。可用性は障害のないノードが結果を戻すことを求め、一貫性はその結果が線形化可能であることを求める。CAP 定理は、ノードのクラッシュそのものより、ノードが相互に通信できなくなるネットワーク分断を議論の中心に据える点が特徴的である。ノードは分断されても一貫性のないリクエストに応答できるが、クラッシュした場合はまったく応答しない。CAP は三角形として図示されることがあるが、一貫性と可用性のバランスは調整できても、分断耐性は現実問題として調整することも入れ替えることもできない特性である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2, §11.2.1) **PACELC 定理**は CAP を拡張したもので、ネットワーク分断が発生すると一貫性と可用性の間で選択が行われる(PAC)一方、分断がない正常時(Else, E)でも、レイテンシと一貫性の間で選択を行う必要があると述べる。分断の有無にかかわらず「同期コストと一貫性のトレードオフ」が常に存在することを CAP より広い視野で捉え直したものである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2) **収穫(harvest)と収量(yield)**は、CAP のトレードオフを絶対的な言葉から相対的な言葉に移すための調整可能なメトリクスである。収穫は問い合わせの完了をどう定義するか(一部ノードが使用不可でも部分的な結果を返すか)を、収量は正常に完了したリクエスト数を試行総数と比較した割合(アップタイムとは異なる)を表す。収量を増大する方法の1つは、問い合わせの結果を利用可能なパーティションからのみ返すことである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2.2) > [!note] CAP における「一貫性」の定義は、ACID における一貫性の定義とかなり異なる。ACID の一貫性はトランザクションによってデータベースがある有効な状態から別の有効な状態に変化し、一意性制約や参照整合性などの特性が維持されることを指す。CAP における一貫性は、操作がアトミックであること(全体として成功するか失敗するか)と、操作がデータを一貫性のない状態のままで放置しないことを意味する。CAP における可用性も、実行時のレイテンシに制限を設けない点、すべての障害の発生しないノードがすべてのリクエストに応答することを必要としない点で、一般的な高可用性の議論とは異なる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2.1) ## 横断的知見 - 未収載(2ソース目以降で充実させる)。 ## 未解決の問い - CAP 定理が対象とする「一貫性」は線形化可能性という単一の一貫性モデルに限定されるが、逐次一貫性や因果一貫性のようなより弱いモデルを採用した場合、CAP のトレードオフはどのように緩和されるか。[[線形化可能性]] concept の一貫性モデル階層との突き合わせが必要。 - PACELC のレイテンシと一貫性のトレードオフ(E)は、[[クォーラムベースレプリケーション]] concept が扱う R + W > N の調整可能な一貫性とどこまで数理的に同型か。 - 収穫と収量というメトリクスは、実運用の SLO・SLI 設計([[サービスレベル目標]]等)にどこまで応用されているか。 ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] - 概念: [[線形化可能性]] / [[結果整合性]] / [[クォーラムベースレプリケーション]] / [[分散システム障害]] ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2 悪名高い CAP, §11.2.1 注意が必要な CAP の使用, §11.2.2 収穫と収量