CAP定理｜分散システム

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：線形化可能性と逐次一貫性　|　関連：PACELC・結果整合性・分散システムとは・なぜ難しいか

要点（BLUF）

CAP定理：ネットワーク分断（Partition）が起きたとき、一貫性（C＝線形化可能）と可用性（A＝全要求に応答）は同時には満たせない。どちらかを諦める。
正しい読み方は「C・A・Pから2つ選ぶ」ではなく「Pは選べない（必ず起きる）→ 分断時にCかAか」。だから実質 CP か AP の二択。
重要な誤読：「常にCを諦める/Aを諦める」ではない。分断していない平時は両方とも得られる（その平時の取引は PACELC が扱う：PACELC・結果整合性）。

問題設定 ── 分断したら何を守るか

2つのノードがネットワーク分断で互いに通信できなくなったとします。ユーザがそれぞれに書き込み/読み込みを要求したとき、システムは究極の二択を迫られます。

flowchart TB
    P["ネットワーク分断が発生（Pは不可避）"] --> Q{"分断中の要求にどう答えるか"}
    Q -->|"古い/不整合を返さない=応答を断る"| CP["CP：一貫性を守り可用性を捨てる"]
    Q -->|"とにかく応答する=古い値もありうる"| AP["AP：可用性を守り一貫性を捨てる"]

モデル ── 3つの性質

C（Consistency）：ここでは線形化可能性（線形化可能性と逐次一貫性）。全ノードが同じ最新を返す。
A（Availability）：生きている全ノードが、有限時間で（エラーでなく）応答する。
P（Partition tolerance）：分断が起きてもシステムとして動き続ける。

定理の主張：分断中は C と A を同時に保てない。分断したノードに書かせれば（A）コピー間がずれる（Cを破る）。ずれを防ぐため応答を断れば（C）可用性が落ちる（Aを破る）。

正しさの観点 ── なぜ両立しないか（簡単な証明スケッチ）

ノード G1・G2 が分断されているとする。クライアントが G1 に x=1 を書く。次に G2 から read(x) する。

C を守るなら、G2 は最新（1）を返さねばならないが、G1 とは通信できない。最新を知る術が無いので、応答できない（A を破る）。
A を守るなら、G2 は何か返すしかなく、知っている古い値（0）を返す（C を破る）。

両立は原理的に不可能——これがCAPの核心です。

設計への翻訳 ── CP と AP

型	分断時の挙動	例
CP	不整合を返すくらいなら応答を断る（少数派は読み書き不可）	合意ベース（Raft）・ZooKeeper・etcd・分散ロック
AP	とにかく応答する（古い値・並行衝突を許し後で収束）	Dynamo系・Cassandra・クォーラム（R+W>N）緩め・DNS

選択基準：正しさが命（残高・在庫・ロック）なら CP、止まらないことが命（カート・SNS・計測）なら AP。

なぜ分散だと難しいか（直観）

分断は「遅延が無限大になった状態」とも言える。分散システムとは・なぜ難しいかの「遅いと死んだが区別できない」がここで効く。CAPは「通信できない相手と整合を保つことはできない」という、ほぼ自明だが見落としがちな事実を、設計判断に落とし込む道具です。

⚠️ よくある誤解・落とし穴

「C・A・Pから常時2つ選ぶ」→ 誤読。分断時の二択。平時は両方得られる。
「CA型システムがある」→ 分断は必ず起きる（Pは前提）。「CA」は分断を考えない単一マシン的状況の話で、分散では非現実的。
「AP＝一貫性ゼロ」→ 結果整合性（PACELC・結果整合性）は保たれる。読み修復や反エントロピー（ゴシップ・反エントロピー・故障検出（SWIM））で収束する。
「CPなら常に遅い」→ 平時のレイテンシは別問題。それを論じるのが PACELC。
「CのCは一貫性なら何でも」→ CAPのCは線形化可能性を指す。弱い一貫性は別の議論。

対応ラボ

なし（概念回）。AP側の重なり調整（R+W>N で一貫性を上げる）はクォーラム（R+W>N）のラボで実証します。