どうぶつの森にハマって、たぬきち商店が早終いする関係で退勤時間もめっさ早くなったmikioです。今回は、Tokyo TyrantのキャッシュとLua拡張を使って超お手軽にリアルタイム検索システムを作る方法について述べます。
ユースケース
高い頻度で更新されるWeb上のテキストをリアルタイムに検索したいと思ったことはありませんか？ mixi日記や各種のブログサービスやRSSリーダなどで扱う大量のコンテンツを安価かつ簡単に検索したいと思ったことはありませんか？ 私は結構あります。要件を箇条書きすると以下のような感じでしょうか。
- 最新データの合計100万件くらいを検索できればよく、古いデータは自動的に消えてほしい。
- ただし、更新はリアルタイムにして、書いた瞬間に検索結果に反映されてほしい。
- サーバ1台で更新1000qpsおよび検索100qpsは処理したい。
- 再現率よりも精度とリアルタイム性を重視したい。
例として「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を最適化する操作を実行して乗りきることにします。
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コミュニティにてお寄せいただけると幸いです。
