CAP定理の問題
Abadi氏は、CAPの定理には次のような問題があると言います。
CA型とCP型のシステムは、事実上区別できない。つまり、CAP定理では、あたかもCA, CP, APの計３種のシステムが存在するような印象を受けるが、実際にはCA/CP型とAP型の２種類しかない。まずはこれについて考えてみましょう。CA型のシステムとは、ConsistentかつAvailableなシステムですが、Partitioningが起きたら、機能を失ってしまうシステムです。CP型のシステムとは、Consistentで、Partitioningが起きても機能を失わないが、その代わりAvailableではないシステムです。
なんだか、確かに分かりにくいですね。よりCAP定理の定義に忠実に従って正確に書いてみましょう。
- CA型のシステムとは:
- Partitioningが起きない限り（＝普段は）、ConsistentかつAvailableである
- Partitioningが起きると、システムは機能を失う
- CP型のシステムとは:
- 普段はConsistentである
- Availableとは、「ノードがfailureしていないかぎり応答を返せること」なので、実は、普段（＝Partitioningが起きていない時）はCP型のシステムもAvailableである
- Partitioningが起きると、Availableではなくなるが、Consistentであり続ける
２つのノードで同期的にレプリケーションを行っているリレーショナルDBを考えましょう。どのWriteも、両方のノードのディスクに書き終わらない限り完了しないという設定で組んでいるとします。もし２つのノード間で通信が途絶えてしまったら、両方のディスクに書けないのでシステムは機能を失ってしまいます。これが、CA型のシステムですね。
これではシステム全体の可用性が少なすぎるとしましょう（どちらかのノードが壊れるか、通信が途絶えるかするだけでシステムが停止するので）。そこで、「通信が途絶えたら、IPの若い（順番が）方が自分のディスクだけをつかってオペレーションを継続する」という約束をすることにしましょう。こうすれば、通信が途絶えてもIPの若いほうが生きてさえいればオペレーションを続けることができます。
IPが古い方のノードは「failしていないのに応答できない（正確には『リクエストを実行できない』というエラー応答となるわけですが）」ことになり、「failしていないノードはリクエストに応答しなくてはならない」というAvailabilityの条件を満たさなくなります。
もし、どうしてもAvailabilityを保持したかったとしたらどうでしょうか？その時は、レプリケーションを非同期にする必要があります。お互いのDBが、発生した変更をキューに貯めておいて、通信が復活したら相手に伝達します。
その間は、お互いDBの中身が違うので、Consistencyは守られません。
つまり、事実上、CA型のシステムとCP型のシステムがあるわけではなく、Pが起きたときにCを選ぶか、Aを選ぶかという選択があるのです。
ここまでが、「CA型とCP型のシステムは、事実上区別できない」とするAbadi氏の主張の説明です。Abadi氏はこの論理から、PACELCの"PAC"を提唱しています。「もしPが起きたら、AとCどちらを選びますか？」という意味です。
次に、残りの"ELC"について見てみましょう。先に説明しますと、ELCとは else Latency xor Consistencyです。PACから書くとこうなります。
if P then Availability xor Consistency else Latency xor Consistency日本語で書くとこうなりますね。
もしネットワーク分断が起きたら、Availabilityを選びますか？それともConsistencyを選びますか？ あと、ネットワーク分断が起きていない時は、Latencyを選びますか？それともConsistencyを選びますか？Latencyという要素が急に入ってきましたが、これはなんでしょうか？これが、Abadi氏が主張するCAPの定理の２つ目の問題です：
CAPの定理は、LatencyとConsistencyのトレードオフを考慮していない。PACだけに注目すると、じゃぁPが発生していないときはAvailabilityとConsistencyどっちも取れてハッピーハッピーになるはずなのですが、世のNoSQLデータベースは普段からConsistencyを犠牲にしています。
どうしてそんなことをするかというと、Latency（≒レスポンスタイム）を短くする為です。例えば、負荷分散のために10台のリレーショナルDBをレプリケーションして使いたいとしましょう(みんな同じ中身)。Consistencyを達成するためには、Create/Update/Deleteを行う時は10台全てにリクエストを発行して、完了するまで待たなければいけませんが、そんなことをしたらLatencyはかなり悪くなってしまいます。２台選んでリクエストを完了し、後からこの２台が他のノードにリクエストを非同期で発行するのはどうでしょうか？これなら運悪く１台が死んでももう１台がいますから１台にだけ発行するのに比べると信頼性がアップしますし、１０ノードに発行するのに比べれば、Latencyが改善します。Cassandraなどは、実際にこれに似たようなことをやっています。
話が少し横にずれてしまいましたが、要するに、LatencyとConsistencyはトレードオフの関係にあり、システムはどちらかを選ぶ必要があるということなのです（実際にはイチゼロじゃなくて、どちらをより優先するか連続的なスペクトルから選ぶ感じですが）。
では、いくつか実例を見てまとめとしましょう。PCECシステム(if Partition then Consistency, else Consistency)はどんなシステムでしょうか？何回か例に出てきた、２つのノードが同期的にレプリケーションを行っているリレーショナルDBなどが考えられます。このシステムは、ネットワーク分断が発生すると、生きていてもリクエストを処理できないノードができてしまいます(if P then Availability喪失)。普段も、２ノードでWriteが完了しないとリクエストが完了しないので、Latencyも悪いです(elseの時、 Latency無し)。その代わり、普段はConsistencyが守られていますし( else Consistency)、Pが起きてもConsistencyを守り続けます。つまり、if P then Consistency (and not Availability), else Consistency (and not Latency)、よってPCECです。
PAELシステムはどうでしょうか？これも前出てきたDNSが当てはまります。普段はそのDNSサーバのテーブルがアップデートされてさえいれば、他のDNSサーバがアップデートされているかなど考えずに応答を返すので、Latencyはいいです(else Latency)。DNSサーバ間で通信が途絶えて、同期が行えなくなっても各自応答は返し続けるので、if P then Availabilityとなっています。その代わり、要求を処理するDNSサーバによって結果が変わることがありえるので、Consistencyは失われています。
他の組み合わせはどうでしょうか？Abadi氏は、PCELなシステムの例としてYahoo!のPNUTSを挙げています。PNUTSは、普段Latencyを得るため伝統的なリレーショナルDBなどに比べて弱いConsistencyを使っていますが、Pが発生すると、Availabilityを犠牲にしてでも、そのレベルのConsistencyを守り続けます。（Consistencyといっても様々なレベルがあるので、ここは分かりにくいですね。。）
PAECシステムだと、普段はConsistencyを維持していますが、Pが起きるとAvailabilityを守るためにConsistencyを犠牲にし始めます。たまにConsistencyが破られる可能性があるというのは、Consistencyがないのに近いので、PAECなシステムが本当にあったとしたら、非常に使いにくそうですが、後からある程度のコストでコンフリクトを解消できるような局面では、あり得ない選択ではないかもしれません。
以上、PACELCで理解するCAPの定理でした！
Recent articles on 分散システム
View Enno Shioji's profile
