PFI Technologies @ WEB+DB PRESS Vol.49

WEB+DB PRESS Vol.49

WEB+DB PRESS Vol.49

WEB+DB PRESS Vol.49(2009年2月24日発売)にPFI関連の記事が2つ紹介されます。

まず1つ目は、「速習レコメンドエンジン」という特集企画です。

徳永さん(id:tkng)と岡野原さんが中心になって書いた記事で、レコメンドとは？という所から始まり、大規模データの処理方法、そして最新のアルゴリズム(SVD, Locality Sensitive Hash, Restricted Boltzmann Machine, PLSI)まで触れるという超気合いの入った記事になっています。これさえ読めば、レコメンドエンジンの技術的な話題が俯瞰できるという素晴らしい記事になっております。

もう1つは伊藤直也さん(id:naoya)による特集「はてなブックマーク 構築ノウハウ大公開」です。

第4章「情報科学理論の実践」にて、はてなブックマークの検索エンジンとして利用されている全文検索エンジンSedueの紹介をして頂いております。こちらは、Sedueで採用されているCompressed Suffix Arrays (圧縮接尾辞配列)のアルゴリズム的な解説などが載っています。同じ章ではてなブックマークの自動テキストカテゴライズ機能の紹介も説明されています。

これは読者層に合ってるんですかね！と軽く心配になる感じですが、個人的には今からVol.49が手元に届くのが楽しみすぎます。

Sennaサンプルコード

Senna C APIのサンプルコードが意外と見つからなかったので、貼り付け。

とりあえずBasic APIを使ってみた。

コード

#include <senna/senna.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;

static int
do_insert(const string& idxname, const string& type, const string& filename)
{
  sen_rc rc;
  cout << "insert: " << idxname << " << " << filename << endl;

  int flag = SEN_INDEX_NORMALIZE;
  if (type == "ngram")
    flag |= SEN_INDEX_NGRAM;

  sen_index *idx = sen_index_create(idxname.c_str(), 0, flag, 1024, sen_enc_utf8);
  assert(idx != NULL);

  string content;
  ifstream ifs(filename.c_str());
  assert((ifs ? 0 : 1) == 0);
  string line;
  while (getline(ifs, line))
    content += line;

  rc = sen_index_upd(idx, filename.c_str(), NULL, 0, content.c_str(), content.size());
  assert(rc == sen_success);

  rc = sen_index_close(idx);
  assert(rc == sen_success);
}

static int
do_select(const string& idxname, const string& query)
{
  sen_rc rc;
  cout << "select: " << idxname << " << " << query << endl;

  sen_index *idx = sen_index_open(idxname.c_str());
  assert(idx != NULL);

  vector<char> keybuf(1024);
  sen_records *records = sen_index_sel(idx, query.c_str(), query.size());
  while (true) {
    int score = 0;
    int keylen = sen_records_next(records, NULL, 0, &score);
    if (keylen == 0) break;
    if (keybuf.size() <= keylen) keybuf.resize(keylen + 1);
    sen_records_curr_key(records, &keybuf[0], keylen);
    keybuf[keylen] = '\0';
    cout << "\t" << "score: " << score << "\t" << string(&keybuf[0]) << endl;
  }

  rc = sen_index_close(idx);
  assert(rc == sen_success);

  return 0;
}

static void
usage()
{
  cout << "a.out <indexname> <ins> <ngram|ii> <string>" << endl;
  cout << "a.out <indexname> <sel> <string>" << endl;
  exit(0);
}

int
main(int argc, char **argv)
{
  if (argc < 3) usage();

  sen_rc rc;
  rc = sen_init();
  assert(rc == sen_success);

  string cmd = argv[2];
  if (cmd == "ins") {
    do_insert(argv[1], argv[3], argv[4]);
  } else if (cmd == "sel") {
    do_select(argv[1], argv[3]);
  } else {
    usage();
  }

  rc = sen_fin();
  assert(rc == sen_success);
  return 0;
}

コンパイル

$ g++ senna.cpp -O2 -lsenna

実行

$ rm hoge.*; ./a.out hoge ins ngram /repos/jawiki/00000/00000001.est
insert: hoge << /repos/jawiki/00000/00000001.est
$ ./a.out hoge sel 浜崎あゆみ
select: hoge << 浜崎あゆみ
        score: 2        /repos/jawiki/00000/00000001.est

疑問っぽいもの

  • KWIC APIの概念が分からない
    • sen_recordsについてKWICを取り出す訳では無くて、別系統の検索APIと考えれば良い？
    • その割にsen_snip_open()のmax_resultsに10より大きい数字を入れるとNULLが帰る

PFI新入社員

年末・新年にかけて、2人の方が入社されました(現在バイト含めて14人)。

主に営業力、製品品質・カスタマーエクスペリエンスの向上などが狙いです。

渡辺さんは初の非エンジニアの方の採用なので、どうなって行くのか楽しみです。

既に滅茶苦茶色々勉強させてもらってます。

本購入

Database Management Systems

Database Management Systems

Real World Haskell: Code You Can Believe In

Real World Haskell: Code You Can Believe In

  • プログラム変換したいものがあるので、Parsecつかいたい

Scalable Input/Output: Achieving System Balance (Scientific and Engineering Computation)

Scalable Input/Output: Achieving System Balance (Scientific and Engineering Computation)

  • 研究用

常駐型サーバーのデバッグ手法

2008/12/23発売のWEB+DB PRESS Vol.48に「常駐型サーバーのデバッグ手法」というタイトルで短い記事を書かせて頂きました。

WEB+DB PRESS Vol.48

WEB+DB PRESS Vol.48

常駐型サーバープログラムにおいて、問題が起こりやすい点をまとめた他、問題解析に役立つ各種ツール(valgrind, google-perftoolsなど)の使い方もまとめてあります。

本当はマルチスレッドプログラムのデバッグについても書きたかったんですが(DeadLockとか止まるだけましとか)、WEB+DB PRESSということで、WEBシステムを開発されている方にも比較的役立ちそうな内容に絞りました。

よろしければ一度目を通してみてください。

# てかakrさんとomoさんと並べられるとかもうね...

はてなブックマーク全文検索機能の裏側

そろそろ落ち着いて来たころ合いなので、はてなブックマーク全文検索機能の裏側について書いてみることにします。

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を使用して本文を保存する事にしました。

  • APIが簡単
  • 4G以上のデータも扱える
  • スレッドセーフ
  • mixiでの高負荷運用実績が有る

な辺りが決め手でした。これで劇的に速度が改善し、色々と作業が進め安くなりました。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)

あと、検索エンジン周りで困られている方がいらっしゃれば、ぜひ伺わせて下さい:-)

関連URL