分散データベースは「整合性」「可用性」「ネットワーク分断耐性」という3つの性質のうち、同時に満たせるのは最大2つだけだということが知られています。これがCAP定理です。本記事ではCAP定理が指す3つの性質、なぜ同時には2つしか取れないのか、そしてその結果として生まれる CA / CP / AP という3つの分類と、各データベースプロダクトがどこに位置するかを整理します。
応答速度×スケール方式による別の分類軸については『応答速度×スケール方式によるデータベース分類: RDBがスケールアウトしない理由とNoSQLの3つの妥協』を参考にしてください。
CAP定理とは
CAP定理は2000年に Eric Brewer 氏が PODC 基調講演で提唱し、2002年に Gilbert と Lynch によって学術的に証明された定理です。「分散システムでは Consistency（整合性）・Availability（可用性）・Partition tolerance（分断耐性）の3つを同時に満たすことはできず、最大2つまでしか選べない」という主張です。
3つの性質はそれぞれ以下を意味します。
- C（Consistency, 整合性）はクラスタ内の全ノードで同時に同じデータが見える状態。強整合性（書いた直後に読むと必ず最新値が返ってくる）と同義
- A（Availability, 可用性）は一部のノードに障害が起きても処理が止まらず、リクエストに応答できる状態
- P（Partition tolerance, 分断耐性）はノード間のネットワークが分断されても、システム全体としては正しく動作する状態
なぜ2つしか取れないのか
CAP定理の核心は ネットワーク分断（P）が起きたときに何が起きるか にあります。
クラスタを構成するノード間のネットワークが分断されると、ノード群は「Aグループ」と「Bグループ」のように複数のサブクラスタに分かれます。このときシステムは以下の二者択一を迫られます。
- Cを優先する場合は、AグループとBグループの両方で読み書きを受けると整合性が崩れるため、少なくとも片方は読み書きを停止して整合性（C）を守る。結果としてその側は応答できなくなり、可用性（A）を失う。
- Aを優先する場合は、両方のグループで読み書きを継続して可用性（A）を守る。結果として両グループのデータが一時的にズレ、整合性（C）を失う。
つまりPが発生した時点でCとAは両立できず、どちらかを諦めることになります。これがCAP定理の本質です。
CA / CP / AP の3分類
CAP定理から導かれる3つの組み合わせと、それぞれの代表的なシステム構成を見ていきます。
CA: 整合性と可用性を取り、分断耐性を諦める
C（整合性）と A（可用性）を取り、P（分断耐性）を持たないシステムです。典型例は Active-Standby 構成の RDB（OLTP）で、書き込みは Active ノード1台、Standby は待機系という構成です。
- 読み書きする箇所が Active 1箇所なので、整合性（C）は自然に保たれる
- Active が落ちても Standby に切り替えれば処理は継続できる（可用性 A）
- ただし Active と Standby を繋ぐネットワークが分断されるとスプリットブレイン（両方が「自分が Active だ」と思い込む状態）が発生し、書き込み競合でデータを破壊するか、両方 Standby になって読み書き不能になる
このため CA 構成のクラスタは「ネットワークが絶対に切れない」前提で組み、間の通信を冗長化した専用線で守るのが定石です。CA は P が起きない前提で動くシステムと理解するとわかりやすいです。
代表プロダクトは PostgreSQL、MySQL、Oracle Database（いずれも Active-Standby のレプリケーション構成時）です。
CP: 整合性と分断耐性を取り、可用性を諦める
C（整合性）と P（分断耐性）を取り、A（可用性）を諦めるシステムです。クラスタを構成する全ノードで同じデータを見ることができ、ネットワーク分断が起きてもデータの整合性は壊れません。ただし分断中は読み書きができなくなることを許容します。
典型的な実装は以下の通りです。
- クラスタを奇数台で構成する（多数決のため）
- ネットワーク分断が起きたら、過半数より多くのノードと通信できる側を「生きているクラスタ」として動作継続させる
- 過半数を取れなかった側は読み書き不能（または読み取りのみ）になる
過半数が見えない側のクライアントから見るとシステムが応答しなくなる（可用性が下がる）ため、「Aを諦めた」と表現されます。
代表プロダクトは Redis（Sentinel/Cluster）、MongoDB、HBase、Couchbase（通常のレプリケーション）です。
AP: 可用性と分断耐性を取り、整合性を諦める
A（可用性）と P（分断耐性）を取り、C（整合性）を諦めるシステムです。クラスタ内の全ノードで読み書きでき、ネットワークが分断されてもどのノードも読み書きを止めません。
イメージとしては Git のような分散リポジトリが近いです。クライアントが各々のリポジトリを持ち、ネットワークから孤立していても自分のリポジトリには読み書きできます。同じ箇所に対して複数クライアントが書き込めば競合が発生しますが、それは分散システムの前提として後から解消するルールが用意されています。
そのため AP 構成では「同じデータを複数のノードが別々に書き換えた」「分断中の読み取りで古いデータが返ってきた」といった事態が起こりますが、システム自体は止まりません。整合性は 結果整合性（最終的には全レプリカが同じ値に収束する）として弱く保たれます。
代表プロダクトは Cassandra、CouchDB、Riak、Couchbase（クロスデータセンタレプリケーション時）、Amazon DynamoDB です。
CA / CP / AP の比較表
| 区分 | 取れる性質 | 諦める性質 | 分断時の挙動 | 整合性モデル | 代表プロダクト |
|---|---|---|---|---|---|
| CA | C・A | P | 想定しない（ネットワーク冗長化で回避） | 強整合性 | RDB（OLTP）の Active-Standby 構成 |
| CP | C・P | A | 過半数を取れない側は停止 | 強整合性 | Redis, MongoDB, HBase, Couchbase（通常レプ） |
| AP | A・P | C | 全ノードで読み書き継続（後で競合解消） | 結果整合性 | Cassandra, CouchDB, Riak, DynamoDB, Couchbase（XDCR） |
「3つから2つを選ぶ」というCAP定理の説明は単純化されすぎている
実運用ではネットワーク分断（P）は避けようがない事象として扱う必要があります。クラウドのアベイラビリティゾーン跨ぎ・データセンタ跨ぎでは分断はゼロにできず、CA を選ぶ＝Pが起きないと信じる、という選択は分散システムでは現実的ではありません。
このため現代の分散データベースの議論では、Pは前提として固定し、「分断が起きたときに C と A のどちらを取るか」を CP / AP の選択として捉える整理の仕方が一般的です。CA に分類される RDB の Active-Standby 構成も、内部的には「分断が起きたら片方を停止する」運用ルールで P を回避しているにすぎません。
CAP定理を拡張したPACELC定理
CAP定理は 分断時のパターン だけを扱います。「分断（P）が起きたときに可用性（A）と整合性（C）のどちらを取るか」というトレードオフです。
しかし実際には分断していない平常時にも、レイテンシ（L: Latency, 応答時間）と整合性（C）のトレードオフが存在します。たとえば書き込みを「全レプリカに送って全員から完了応答を受け取ってからクライアントに応答を返す」方式（同期レプリケーション）にすると、どのレプリカから読んでも最新値が見える代わりに、レイテンシは最も遅いレプリカに引きずられて伸びます。逆に「1ノードに書いた時点でクライアントに応答を返し、他レプリカへは後から非同期で伝播させる」方式にすると、レイテンシは短くなりますが、伝播完了前に他レプリカから読むと古い値が返ってきます。
このように平常時にも レイテンシ（L）と整合性（C）のトレードオフ が存在しますが、CAP定理ではこれが捉えられません。そこで分断時のパターンと平常時のパターンの両方を組み合わせて分類するように拡張したのが PACELC定理（Daniel Abadi, 2010）です。
PACELCは頭字語を以下のように分解して読みます。
- Partition（分断時）には A（可用性）か C（整合性）
- Else（それ以外＝平常時）には L（レイテンシ）か C（整合性）
| 分類軸 | CAP定理 | PACELC定理 |
|---|---|---|
| 分断時（P） | A か C を選ぶ | A か C を選ぶ |
| 平常時（E） | （対象外） | L か C を選ぶ |
表記は PA/EL のように「分断時の選択 / 平常時の選択」を並べます。たとえば PA/EL は 分断時に A（可用性）を選び、平常時に L（レイテンシ）を選ぶ という意味です。
ここで注意したいのは、A と L は別の性質だという点です。A は「分断時に応答を止めない」性質、L は「平常時に応答を遅らせない」性質です。ただしどちらも「整合性 C を諦める代わりに、応答性を優先する方向」にあり、選び方の傾向が揃いやすいので、PA/EL をまとめて「速さ重視のシステム」と表現できます。同様に PC/EC は分断時も平常時も C（整合性）を取るシステムで、まとめて「整合性重視のシステム」になります。
組み合わせは論理的には4通り（PA/EL・PA/EC・PC/EC・PC/EL）ですが、実用上は PA/EL・PA/EC・PC/EC の3パターン が中心です。PC/EL は「分断時は整合性を取るのに平常時はレイテンシを優先する」という一貫性のないトレードオフになるため、実例はほぼ見られません。
3パターンの位置づけは以下のとおりです。
- PA/EL（速さ重視）は分断時も平常時も応答性（A・L）を優先し、整合性は結果整合性として弱く保つ
- PA/EC（中間）は分断時はAを取って応答を継続するが、平常時はCを取り、レイテンシが多少伸びても整合性を維持する
- PC/EC（整合性重視）は分断時も平常時もCを取り、応答が止まる／遅くなることを許容する
| プロダクト | PACELC | 分断時 / 平常時 |
|---|---|---|
| Cassandra, DynamoDB, Riak | PA/EL | 分断時はA（可用性）、平常時はL（レイテンシ）を取る（どちらもCを諦めて応答性を優先） |
| PostgreSQL（同期レプリケーション） | PC/EC | 分断時も平常時もC（整合性）を取る |
PACELC を加えると CAP よりも分類のパターン数が増えるため、実装の特性をより細かく見分けられます（例: AP系のシステム同士でも、平常時に L 重視か C 重視かが違う）。データベースを技術選定する場面では、CAP の CA / CP / AP に加えて、平常時のレイテンシと整合性の調整可能性（書き込みコーラム数、読み取りコーラム数など）も合わせて見るのが実務的です。
なお個別プロダクトのPACELC分類は設定（書き込みコーラム数、読み取り整合性レベルなど）やバージョンによって変わりうるため、上の表はあくまで「典型的な使い方の場合」の例です。
各NoSQLプロダクトの整合性オプション・トランザクション対応範囲・落とし穴の個別整理は『主要NoSQLプロダクトリファレンス: Redis・Cassandra・DynamoDB・MongoDB・Neo4j を中心に』で扱っています。「強整合性が必要な決済」「結果整合性で十分なIoT時系列」のようにユースケース起点で候補プロダクトを逆引きする整理は『ユースケース別NoSQL選定ガイド: 「こういうときはどのNoSQL？」を逆引きする』を参照してください。
まとめ
- CAP定理は分散システムにおいて C（整合性）・A（可用性）・P（分断耐性）のうち最大2つしか同時に満たせないという定理
- 結果として分散DBは CA / CP / AP のいずれかに分類される
- CAはネットワーク分断を起こさない前提で組む。RDB（OLTP）のActive-Standbyが典型
- CPは分断時に過半数を取れない側を停止して整合性を守る。Redis・MongoDB・HBaseなど
- APは分断時も全ノードで読み書きを継続し、整合性は結果整合性として弱く保つ。Cassandra・DynamoDB・Riakなど
- 現代の分散システムでは P は事実上避けられないため、CP / AP の選択として理解する方が実用的
- CAP定理は分断時のパターンしか分類しないが、PACELC定理はそれに「平常時はLatency重視かConsistency重視か」を追加して分類軸を増やしたもので、CAP では同じ分類になるシステム同士の違いも見分けられる
参考
- Eric Brewer, “Towards Robust Distributed Systems” (PODC 2000 Keynote)
- Daniel Abadi, “Consistency Tradeoffs in Modern Distributed Database System Design” (2012)