はてなブックマーク全文検索機能の裏側
そろそろ落ち着いて来たころ合いなので、はてなブックマーク全文検索機能の裏側について書いてみることにします。
PFI側は、8月ぐらいからバイトに来てもらっているid:nobu-qと、id:kzkの2人がメインになって進めました(参考: 制作スタッフ)。数学的な所は他のメンバーに色々と助言をしてもらいました。
はてな側は主にid:naoyaさんを中心に、こちらの希望や要求を聞いて頂きました。開発期間は大体1〜2か月ぐらいで、9月の上旬に一度id:naoyaさんにオフィスに来て頂いて合宿をしました。その他の開発はSkypeのチャットで連絡を取りながら進めてました。インフラ面ではid:stanakaさん、契約面ではid:jkondoさん、id:kossyさんにお世話になりました。
全文検索エンジンSedue
今回の検索エンジンはSedue(セデュー)という製品をベースにして構築しています。SedueはCompressed Suffix Arrays(圧縮サフィックスアレイ, CSA)というアルゴリズムを核にする検索エンジンです。元々は岡野原さんが未踏で作ったものをベースにしています。
CSAはテキストを圧縮した状態で保持しながら、かつ検索が出来るという面白いデータ構造です。これを使用すると検索用インデックスのサイズが小さくなり、通常は元文章に加えて検索用インデックスが必要なところが、元文章のサイズより少し小さいぐらいのインデックスで検索と文章復元が行えます。本当は情報限界まで縮むのですが、速度とのトレードオフでこのぐらいになっています。
複数台に簡単に分散できるのも特徴です。先ほどのサイズ見積もりから、100Gのデータを高スループットで検索するためには、8Gのメモリを積んだマシンが15〜20台程度で済みます(カーネルが使用するメモリ分多めに取る必要が有る)。文章が増えてきたら、その都度マシンを足せば、自動的にに使用メモリ量をリバランシングします。落ちた時も、そのマシンが担当していたインデックスを他のマシンに移動させます。
はてなブックマークとSedueのつなぎこみ
はてなさんにはWebUIと、はてなブックマークシステムからSedueへの繋ぎこみの部分を作成していただきました。また、インフラも用意して頂いています。
Sedueには"文章登録"と"検索"の2つの操作ができます。
誰もブックマークされていない記事を誰かがブックマークすると、JobQueueサーバー(TheSchwartz)にそのurlが挿入されます。挿入されたurlについて、順次ページの取得と本文抽出を行い、Sedueに登録要求を送信します。
Sedueは文章が更新されると、定期的にインデックスを自動アップデートします。この際、より早く多くのブックマークが付いたものから優先的にインデクシングする仕組みを入れてあります。すぐにホットエントリーになったものについては、2〜3分で検索に反映されていると思います。
検索のほうは、言うまでもないですがUIに単語を入力した時にSedueにクエリーを投げます。検索結果としてヒットしたエントリのIDリストを返すので、それを使用してUI側で色々な情報(お気に入りユーザー等)を表示して頂いています。
登録・検索をするにはSedueのサーバーにSocketで繋いで独自のプロトコルでデータを送ってもらう形になっているのですが、id:naoyaさんがサクっとPerlのクライアントライブラリを作ってくれました。この辺りの仕事の速さは流石すぎました。
Sedueの改良
当初はそのままSedueをインストールすれば終わるんじゃねぐらいに思っていたのですが、そう甘くも行きませんでした。
一番問題となったのは登録時のパフォーマンス。Sedueでは今まで適当に本文を1文章1ファイルで格納していたのですが、バッチで全文章を登録するとなるとこれでは遅すぎたので、TokyoCabinetを使用して本文を保存する事にしました。
な辺りが決め手でした。これで劇的に速度が改善し、色々と作業が進め安くなりました。mikio先生++。あとは統計情報を各プロセスから収集する機能を作ったりもしました。
Sedueのインストール
現状では、はてなのデータセンターにSedue用クラスタを用意して頂いて、そこで検索エンジンを運用して頂いています。id:stanakaさんを始めとするインフラチームの方々にお世話になっています。
起動時にUDPのブロードキャストで他のサーバーを見つける形になっているので、インストールして設定ファイルをばらまき、各ノードにプロセスを1個立てるだけでセットアップが終了します。各サービスの監視や、万が一落ちた際の再起動も、ノード管理機能が勝手にやってくれます。
ランキング関数の作成
さて、今回一番おもしろかったのがランキング関数の作成です。
ソーシャルブックマークサービスには予想以上のメタデータが溜まっており、これらを利用して、どういう面白いランキングを作るかが全文検索機能の肝でした。これは非常に面白い問題です。
既存研究等もサーベイしつつ色々と試行錯誤したのですが、現在は以下の3つを主に使用してスコアリングが行っています。リンク構造は利用していません。
- テキスト自体の情報(TF/IDF値など)
- エントリの持っているメタデータ(ブクマ数、ブクマされた日付、ユーザー、etc)
- 情報鮮度(初めてブックマークされた日からの経過時間)
目指した所としては、やっぱりユーザーさんが面白い！とか役立つ！とか思われるものを上に持って来るということです。汎用の検索エンジンとしてはGoogle, Yahooがもう有るので、別にトップページやWikipediaが上に来なくても良いかな、とか割り切ってます。いくつかのクエリを、おこがましくもGoogle, Yahooと比較してみます。
こういう技術系のワードについては特徴が出ていると思います。結構凄いと思っているのは、Googleの方は世界中で1兆ぐらいのwebをクローリングしてきて、リンク解析を行ってスコアリングしているのに対して、こちらはテキストの内容と人の付けたメタデータだけでスコアリングしています。
全く同じものが1番目になるものもあるのですが、この事実自体が面白いです。はてなブックマーク検索では1000万URL程度しかインデクシングしていないので、圧倒的にインフラコストも少なくしてこの精度が出せています。これは結構凄いと思っていて、確かに網羅性では負けるけれど、メジャーなクエリーに対しては良い結果が返せると思っています。
ただ、逆に現状ブックマークが少ないエンターテイメント系の話題などについては、あんまりぱっとしないですね。この辺は頑張って色々な層のユーザー数を増やして頂く予定です!?。
開発方法については、Sedueではランキング関数の部分はプラグイン(動的ライブラリ)の形になっていて、サーバーを走らせながらランキング関数を色々と変えることができます(C++で記述可能)。これのお陰で試行回数が増え、だいぶ楽が出来たと思います。
あとこだわった所としては、エントリの持っているメタデータを、リアルタイムに使用する部分です。これにはTokyoTyrantを使用しました。
ブックマーク数を例に取ると、ユーザーがブックマークをした際に、更新用のTokyoTyrantにブックマーク数を記録しておきます(eid -> bookmark_count)。TokyoTyrantのレプリケーション機能を使って、参照用のSlaveを並べておきます(/dev/shm/にハッシュDBを置いています)。
これらのTokyoTyrant Slaveを、ランキングプラグインからアクセスする事で、検索されたまさにその時点でのブックマーク数を利用してスコアリングを行います。1つの検索クエリにつき、TokyoTyrantに1万キーぐらいの取得要求が行くこともあって、結構激しいことになってます。でも普通に裁けているので、TokyoTyrant凄い。これぐらいのQPSが出てくれるとKey-Value Storageの応用範囲がぐっと広がって楽しいです。mikio先生++。
先ほどの登録の件もそうですが、mikio先生には足を向けて寝れません。今度飯でもおごらせて下さい。
今後の予定
というわけで、無事に全文検索機能を実装する事が出来ました。個人的には便利に使っているのですが(主に技術系のワードを調べる)、まだまだ検索までの導線が足りないという所が課題と感じているので、まずはこの辺りをはてなの方と議論しながら改善していく予定です。先日リリースした関連エントリ機能については相当な方に使用して頂いているようで、今回もそれを目指して頑張りたいと思います。より良い情報を効率的に得るための施策を色々と練りたいと思います。
もちろんランキング精度については、地道に向上させて行く予定です。また、ブックマークされたページを起点としてその周りをクローリングする事で、超低コストで良質なWeb検索エンジンを作れないかという事も試みています。ブックマークされたページは、Webという膨大な空間の良いサンプリングになっていると思っていて、これを利用しない手はないわけです。
まとめ
というわけで、はてなブックマーク全文検索機能の裏側をご紹介しました。また面白い問題・結果が出てきたら報告したいと思います。宜しければ使ってやって下さい。
ソーシャルブックマークは色々なデータの宝庫で、Computer Scienceをやってる者の端くれとしては非常に面白い事だらけです。この辺り興味がある方は、ぜひ色々議論しましょう。オフィスに来て頂くのも良しです(メール下さい:-P)
あと、検索エンジン周りで困られている方がいらっしゃれば、ぜひ伺わせて下さい:-)
