2006-09-11

近況

今月は貧乏なので慎しく暮らしている. 週末もひきこもりとしてオンラインの記事を読んで過ごすことに. ウェブを眺めているといいタイミングで Google の新作論文が出ていた. ありがとう, Google の中の人.

Bigtable: A Distributed Storage System for Structured Data

これ.

GFS, MapReduce, Sawzall とつづく Google インフラ N 部作の 4 章が幕をあげた. 実はデータベースも作ってるんだぜ, という話. BigTable という名前だけは以前から O'Reilly Radar などに登場していた. ようやく公式な文書があらわれた.

BigTable は GFS をはじめとする Google インフラの上に作られた分散データベース. 少し変わったデータモデルと, 運用までワンセットのヘビーな実装を持つ. 実装の話もまあ面白いんだけれど, それよりデータモデルが印象的だった. 先にその話を書きます.

データモデル: RDB でも BDB でもなく

BigTable は基本的にテーブルひとつが論理単位だ. 複数のテーブル群をまとめて扱う Relational DB とは違う. join とかはない. そういう意味ではどちらかというと Berkley DB に近い. ただ, テーブルは保持しているレコード(行)についてのスキーマを持つ. ここは RDB 寄りだ. また, 行の各列は任意長のデータを持つことができる. 要は BLOB ね. この点は固定長を前提とする古典的な RDB や BDB のどちらよりも 柔軟だと言える.

これだけだと BDB と RDB の中間みたいなものにしか見えないけれど, BigTable のデータモデルには際立った特徴がふたつある.

ひとつは レコード(の列)の中身がバージョンづけされていること. 各レコードはタイムスタンプで識別される複数のバージョンを保持している. だから古いバージョンをとりだすことができる. どれだけ古いものを残しておくかはユーザが指定する. データベースのスキーマでも, よくタイムスタンプや "削除" フラグなどを使って アプリケーションレベルでレコードのバージョンづけをすることがある. BigTable はその機能を built-in で持っている.

もう一つの特徴は, 列の数が "行毎に" 任意であること. 同じテーブルの中のある行は "A:", "B:0", "B:1", という 3 つの列を, 別の行は "A:0", "A:1", "B:0", "B:1", "B:2" の 5 つの列を持つ, といったことができる. prefix が制限されている, この例だと各列とも "A:" か "B:" どちらかの prefix を持っているのがポイント. この prefix を "column family" といい, こいつらはスキーマとして固定されている. でも個々の column family は任意個の列を持てる. スキーマで列が固定されている RDB と比べなかなか強力だ. 論文ではこの構造をざっくり "multidimensional sorted map" と読んでいる.

論文には次のような例がのっている. (ruby 記法なのは私の趣味です.)

 { "com.cnn.www" => { "contents" => "<html> .... ",
                      "anchor:cnnsi.com" => "CNN",
                      "anchor:my.look.ca" => "CNN.com" } ... }

"com.cnn.www" が URL でキー. "contents:" はそのページの本文, "anchor:" ファミリはそのページにリンクしている URL をキーに, アンカー文字列を値に持っている.

column family を強調してこんな風に書いてもいい.

 { "com.cnn.www" => { "contents" => "<html> .... ",
                      "anchor:"  => { "cnnsi.com"  => "CNN",
                                      "my.look.ca" => "CNN.com" } } ... }

map の中に map が入って multi-dimensional ぽくなる.

例を見ればわかるけれど, この多次元のマップというモデルは RDB の非正規化と似ている. たとえば上の例は次のようなふたつのテーブルをひとつに非正規化したものと考えることができる.

create table web (id identity, uri text, content text);
create table anchor (id identity, web_id integer, word text);

RDB だと非正規化は高速化の手段であって, あまり推奨されるものではない. BigTable は関係演算を実装しないかわりにこうした制限つきの多次元マップを用意した. 関係代数のような優美さはなくクセがあるけれど (著者らもエンジニアにとって馴染みがない点を懸念している.) Google のアプリケーション分野には向いたモデルなのだろう. このへんのぎくしゃくした違和感は MapReduce と似ている.

ただ個人的な意見として, 検索 proxy であるところの flino を作った感覚からいうと, このモデルはかなりツボをついている. すごく使いたい. 誰かつくってくれーっと言いたい.

まず, proxy ではウェブから収集したデータを保存する. このデータはキャッシュなわけだから URL をキーとして高速に lookup したい. だから データベースにつっこみたい. でも色々と運用上の面倒がある (less で中身を覗けないとか) ので flino ではファイルとして管理している. 高速 lookup は諦めてファイルシステムにお任せ. でも, ファイルに保存するのはそれはそれで面倒だ. まずファイル名を考えるのが面倒. たとえば大量のファイルを一つのディレクトリには置きたくない. ファイルシステムがへぼいと該当 i-node の検索に時間がかかりそうだし, シェルから扱いにくい. じゃあ ドメインをディレクトリとして分割すればいいかというと, それはそれで偏りがある. (個人の見るページはかなり偏っている. まあブラウザのキャッシュとか他の proxy はこの口だらかいいのかもしらんけどね...) flino では日付単位でディレクトリを分割している. ファイル数は分散するけどぱっと見はわかりづらい.

次に保存したいのはメタデータ. ページには色々メタデータがある. そういうのもページと一緒に保存したい. でもメタデータとページをセットで保存するフォーマットを考えるのは面倒だ. ファイルフォーマットがテキストだと改行をエスケープしないといかんとか. そこでデータベースに入れようとすると, 今度は一部のメタデータが可変長だったりする. flino ではあるメタデータは (疑似 HTTP ヘッダとして) ファイルに, 一部は RDB のテーブルとして保存している. はっきり言って面倒でやってらんない. ウェブのデータは, 本体/メタデータを問わずテキストだったり画像だったりで可変長なものが多い. バイナリも文字列もある. BigTable はそこらへんに神経を使わず同じ仕組みで扱えるのが羨しい.

キャッシュに限らず, 閲覧履歴やブックマーク, メールも似たような問題がある. 結局 Web は "URL で識別できるページとそれに付随するメタデータ" みたいなモデルでかなり広い範囲が扱えてしまう. だから join できなくても, 中心のテーブルに (多くの場合 URL やホスト名を主キーとしたもの) ざっくざっくと データを放り込める BigTable の方がありがたい気持はわかる. flino は内部にいくつかテーブルがあるけれど, 結局ほとんどの SQL はページ ID (URL と時刻の対だと思ってください)をキーに ページのテーブルと別のテーブルを join している.

ついでに flino はタイムスタンプでの versioning もやっている. オープンソースの BigTable があったらこのへん一瞬なわけですよ. もう羨しくて仕方ない.

話がそれた... BigTable は Web や検索をやるにはなかなかよく考えられたモデルだと思う, という話でした.

あとはインデクスについて. BigTable では基本的に主キーでインデクシングされているらしい. 先の例でいうと "com.cnn.www". このへんは BDB みたいなもんだね. API はよくある std::set みたいのを想像すればよさそう. 列ひとつを検索する set.find() 相当の RowMutation, イテレータ相当の Scanner などが 例としてあげられている. 雰囲気を知るには論文のサンプルコードがわかりやすい.

データベースのくせに join がないのはいかがなものかと思うかもしれないけれど, (当人は Database じゃなくて Storage System と呼んでいる...) そこはプログララマが for 文を書くか, Sawzall みたいな高級言語で支援するんだろう. Sawzall の論文にも join についての話がちらっとでてくる. あと MapRecude にも Bigtable 支援はあるようす. そのへんの概念が整理されきっていないのは, システム on progress だということ. いずれはより整理された強力なモデルがでてくるのだと思う. それが Google 製なのかはまた別問題だとしても.

アプリケーション

次は実装について書こうと思ったんだけれど, 正直なところただひたすら大変だねえ偉いねえという感じだった. 色々やっているのだが, 色々あるせいでどのへんがミソなのよくわからない. とりあえずいくつか箇条書きだけしておく.

BigTable を使うアプリケーションの例として, Google Analytics, Google Earth, Personalized Search が挙げられている. user id をキーにもつ Personalized Search のテーブルは 他のサービスにも相乗りされて巨大にふくれあがっているという話は面白い. 複数サービスからの利用などを考慮し, BigTable はフィールド毎のアクセス管理もできるらしい. ふーん.

Google Earth も気になる. Google Earth のデータは, サイズ自体は比較的小さい. かわりに大量のアクセスを高速にさばくため, データのうち大きな割合がオンメモリに置かれているという. そういう設定もできるわけね. Google Earth ということは, BigTable はかなりユーザに近い部分でも使われていることになる. 裏方専用の MapReduce と違う. このごっついシステムがテクスチャや何やらをどかどかと配信しているかと思うと戦慄. もともと Google Earth は keyhole という会社を製品ごと買収したものだった. つまり他所の技術だった. それが今や BigTable というインフラを組込み, Google に帰化している. これはなかなか大したものだとおもう.

そんなこんなでまた一歩 Google 信仰を深めたのでした.

まとめ: