読者です 読者をやめる 読者になる 読者になる

mixi engineer blog

ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

Tokyo Tyrantによるリアルタイム検索

mixi

どうぶつの森にハマって、たぬきち商店が早終いする関係で退勤時間もめっさ早くなったmikioです。今回は、Tokyo TyrantのキャッシュとLua拡張を使って超お手軽にリアルタイム検索システムを作る方法について述べます。

ユースケース

高い頻度で更新されるWeb上のテキストをリアルタイムに検索したいと思ったことはありませんか? mixi日記や各種のブログサービスやRSSリーダなどで扱う大量のコンテンツを安価かつ簡単に検索したいと思ったことはありませんか? 私は結構あります。要件を箇条書きすると以下のような感じでしょうか。

  1. 最新データの合計100万件くらいを検索できればよく、古いデータは自動的に消えてほしい。
  2. ただし、更新はリアルタイムにして、書いた瞬間に検索結果に反映されてほしい。
  3. サーバ1台で更新1000qpsおよび検索100qpsは処理したい。
  4. 再現率よりも精度とリアルタイム性を重視したい。

例として「mixiエコー」を考えてみます(あるいはWassr/Twitter/はてなブックマークなどでも同様です)。100文字以下くらいの短いテキストが高い頻度で更新され、主に最新のデータに注目が集まるコンテンツです。これをリアルタイムに検索可能にしたいのです。

こうした要求は、キャッシュ風に振る舞う転置インデックスを用いることで実現することができます。ということで、Tokyo Tyrant(TT)のキャッシュとLua拡張機能を用いた転置インデックスを実装してみました。キャッシュはTokyo Cabinet(TC)のオンメモリハッシュデータベースとして表現します。

転置インデックスを表現するキャッシュ

転置インデックスとは、レコードのテキスト内のトークンをキーとして、その出現位置情報のリスト(posting list)を関連づけるkey/valueデータベースです。これを作るには、レコードのテキストをトークンに分割するとともに、各トークンに対してレコードIDをposting listの末尾に連結していくという操作を繰り返します。擬似コードで書くと以下のようになります。

FOR_EACH record (all_records){
  all_tokens = tokenize(record.text)
  FOR_EACH token (all_tokens){
    concatenate_to_posting_list(index, token, record.id)
  }
}

今回は、上記のindexとしてTCのオンメモリハッシュデータベースを用います。concatenate_to_posting_list操作はLua拡張の組み込み関数_putcatを使うだけでOKです。TTでオンメモリハッシュデータベースを用いる場合、キャッシュの最大サイズを指定すると、それに溢れた場合はLRU(least recent used)のレコードから削除してメモリ使用量を一定に保つことができます。そうすると「古いデータは自動的に消えてほしい」が一部達成できるわけですが、それだけでは充分ではありません。頻出するトークンのposting listは連結を続けると肥大化していくので、ある一定の長さで前の方を切ってあげないといけません。そのため、一定の頻度でposting listを最適化する操作を実行して乗りきることにします。

lru_rotate.png

Lua拡張での実装

Luaの関数として、以下の操作を実装します。トークンの分割はクライアント側で行い、空白区切りのリストとして渡すものとします。日本語のテキストを扱う場合はmecabやchasenなどの形態素解析器を使ってトークンを切り出すことになるでしょう。

  • put : レコードIDとトークンのリストを受け取り、各トークンのデータをposting listに連結する。
  • search : トークンのリストを受け取り、その全てを含むレコードのIDのリストを返す。

putを最も単純化すると、以下のような実装になります。たったこれだけで最低限の転置インデックスって作れちゃうものなんです。posting listはレコードIDをBERエンコードしたデータを連結して表現しています。

DELIMS = " \\t\\r\\n"   -- delimiters of tokenizing

function put(id, text)
   local tokens = _tokenize(text, DELIMS)
   local idsel = _pack("w", id)
   for i = 1, #tokens do
      _putcat(tokens[i], idsel)
   end
   return "ok"
end

function _tokenize(text, delims)
   local tokens = {}
   for token in string.gmatch(text, "[^" .. delims .. "]+") do
      if #token > 0 then
         table.insert(tokens, token)
      end
   end
   return tokens
end

とはいえ、今回は定期的にposting listを最適化するという操作が必要なので、実際にはもうちょっと複雑になります。また、最低限のエラーチェックも入れるようにします。以下では、10回に1回の確率でoptが真になり、その場合はposting listの後方500個を残して前方を捨てる処理を行います。それらの処理をアトミックに行うため、トークンをロック/アンロックする処理を前後に入れています。

DELIMS = " \\t\\r\\n"   -- delimiters of tokenizing
OPTFREQ = 0.1        -- frequency of optimization
LIMNUM = 500         -- limit number of kept occurrence

function put(id, text)
   id = tonumber(id)
   if not id or id < 1 then
      return nil
   end
   if not text then
      return nil
   end
   local opt = math.random() < OPTFREQ
   local tokens = _tokenize(text, DELIMS)
   local idsel = _pack("w", id)
   for i = 1, #tokens do
      token = tokens[i]
      if not _lock(token) then
         break
      end
      if opt then
         local ids = {}
         local idsel = _get(token)
         if idsel then
            ids = _unpack("w*", idsel)
         end
         local nids = {}
         local top = #ids - LIMNUM + 2
         if top < 1 then
            top = 1
         end
         for j = top, #ids do
            table.insert(nids, ids[j])
         end
         table.insert(nids, id)
         idsel = _pack("w*", nids)
         _put(token, idsel)
      else
         _putcat(token, idsel)
      end
      _unlock(token)
   end
   return "ok"
end

searchは以下のような実装になります。トークンが複数指定された場合はそれらのAND検索を行うことになるのですが、Luaのテーブルを使ってハッシュジョインすることで論理積を実装しています。なお、第2引数に戻り値の最大件数を指定するとともに、戻り値の第1行目には全体のヒット数を返すようにしています。

DELIMS = " \\t\\r\\n"   -- delimiters of tokenizing
DEFMAX = 10          -- default maximum number of search

function search(phrase, max)
   if not phrase then
      return nil
   end
   max = tonumber(max)
   if not max or max < 0 then
      max = DEFMAX
   end
   local tokens = _tokenize(phrase, DELIMS)
   local hits = {}
   local tnum = #tokens
   for i = 1, tnum do
      local idsel = _get(tokens[i])
      if idsel then
         local ids = _unpack("w*", idsel)
         local uniq = {}
         for j = 1, #ids do
            local id = ids[j]
            if not uniq[id] then
               local old = hits[id]
               if old then
                  hits[id] = old + 1
               else
                  hits[id] = 1
               end
               uniq[id] = true
            end
         end
      end
   end
   local result = {}
   for id, num in pairs(hits) do
      if num == tnum then
         table.insert(result, id)
      end
   end
   table.sort(result)
   local rtxt = #result .. "\\n"
   local bot = #result - max
   if bot < 1 then
      bot = 1
   end
   for i = #result, bot, -1 do
      if max < 1 then
         break
      end
      rtxt = rtxt .. result[i] .. "\\n"
      max = max - 1
   end
   return rtxt
end

上記のソースコード全体をTTの最新版(1.1.8)にusherette.luaというファイルとして同梱しておきましたので、いろいろ改造してみて遊んでみてください。

実際のサービスでは必ずしも各エントリに単純な数値のプライマリIDが与えられているわけではないので、そういった場合はインデックス用の内部IDを振り直した上で、内部IDと外部IDの関連づけもデータベースに入れて管理することになるでしょう。

実際に動かしてみる

で、オンメモリだとどんだけ早いのかというのが問題なわけです。TTのPerlクライアントライブラリを使ってテストしてみましょう。まずは、以下のようなクライアントを書きます。平均20トークンのレコード20万件を登録するスクリプトです。register.plなどとして保存してください。

use TokyoTyrant;

my $rdb = TokyoTyrant::RDB->new();
$rdb->open("localhost", 1978);

for(my $i = 1; $i <= 200000; $i++){
    my $text = "";
    my $wnum = int(rand(19)+1);
    for(my $j = 0; $j < $wnum; $j++){
        $text .= sprintf("\\t%d", int(rand($i/10)));
    }
    $rdb->ext("put", $i, $text);
}

$rdb->close();

次に、サーバを起動します(TTは--enable-luaをつけてビルドしておいてください)。データベースの設定は、オンメモリデータベースを、最大サイズ100MB、バケット数10万にします。これは、メモリ使用量200MBくらい、異なり語数10万語くらいを想定した設定です。

$ ttserver -ext usherette.lua '*#capsiz=100m#bnum=100000'

でもって、別端末でクライアントを動かしましょう。5個のクライアントを同時に動かして、合計100万レコードを登録します。

$ perl register.pl &
perl register.pl &
perl register.pl &
perl register.pl &
time perl register.pl

私の環境では100秒かかりました。ということはだいたい10000qps程度の登録性能が出るようです。これならどんなに大繁盛しているサイトで使ってもボトルネックにはならないでしょう。ちなみに検索は以下のようなスクリプトでテストできます。

use TokyoTyrant;

my $rdb = TokyoTyrant::RDB->new();
$rdb->open("localhost", 1978);

for(my $i = 1; $i <= 200000; $i++){
    my $text = "";
    my $wnum = int(rand(2)+1);
    for(my $j = 0; $j < $wnum; $j++){
        $text .= sprintf("\\t%d", int(rand($i/10)));
    }
    $rdb->ext("search", $text);
}

$rdb->close();

5クライアント同時実行で269秒かかりましたので、3700qps程度の検索性能が出るようです。Luaのテーブルのオーバーヘッドが思ったより大きいみたいでちょっとがっかりですが、まあ検索クエリが3700qpsを越えるサイトなんて知らないので問題ないでしょう。

まとめ

Tokyo Tyrantのサーバ1台を用意するだけで、任意のタグ方式(もしくは分かち書き方式)のリアルタイムな検索システムを、mixiのような大規模なサイトのQPSにも耐えるように稼働させることができます。あるいは、あるエントリが書かれた瞬間に、同じ語彙を含むエントリを提示する、はてなのおとなり日記みたいな機能をリアルタイムに実現することができます。

オンメモリだとサーバが落ちたらインデックスが消えてしまうわけですが、それに関してはレプリケーション機能で冗長性を確保することで対処できるでしょう。巨大なインデックスを更新するのにはある程度時間がかかりますが、その更新間の遅延を埋め合わせるためにオンメモリの簡易検索システムを併用するというのもよいアイデアだと思います。再現率ではタグ方式の転置インデックスに優るN-gram方式の転置インデックスやsuffix arrayを使っても更新遅延が大きくなりがちなので、それらと組み合わせるのも妙案かもしれません。

リアルタイム検索の手法は今後も模索していく所存ですので、質問や要望などあれば、Tokyo Cabinetコミュニティにてお寄せいただけると幸いです。