なぜCAPの3つを同時に満たせないのか

まず3つの性質を正確に定義する。Consistencyとは、すべての操作が、その呼び出しから応答までの間のある一点で原子的に実行されたかのように振る舞い、かつその順序が実時間の順序と矛盾しないことである。これはlinearizabilityと呼ばれる性質であり、RDBMSのACIDにおけるC（整合性制約の充足）とは異なる概念である。直感的には「どのノードに読みに行っても、完了済みの最新の書き込みが反映されている」という保証だと思えばよい。Availabilityとは、障害の起きていないすべてのノードが、すべてのリクエストに対して妥当なレスポンスを返すことである。「システム全体として応答する」ではなく「個々の非障害ノードが必ず応答する」という、一般的な可用性のイメージよりも強い条件である点に注意が要る。Partition Toleranceとは、ネットワーク分断（ノード間の通信が任意に遅延・喪失する状態）が発生してもシステムが動作し続けることである。

ここで決定的に重要な事実がある。現実のネットワークではパーティションは必ず起こりうるということだ。物理的なケーブルの断線、スイッチの故障、データセンター間の接続障害、あるいはGCの長時間停止による実質的な通信不能など、分散システムを運用する限りネットワーク分断は避けられない前提条件である。したがってPartition Toleranceを「捨てる」という選択肢は、分散システムである限り現実的に存在しない。CAP定理の本質的な問いは「パーティションが発生したとき、ConsistencyとAvailabilityのどちらを犠牲にするか」である。

では、なぜパーティション発生時にCとAを同時に保てないのか。これは思考実験で端的に示せる。2台のノードN1とN2がレプリケーションで同じデータを持つ分散システムを考える。いまN1とN2の間のネットワークが分断されたとする。この状態でクライアントがN1にデータを書き込んだ。直後に別のクライアントがN2から同じデータを読み取ろうとする。ここで起こることを考える。

Consistencyを守ろうとすると、N2はN1の最新の書き込みを反映したデータを返さなければならない。しかしネットワークが分断されているのでN1からN2へのレプリケーションは届かない。N2が正確なデータを返す方法がない以上、N2は「応答しない（エラーを返す、タイムアウトする）」という選択をするしかない。これはAvailabilityの放棄を意味する。

逆にAvailabilityを守ろうとすると、N2はリクエストに対して何らかの応答を返さなければならない。しかし手元にあるのは分断前の古いデータだけである。N2は古いデータを返すことになり、N1に書き込まれた最新の値とは異なる結果をクライアントに返す。これはConsistencyの放棄を意味する。

「パーティションが起きたらシステム全体を停止する」という第三の経路もありうるが、それは分断時にシステムが動作し続けられていないのでPartition Toleranceの放棄にほかならない。

この3通りしかないことが、CAP定理の核心である。ネットワーク分断時に、最新のデータを持たないノードができてしまうことは物理的に避けられない。そのノードに対するリクエストをどう扱うかには「正しいデータがないので応答しない（C優先、A放棄）」か「古くてもいいから応答する（A優先、C放棄）」の二択しかない。両方を同時に実現する経路が物理的に存在しないのである。情報の伝搬には時間がかかり、分断中はその伝搬が不可能になる。この物理的制約がCAP定理の根底にある。

現実のシステム設計では、この二択は常時適用されるものではなく、パーティション発生時にのみ顕在化する。通常時（ネットワークが正常なとき）はCもAも同時に達成できる。パーティションは一時的なイベントであり、その間だけCかAのどちらかが劣化する。したがって設計判断は「パーティション中にシステムをどう振る舞わせるか」のポリシー選択である。CP系（例：ZooKeeper、HBase）はパーティション中に一部のノードが応答不能になることを許容し、データの正確性を守る。AP系（例：Cassandra、DynamoDBのデフォルト挙動）はパーティション中も全ノードが応答を続けるが、ノード間でデータの食い違いが生じることを許容し、後から整合性を回復する（結果整合性）。ただし現実のシステムはこの二分法に収まらず、DynamoDBのようにリクエスト単位でstrongly consistent readを選択できるものもある。

Brewerが後に自ら訂正した通り、CAPは「3つから2つを選ぶピックアップ問題」ではない。Pは現実には放棄できないため、実質的にはパーティション時のC vs Aのトレードオフであり、かつその選択はシステム全体で一律である必要もない。操作の種類やデータの重要度に応じて、ある操作ではCを優先し別の操作ではAを優先する、といった粒度の細かい設計が可能であり、実際のプロダクションシステムではそうしている。

まとめると、CAP定理で3つを同時に満たせない理由は次の一文に集約できる。ネットワーク分断中は、あるノードが持つ情報と別のノードが持つ情報の間にギャップが物理的に生じ、そのギャップを「応答しないことで隠す」か「古い情報で応答することで露出させる」かの二者択一を避けられないからである。