CAP 定理とは何か
データベースの勉強をしていると CAP 定理なるものに遭遇する。ずっと CAP 定理ってピンと来ないなぁと感じていたが、どうやら提唱者の Eric Brewer いわく CAP 定理は誤解された形で広がっているらしい。以下の記事に詳細がある。
自分が CAP 定理をよく理解できていないのは間違った説明を見ていたからかもしれない。ってことで今回は、上記の Eric Brewer の記事と Wikipediaのページ を参考に CAP 定理についてまとめてみた。（ちなみに、ざっとググってみた感じ CAP 定理について日本語で解説した記事はいくつかあるようだが、Eric Brewer が意図するものとは異なるものが多い印象を受けた。）
準備："分散" と CAP
前提として、CAP 定理は分散データストア（Distributed data store）の性質に関して述べたのものである。分散データストアでは、ネットワーク上に分散された複数のストレージ（ノード）上にデータが格納されている。分散データストアではユーザのリクエストに対して、各所に散らばっているノードから関連するデータを収集する必要がある。CAP 定理はこのような分散データストアを前提としたものであり、1つのインスタンス内でデータのやりとりが完結するようなデータストアについて述べたものではない。
次に CAP 定理（CAP theorem）を構成する C, A, P の3つに対応する概念を説明する。
C は Consistency の頭文字である
Consistency とは「ユーザの読み取り処理のリクエストに対して、常に最新の書き込みを返せる」という、データストアが持つべき性質である。
そんなの当たり前に満たされるのでは？と思う人は、CAP 定理が分散データストアを対象としていることを思い出して欲しい。どこか遠くのノードに赤の他人が書き込み処理をしたとき、本当に自分が最新のデータを取得できているのか？場合によっては難しい問題であろう。
ちなみに、CAP の Consistency はトランザクションの ACID の Consistency とは別のものである。
A は Availability の頭文字である
Availability とは「ユーザのリクエストに対して、常にエラーでないレスポンスを返せる」という、データストアが持つべき性質である。
データストアのユーザからすると、分散データストアからデータを取得したいのに、エラーばかり返ってきては使い物にならない。こういう事態を避けるのが Availability の意図するところである。ただし、エラーでないレスポンスを返すことが Availability の要件であり、常に最新のデータを返さなくてもこの要件は満たされるものとする。
ちなみに Availability の説明として「単一障害点がないこと」を前提とする説明が見られるが、これは誤りだと思われる。こういうネットワーク構成の話をしているのではなく、あくまでユーザ目線で見たときにすぐにレスポンスを得られるかという観点が重要である。たとえ単一障害点で障害が起きても他のノードで該当するデータをキャッシュしていれば Availability を担保できる場合がある。また、障害のためユーザの更新処理を実行できない場合でも、ユーザに「リクエストを受け付けました」とレスポンスを返せば Availability を担保していると言える。ネットワークが復旧してから裏で更新処理をかければよい。
P は Partition tolerance の頭文字である
Partition tolerance とは「ノード間をつなぐネットワークの分断や遅延が起こってもデータストア全体としては可動し続ける」 という、データストアが満たすべき性質である。
分散データストアを構成するノード数は非常に大きくなる一方で、ネットワークを介した通信は必ずしも安定しないことが知られている。もし一部のノード間で障害が起こっただけでネットワーク全体がダメになってしまうようではデータストアとして使い物にならない。それに対して Partition tolerance が満たされている場合、ネットワークの一部が死んでも全体としては動き続けることが保証される。
CAP 定理とは
ここから CAP 定理の説明に入る。以降に登場する "C", "A", "P" はそれぞれ Consistency, Availability, Partition tolerance の略である。
まず前提として P は分散データストアとして必須の要件である。その理由は、P を想定しない分散データストアは、ネットワークの一部が死んだだけで全体が死ぬような非常に脆い構造であり使い物にならないからである。C, A, P の中にも優先度があり、P が最も優先されるべきということである。
そして CAP 定理は以下を主張するものである。
P を満たす分散データストアでは、C と A を同時に満たすような設計にはできない。
分散データストアを設計するにあたり、P の要件「ネットワークの一部が死んでも全体としては動き続ける」を満たすためには、ネットワークの一部が死んでいるかもしれない前提でユーザのリクエストを処理しなければならない。しかしこのとき、「ユーザに最新のデータを返す」（C の要件）と「ユーザにエラーを返さない」（A の要件）を両立することはできない、というのが CAP 定理の主張である。C と A のトレードオフについて述べたものである。
なぜこのような定理が成り立つのか？理由を考えてみると単純で、常に最新のデータを返す（つまり C を満たす）ことを優先した設計にするとネットワークの障害時にはその復旧を待つことになる。ユーザのリクエストが、障害の起きたネットワークを介するアクセスを必要とする場合、もちろんユーザはレスポンスが得られない（普通はタイムアウトエラーが返ってくる）。つまり A が満たされない。
一方、ネットワーク障害が起こっていても常にユーザに何らかのレスポンスを返すこと（つまり A を満たす）を優先した設計にすると、最新でないにしてもユーザにとって有用そうなデータにアクセスできるようにしておくことが望ましい。過去に使用したデータをキャッシュしたり、ノードのデータ全体を複製しておいたりするのが現実的なアプローチである。もちろん、そのような代替手段によって提供するデータは最新ではない可能性がある。つまり C が満たされない。
CAP 定理をとても簡単に言うと「分散データストアにおいて、最新のデータを提供し続けるならユーザを待たせることは避けられない一方で、ユーザを待たせないなら最新でないデータを提供することは避けられない」ということである。
CAP 定理に対するよくある誤解
ここまで述べたように、CAP 定理の主張はたいして難しいものではないし、分散データストアを設計するにあたりいかにも役立ちそうな知見である。しかし冒頭で述べたように世の中には誤解が広まっていて CAP 定理が意図するものを曖昧にしている。ここでは、生じそうな誤解に対して正しそうな解釈をまとめる。
「2つを選択すると◯◯」
よくある説明として「CAP 定理によると C, A, P のうち2つを選択すると残り1つは保証されない」のようなものがある。C と P、A と P の組み合わせはよいとして、C と A の組み合わせに対して「C と A を選択すると P は満たされない」と言ってしまうのが誤解を招きがちである。
「C と A を選択すると P は満たされない」という表現は、C でもあり A でもある設計にするとネットワーク障害が起きないシステムが構築される かのように聞こえる。そんなはずがない。実際は分散システムにおいて P を無視した時点でシステムとして成立しないのである。上記でも述べたとおり、分散データストアの設計として P が最優先で、C と A が次に考慮されるべきである。P は人間がコントロール不可能な現象に対応するためのものであり、C と A が設計思想として人間がコントロールする部分である。
P を無視して C と A を選択したくなるようなケースはそもそもデータストアに分散性がない状況なのかもしれない。その場合は CAP 定理など考えずに C と A を満たす設計を目指せばよい、とも言える。もっというと ACID を目指した設計にするのが自然である。
「プロダクトごとに CAP を決定する」
CAP 定理から導かれる結論として「プロダクトの方針として C を優先するか A を優先するか決めよう」とするのは早合点である。「このプロダクトは CP を採用していて、このプロダクトは AP を採用している」みたいな分類がこの勘違いを生む原因になっている気がする。
CAP の中でどれを優先するのかはシステムの実行時状態に応じで動的に切り替えればよい。たとえばネットワーク障害が発生していないことが明らかなときは常に C と A を保証するような設計にしておき、障害が発生したときだけ C または A の保証を諦めるような設計にすることもできる。
したがって「このプロダクトは AP を採用しています」と言っているからといって平常時でも C が犠牲にされているとは思わないほうがよさそう。ネットワーク障害が起きていない限りは最新のデータが返ってくる（C である）ことを期待してよい。
「C を捨てれば A が必ず保証される」
CAP 定理の主張は、P のもとでは「C と A を同時に満たすことはできない」というものである。この論理構造を勘違いして「C を否定すれば A が必ず成り立つ」とするのは誤りである。論理学に慣れていない人がしてしまいそうなミスである。
場合によっては C も A も満たされない可能性がある。論理的にいえば、CAP 定理は ¬ (C ∧ A ∧ P) である。P を仮定して導かれるのは ¬(C ∧ A) である。ここから ¬ C → A や ¬ A → C は導かれない。CAP 定理は C と A の両立性について限界を示しているに過ぎない。
もちろん C も A もあえて保証しないような設計にしても構わない。C や A は 0/1 ではなく、0-1 の値を取るファジーなものである。分散データストアに求められる要件を加味したうえで C と A がよいバランスになるような設計を目指すべきである。ただしどちらも 1 にすることはできないことだけ忘れないようにしたい。
ちなみに同様に、論理構造から来る勘違いとして「CAP のうち1つを捨てれば残り2つが満たされる」というものがある。これも誤りである。たとえば P を選択しないこと ¬ P を仮定するだけで CAP 定理 ¬ (C ∧ A ∧ P) は常に成り立つ。C や A が真であることが導かれるわけではない。
最後に
この記事の要約を1枚絵にまとめて終わろうと思う。P は必須で C と A をバランスさせるのが CAP 定理の意図するところである。ちなみに As-Is の絵は Wikipedia から借りてきた。
この記事では CAP 定理のユースケースを述べていないので、それについては Eric Brewer の記事 の記事を見るのがよいと思われる。銀行の ATM を設計するときに C と A のどちらを優先すべきか？みたいなことが書いている。金融システムなんだから C を優先すべきだろうってのが自分の直感だったが、どうやら A を優先することも多いらしい。ATM の利用者が金を預ける分には口座残高が不正になることはない（なので復旧後に口座に反映するのが簡単である）し、金が引き出されて残高がマイナスになるのはレアケースだしそうなっても後から回収したらええやろ、みたいなことらしい。なるほどなぁ。
あと、ネットワークの分断（network partition）から復旧する具体的な考え方なども同じく Eric Brewer の記事を参考にするのがよさそう。分断している間は各ノードで操作列を蓄積しておいて、復旧後にそれらをマージしたりするらしい。考えただけで頭が痛くなりそう。
おしまい。
関連記事：トランザクションの ACID については過去に整理したことがあるのでよかったら。
