コンピューターサイエンス：アルゴリズム / OS / ネットワーク / DB
CAP 定理
CAP 定理
このレッスンで分かること
- CAP 定理の 3 つの性質（Consistency / Availability / Partition tolerance）
- 「3 つのうち 2 つ」の本当の意味
- CP 系・AP 系それぞれの代表 DB
CAP 定理 とは
Consistency / Availability / Partition tolerance の同時達成不可性。
CAP 定理とは
CAP 定理 は 2000 年に Eric Brewer が提唱し、2002 年に Gilbert と Lynch が証明した分散システムの基本原理です。
主張は次の通りです。
ネットワーク分断が起きたとき、Consistency (一貫性) と Availability (可用性) を 同時に満たすことはできない。
3 つの頭文字は次のものです。
- C (Consistency) — どのノードから読んでも常に最新の同じ値が返る
- A (Availability) — どのノードもリクエストに必ず応答する
- P (Partition tolerance) — ネットワーク分断が起きても動き続ける
「3 つのうち 2 つ」の誤解
よく「CAP は 3 つのうち 2 つを選ぶ」と説明されますが、これは正確には間違いです。ネットワーク分断 (P) は避けられない ので、実質的には次の二択になります。
- CP 系 — 分断時に 一貫性を取り、可用性を犠牲 にする
- AP 系 — 分断時に 可用性を取り、一貫性を犠牲 にする
CA（一貫性 + 可用性 + 分断なし）は 単一マシンの DB のことで、分散システムでは選べません。
分断が起きるとどうなるか
3 ノードのクラスタを考えます。ネットワーク分断で 1 ノードだけ孤立しました。
クライアントが Node C に書き込みを送ったとき、CP 系と AP 系で挙動が違います。
CP 系の挙動
「他のノードに同期できないなら書き込めない」と判断し、エラーを返します。一貫性は守られますが、Node C のクライアントは何もできません。これが 可用性の犠牲 です。
AP 系の挙動
「とりあえず Node C のローカルに書き込む。後で復旧したら他と同期する」と判断します。Node C のクライアントは成功しますが、Node A / B のクライアントは古い値を見ます。これが 一貫性の犠牲 で、後でデータの衝突を解決する必要があります。
代表的な DB の分類
| DB | 分類 | 備考 |
|---|---|---|
| MongoDB (デフォルト) | CP | Primary が落ちると一時的に書き込み停止 |
| Cassandra | AP | 結果整合性、衝突は last-write-wins |
| DynamoDB | AP | 設定で CP 寄りにも可 |
| Riak | AP | クライアント側で衝突解決 |
| HBase | CP | 強一貫性、リージョンサーバ単位で可用性低下 |
| etcd / ZooKeeper | CP | コンセンサスで一貫性を厳守 |
| Spanner / TiDB | CP | TrueTime / Raft で広域 CP を実現 |
「自分の DB は CP か AP か」を知っておくと、障害時の挙動が予測できる。
CAP は二者択一ではなくスペクトラム
実際は「CP」「AP」が二極化しているわけではなく、設定で調整できる DB が多いです。
Cassandra の Consistency Level を例にすると次のようになります。
ONE— 1 ノードが応答すれば成功（AP 寄り、最も速い）QUORUM— 過半数のノードが応答すれば成功（バランス）ALL— 全ノードが応答すれば成功（CP 寄り、最も遅い）
QUORUM 設定なら 5 ノードで 3 ノード応答が必要。これは「R + W > N」というクォーラム式で書け、強整合性を実現できます。
PACELC 定理
CAP は「分断時 の挙動」を語るだけです。実は 分断していない平時 にも選択があります。これを補完するのが PACELC 定理 です。
Partition があれば A vs C を選ぶ。Else (平時) は L (Latency) vs C (Consistency) を選ぶ。
平時でも「同期書き込みで遅延を取るか、非同期で速さを取るか」のトレードオフが続きます。
| DB | 分断時 | 平時 |
|---|---|---|
| Cassandra | AP | EL（遅延優先） |
| MongoDB | CP | EC（一貫性優先） |
| DynamoDB | AP | EL |
| Spanner | CP | EC |
ACID と CAP の関係
ACID は単一 DB のトランザクション特性、CAP は分散システムの特性です。混同しがちですが別の階層です。
- ACID の C — 整合性制約 を守ること
- CAP の C — 複数ノード間で同じ値 を見せること
分散 DB で ACID を提供するのは難しいですが、Spanner や TiDB が分散 2PC とコンセンサス（Paxos / Raft）で実現しています。これが NewSQL の核心です。
実務での判断軸
選ぶときは次の問いに答えます。
- ネットワーク分断が起きたとき、古いデータが見える のは許容できるか
- それとも 書き込めなくなる 方が許容できるか
- 平時のレイテンシは何 ms 以下でないと困るか
金融や予約は CP、SNS のいいねやキャッシュは AP、というのが大まかな目安です。
やってみよう
- 自分のプロジェクトの主要機能を「CP 寄り / AP 寄り」に分類する
- いいね数、決済、メッセージ、ユーザープロフィール、それぞれの要件を書き出す
- AWS DynamoDB の
ConsistentReadオプションで挙動が変わることを確認する
よくある質問
Q. CAP の C / A / P は何の頭文字ですか？
A. Consistency（一貫性）、Availability（可用性）、Partition tolerance（分断耐性）の頭文字です。分散システムは P を捨てられないため、実質的には CP と AP のどちらを取るかという選択になります。
Q. CAP と BASE の関係は？
A. BASE（Basically Available, Soft state, Eventually consistent）は CAP で AP を選んだ場合の設計指針です。最終的に整合性が取れる「結果整合性」を許容することで可用性を最大化する考え方で、NoSQL の多くがこれに該当します。
Q. AP と CP の代表例を教えてください
A. AP は Cassandra、DynamoDB、Couchbase などで、書き込み可用性を優先します。CP は HBase、Zookeeper、etcd など、不整合を避けるため一部ノード停止時にサービス停止を受け入れる設計です。要件に応じて使い分けてください。
次のレッスン
次は 結果整合性 で、Consistency / Availability / Partition tolerance の同時達成不可性 を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- CAP 定理 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. CAP 定理 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン