CodeZine にて KOF 2008 の記事と補足
大阪南港ATCで開催された「関西オープンソース2008」の2日目（11月8日）午前中のセッションで、株式会社はてなCTOの伊藤直也氏が「はてな流大規模データ処理」と題した発表を行った。
CodeZine で先日の KOF 2008 (あらかじめ言っておきますが King of Fighters ではないですよ、関西オープンフォーラムです) の発表を記事にしていただきました。ありがとうございます。
発表資料は以下のエントリーにありますので一緒にご覧いただければと思います。
さて、記事内容について少し補足をしておきたいと思います。
メモリとディスクの速度比較について
「メモリはディスクの 150 倍」という話ですが、その後知人と話して検索のインデックスをシークする場合などは ms 対 ns くらい違うよ、という風に教えていただきました。詳しくは資料のエントリーの追記をご覧ください。150 倍というのはデータ転送速度です。この文脈の話から行くとシーク速度の話をするべきでした。知識がいたらずすみませんでした。
メモリを増設して I/O を分散する方針について
この補足は蛇足だと思いますが念のため。
I/O 分散はキャッシュサイズのサイジングをしっかり行いましょう...という意味で「単純にメモリを増やすことで、I/O負荷を軽減させることができる」のはその通りです。ですが、それは当然 I/O 回数を最小化するアルゴリズム、ドメインロジックを採用した前提での話になります。「アプリケーションで対応しないでハードで解決しなさい」という意味ではないのであしからず。またページキャッシュに関しては read/write のどちらの負荷を減らすかによって話が違って来ます。
SQL の JOIN を使わない方針について
これも蛇足ですが「JOIN を使わない」というのは分散を前提とすると是なのですが、必ずしも JOIN クエリが悪いという話ではありません。
しっかりインデックスを効かせた上で、それほどデータ量の増加が見込まれないテーブル同士であれば JOIN しても構わないでしょう。また JOIN クエリでなければなかなか出力が難しい計算結果というのがもちろんあります。
巨大なテーブル同士を JOIN していると、そこが密結合して分散時に困るので、データ量的に支配的なテーブルはあらかじめ分散を前提に、JOIN を使わない方法で回避したほうが良い、という風に考えています。
JOIN を使うと分散できないというものでもないし、絶対に使ってはいけないという意味ではありません。
キーワードリンクの実装について
キーワードリンクの実装には Aho-Corasick や Double Array TRIE の話を取り上げましたが、現在のはてなダイアリーやはてなグループでは別の実装を使っています。Aho-Corasick, Double Array TRIE はいずれもキーワードリンクのような機能を高速に実装できる例であって、はてなで利用しているのはまた別という風にご理解ください。
ベクトル空間モデルと Compressed Suffix Arrays について
はてなブックマークの検索は PFI さんが開発した Sedue で実現されています。Sedue は Compressed Suffix Arrays を軸にした、大規模データに対してスケーラブルな検索エンジンです。(Sedue はアルゴリズムが優れているだけでなく実装の技術もハイレベル、高速で素晴らしいエンジンです)
さて、記事中ではベクトル空間モデルに対して CSA が比較されていますが、ここで CSA と比較したいのは転置インデックスです。(ベクトル空間モデルは比較対象としては層が違います。) 転置インデックスの辞書を分かち書きあるいは N-gram 辞書で実現するときの欠点に対して、CSA などの圧縮全文索引があるという風にご理解ください。
ベクトル空間モデルの話は、データベースでは扱い切れない検索要求をどう処理するか、という文脈での紹介になります。ベクトル空間モデルは情報検索だけでなく、クラスタリングやテキスト分類など様々な手法の基盤となるモデルです。ブックマークのテキスト分類でも、Complement Naive Bayes でスコアリングしたものを Cosine Similarity 相当のアルゴリズムで足切りしています。
会場での自分の説明が至らなかったものが多かったと反省しています。申し訳ありません。ほかにも何か間違い、不明な点などありましたら是非フィードバックをお待ちしています。
