CAP定理
CAP Theorem ・ きゃっぷていり
ネットワークが分断されたとき、一貫性と可用性のどちらかを諦めるしかないという定理。
✦ 30秒で試す — 航海ケーブル1本で「正しさ」か「返事」かを選ばされる線をつなぎ直すと、2つの書き込みはどうなる？予想してみる概要
CAP定理は、データを複数のノードに複製する分散システムについて、「一貫性（Consistency）」「可用性（Availability）」「分断耐性（Partition tolerance）」の三つを同時には満たせないことを示した定理です。三つの頭文字を取って CAP と呼ばれ、提唱者の名から「ブリュワーの定理」とも言います。
三つの性質は、ふだんの言葉よりずっと厳密な意味で定義されています。C は線形化可能性（linearizability）と呼ばれる性質で、「どのノードに読みに行っても、完了した最新の書き込みの値が返る。システム全体が1台であるかのように振る舞う」ことです。A は「故障していないノードに届いたリクエストには、どれも必ず（エラーではない）応答を返す」ことで、一部のノードだけが応答すればよいわけではありません。P は「ノード間のメッセージが失われても（ネットワークが分断されても）動き続ける」ことです。
よくある誤解は「三つのうち好きな二つを選べる」という読み方です。ネットワークの分断は起きるかどうかを選べないので、本当に迫られる選択は「分断が起きた瞬間に、C と A のどちらを諦めるか」の二者択一です。RDBMS のレプリケーション構成から NoSQL まで、データを複製するシステムの設計には必ずこの問いが潜んでいます。
なぜ生まれたか
1台のデータベースなら、書き込みが終わった後に読めば必ずその値が返ります。ACID のトランザクションが守る世界では、「常に正しい値」は当たり前でした。ところが可用性を上げるためにデータを複数ノードへレプリケーションした途端、この当たり前が崩れます。あるノードへの書き込みがほかのノードに伝わる前に別のノードが読まれれば、古い値が返るからです。1990年代後半、Web の大規模サービスを支える分散システムの現場では、「速くて、いつでも応答して、しかも常に正しい」システムを漠然と目指し、そのどれもが中途半端になっていました。
2000年、カリフォルニア大学バークレー校のエリック・ブリュワーは、分散コンピューティングの国際会議 PODC の基調講演で「一貫性・可用性・分断耐性は同時に満たせない」という予想を示しました。2002年にセス・ギルバートとナンシー・リンチがこれを定式化して証明し、予想は定理になりました。これで「あれもこれも」という願望ではなく、「分断時に何を諦めるか」を意識的に選ぶことが分散データストア設計の出発点になり、2000年代後半の NoSQL の多くは、あえて一貫性を緩めて可用性を取る設計を打ち出しました。
その後ブリュワー自身も、2012年の論考「CAP Twelve Years Later」で「三つから二つ」という言い方は誤解を招くと振り返っています。分断はまれにしか起きず、起きていない間は C と A を両立できるので、選択は分断の間だけの話だ、という整理です。
詳細
分断が起きた瞬間の二者択一
CAP定理の核心は、ネットワーク分断が発生した「その瞬間」に現れます。データが2台のノード N1・N2 に複製されていて、その間の通信が切れたと想像してください。どちらのノードも生きていて、クライアントからのリクエストは届きます。クライアント X が N1 に「x=2 を書いて」と頼んだとき、N1 は N2 にその変更を伝えられません。
N1 が採れる道は二つしかありません。一つは「書き込みを受け付けて OK を返す（可用性を守る）」道です。応答は返せますが、N2 は x=1 のままなので、直後に Y が N2 から読むと、完了したはずの書き込みより古い値が返ります。一貫性（線形化可能性）が破れた状態です。もう一つは「N2 に伝えられない以上、書き込みを拒否してエラーを返す（一貫性を守る）」道です。食い違いは生まれませんが、生きているノードがエラーを返すので、可用性を諦めたことになります。N2 も同じで、手元の値が最新だと N1 に確かめられない以上、古いかもしれない値を返すか、エラーを返すかのどちらかです。
下の部品で、N1 と N2 の間の線を押して分断を作り、CP と AP のそれぞれで書いて読んでみてください。AP で両側から書いてから線を戻すと、値がどう収束するかも確かめられます。
まず「X が N1 に書く」を押して、値が N2 にも複製されるのを見てください。次に、N1 と N2 の間の線を押して切り、書いてから Y で読んでみます。
CP型とAP型 — 何を選ぶか
一貫性を優先する設計を「CP型」と呼びます。分断中は応答を止めてでも間違った値を返さない方針で、銀行の残高、在庫数、分散ロックの持ち主のように「古い値を見せると事故になる」領域が該当します。過半数のノードで合意が取れないと書き込みを認めない etcd や ZooKeeper はこちら側です。ただし、ここでも CAP の A の定義の厳しさが効いてきます。合意ベースのシステムは、分断されても過半数の側では読み書きを続けられますが、少数派の側のノードはエラーを返します。「故障していないノードはすべて応答する」を満たさないので、CAP の意味では可用ではありません。現実の「落ちにくさ」と CAP の A は別物です。
可用性を優先する設計が「AP型」です。分断中もとにかく応答を返し、食い違いは分断が解けた後に埋め合わせます。SNS のタイムライン、ショッピングカート、いいね数のように、「一時的に少し古くても支障が小さく、止まらないことのほうが大事」な領域に向きます。AP型は、分断が解けた後に各ノードの値を収束させる結果整合性とセットで語られます。収束させるには、両側で別々に書かれた値のどちらを残すかを決めなければならず、時刻の新しいほうを勝たせる（Last Write Wins）と、片方の書き込みが黙って消えます。部品で両側から書いてから線を戻すと、このことが確かめられます。AP を選ぶことは、この衝突の後始末を引き受けることでもあります。
分断が「無い」ときの姿 — PACELC
CAP が語るのは、あくまで分断が起きている間の話です。ネットワークが正常なときは、一貫性と可用性を両立できます。ただし平常時にも別のトレードオフがあります。すべての複製の同期を待ってから応答すれば一貫性は強くなりますが、そのぶん遅くなります。待たずに応答すれば速い代わりに、古い値が見えることがあります。
2012年にダニエル・アバディはこれを加えて、「分断時（Partition）は可用性（A）か一貫性（C）か、そうでない平常時（Else）は遅延（Latency）か一貫性（Consistency）か」を問う PACELC という枠組みを提案しました。アバディの分類では、Dynamo や Cassandra は分断時に A、平常時に L を取る PA/EL、Bigtable や HBase は両方で C を取る PC/EC です。実務では分断より平常時の時間のほうがはるかに長いので、日々の体感を決めているのはむしろ EL か EC かの選択です。
実務で誤解しないために
第一に、CAP の C と ACID の C は別物です。ACID の一貫性は「制約（残高が負にならない、外部キーが壊れない）を破らない」という、アプリケーションが決めるルールの話です。CAP の C は「複製がすべて同じ最新の値に見える」という、複製の見え方の話です。名前が同じなので混同しがちですが、ACID の一貫性を満たすデータベースでも、非同期のレプリケーションで読み取り専用の複製から読めば、CAP の C は満たしません。
第二に、CAP は定義がとても厳しい分、実在のシステムの多くは CP にも AP にもきれいに当てはまりません。設定次第で振る舞いが変わるもの（読み書きに必要な複製の数を選べるものなど）や、機能によって方針が違うものがほとんどです。そのためマーティン・クレップマンらは、製品に「CP」「AP」のラベルを貼るより、「分断時にこの操作はエラーを返すのか、古い値を返すのか」を操作ごとに確かめるよう勧めています。一つのシステムの中でも「残高照会はエラーを返してでも正確に、通知の既読数は古くてもよい」と使い分けるのが実践的です。
CAP定理は答えを与える道具ではなく、「あなたの選択は、分断の間に何を諦めているのか」を毎回突きつけてくれる問いだと捉えるのがよいでしょう。
試問
2台のサーバー N1・N2 が同じ値 x を複製して持ち、クライアント X は N1 に、Y は N2 にだけつながっています。N1 と N2 の間の線は押すと切れ（分断）、分断したときの方針を「CP: 正しさを守る」「AP: 応答を守る」から選べます。書く・読むのボタンで、分断中に何が起きるかを確かめます。
まず「X が N1 に書く」を押して、値が N2 にも複製されるのを見てください。次に、N1 と N2 の間の線を押して切り、書いてから Y で読んでみます。