CAPのCとACIDのC

» Permanent link | |

CAP 定理と BASE の概念を考えたのは UCB の Brewer 先生で、彼は inktomi の偉い人だったというのは前回述べた。

当時のinktomiはYahoo!や Microsoft、それにgooにも検索エンジンを提供していて、1億以上のWebページ(テラバイト級のデータ)を扱っていたようだ。

手元のWEB+DB PRESS Vol.49 のはてなブックマークリニューアル記事によると、現在のはてなブックマークは1160万URLと100GBのHTMLデータ(圧縮済み)を扱っているらしいので、ざっくりいって98年の時点でinktomi は現在のはてブの10倍のデータを扱っていたといってもいい。inktomiで使っていたコンピュータの性能は現在のPCサ ーバに比べれば1/10程度の性能なので、システム全体でみると現在のはてブの100倍の規模になるだろうか。

結果的には、inktomiのビジネスは失敗し、検索大手の座はGoogleに奪われることになるのだが、Googleに数年先ん じてWebのための分散システムを構築することでBrewerはWebスケールの分散システム構築における理論的基盤を獲得す るための経験値を得たのだと思う。

彼がこの時点で得た理論的基盤というのがCAP定理と伝統的なACIDトランザクションを緩和するBASEという考え方で ある。これが2000年の話。

CAPは2002年にMITのSeth Gilbert と Nancy Lynchによって形式化され、 晴れて定理となる。CAP定理によれば

• Consistency (データの整合性)
• Availability (システムの可用性)
• tolerance to network Partitions (ネットワーク分断への耐性)

の三つのうち同時に達成できるのは常に二つしかない、ことが明かになっている。

CAP のうち、AとPの意味するところは簡単にいうと以下のようになる。

Availability は分散システムにおけるデータの受給者(簡単にいうとブラウザなどのクライアントのこと)が、 常にサービスにアクセス(読込みも、書込みも)できるということを保証する。 サーバ側の都合でデータにアクセスできないことがあるとき、そのシステムは Availability を満たしていない。

Partition tolerance は、分散システムを構成するノード(簡単に言うと物理・仮想サーバ)がひとつ壊れたとして もシステム全体が問題なく動作しつづけることを保証する。 システム中のデータを保持しているサーバのうち1台がが物理的にクラッシュしたときに、 データの読込みや書込みができなくなったら、そのシステムは Partition tolerance を満たしていない。

残りの一つ、Consistency はACIDのCと混同しがちであるが、両者の定義は違う(ここ重要)。 ACIDトランザクションの文脈での C は、 Wikipediaでは以下のように説明されている。

日本語では一貫性とも呼ばれる。トランザクション開始と終了時にあらかじめ与えられた整合性を満たすことを保 証する性質を指す。つまり、データベースのルール、つまり整合性条件を満たさない状態を起こすようなトランザクシ ョンは実行が中断される。

預金残高を例にすると、その値は一般的に0あるいは正の値を取る条件を満たす必要がある。よって、口座Aから送 金を行うとき、その前後でAの口座残高が負になるような額を送金することはできないが、これを保証するのが Consistencyの役割である。

これに対してCAP 定理の C は異なる。 CAPの Consistency は、あるクライアントがシステムのデータを更新したら、 続いてアクセスするすべてのクライアントが必ず更新されたデータを取得できることを保証するものである。

このconsistency をめぐる混乱は、CAPとBASEの議論をわかりづらくしているように思える。 実際に Seth Gilbert と Nancy Lynchの論文では Consistency という言葉は使わずに、 Atomic data object という言葉を使っている(しかしこの Atomic も ACID の Aとは定義が違うので注意!)。

インターネットスケールのサービスでは、 必然的に並列処理とノンストップのサービスが求められるので、 可用性とネットワーク分断耐性が必須となり、CAP定理に従えば整合性については妥協することになる…

…なる、はずだが現在のWebサービスは、超大規模な分散システムとして運用されているにもかかかわらず、 CAPのC(整合性)も満たした上でA(可用性)とP(ネットワーク分断耐性)を実現しているように見える。

実はいろいろな大規模サイト(Amazon, eBay, Windows Live, ...)が、 CAP/BASE を知ってか知らずか、独自にそれぞれ分散システムを作ってきたら、 可用性とネットワーク分断耐性を確保しながら、 ある程度の整合性を確保するような分散システムの構築方法について同じような結論を得て、 その理論的背景として CAP/BASE がぴったり収まった、というのが面白いところだと思う。

この分散システム構築のノウハウのキーワードとなるのが BASE の E、Eventually Consistent という考え方なのである。

つづく