Tokyo TyrantとテーブルDBでリアルタイム検索

ドラクエは卒業して、もっと英語漬けをやっているmikioです。さて今回は、データベースサーバTokyo Tyrantとテーブルデータベースを使ってリアルタイム検索システムを構築する方法について語ります。

テーブルDBを分散させたい

Tokyo TyrantでもテーブルDBがサポートされているわけですが、これはリアルタイム検索システムへの布石です。テーブルDBは任意のコラムにインデックスを張ることができ、時系列のコラムにインデックスを張ればその値によって古いコラムを効率的に消すことができます。チュートリアルの「Persistent but Expirable Cache」でもその方法を示しています。また、任意のコラムに分かち書きトークン方式もしくは文字N-gram方式で転置インデックスを張ることができます。これらを総合すると、最新のデータのみを保持してサイズと性能を一定に保ったインデックスを維持できることになります。

上記で最新のデータを検索できるわけですが、次にそれをスケールアウトできるようにしたくなります。「リアルタイム検索システム」として運用しようとするならば、更新の負荷をできるだけ小さくするために、インデックスを小さな規模で分割しておくことが望ましいでしょう。更新の負荷、とりわけ登録文書を削除する処理の負荷が重いのです。Posting Listから該当の文書IDの要素を消すために全体をスキャンしなきゃなりません。

ところで、TCやTDでの転置インデックスは必ずPosting Listを同一のページに入れる構造になっていて、でかいPosting Listを格納しようとした時に効率が悪いというご意見をいただくことがよくあります。たしかに、でかいPosting Listはチェーンでつないで別ページで管理する方が文書の登録は速くて済むでしょう。しかし、それだと検索や削除は必ずしも速くならないのです。私の見解としては、Posting Listが長くてやってられなくなった時点でインデックスの分割を上位レイヤで検討すべきということです。遥か昔にSnatcherという全文検索システムを作っていた時はチェーン方式を採用していたのですが、その時に懲りました。

並列メタ検索メソッド

分割されたデータベースへの文書の登録は、IDのハッシュ値でいわゆるアルゴリズム方式の水平分散で行えばよいでしょう。削除も同様です。問題は検索操作です。全てのデータベースに対して個別に検索を行って、その結果をマージする必要があります。ちと大げさですが、これを「メタ検索」と呼びます。ですが、メタ検索はソート条件などを維持する必要があって実装が面倒なので、アプリ側の工夫だけで頑張れというのは酷ですよね。なので、メタ検索用のユーティリティを用意しました。以下のシグネチャです。

/* Search records for multiple servers in parallel.
   `qrys' specifies an array of the query objects.
   `num' specifies the number of elements of the array.
   The return value is a list object of zero separated columns
   of the corresponding records. */

TCLIST *tcrdbparasearch(RDBQRY **qrys, int num);

それぞれ別のRDBオブジェクトから作ったクエリオブジェクトを格納した配列とその要素数を与えると、並列してクエリを投げて、その該当のレコードを取得して順序を整えてから、結果セットをリストとして返します。結果セットはキーだけでなくレコード本体も取得してきているので、1回のネットワーク通信で検索結果を提示できます。処理は内部でスレッドを立てて勝手に並列化してくれます。

利用例を以下に示します。この関数は、データベースオブジェクトの配列rdbsとその要素数divnumと検索式exprを渡すとメタ検索を行ってくれます。

static void searchprint(TCRDB **rdbs, int divnum, const char *expr){

  // クエリオブジェクトの準備
  RDBQRY *qrys[divnum];
  for(int i = 0; i < divnum; i++){
    qrys[i] = tcrdbqrynew(rdbs[i]);
    // textコラムの全文検索
    tcrdbqryaddcond(qrys[i], "text", RDBQCFTSEX, expr);
    // numコラムの降順に整列
    tcrdbqrysetorder(qrys[i], "num", RDBQONUMDESC);
  }

  // 一撃で並列検索
  TCLIST *res = tcrdbparasearch(qrys, divnum);
  int rnum = tclistnum(res);

  // 結果セットの個々の要素をループ
  for(int i = 0; i < rnum; i++){
    // コラムオブジェクトを結果セットから抜き出す
    TCMAP *cols = tcrdbqryrescols(res, i);
    // 各コラムを印字する
    tcmapiterinit(cols);
    const char *name, *value;
    while((name = tcmapiternext2(cols)) != NULL){
      value = tcmapget2(cols, name);
      printf(" [%s=%s]", name, value);
    }
    printf("\n");
    tcmapdel(cols);
  }

  // 片付け
  tclistdel(res);
  for(int i = 0; i < divnum; i++){
    tcrdbqrydel(qrys[i]);
  }
}

皮算用

最近のPCはコアが多いから、各マシンに4つくらいTTを立ててもいいでしょう。仮にそのマシンを4台セットで利用するなら、16個のTTサーバが動くことになります。1サーバに10万件のデータを入れるならば、総計160万件のデータを検索対象にすることができます。これはmixiの1日の日記を全部格納しても余裕の数です。耐障害性を考えて二重化しても8台で済みます。もちろん、実際のインデックス分割数とマシン台数は検索と更新の負荷に応じて決定すべきです。

1日分しか検索対象にできないなんて意味がないと言われるかもしれません。でも、リアルタイム検索はそれでいいのです。24時間も稼げれば、その間に別の大規模なインデックスを構築できます。古いインデックスとリアルタイムインデックスのメタ検索を行えば全コンテンツをリアルタイム検索していることになるというわけです。

まとめ

Tokyo Tyrant上でテーブルDBを動かせばリアルタイム検索ができます。そのためにはインデックスを小さく分割して分散させます。分散したサーバを対象とした検索操作はメタ検索メソッドを用いれば簡単です。リアルタイム検索は最新のものだけを扱い、全体のインデックスと相互補完する目的で用います。

このアーキテクチャでどこまでスケールするのか、あるいはどこまで性能が出るのかは、まだ実データで実験していないので確たることは言えません。いずれちゃんとした性能測定をしてまた報告したいと存じます。TT+テーブルDBを再利用するのではなくリアルタイム検索専用のインデックスを書き起こした方がもちろん高効率が実現できるのでしょうし、あるいはインデックスを作らないでオンメモリのキャッシュを逐次探索するモデルの方が適する場合もあるでしょう。とはいえ、テーブルDBを並べるだけという手軽さの点では今回の手法も利点があるかなと思っています。