9月もおわり。10月といえば OSDI '10 で Percolator のはなしがあるので、いまのうちに予習をはじめることにした。
Caffeine
今年の6月、Google は Caffeine という新しいインデクシングシステムの完成をアナウンスした。Google Official Blog いわく
- Web はサイズだけじゃなく、内容も豊かに、複雑になっている: 動画、画像、ニュース、リアルタイムな更新情報など。
- ユーザーの要求するレベルも高くなっている: 検索する側は適合度が高く新しい情報をみたいし、される側も更新がすぐ反映してほしい。
- いままでの Google のインデックスは更新頻度ごとに複数の階層にわかれていて、ページをクロールしても、それが検索結果に反映されるまでに期間があった。
- Caffeine では Web を部分ごとに分析してインデックスを常に更新している。誰かがページを更新してから、Google の検索結果に反映されるまでがはやくなる。
ということらしい。
MapReduce を使ってない
それからしばらくたって、9月になってから Caffeine は MapReduce を使ってない という話がでてくる。The Register の Eisar Lipkovitz (Akamai -> Google) への取材で
- Caffeine は MapReduce じゃなくて Bigtable を使っている。
- 論文は来月の OSDI に出す。
- MapReduce でインデックスを作るのは、複数段のバッチ処理になっているのだけど、これは前段が終わるまで次の段がはじまらないし、どこかで詰まるとそれを待ってしまう。
- Caffeine では Bigtable 上の更新がそのままインデックスの更新になり、クロール結果がすぐに反映される。
- システムは GFS2 (社内では Colossus と呼んでいる) に支えられている。もともとの GFS ではだめだった。
- Colossus は Bigtable むけに設計されていてる。GFS の一般的な用途とは違う。
- MapReduce が終わるわけではない。Google の最大の MapReduce アプリケーションであるインデクシングまわりが移行した、というだけ。
なんてことが明らかになった。The Register の最後の2段落が煽り気味のせいか、これは結構センセーショナルに伝えられたように思う。たとえば Googleは既にMapReduceを使っていない には
MapReduceは結局データベースを知らない奴が書いたのさ
なんてひとことまで引用されているけど、この発言者は MapReduce の宿敵 Michael Stonebraker 先生なので、まあ、適度にわりひいたほうが良いんじゃないかと。
Percolator
そして9月24日。参加者は OSDI の論文が読めるようになったのか、The Register に 続報 が出た。論文では Percolator という分散逐次情報処理システムが説明されているらしい。
ただこの The Register の記事は、MapReduce だけは論文をみていて GFS, Bigtable は追ってなかった私にはちょっときびしかった。
予習
ということで Percolator の論文全体が公開される前に予習をしておこうと思う。
MapReduce は
- MapReduce: Simplified Data Processing on Large Clusters
- MapReduce: A Flexible Data Processing Tool
- これは MapReduce and Parallel DBMSs: Friend or Foe への反論なのでこっちも読んだ方がいいかも
Bigtable は
GFS は
あたりを読めばいいのかなあ。ちなみに MapReduce のところに挙げた3つ以外は全部未読です。