Thursday, February 2, 2012

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回しか入っていないマップを得ることがアプリの目的です。

def insert(kx, vx):
    map.put(kx, vx)
    for ky, vy in map.values():
        if vx == vy and ky != kx:
            delete_list.add((kx,ky))



さて、今まさに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について解説していきたいと思います。

What will happen with Ethereum in 30 years?

tl;dr : We will continue to have a decentralized, global chain powered by ETH, but most of the economic activities using smart contracts ...