CAP定理（キャップ定理）とは、分散システムにおいて、一貫性（Consistency）、可用性（Availability）、分断耐性（Partition-Tolerance）の3つの性質のうち、同時に2つを満たすことしかできないという定理である。
CAP定理の概要
2000年にカリフォルニア大学バークレー校の教授であるエリック・ブリュワーによって提唱された。そのため別名「ブリューワーの定理」とも呼ばれる。
CAP定理の3つの特性を簡単に説明すると、以下のようになる。
一貫性（Consistency）
すべてのノードが同じデータを持っている状態を維持すること。
可用性（Availability）
すべてのリクエストに対して、常に応答できる状態を維持すること。
分断耐性（Partition Tolerance）
ネットワークの一部が分断されても、システムが動作し続けること。
CAP定理によれば、分散システムにおいては、この3つの特性を同時に満たすことは不可能である。そのため、分散システムにおいてはトレードオフを考える必要があることを示している。
CAP定理の証明
CAP定理の証明は、以下の2つのケースを検討することで行うことができる。
ネットワークが分断されていない場合
ネットワークが分断されていない場合、すべてのノードが常に通信できる状態である。そのため、一貫性と可用性、分断耐性の3つの特性を同時に満たすことは可能である。
具体的には、一貫性を採用することで、一貫性と可用性の両方を満たすことができる。また、分断耐性を実現するためには、ネットワークの分断が発生した場合でも、すべてのノードがデータを保持するようにすればよい。
ネットワークが分断されている場合（分散システムの場合）
ネットワークが分断されている場合、ノードが通信できなくなる可能性がある。この場合、一貫性と可用性のどちらかを選択する必要がある。
一貫性を重視した場合
一貫性を選択した場合、ネットワークが分断された場合でも、すべてのノードが同じデータを持つ必要がある。そのため、可用性を犠牲にする必要がある。
具体的には、ネットワークが分断された場合、データの更新は行われなくなる。これにより、ネットワークが再び接続されたときに、データの一貫性が保たれることになる。
可用性を重視した場合
可用性を選択した場合、ネットワークが分断された場合でも、すべてのノードが利用可能である必要がある。そのため、一貫性を犠牲にする必要がある。
具体的には、ネットワークが分断された場合、各ノードは、ネットワークが再び接続されるまで、独立してデータの更新を行うことができる。これにより、システムは常に利用可能になる。
CAP定理の例
CAP定理の3つのパターンに分けて、代表的なシステムの例を紹介する。
一貫性＋可用性
一貫性と可用性を両立するパターンは、一貫性を採用する。一貫性を実現するためには、すべてのノード間でデータの同期を常に行う必要があるため、ネットワークの負荷が高くなる可能性がある。
一貫性を採用する代表的なシステムとしては、以下のようなものが挙げられる。
リアルタイムシステム
リアルタイムシステムでは、データの最新性や正確性が重要であるため、一貫性が求められる。
例えば、航空管制システムや金融取引システムなどは、一貫性を採用している。
データベース
データベースにおいても、データの整合性が重要であるため、一貫性が求められる。
例えば、OLTP（オンライントランザクション処理）システムや関係データベースなどは、一貫性を採用している。
可用性＋分断耐性
可用性と分断耐性を両立するパターンは、耐久性を採用する。耐久性を実現するためには、すべてのノードでデータを保持するようにすればよい。
耐久性を採用する代表的なシステムとしては、以下のようなものが挙げられる。
分散ファイルシステム
分散ファイルシステムでは、データの可用性が重要であるため、耐久性が求められる。
例えば、NFSやGlusterFSなどは、耐久性を採用している。
キャッシュシステム
キャッシュシステムでは、データの可用性が重要であるため、耐久性が求められる。
例えば、WebアプリケーションのキャッシュシステムやCDNなどは、耐久性を採用している。
一貫性＋分断耐性
一貫性と分断耐性を両立するパターンは、弱一貫性を採用する。弱一貫性を実現するためには、すべてのノードでデータを同期する必要はない。
弱一貫性を採用する代表的なシステムとしては、以下のようなものが挙げられる。
検索エンジン
検索エンジンでは、データの最新性よりも、検索結果の正確性が重要であるため、弱一貫性が求められる。
例えば、GoogleやYahoo!などの検索エンジンは、弱一貫性を採用している。
ソーシャルネットワーク
ソーシャルネットワークでは、データの最新性よりも、ユーザーの利便性が重要であるため、弱一貫性が求められる。
CAP定理の限界
しかしながら近年では「CAP定理の考え方は古い」との指摘も出てきている。その理由として分散技術の進化が挙げられる。具体的にはその理由としては、以下が挙げられる。
分散コンピューティング技術の進化
ネットワークの分断は、自然災害やサイバー攻撃などによって発生する可能性がある。しかし、近年では、ネットワークの冗長化や分散ストレージの採用などにより、ネットワークの分断が発生する可能性が低下している。そのため、ネットワークが分断される可能性を低く抑えることで、一貫性と可用性を両立することが可能になっている。
また、分散システムでは、データの同期に時間がかかるという課題があったが、近年ではLSM-Tree等のストレージエンジンや、Raft等の同期アルゴリズムの登場により、従来よりも高速にデータ同期を行う方法が確立されつつある。
「弱い一貫性」を採用したアプリケーションの登場
一貫性は、厳密には「強い一貫性」と「弱い一貫性」に分類される。強い一貫性は、すべてのノードが常に同じデータを持っている状態を維持する。弱い一貫性は、すべてのノードが常に同じデータを持っている状態を維持することはないが、最終的には同じデータになる状態を維持する。
CAP定理においては強い一貫性を前提に述べられているが、アプリケーション側の工夫で弱い一貫性で業務が遂行できるシステムを作ることも可能である。例として、弱い一貫性であるNoSQLを採用したECシステムなどの事例がある。
これらの理由により、CAP定理に反して一貫性と可用性、分散耐性を持つシステム構築も可能となってきている。しかしながら、これらの最新技術の採用には、開発や運用に相応のコストがかかるという課題もある。またこれらの技術は一貫性、可用性、分散耐性のすべてをほぼ完全に保証する技術であり、完全に保証することは難しいため、現在でもCAP定理によるトレードオフ関係を知っておくことは重要であると言えるだろう。
まとめ
CAP定理は、分散システムの設計思想を決定する際の基本となる概念である。CAP定理を理解した上で、システムの要件を満たす組み合わせを選択することが重要である。
CAP定理の考え方は、分散コンピューティング技術の進化により古くなりつつある。しかし、CAP定理は、分散システムの設計において重要な概念であることに変わりはない。CAP定理を理解した上で、分散技術の進化を踏まえたシステム設計とが重要である。