CAP 定理
概要
CAP 定理は分散データベースシステムにおいてネットワーク分断 (partitioning) が発生したときに一貫性 (consistensy) か可用性 (availability) のどちらかしか取ることができないという原則。一般的な定理や原理といった強い制約ではなく、現在では分散データベースの特性や傾向、設計方針を分類する目的の言葉として使用されている。
CAP 定理で扱うそれぞれの特性は以下のように説明することができる。
一貫性
CAP 定理における一貫性 (consistency) とは、一度状態が確定すると、システムの外からその状態が明示的に変更されない限り、それ以降の全ての操作は同じ状態を参照することを保証する (さもなくばエラーが報告される) 特性。
一貫性を保証する分散システムは合意形成を行うノード間で密に通信する必要があるため、合意ネットワークに参加するノード数を増やすと急激にパフォーマンスが低下する傾向にある。
同じ一貫性でもデータベースにおけるトランザクション特性の ACID の C を意味する "事前に定義されたある整合性条件が満たされていることを保証する特性" とは異なる、あるいは包含している点に注意。
本の購入に例えると、分散システムにおける一貫性は、購入が確定した後にシステムから「未購入」の状態が観測されないことを保証する。一方、データ整合性の視点から在庫が存在しない商品の購入を失敗させるような特性を含めることもあるが、これは本質的に CAP 定理での一貫性の観点とは異なる。
可用性
可用性 (availability) はシステム内の一部のノードや部分的なネットワークで障害が起きても全体として機能は失われずデータの損失も起きないことを保証する特性。これはシステムが適切に冗長化されており単一障害点が存在しないことを意味することから障害耐性 (fault tolerance) の意味にも使用される。
一般的にデータのレプリケーションを行うノード数を増やすとシステムの可用性が直接的に向上する。可用性は単なる障害耐性だけではなく、同時読み取りのような操作の負荷分散にも利用することができる。
分散システムの導入理由は高可用性と負荷分散を目的としているケースがほとんどであり、可用性に加えて一貫性と分断耐性のどちらを選択するかのみが論議の対象となる。
本の購入に例えると、分散システムにおける可用性は、近所の本屋が定休日で目的の本が買えなかったとしても、日本のどこかの本屋ではその本が問題なく購入できることを保証する。副作用として、複数の書店で同一の書籍を扱うことで新書の発売日であっても 1 店舗に全ての客が押しかけない効果も期待できる。
分断耐性
分断耐性 (partition tolerance) はノード間のネットワークに深刻なメッセージ遅延や一時的な分断が発生していたとしても、全体としてシステムが正しく駆動し続けることを保証することができる特性。ただし、分断耐性は必ずしも正常なサービスの継続が可能であることを意味してはいない点に注意。
銀行業務に例えると、分散システムにおける分断耐性は、災害で孤立地域が発生したとしても銀行が自立的に引き出しや預け入れを行って後で全国の取引の整合性を合わせることができるか、あるいは全国の銀行窓口の業務を取りやめるかのどちらかを取ることで結果的に取引の不整合が発生しないことを保証する。
特性の組み合わせ
CAP 定理は前述の 3 特性の全てを同時に満たすことはできないというものであった。それぞれの組み合わせは以下のように説明することができる。
CA: 一貫性 - 可用性
全てのノードがオンラインである限りシステム内でデータは一貫しており同じデータを読み書きすることができる。ただし、ネットワーク分断が発生した場合、分断されたどちらかのサブネットワークは同期が取れないためサービスを停止する。
CA タイプの代表例は冗長構成の RDBMS (PostgreSQL, MySQL, etc.) である。分散合意アルゴリズムとしては Raft や pBFT が CA タイプである。
CP: 一貫性-分断耐性
全てのノードがオンラインである限りシステム内でデータは一貫しており同じデータを読み書きすることができる。ただしネットワーク分断が発生した場合や、特定のノードに故障が発生した場合、サービス全体が停止する (全てが明確に失敗することも一貫性の特性である点に注意)。
最も簡単な例としては非冗長構成 (スタンドアロン) のデータベースは一貫性を持ちネットワーク分断の影響を受けないが単一故障でサービス不可能になるため CP タイプである。
初期の頃に単一障害点の存在した MongoDB や、Google BigTable 論文に基づく HBase は CP タイプに分類されることが多いが、現在それらは単一障害点を冗長化しているため、正しく構成すれば実質的に CA タイプと等価と見なしても良い。
AP: 可用性-分断耐性
ネットワーク分断が発生した場合、それぞれのサブネットワークは独立して動作しネットワークの回復後に自動的にデータを再同期する。ただしノードがオンラインであってもシステムとして完全に同期されたデータを参照可能とは限らない。
AP タイプの分散データベースはある程度の時間が経過すると一貫性が保証される結果整合性 (eventual consistency) と呼ばれる特性を持っている。
Amazon DynamoDB 論文に基づく Cassandra や Riak, CouchDB, クラスタ構成された Redis などが AP タイプに分類される。Riak は更新時に Quorum (定足数) を指定することである程度一貫性を強化した振る舞いを選択することができる。
後年の訂正
CAP 定理を提唱した Eric Brewer 氏により、CAP 定理を 3 つに分類したのは混乱を招くミスリーディングだったという記事が提出された。法則や定理というより傾向や特性を指すものであり、設計によって欠けている部分を補ったり軽減することができる。ただし CAP 定理は厳密な定義ではないというだけで、分散データベースの特性を伝えるための便利な言葉として現在でも使用されている。
すべてのシステムで一貫性、可用性、分断耐性を実現することが望ましいとはいえ、残念ながら3つのシステムすべてを同時に実現できるシステムは存在しない。It states, that though its desirable to have Consistency, High-Availability and Partition-tolerance in every system, unfortunately no system can achieve all three at the same time.
CAP 定理は、200x 年代の Key-Value ストアの黎明期に (CA 型と言われる) 従来の RDBMS との対比を強調するために「一貫性 (C)、可用性 (A)、分断耐性 (P) のいずれか一つしか選択できない」と広まった。現在ではネットワーク分断は発生するものとして C と A の、分断耐性 (partition-tolerance) の 3 つの特性のうち 2 つまでしか満たすことができないという概念。