前回 は Michael Stonebraker らの "MapReduce and Parallel DBMSs: Friends or Foes?" を紹介した。
ひとつは MR と並列 DBMS を比較し、実際に Hadoop と商用の DBMS でベンチマークもとったけど DBMS のほうが速かったよ、という Michael Stonebraker らによる "MapReduce and Parallel DBMSs: Friends or Foes?"。これは、同著者ら (ただし 1st author はちがう) による "A comparison of approaches to large-scale analysis" の続きというかまとめ的な感じ。
CACM に載っていたもうひとつが、Andrew Pavlo らの "A comparison of approaches to large-scale analysis" での MapReduce vs. 並列 DBMS に意義を申し立てる "MapReduce: A Flexible Data Processing Tool" だ。著者の Jeffery Dean, Sanjay Ghemawat は2004年のそもそもの MR 論文 ("MapReduce: Simplified data processing on large clusters") を書いた Google のひとです。
MapReduce: A Flexible Data Processing Tool
著者らはまず、先の論文や Stonebaker, David Dewitt のブログ記事には MR に対する誤解があることを指摘し、さらに MR の利点を紹介。彼らの結論は特定の実装にもとづくもので、欠点も MR 一般に通じるものではない、という。
MapReduce のつかいかた
最初は「MR はそれ単体ですべてをやるものではないよ」というはなし。
多くのシステムは顧客情報を RDBMS に、ログをファイルシステムにと、様々なストレージを組み合わせて構成されている。MR はこのような混成 (hetorogeneous) なシステムに、情報を分析するためのシンプルなモデルを提供するものだ。MR を新しい種類のストレージで動かすには、ユーザーが簡単な reader, writer を書いて拡張するだけでよく、実際に分散ファイルシステムやデータベース、Bigtable まで、様々なストレージが使えるようになっている。これに比べると、並列 DBMS は分析前にまずデータを INSERT しなくてはいけない。これは不便だし、おそらくは許容できないくらい遅いだろう。
また、MR にはインデックスの利点をうけられないというが、インデックスがあるデータがあるなら、それを最初に使うことはできる。DBMS が元データならそこでインデックスのきく SELECT 文を書けばいいし、ログファイルならふつう日付をファイル名にいれてローテートさせるので、全ファイルを MR に渡して日付でしぼりこまなくても、あらかじめ特定のファイルだけを渡せばいい。
次に、著者らは MR で実際に行っている (つまり Google でやっている) SQL で書けない複雑な処理を紹介していく:
- HTML の文章群からリンクをあつめて、それをリンク先でまとめる
- 衛星写真をつなげつつも重複部分を省き、Google Earth むけの画像をつくる
- 検索でつかう圧縮された転置インデックスをつくる
- 世界中のすべての道路のつながりを処理して、Google Maps むけのタイル画像をつくる
- Sawzall や Pig Latin (Hadoop で使える) のような高級言語で書かれたプログラムを、耐障害性のあるかたちで並列実行する
さらに、理論的には UDF で出来るといっても、実際の Pavlo らのベンチマークでは DBMS-X で UDF を使ったときにはバグをふみ、Vertica にはそもそも UDF 自体が無かった、というところにも触れている。
実装上の工夫
ここからは実装上の工夫のはなしが続く。
まず、著者らは Pavlo らの主張するスキーマの有用性を認め、だから Google では MR でも大抵 Protocol Buffers を使っているよ、と続ける。それはそうですよね。
次に、push vs. pull モデルのはなし。pull モデルがたくさん小さいファイルを生成したり、mapper と reducer の間で多くのディスクのシークがあるのは事実だ。しかし、Google の MR 実装ではバッチやソート、中間データのグルーピングや読み込みのスケジューリングなどの "implementation tricks" でそのコストを軽減させている。また、MR が push モデルなのは、決して耐障害性だけのためにあるものではない。実際に障害が起きることはそんなに多いわけではない。しかし、例えば Google のクラスタのスケジューラは、より優先度の高い MR タスクのために他のタスクを殺して場所をあけたりしてくれる。こういう際にも MR が自動的かつ部分的に再実行できることは重要になるという。
Google が扱うデータ量は、あるいは Google 外でも、大量のデータを相手にしなくてはいけない局面は、日々拡大していてる。データ量が増えれば、MR のような耐障害性のあるシステムを必要とする人々も増えるだろう、と著者らはいう。
最後に、Pavlo らの実行速度についての比較について:
- エンジニアが気をつけるべきところ: 起動のコストや読み込みの速度は実装の成熟度を表すもので、プログラミングモデルとは関係ない。起動コストは MR のワーカープロセスを立ち上げたままにして呼び出しごとに殺さないことで、読み込みの速度は Protocol Buffers のような効率的なフォーマットを使うことで改善できる。
- 必要のないデータも読むのは MR では避けられない: そんなことはない (ここは前述のぶぶんの繰り返し)
- 結果のマージ: マージは必須ではない。MR タスクの結果をさらに他の MR タスクに渡すときは、マージする必要は無い。
- データの読み込み: やっぱり並列 DBMS は遅い。INSERT し終わったものをいろいろなクエリで分析する場合には問題ないかもしれないけど、実際そういうことは少ないだろう。
おわり
というわけで Communication of the ACM の2010年1月号から MapReduce に関する2つの論文を紹介しました。ややすれちがい気味のところもあるけど面白くて、あと並列 DBMS というのは正直初めて知ったので勉強になりました。MySQL 上に似たようなの作れないかなあ。
Vertica は今回だと旧勢力側だけど「Orace より安いぜ」とか「列ベースはださいぜ」とか普段は挑戦者っぽい立ち位置なんですかね。使っている会社のなかには Mochi Media なんかもあり、Bob Ippolito 曰く:
Vertica works well for Mochi, both for ad-hoc and for on-line production queries. It's expensive but so is building your own.
らしい。Erlang のはなし のなかにもごくわずかに出てきます。
MapReduce は、Hadoop がやや残念だったのと、Google での細かな改良と実例が印象的。ただ Hadoop の実装がすごく良くなったとしても MapReduce モデルを使う損益分岐点はまだよくわからず。衛星写真とか日頃取り扱わないし、アクセスログみたいな文字列処理にはオーバースペックな気もします。