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 という考え方なのである。

つづく

CAP と BASE について調べたこと

» Permanent link | |

時系列で

• 1990年代後半: Eric Brewer (UCB)が inktomi でいろいろ作る
  • CAPとBASEの基礎ができる
  • http://www.ccs.neu.edu/groups/IEEE/ind-acad/brewer/
• 2000年7月19日: Eric Brewer が PODC (Principles of Distributed Computing) の基調講演で CAP 定理?と BASE を発表
  • CAP は Brewer 予測として知られるようになる
  • この時点で、inktomiと同等スケールのWebサービスの問題に対処していた人はあまりいなかったのかもしれない
• 2002年 MIT の Seth Gilbert と Nancy Lynch が CAP を形式化
  • ここで Brewer の CAP が晴れて定理となった
• この間、よくわからず
• 2007年-: eBay の Dan Pritchett が CAP/BASE ベースでいろいろ考える
  • Colorado Software Summit 2007
  • InfoQ の記事とインタビュー
  • QCon 2008
  • 2008年1月の ACM Queue に Dan Pritchett の記事(BASE an ACID alternative)が載る
• 2007年- Amazon CTO の Werner Vogels が Eventually Consistensy 関係でいろいろ
  • QCon London でのプレゼン (2007/08)
  • Eventually Consistent のエントリ(2007/12)をポスト(日本語訳)
  • CACM に Vogels の論文(Eventually consistent)が載る(2009/01)
• 今ここ

歴史的には Brewer が inktomi の創業者であることが興味深い。

すでに inktomi を知らない人がいるかもしれないけれど、 検索エンジンの淘汰の歴史の流れの中で AltaVista と Google の間にいるのが inktomi だ。 inktomiは創業が1996年。Web初期の検索エンジンの座をAltaVistaから奪い、後にYahoo!に買収された。

Wikipedia の記事が詳しいが AltaVista が DEC の Alpha サーバの性能を売りにした scale-up 的アプローチだったのに対し、inktomi は Scale-out 的アプローチを取ったのが(AltaVistaに対する)技術的な成功要因だったようだ。Brewer のスライドの写真を見ると、時期的にはどうやら Sun の UltraSparc II のクラスタを構築していたようだ。これはまさに僕がNAISTの自席で使っていたワークステーションだけれど、CPUが250MHzで640MBメモリを搭載していたと記憶している。

inktomiが取ったこのscale-out戦略ベースのアーキテクチャは今のWebの大規模分散システムの根源となるアーキテクチャとなっている。

つづく