QCon Tokyoでは色々なところで「CAP Theorem」という定理が出てきた。が、eBayの人をのぞけば（たぶん）正確な定義は提示されておらず、不明な点がいくつか残っている。これからのインフラを考える上でも、QConセッションの内容をより良く理解するためにも、このあたりをまずきちんと理解しておきたい。主な疑問点は以下のとおり。
CAP Theoremそのものは、Eric BrewerがPODCカンファレンスのキーノートで提唱したものらしい。CAP Theoremには形式的な証明があるらしいので、数学的に証明された、文字通りの定理であるようだ。証明の論文はACMの有料会員にならなければ見られないらしく、無料のWeb会員では見ることができなかった。残念。Eric Brewerの資料はWeb上で公開されているので、これを見るのが一番良さそう。
Eric Brewerのスライドでは、availabilityやgraceful degradation, performanceのためにはCとIが犠牲になるが、これは根本的なトレードオフである、という認識が出発点になっており、丸山先生も紹介している BASE（Basically Available, Soft-state, Eventural consistency）の概念の提示に続いている。さらに、ACIDとBASEはどちらかを選択しなければならないような排他的なものではなく、スペクトラム のようなものではないか、とも書かれている。
C, A, Pの定義
さて、CAP Theoremだが、CAPは以下のように紹介されている。
AmazonのCTOによる、2007年InfoQの発表では....
となっているらしい。Partition-toleranceは、システムが分割された場合でもシステムが保持する特性、と定義されている。つまり、 Partition-toleranceが低いシステムは、分割すると色々な特性が失われる、ということだろうか。この定義からすると、並列可能性というのもあながち間違った表現ではないように感じる。
CAP定理
さて、以上のように簡単な定義がなされた上で、CAP定理は以下のように定義される。
すなわち、「共有データを持つシステムは、CAPとして定義された特性のうち最大でも2つの特性しか持つことはできない」。以降、例をもとに説明してあるんだが、例自体があいまいなので、例の技術に詳しくない自分にはなかなかわかりづらい。想定している状況の単純なモデルを先に確認した方が話が早いと思う。
想定するモデル
2つのモジュールと、その間のインタフェースについて考える。クライアントとサーバーでも、ピアとピアでもなんでも良い。典型的には、プロシージャコール の形を取るが、この際インタフェースをはさんだどちらの側も同一のアドレス空間にいる。スレッドはこのインタフェースを超えていく。
しかし、インタフェースをはさんだそれぞれの空間が同じアドレス空間ではない場合、Call by Referenceは使えず、データをコピーしなければならなくなる。こうした状況になった場合のCAPについて議論しているようだ…うーん。それでもやっぱりわかりづらいな。例を確認してみる。
C+Aを持つケース
単一サイトのデータベースを考えてみると、確かに一貫性は得られている。ネットワーク分断で失われる特性が多いというのは、何をさしているのだろうか？少なくとも、 ネットワーク分断をすすめていくと、性能が犠牲になるのは間違いなさそうだが。
可用性が得られている、というのはさらによくわからない。2PCの例では、TMがACID特性を保証しているので、データのコピーは発生せず、常にすべてのデータが得られるため可用性が高い、ということだろうか？少なくとも、クラスタでは可用性は高そうだが。
C+Pを持つケース
分散データベースを考えると、ネットワーク分断への耐性はかなり高そうなのはわかる。また、システムが一部故障した際にはすべてのデータを得られなくなる だろうから、可用性が低いというのも理解できる。分散データベースの一貫性については、実はよくわかってないのだが、きちんと保証できているのだろうか？本当にきちんとできているなら、2pcとあまり変わらない気がするのだが。
A+Pを持つケース
DNSについて考えると、確かにネットワーク分散しても失われる特性は小さく、可用性も非常に高いが、一貫性を失っていると言える。
この後もスライドとしては細かい話が続いていくんだけど、結局CAP定理が前提としているモデルがどのようなものであるのかは、正確にはわからないままだ。
例えば…
- C, A, Pの特性の正確な定義は何なのか
- CAP定理が前提にしているシステムのモデルはどのようなものなのか
- Theoremとなっているが、単なる経験則なのか、それとも数学的な定理なのか
CAP Theoremそのものは、Eric BrewerがPODCカンファレンスのキーノートで提唱したものらしい。CAP Theoremには形式的な証明があるらしいので、数学的に証明された、文字通りの定理であるようだ。証明の論文はACMの有料会員にならなければ見られないらしく、無料のWeb会員では見ることができなかった。残念。Eric Brewerの資料はWeb上で公開されているので、これを見るのが一番良さそう。
Eric Brewerのスライドでは、availabilityやgraceful degradation, performanceのためにはCとIが犠牲になるが、これは根本的なトレードオフである、という認識が出発点になっており、丸山先生も紹介している BASE（Basically Available, Soft-state, Eventural consistency）の概念の提示に続いている。さらに、ACIDとBASEはどちらかを選択しなければならないような排他的なものではなく、スペクトラム のようなものではないか、とも書かれている。
C, A, Pの定義
さて、CAP Theoremだが、CAPは以下のように紹介されている。
- C:Consistency
- A:Availability
- P:Tolerance to network Partition
AmazonのCTOによる、2007年InfoQの発表では....
- Strong Consistency: all clients see the same view, even in presence of updates
- High Availability: all clients can find some replica of the data, even in the presence of failures
- Partition-tolerance: the system properties hold even when the system is partitioned
となっているらしい。Partition-toleranceは、システムが分割された場合でもシステムが保持する特性、と定義されている。つまり、 Partition-toleranceが低いシステムは、分割すると色々な特性が失われる、ということだろうか。この定義からすると、並列可能性というのもあながち間違った表現ではないように感じる。
CAP定理
さて、以上のように簡単な定義がなされた上で、CAP定理は以下のように定義される。
You can have at most two of these properties for any shared-data system
すなわち、「共有データを持つシステムは、CAPとして定義された特性のうち最大でも2つの特性しか持つことはできない」。以降、例をもとに説明してあるんだが、例自体があいまいなので、例の技術に詳しくない自分にはなかなかわかりづらい。想定している状況の単純なモデルを先に確認した方が話が早いと思う。
想定するモデル
2つのモジュールと、その間のインタフェースについて考える。クライアントとサーバーでも、ピアとピアでもなんでも良い。典型的には、プロシージャコール の形を取るが、この際インタフェースをはさんだどちらの側も同一のアドレス空間にいる。スレッドはこのインタフェースを超えていく。
しかし、インタフェースをはさんだそれぞれの空間が同じアドレス空間ではない場合、Call by Referenceは使えず、データをコピーしなければならなくなる。こうした状況になった場合のCAPについて議論しているようだ…うーん。それでもやっぱりわかりづらいな。例を確認してみる。
C+Aを持つケース
- 単一サイトのデータベース
- クラスタデータベース
- LDAP
- xFS file System
単一サイトのデータベースを考えてみると、確かに一貫性は得られている。ネットワーク分断で失われる特性が多いというのは、何をさしているのだろうか？少なくとも、 ネットワーク分断をすすめていくと、性能が犠牲になるのは間違いなさそうだが。
可用性が得られている、というのはさらによくわからない。2PCの例では、TMがACID特性を保証しているので、データのコピーは発生せず、常にすべてのデータが得られるため可用性が高い、ということだろうか？少なくとも、クラスタでは可用性は高そうだが。
C+Pを持つケース
- 分散データベース
- 分散ロック
- 主要なプロトコル
分散データベースを考えると、ネットワーク分断への耐性はかなり高そうなのはわかる。また、システムが一部故障した際にはすべてのデータを得られなくなる だろうから、可用性が低いというのも理解できる。分散データベースの一貫性については、実はよくわかってないのだが、きちんと保証できているのだろうか？本当にきちんとできているなら、2pcとあまり変わらない気がするのだが。
A+Pを持つケース
- Coda
- Webキャッシュ
- DNS
DNSについて考えると、確かにネットワーク分散しても失われる特性は小さく、可用性も非常に高いが、一貫性を失っていると言える。
この後もスライドとしては細かい話が続いていくんだけど、結局CAP定理が前提としているモデルがどのようなものであるのかは、正確にはわからないままだ。
例えば…
- ネットワーク分断というのは、どの要素とどの要素の分断のことを言っているのか（あらゆるシステム要素間の分断なのか、特定の部分の分断なのか）
- 分断によって失われる特性、失われない特性とはどのようなものなのか
- 高い可用性が意味するものは何なのか
- などなど
ネットワーク分断への耐性を捨てたシステムなら, データの整合性と可用性を実現できる. これには普通トランザクション・プロトコルを使う. 実現のためにはクライアントとストレージ・システムが同じ環境にある必要がある. これだとシナリオによってはシステム全体が故障してしまうし, クライアントは分断を検知できない. 重要な洞察がある: 大規模な分散システムではネットワークの分断が所与のものであり, 従って整合性と可用性は両立しない. どちらか一方は捨てる必要がある. 整合性を妥協すればシステムは分断のある状況でも高可用性を実現できる. 整合性を優先すればシステムの使えない状況を生む.
コメント