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

2011/Jul/10

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

 CAPの定理が何故最近話題になっているかについての説明などは他サイトに任せることにして、このエントリではCAP定理の技術的な解説、および、CAP定理をより分かりやすく、かつ(簡単に言えば)より正確にした「PACELC定理」の解説を行います。
 PACELCの定理とは、エール大学のAbadi氏が提唱しているもので、CAPの定理のいわば発展形です。CAPの定理の「難しい版」と思われていることがあるようですが、そんな事はありません。むしろ、多くの学生がCAPの定理で苦労するのを見たAbadi氏が、学生に分かりやすく説明するために考えたものなので、CAPの定理をより分かりやすくしたものと言えます。ただ、それだけでなく、CAPの定理には入っていなかったLatency(≒レスポンス時間)の概念も合わせて捉えることで、より正確に分散データベースの特性を考えられるようになっています。

 ではまず、第一回目はCAPの定理をおさらいしましょう。

CAPの定理:次の3つの特性を、全て同時に示す分散システムを実現することはできない。
  1. Consistency(一貫性, C)
  2. Availability(可用性, A)
  3. Partition-tolerance(分断耐性, P)
すなわち、どのような方法をもってしても、ある時点でシステムが示すことができる特性は、C, A, Pのうち任意の2つまでである。

Consistencyとは
 ここでは広義に使われており、ACIDのCと同義ではありません。説明をわかりやすくするため、ここでは単純な分散Hash mapを具体例として見ていきましょう。
 最も単純なConsistencyには、AtomicityとVisibilityがあります。Atomicityのうち、最も単純なのは、「全てのReadは、Write処理が完了する前の状態か、または完了した後の状態のいずれかしか見ることがない」という性質です。プログラミングで例えるなら、map.get(key)を呼んだら、値が返ってくるか返ってこないかの2択しかしかなく、「値が半分だけ」返ってくることが絶対にないということです。「半分だけ」値が返ってくるってどういうことよと言われてしまいそうですが、この例では例えば正しくメモリ上に書き込みが終わっていない値が返ってくることが想定できます。イメージとしては、本当は10100010が返されなければいけないのに、まだ書き込みが終わっていないために00000010が返ってしまう感じです。この単純なAtomicityが実現されているということは、これが起こることがないという保証があるということです。※一般的にアトミックと言うとリレーショナルDBでいうAtomicityを考えると思いますが、今回の説明ではこの最低限のAtomicityで十分なので、単純化しています。

 Visibilityとは、全てのユーザ(例えばスレッド)が同じ状態を「見る」ことができることです。もう少し具体的に言うと、あるWriteが完了したなら、その後に発行されたReadは全て「最悪でも」このWriteの結果を返すという約束です。当たり前に聞こえますが、後述するように、パフォーマンスなどを考えて、「Writeが起こった直後は書いた人にしか見えないが、じわじわと他の人にも見えていくようにする」ことを許す場合があります。これがよく分散データベース("NoSQL")で言われる"Eventual Consistency"の一種です。すぐみんなが同じ状態を見れはしないけど、いずれは見ることができるようになる、という意味で"Eventual"なのですね。意図せずにこれを許してしまうのがVisibilityバグで、マルチスレッドプログラミングでよく起こるバグの一つです。
 ところで「最悪でも」ってなんやねんという話なのですが、これは、Write1→Read1→Write2の順にオペレーションが発行されたときに、Read1がWrite2の結果を見るのはOKということです。別にWrite2の結果が見えたほうがいいということではないので「最悪でも」という言い方は誤解を招くかもしれませんが、「少なくともWrite1までのアップデートを逃すことだけはNGにしましょうね」ということです。「Read1が、Write2ではなく、必ずWrite1の結果を受け取らなければいけない」というのはもう一つさらにきついレベルのConsistencyです。ここでは最低限のConsistencyについて考えたいので、よりゆるい、Write2の結果が返ってしまうことを許すvisibilityを考えます。

 「Writeの結果がすぐに全員に見える」のと、「ちょっと後に全員に見えるようになる」のと何か本質的な違いはあるのでしょうか?これについて考えるために、「同じ値(value)を許さない」Hash mapベースのアプリを考えてみましょう。どのスレッドも、一旦挿入したい(kx,vx)を挿入してしまってから(map.put(kx, vx))、map.values (v0 ... vx ... vn)を1つ1つイテレートしてvxと比べ、vx以外にvxと同じvyを発見したら、重複の疑いがあるケースとしてマークし、後で調査して削除するためにどこか(delete_list)に書き残します(次のinsert関数参照)。
 これをたくさんの(k,v)ペアに対して行い、最終的にユニーク、つまりどの値(value)も1回しか入っていないマップを得ることがアプリの目的です。



 さて、今まさに2つのスレッド(t1, t2)がそれぞれ(k1, v1), (k2, v1)を登録しようとしているとしましょう。同じv1なので、少なくとも1回重複疑いのアラートがあげられなければいけません(2回以上あがってしまうのはOK)。

 このHash mapは最低限のAtomicityしか備えていない設定ですので、put, removeはそれぞれアトミックですが、insert自体はアトミックではありません(これは、insert処理の途中の状態を、他のスレッドに見られたり、書き換えられたりする可能性がある、ということ)。なので、考えられる処理の順番としては、次の3つが考えられます(t1とt2を入れ替えたものは同じと考える。t1、t2それぞれの中ではput→readの順番は保たれる)。
    1. t1のput(k1,v1)
    2. t1のread(他のv1無し)
    3. t2のput(k2,v1)
    4. t2のread(他のv1有り)

    1. t1のput(k1,v1)
    2. t2のput(k2,v1)
    3. t1のread(他のv1有り)
    4. t2のread(他のv1有り)

    1. t1のput(k1,v1)
    2. t2のput(k2,v1)
    3. t2のread(他のv1有り)
    4. t1のread(他のv1有り)

 これが、「すぐに結果が全員に見える」という保証がなかったらどうなるでしょうか?タイミングによってこういうことがあり得てしまいます。
    1. t1のput(k1,v1)
    2. t1のread(他のv1無し)
    3. t2のput(k2,v1)
    4. t2のread(他のv1無し(まだ見えなかった))

    1. t1のput(k1,v1)
    2. t2のput(k2,v1)
    3. t1のread(他のv1無し(まだ見えなかった))
    4. t2のread(他のv1無し(まだ見えなかった))

    1. t1のput(k1,v1)
    2. t2のput(k2,v1)
    3. t2のread(他のv1無し(まだ見えなかった))
    4. t1のread(他のv1無し(まだ見えなかった))

正確には、先述のvisibilityの仮定から、ReadがWriteの結果を「先取り」してしまうことはあり得る。「アラートがあがらない保証がある」ではなく、あくまで「アラートが必ずあがる保証がない」ということに注意


 これで、visibilityがあるのとないのとでは本質な違いがあることが分かっていただけたかと思います。この違いは性能面でも顕著に現れます。visibilityを担保しなくてはいけない処理系は、visibilityを担保しなくても良い処理系に比べて性能が低くなります。CAPの定理を説明する上では、とりあえずこのようなVisibility(と最低限のatomicity)を備えたものを「Cのある分散DB」、備えていないものを「Cのない分散DB」と考えておけば良いです。

Availabilityとは
 Availabilityとは、「failしていないノードに発行した(発行できた)リクエストは、必ずレスポンスを返さなければならない」ということです。リクエストが発行できたなら、必ず結果が返ってこなければいけないということですね。

Partition Toleranceとは
 Partition Toleranceとは、分散システムにおいて、ノード間で通信ができなくなってもAvailabilityまたはConsistency(のどちらか1個)が保持されることです。「通信分断耐性」とでも訳せるでしょうか。分散システムなので当然複数のノード(サーバ)があるわけですが、これらノード間で通信ができなくなっても、システムが機能を維持できる特性のことです。機能といってもAvailabilityを保証するシステムもあれば、Consistencyを保証するシステムもあるので、「Pを備える」という言葉は、システムによって違う意味を持ちます。Availabilityを保証するシステムでは、ネットワークの分断が起きてもAvailabilityが保証され続けることを意味し、Consistencyを保証するシステムでは、ネットワークの分断が起きてもConsistencyが保証され続けることを意味します。

※正確な定義、CAPの定理の証明についてはLynch & Gilbertの論文を参照

具体例
 ちょっと分かりにくくなってきたかもしれないので、具体例で説明しましょう。例えば、DNSは典型的なAP型システムです。DNSでは、DNSサーバ1に問い合わせると「見つからない」というレスポンスが返ってくるが、DNSサーバ2に問い合わせるとちゃんとIPが返ってくる、ということが日頃起きています。そのうちどちらのサーバも最新に更新されていくわけですが、ラグがあったりして、少なくともある時点に着目したときに、問い合わせるサーバによって結果が異なることがあり得る、つまり、「全員が同じ状態を見るという保証がない」ため、Consistencyが破られていることになります。
 さて、ある日ルータの故障か何かでDNSサーバ1と2の間の通信が不能になったとします(Partitioningの発生)。DNSでいうPartition Toleranceとは、この状況でAvailabilityを保証し続けること、すなわち、DNSサーバ1へのリクエストも、DNSサーバ2へのリクエストも、必ずレスポンスが返ることを保証することです。DNSサーバ1,2の間で通信ができなくなったところで、更新が遅れるだけで、引き続きどちらのサーバに対してもRead/Writeは実行できるため、Availabilityは達成されていることになります。もし、通信ができないからと言って問い合わせやレコードの追加を拒否する状態になればPartition Toleranceが満たされていないことになります。


 逆にCP型のシステムにはどんなものがあるでしょうか?最も分かりやすいのは、2つのノードで同期的にレプリケーションを行っているリレーショナルDBです。どのWriteも、両方のノードのディスクに書き終わらない限り完了しないという設定で組んでいるとしましょう。もし2つのノード間で通信が途絶えてしまったら、両方のディスクに書けないのでシステムは機能を失ってしまいます。それでは不便なので、「通信が途絶えたら、IPの若い(順番が)方が自分のディスクだけをつかってオペレーションを継続する」という約束をすれば、通信が途絶えてもIPの若いほうが生きてさえいればオペレーションを続けることができます。しかし、IPが古い方のノードは「failしていないのに応答できない(正確には『リクエストを実行できない』というエラー応答となるわけですが)」ことになり、「failしていないノードはリクエストに応答しなくてはならない」というAvailabilityの条件を満たさなくなります。もし両方ともオペレーションを続けたら、Consistencyを保てなくなる点に注意してください。例えば、ノード1にWriteした結果が、ノード2からは見えないわけですので、こういう約束をしていなければシステムを止めなければいけなくなります。
 ノードが1つだけオペレーションを続けたときは、当然従来通りConsistencyが保たれます。

 CAPの定理に従えば、残るはAC型のシステムですが、これがCAP定理を理解しにくくしている原因の1つであるとAbadi氏は主張します。AC型のシステムとは、Partitioningが起きない限りはAvailableかつConsistentなシステムですが、CP型のシステムだって、Partitioningが起きない限りはAvailableなわけです。逆に、AC型のシステムだって、Partitioningが起きてしまったら結局Availabilityを失います。つまり、AC型のシステムと、CP型のシステムは、事実上同一なのです。CAPの定理では「3つのシステム」が作れると説明しますので、AC型のシステムとCP型のシステムは別物と考える人が多く、混乱を招いていると氏は主張します。


と、とりあえず今日はここまでとして、次回はこれを踏まえてAbadi氏が提唱するPACELCについて解説していきたいと思います。


posted by 塩路慧能 (Enno Shioji) at 14:35 | Comment(0) | TrackBack(0) | 分散システム | Subscribe to this blog | Check for updates
×

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