XML と REST/Web サービス関連の話題が中心の weblog です
» Permanent link
|
先週の金曜日に開催された yokohama.pm で、最近のこのブログのメインネタである CAPとBASEとEventually Consistentについてお話してきました。 このネタ、あまり公の場で話すチャンスがないのでこういう機会をいただけてよかったです。 ありがとうございました。
最近なにかと忙しくてあんまり更新できませんが、 まだ続く予定です。
そんじゃーね
ラベル: base, cap, eventuallyconsistent
posted by yohei @ 14:26
0 comments
links to this post
» 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定理によれば
の三つのうち同時に達成できるのは常に二つしかない、ことが明かになっている。
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 という考え方なのである。
つづく
posted by yohei @ 07:40
0 comments
links to this post
» Permanent link
|
時系列で
歴史的には 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の大規模分散システムの根源となるアーキテクチャとなっている。
posted by yohei @ 14:08
0 comments
links to this post
» Permanent link
|
2年間 WEB+DB PRESS で連載してきましたが、今回ついに最終回となりました。 正直 REST ネタでこんなにも書くことがあるのかと今でも不思議です。 ほとんどコードが登場しないで文字ばかりという異色な連載を載せ続けてくれた編集部さんに感謝です。 あと毎回締切ギリギリになってすんませんでした。
ところで最終回のネタですが、連載を始める前からずっと書きたかったリソースモデリングについてやっと書くことができました。 まだまだ確立された手法とは言い難いですが、僕なりにまとめてみたものです。 みなさんの Web システムを RESTful にするお手伝いができればいいなと思っています。
ありがとうございました。
posted by yohei @ 13:11
0 comments
links to this post
» Permanent link
|
国島先生や斉藤先生が XML や半構造データについていろいろ書いてくださっており、それに反応する形ではてなブックマークや twitter 上での議論が日本語で進んでいて面白い。
ブックマークや twitter で細かいコメントを書いているだけでは申し訳ないような気がするので、久々にエントリを書こうとしたのだけれど、なんだかバックグラウンドが長くなってしまった。最先端の研究者のみなさんに失礼な物言いもありますが、XML guy としては XML の話題は釣られるものなのでご容赦ください。
僕の個人的なコンピュータの原体験は、当時電電公社に勤めていた伯父からもらった PC-8201 である。これはいわゆるハンドヘルドコンピュータで、僕はこれを80年代後半に手に入れた。すでに世の中の流れからは置き去りにされてしまった悲しいコンピュータだったが、N82 BASIC が40文字×8行の液晶で動作して、プログラミングができた。
僕が作ったプログラムは F1 データベースで、歴代のチャンピオンがファリーナ/ファンジオからプロスト/セナまで検索できるものだった。このプログラムはデータとコードと画面がぐちゃぐちゃに入り混じった大変格好の悪いものだったが、それでも自分が書いたプログラムが動作する快感を知ることができたし、何より自分の中では実用的だった。
PC-8201 のあとはプログラミングへの興味は薄れ、 PC-9801 RX21 でゲーム(A列車で行こうIIIはやりまくったなあ)をしたりしていた程度だったが、94年に大学に入学し、その年の暮に「インターネット」の存在を知り、年明け早々に大学ネットワークのアカウントをもらったことでコンピュータ熱が再燃した。MLも入りまくったし、ネットニュースもさんざんチェックしていた。SunOS4 の上で、NCSA httpd 経由の CGI (JPerl4)でご多分にもれず掲示板を作ったりもしていた。
こんなことを書いてるとおまえは情報系の学生だったのではないかと思われるかもしれないけれど、僕はれっきとした機械工学の学部生で、卒論はロボット(特にScara)のシミュレーションを OpenGL でやっていたりした。
ロボットの研究はとても面白く、研究室も居心地がよかったのだけれど、一方で自分の中では Web、特にマークアップ言語・構造化文書としての SGML/XML への興味が非常に大きくなってきたため、当時 XML を研究対象にしていた数少ない研究者のおひとりである当時 NAIST (現京大)の吉川先生の研究室に行くことにした。幸い NAIST は大学院大学という特性もあり、情報系以外の学生にも手厚く教育をしてくれ、おもに M1 のときに僕はデータベースシステムについて学んだ。
当時(90年代後半)の XML 業界はある種異常な雰囲気に包まれており、当時世間知らずの田舎学生だった僕の目から見てもアヤシゲなベンダーやコンサルが入り乱れていた(日本国内も、米国も)。それでも毎日 W3C TR のページは必ずチェックし、xml-dev/xml-user を購読し、暇さえあれば XSL(T) のアップデートを追随する毎日を送っていた。
XML勧告直後からは、村田さんという偉大な存在があったこともあり、日本国内でも XML コミュニティが立ち上がった。XML開発者の日というイベントは、昨今の勉強会・カンファレンスブームのさきがけだったと思う。そして、僕はそのコミュニティである程度のポジションを得ることができて、世の中にはすごい人がいるということを実感した。
当時から今まで、僕の基本的な興味のスタンスは変わっていない。僕にとって XML はあくまでも応用ありきである。もちろん基本知識として XML 1.0 のスペックは抑えなければいけないし、最低限 DOM/SAX/XSLT (今なら XQuery か)を使って XML 処理を行えなければならないが、しかし仕様をいくら知っていても、変換プログラムがいくらあっても現実の世界では役に立たないのである。XML で最も重要なのは XML インスタンス、XML 文書そのものであり、スキーマや各種 API はそれを便利に使うための補助ツールでしかない、という意識が僕にはある。
では僕にとって重要な XML 応用は何かというと、当時でいえば XHTML であり、現在はそれに Atom/RSS と microformats が加わったくらいである。もちろん必要であれば docbook を使うし(Markup Technologies99(XML99併催)の論文は docbook で書いた、というより書かされた)、ODF や OOXML も使うのだけれど、自分の中で重要なのは簡単にいえば XHTML と Atom なのである。これは言い換えると Web 上で流通するデータである。
Web はデータベースか? この問いに対する答えは人によって異なると思うけれど、僕の答えは簡単だ。Web はデータベースである。しかし、Web はデータベース管理システムではない。
Web には集中管理機構はない。Web はその名の通り世界規模の分散システムであるが、そのアーキテクチャは集中的な管理機構で守られるのではなく、統一インターフェースとアドレス可能性というアーキテクチャスタイル(制約)で形作られている。
つまり Web 上のデータというのは、管理システムの制約から解放され、(RESTの制約にさえ逆らわなければ)自由にただデータとして振る舞うことができるのである。ここが RDBMS 中に格納されたデータと Web 上のデータの一番の違いだと思う。
Web 上のデータは、あらゆるプログラムから独立して生き延びることができる。Web 上のデータはプログラムによって性格を変える。Web アプリケーションを作る人と、検索エンジンを作る人、フィードリーダを作る人が独立して作業を行えるのは、Web上のデータがプログラムから独立しているからである。
XML の最も革新的な一面をあげるとすれば、僕は真っ先に整形式を許したことを挙げたい。XML ではスキーマが明示的に存在しなくても、プログラムからデータを利用可能になったのである。XML 文書に固定的なスキーマはない。これは逆に言うと、一つのXML文書に複数のスキーマを適用してもいい、ということになる。
一つのXML文書に複数のスキーマを適用できるとどうなるのか。それぞれのスキーマごとに、一つのXML文書が違った顔を見せるようになるのである。たとえばあるフィードリーダから見ると単純にサイトの新着情報を通知してくれていたAtomフィードが、OpenSearch 拡張を解釈できる検索アプリから見ると検索結果一覧に見える、といった具合である。
これはすなわち、XML文書はアプリケーションプログラムから独立しており、それはつまり Web 上のデータが持つ特性そのものである(整形式と名前空間でその特性をエンハンスしている)。
「Web 上のデータ」とさんざん言ってきたのだが、わかる人にはわかると思うけどこれは "Data on the Web" なわけである。僕の意見がどれくらい Abiteboul 先生の意思と被っているのかはわからないけれど、彼の最初の半構造データ論文が "Querying semi-structured data" であり、"Managing semi-structured data" ではなかったのは何かを暗示しているような気がしてならない(単なる思い込みかもしれないが)。
半構造データとは Web 上のデータであり、原理上 Web 上のデータは集中管理できない。なので単一の「管理システム」は存在するはずもない。逆に言うと単一の管理システムで管理できるような XML データは半構造データの文脈を持っていない XML データなわけで、そのようなデータは本来のモデルに基づいて管理するのが正しい姿だと思われる。
ラベル: semistructureddata, xml
posted by yohei @ 09:05
0 comments
links to this post
この日記に記述されている内容は、筆者の個人的な主張や考えであり、筆者の勤務する企業や属する組織とはまったく関係ないことをお断りしておきます。
この作品は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。