イベントレポート

「実現したいことを計算機の問題に置き換えることが『技術力』」、伊藤CTOが“はてな流”大規模データ処理の極意を語る

関西オープンソースカンファレンス2008セッションレポート

CodeZine編集部[著]

更新日: 2012/07/09
公開日: 2008/11/19

ポスト

大規模データアプリケーションの開発その2

※注

この章の内容の一部に、編集部側の理解不足がございました。伊藤氏が、下記エントリーにてご指摘いただいてるので、併せてご確認ください。

CodeZineにてKOF 2008の記事と補足：Hatena Diary naoya

例3-1：全文検索用の転置インデックス

　新しいはてなブックマークでは全文検索を導入しており、かなり大量のデータを検索する必要がある。さらに、単に時系列順に表示するのではなく「『いい感じ』の文書を上位にしたい、しかも高速に検索したい」となると、RDB検索では最早不可能に近くなるので、情報検索のアルゴリズムをしっかり活用しなくてはいけないという。

　具体的には、RDBのデータをバッチで取得して、転置インデックスを作成する。あらかじめ検索されるであろうキーワードで「索引」を作るという方法を採用している。RDBMSと同じことを自前でやるわけだ。「あらかじめ検索されるであろうキーワード」は、MeCabで分かち書きするなどして用意しているという。

　転置インデックスを利用すると、大規模データを高速に検索できるだけでなく、アルゴリズムを工夫してやればランク付けされた検索（ranked retrieval）、つまりスコアリングして『いい感じ』の文章を抽出できる。このスコアリングの設計と実装が肝のようだ。

　転置インデックスでは、ソートされていることが非常に重要だという。ドキュメントをID順に並べておくとID番号の差分を取って、デルタ圧縮という手法でデータを小さく持つことができる。データを小さく持てれば、ディスク上で占める領域が小さくなり、ディスクI/Oでディスクにアクセスする回数が減る。

　従来は、ディスク上のサイズを小さくすること自体が圧縮の目的だったが、最近はそれによってディスクアクセスを減らし、I/O負荷を減らすことが焦点になっているという。

例3-2：検索結果のスコアリング

　転置インデックスのpostings listからIDを取ってきただけでは、どれがいま自分が1番欲しいドキュメントか分からないため、スコアリングが必要になる。

　はてなでは「ベクトル空間モデル」という手法を用いている。クエリやドキュメントをベクトル化して、ベクトル空間上でどのドキュメントのベクトルが近いかを計算し、検索のスコアリングを行う。検索の基盤になる技術だ。

　「ベクトル空間モデルは、古典的で理論的な裏づけが弱いモデルだが、十分にうまく動作し、しかも速い。より正確で理論的な裏づけも強い確率モデルなどもあるが、ユーザービリティの面で長があるベクトル空間モデルが、最近は大抵のWeb検索エンジンのベースになっている」と伊藤氏は説明する。

　ベクトル空間モデルでは、辞書の単語数次元の内積を大量に計算しなくてはならない。辞書にあってもそのドキュメントに登場しない単語は出現確率がゼロになることから、ゼロがたくさんある行列を計算する古典的なアルゴリズムは確立されており、計算コストを下げることができる。

例3-3：その他の技術

　ベクトル空間モデルでは、辞書に含まれてない単語は探せない。例えば、新人アイドルが突然大ブレイクすると、辞書に掲載されるまでは検索漏れが発生することになる。これを補うために「Compressed Suffix Arrays」という部分文字列検索の技術を利用している。これは、戦略提携する株式会社プリファードインフラストラクチャーの検索エンジン「Sedue」によって実現している。

　また、サーバー1台で処理しきれないような大量なデータを解析する際には、Googleが考案した「MapReduce」という複数サーバー技術で並列分散処理している。具体的には、Yahoo!が実装した大規模分散計算フレームワーク「Hadoop」により、タスクをメモリ中で処理できるよう細切れにして、ディスクを使わないでメモリで処理するという。