2011/Aug/28

PACELCで理解するCAPの定理(2)

第一回目は、CAPの定理をおさらいしました。今回は、いよいよPACELCについて見ていきます。

CAP定理の問題
Abadi氏は、CAPの定理には次のような問題があると言います。
CA型とCP型のシステムは、事実上区別できない。つまり、CAP定理では、あたかもCA, CP, APの計3種のシステムが存在するような印象を受けるが、実際にはCA/CP型とAP型の2種類しかない。
まずはこれについて考えてみましょう。CA型のシステムとは、ConsistentかつAvailableなシステムですが、Partitioningが起きたら、機能を失ってしまうシステムです。CP型のシステムとは、Consistentで、Partitioningが起きても機能を失わないが、その代わりAvailableではないシステムです。
なんだか、確かに分かりにくいですね。よりCAP定理の定義に忠実に従って正確に書いてみましょう。
  1. CA型のシステムとは:
    • Partitioningが起きない限り(=普段は)、ConsistentかつAvailableである
    • Partitioningが起きると、システムは機能を失う
  2. CP型のシステムとは:
    • 普段はConsistentである
    • Availableとは、「ノードがfailureしていないかぎり応答を返せること」なので、実は、普段(=Partitioningが起きていない時)はCP型のシステムもAvailableである
    • Partitioningが起きると、Availableではなくなるが、Consistentであり続ける
まだ分かりにくいので、具体例で見ていきましょう。

 2つのノードで同期的にレプリケーションを行っているリレーショナルDBを考えましょう。どのWriteも、両方のノードのディスクに書き終わらない限り完了しないという設定で組んでいるとします。もし2つのノード間で通信が途絶えてしまったら、両方のディスクに書けないのでシステムは機能を失ってしまいます。これが、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の定理の2つ目の問題です:
CAPの定理は、LatencyとConsistencyのトレードオフを考慮していない。
PACだけに注目すると、じゃぁPが発生していないときはAvailabilityとConsistencyどっちも取れてハッピーハッピーになるはずなのですが、世のNoSQLデータベースは普段からConsistencyを犠牲にしています。

 どうしてそんなことをするかというと、Latency(≒レスポンスタイム)を短くする為です。例えば、負荷分散のために10台のリレーショナルDBをレプリケーションして使いたいとしましょう(みんな同じ中身)。Consistencyを達成するためには、Create/Update/Deleteを行う時は10台全てにリクエストを発行して、完了するまで待たなければいけませんが、そんなことをしたらLatencyはかなり悪くなってしまいます。2台選んでリクエストを完了し、後からこの2台が他のノードにリクエストを非同期で発行するのはどうでしょうか?これなら運悪く1台が死んでももう1台がいますから1台にだけ発行するのに比べると信頼性がアップしますし、10ノードに発行するのに比べれば、Latencyが改善します。Cassandraなどは、実際にこれに似たようなことをやっています。

 話が少し横にずれてしまいましたが、要するに、LatencyとConsistencyはトレードオフの関係にあり、システムはどちらかを選ぶ必要があるということなのです(実際にはイチゼロじゃなくて、どちらをより優先するか連続的なスペクトルから選ぶ感じですが)。

 では、いくつか実例を見てまとめとしましょう。PCECシステム(if Partition then Consistency, else Consistency)はどんなシステムでしょうか?何回か例に出てきた、2つのノードが同期的にレプリケーションを行っているリレーショナルDBなどが考えられます。このシステムは、ネットワーク分断が発生すると、生きていてもリクエストを処理できないノードができてしまいます(if P then Availability喪失)。普段も、2ノードで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 分散システム
posted by 塩路慧能 (Enno Shioji) at 11:53 | Comment(1) | TrackBack(0) | 分散システム | Subscribe to this blog | Check for updates
Comments to this article
こんにちは
CAP定理について調べていて、探せど探せど納得できず
こちらにたどり着きました。
他のサイト等では、そもそもCAPそれぞれの定義がいきなり
間違えてたり、曖昧だったりで困りました。
とりわけAの認識がさまざまで、
なんとなくいつでも使えることとされていたりして、
それだと、一般的にACとされているRDBは、
ノード故障しない前提で高可用性とされているのに、
Pを実現しているシステムはノード故障や分断を
担保しようとしてる時点で比較になっていません。

すいません前置きが長くなりました。
こちらに記載されている内容は非常に納得感のあるもので、
参考にさせていただいたのですが、
一点質問があり、投稿させていただきました。

ざっくり言うと
>IPが古い方のノードは「failしていないのに応答できない」
という例の部分で、
「分断時に、少数派であるノード群は自動的にfailerに移行する」
というのは何らかのロジックにより設計可能であり、実際そういったシステムは
存在します。これはAも満たせた状態になる気がするのです。

この設計の場合、なにかAを満たせなくなるパターンがあるのだと思いますが、
思い至りません。

Cを満たしているタイプの分散環境で比較的メジャーなのは、
明確なマスターノードを持つタイプです。

・HBaseタイプ(一般的にはCP)
常にマスターノードがある方が有効
→マスターノードが落ちたらサービスが提供できないので
可用性が低いということ?
→しかしそれだとAC型とされているRDBも同じ条件では
そもそもAってそういう意味ではないのでは・・・
→むしろ、
「スレーブは、masterノードが認識できなくなったら自動的にfailerに移行する」
という仕組みがあればCAPを満たせるのでは

・MongoDBタイプ(一般的にはCP)
障害時に、障害前の数の過半数をこすノード群側から
マスターノードを自動的に創出する。
マイナー群は自らfailerとする。
見かけ上CAP定理はクリアすることになりそうな気がする。
たしかに一般的にAP型とされている、Cを犠牲にしてどのノードでも
いつでも応答できるようなタイプに比べると、
システム全体の可用性は下がるが、CAP定理でいうAは
満たせるのではないか

こちらのエントリでも言われていることだと思いますが、
A(可用性)の定義を「システム全体の可用性」といった意味合い
にしてしまうと、どの仕組みであっても、使えなくなる障害パターン
というのは存在してしまうわけで、定理と呼ぶようなロジカルな証明は
できないのはないかと思ってしまうのです。

こちらでおっしゃられている通り、CAもCPも一緒であって、
分断をもともと想定していない
システムをACと分類する事自体が無意味ですし。

感情的には、分断が発生したらシステム全体が落ちるからAが確保できてると
みなすのは抵抗があります。

比較的しっかり説明しているようなサイトを見ても、
Aの定義を「分断時の可用性」を例にあげて説明していたりして、
それなら分断を想定していないシステムを併記する意味ないですし、
分断耐性(P)側の説明とごっちゃになっていたりもします。

はじめからAを「分断時の可用性(相対評価)」としてくれていれば
まだ納得感もあるのですが。
(そして普通のRDBなどをCAではなくCと記載してくれれば・・・)

私がAbadi氏と少し異なる切り口で展開してみたいと思うのは、
これって、たいそうな名前をつけるまでもなくものすごく単純な話で、

1)それぞれの更新が反映完了するまで待つ
=Cを保証する

2)結果反映を遅延し、それぞれで応答する
=Cをゆるい形でしか保証しない

という2タイプの話なのではないかと。

1)は、レイテンシ問題が許容出来(DNSだといちいち全反映までまっていられるわけがない)
分断時に、生きてるノードが自らfailerとなったり、マスターノードが停止したら
システム全体が停止してたとしても、Cを確保したい場合に利用

2)は、その逆で、結果反映にある程度の遅延を認める代わりに、
超大規模でも遅延が少なく、分断時もそれぞれの判断で動作し続け、
復旧時にまたデータを反映できる

という形で説明されていれば、あとからこのあたりを調べる
方々も理解しやすいのではと思いました。

いきなり長文投稿となってしまい失礼しました。

Posted by r at 2012年01月23日 14:42
Write a comment
Name:

Email:

Website:

Comment: [Required]

Verification code: [Required]


Please enter the characters in the image
Comments appear on the blog after the webmaster's approval. Thanks for your comment!

Trackbacks
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。