ぱぱネット（仮）

_ [Linux][開発] TokyoCabinetの複合検索を高速化した

http://linux.papa.to/image/tokyocabinet-1.4.45.scost.patch.tar.gz がパッチとバッチ。 彗星の煌めきのごときmikio wareに、俺のゴミパッチを当てたら当然 クォリティは下がりますので、そこんとこよろしく。責任とれまへん。 ライセンスはオリジナル準拠です。

_ [Linux][開発] 内容説明

TokyoTyrantのサーバであるttserverを起動しておいて、

% sh server.sh [ENTER]

setindex.plを実行してインデックスを作成し、ins.plで100万レコードを 登録したデータベースに対して、search.plで複合検索を行う、という実験です。 パッチ自体はTokyoCabinetに対するものですが。

登録するデータは、ニコニコ動画のタグや掲示板の書き込みのようなものを思い浮かべてください。 投稿者(uname)と、投稿本文またはタグ(ptoken)と、投稿時刻(time)がある。 時刻はUNIX起源時間にすると見辛いので1〜100万までの整数にしてある。

search.plは、このTTに対して複合的な検索クエリーを発行する。例えば 「ある開始時刻〜終了時刻の、ユーザほげほげさんの投稿を、古い順に100件探す」みたいなかんじです。 ありがちな処理でしょ？

my $qry = TokyoTyrant::RDBQRY->new($db);
my $start = ($j * 12345) % 1000000;
my $end = $start + 3600;
my $user = $users[$j % 50];
print "TIMERANGE: $start - $end  USER $user\n";
$qry->addcond('uname', $qry->QCSTREQ, $user);
$qry->addcond('time', $qry->QCNUMGE, $start);
$qry->addcond('time', $qry->QCNUMLE, $end);
$qry->setorder('time', $qry->QONUMASC);
$qry->setlimit(100);
my $rv = $qry->search();

完全乱数だと実行結果の比較がしにくいので、検索時刻範囲やユーザ名は、 剰余によって、同じものが決まった順番で繰り返し出るように細工してあります。

_ [Linux][開発] ベンチマーク

search.plの100クエリーの総実行時間(秒)

各クエリーのラウンドトリップタイムの分布(X軸: 試行回数, Y軸：秒)。

条件によってはオリジナルの方が速いこともありますが、 概ね安定していることがこのパッチのメリットであります。

当たり前ですが

検索結果自体はパッチ前と後で同じです(grep KEY:したテキストを比較して確認)。 ただし、このパッチでは20秒以上かかる検索は問答無用で打ち切りますので、 検索結果が異なることはあります。

_ [Linux][開発] なぜ速くなるのか？

検索条件に対して 投機的コスト算定とソーティング を行っているためです。 但し、まともな算術アルゴリズムではなく、tctdbqryidxfetch()にタイムアウトを付加した アドホックなものです。Athlon64/2.4GHzより速かったり遅かったりするマシンでは 動かないかもしれません。