こんにちは、求人情報サイト Find Job !の開発を担当しているmasutaroです。

今日は、前回のエントリ「IRCのボットで職場(Find Job !事業部)を楽しく便利に！」でお話していたとおり、Robotaro_DXのソースを晒したいと思います。公開が遅くなった理由は、僕が無精者だからではなく、ソースをさらすのが怖かったからでもありません。みなさんをじらすためです（汗）（汗）（汗） ；-）

それでは早速ですが、使い方の説明をしたいと思います。こちらからソースコードをダウンロードしてください。

ファイル構成

ダウンロードしたファイルを解凍すると、以下のようなファイル構成になっていると思います。

解凍したディレクトリ
│
├─ robotaro_irc.pl
│
├─ config.yml
│
└─ lib ─ Robotaro ┬─ Hotpepeer.pm
                     │
                     └─ Wheather.pm

・robotaro_irc.pl
メインの処理を記述したファイルです。

・config.yml
ボットの接続情報やつぶやく時間、言葉を定義するファイルです。YAMLで書いてあります。

・lib下のモジュールファイル
外部APIを使ってつぶやく処理は一部モジュールに分けて書いています。

実行の準備作業

さて、さっそく実行！といきたいところなのですが、皆さんの環境に合わせて設定ファイルを少し書き換えていただかなくてはなりません。下記の説明のとおりconfig.ymlを書き換えてください。

config.yml の書き換え作業
ボットに関する設定は、以下のような書き方でconfig.ymlに定義されています。

nickname: Robotaro_DX
server: ****
password: ****
port: 6667
master: ****
join_channel: #channel1,#channel2,#****,#****
task:
    schedule1:
        channel: #channel1,#channel2
        type: string
        when:
            hour: 10
            min: 0
            sec: 0
        action: Robotaro_DX起動...
・
・
・
(以下、scheduleNの設定が続く)

YAMLの設定の意味は以下のとおりです。参考にしながら、各項目を設定していってください。まずは、青字の項目だけ設定すればOKです。

■ 基本設定部(1 ～ 6行目まで)

・server：ご利用のIRCサーバ名
・password：パスワード
・port：ポート番号。通常はデフォルトの6667のままでOK
・master：管理者のnickname。
・join_channel：ボットが接続するチャンネル。コンマ区切りで複数指定が可能です。

■ タスク設定部(7行目以降)
・scheduleN：scheduleN (Nは任意の一意の番号）という名前で、スケジュールを設定していきます。
・channel：つぶやくチャンネルを指定。コンマ区切りで複数指定が可能です。
・type：”string” か “function” を指定。
・hour：時間(0-23で指定)
・min：分(0-59で指定)
・sec：秒(0-59で指定)
・wday：曜日(0-6で指定。0が日曜日。省略可能で、省略した場合は毎日実行)
・action：typeで指定したのがstringなら値を文字列としてつぶやきます。functionだったら、値で指定した名前の関数を呼び出します。デフォルトではuranaiとforecastが指定可能です。

Robotaro_DX起動…！！

さて、これでボットを起動するための準備が整いました。robotaro_irc.plを実行してみてください。問題なく起動できるでしょうか？

デフォルトの設定ですと、

・毎日10:00に、#channel1 と #channel2 に「Robotaro_DX起動…」とつぶやく。
・毎日10:05に、#channel1 で占いカウントダウンをする。
・毎日13:00に、#channel1 に「そろそろお昼にしませんか？」とつぶやく。
・毎日18:00に、#channel1 に翌日の天気予報をつぶやく。
・毎日18:15に、#channel1 に「そろそろブラインドを閉めてもらっていいですか？」とつぶやく。
・水曜日の18:30に、#channel1 に「今日はノー残業デーやで。日報書いてや。」とつぶやく。

をするようになっています。上述の設定ファイルの仕様に従って、時間などの指定をいじって遊んでみてください。

つぶやく以外の機能

ボットの起動ができるようになったところで、実はまだ紹介する機能があります。グルメ検索と腹話術の機能です。

グルメ検索
ボットが常駐しているチャンネルにおいて、”@robotaro キーワード(キーワードは半角スペース区切りで複数指定可能)”で発言すると、ボットがHotpepper検索をして渋谷界隈の飲食店を1件ランダム抽出して返してくれます。ランチに行く前などにお使いください。お昼に行くにはちょっと微妙な店がヒットしたりしますが、ノリと勢いで行ってみるのもいいかもしれません。

腹話術（裏技）
緊急(?)の際に、ボットにプライベートで”チャンネル名:しゃべらせたい内容”で話しかけると、指定したチャンネルに対して、指定した文言でボットが発言します。無機質に発言を繰り返すボットに突然人間らしいことをしゃべらせて、周りをあっと言わせてやりましょう。

※ちなみにこの腹話術機能は、設定ファイル(config.yml)のmasterで設定されたnicknameの人にしか反応しないようになっています。ご注意ください。

おわりに

これでボットの使い方の説明は終わりです。次にソースコードの解説にうつり・・と行きたいところですが、ボットの仕組みはダウンロードしたファイルから直接ご覧ください。皆さんに読んでいただきやすいように、コメントを入れつつできるだけ丁寧に書いたつもりです。

ボットを高機能化させたり、他のAPIを使って拡張したりして、ぜひ遊んでみてください：-)
ライセンスはGNU Lesser General Public Licenseに基づきます。

利用API 一覧

ボットの機能を開発するにあたって、利用したAPIの一覧です。

・占い：Web ad Fortune　(paperboy&co.様 ご提供)
・グルメ検索：ホットペッパー (リクルートWEBサービス様 ご提供)
・天気予報：お天気Webサービス (ライブドア様 ご提供)

チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。

圧縮B+木

B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基づいてレコードを走査したりできる利点もあります。TCでもB+木をサポートしていて、データマイニングや全文検索のインデックスなどの用途で私もよく利用しています。

B+木は空間効率においても優れています。ページ単位で記憶領域を管理するので、レコード毎のオーバーヘッドが小さく、記憶領域のフラグメンテーションも起きにくいからです。その上、B+木の各ページを圧縮すると、データベースとしての検索や更新などの機能を保ったままで、空間効率をさらに向上させることができます。この手法を圧縮B+木と呼ぶことにします。

ZLIBとBZIP2

TCは以前からZLIBによる圧縮B+木をサポートしていました。チューニングのオプションとしてBDBTDEFLATEフラグを指定するとB+木がZLIB（Deflate）圧縮B+木として作成されます。ZLIBはgzipコマンドやPNGなどでも使われている、圧縮も伸長もそこそこ高速で、圧縮率もそこそこ良い、いわばバランスのとれた圧縮手法です。内部的にはLZ77というスライド窓を使った符号化とハフマン符号化を用いているそうです。

最新バージョンのTCでは、BZIP2もサポートするようになりました（そのおかげで、ビルドする際にbzlib.hが必要になりましたが）。チューニングのオプションとしてBDBTBZIPフラグを指定するとB+木がBZIP2圧縮B+木として作成されます。BIP2はbzip2コマンドで使われている、圧縮も伸長もあんまり高速ではないが、圧縮率はZLIBを上回る、いわばアーカイブ用の圧縮手法です。内部的にはBWTという並び替え処理とMTFという置換処理をした上でハフマン符号化を用いているそうです。

正直なところ、TCで利用する分にはZLIBで十分だと思っており、BZIP2を使う必要性は個人的にはまったく感じていません。とはいえ人によっては過去ログの保存などで少しでもデータベースを小さくしたいこともあるでしょうから、ZLIBと並んでポピュラーになってきたBZIP2をつけておくのは別に悪いことでもないかなと。

LZMA

アーカイブ的なユースケース（更新はあんまりしないが検索はたまにする）を考えるならば、極右的なLZMA（Lempel-Ziv-Markov chain-Algorithm）というアルゴリズムがあります。圧縮にものすごい時間がかかるが、圧縮率はBZIP2をさらに上回り、伸長はBZIP2よりも高速だという特徴があります。LZMAは7zipというアーカイバに組み込まれていて、SDKも公開されています。

しかし、このSDKがびっくりするほど使いづらいです。圧縮処理はC++で実装していながら伸長処理はCで実装していたり、C用のライブラリでは伸長処理しかできなかったり、APIの使い方がドキュメントを読んでもよくわからなかったりします。ということで、あんまり細かいことを考えずにメモリ上でLZMA圧縮およびその伸長を行うためのラッパーライブラリを作りました。zlibに倣って、lzmalibと名づけて公開いたします。こんな風に使います（ビルド時のリンカオプションには-llzmaをつけてください）。

#include <lzmalib.h>
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv){
  char *orig_buf, *comp_buf, *decomp_buf;
  int orig_size, comp_size, decomp_size;

  orig_buf = "A thin wrapper library of LZMA";
  orig_size = strlen(orig_buf);

  comp_buf = lzma_compress(orig_buf, orig_size, &comp_size);
  printf("compressoin: from %d to %d\n", orig_size, comp_size);

  decomp_buf = lzma_decompress(comp_buf, comp_size, &decomp_size);
  printf("decompression: from %d to %d\n", comp_size, decomp_size);

  free(decomp_buf);
  free(comp_buf);

  return 0;
}

ついでに、LZMAのPerlモジュールが外部コマンド呼び出しのものしかCPANになかったので、上述のlzmalibを使ったPerlモジュールも作りました。Compress-LZMA-Simpleとして公開しておきます。

LZO

リアルタイム的なユースケース（更新も検索もヘヴィにする）を考えるならば、極左的なLZO（Lempel-Ziv-Oberhumer）というアルゴリズムがあります。これは圧縮率は他の方式に負けますが、圧縮速度も伸長速度も爆速で、なんとmemcpyの2倍程度の時間で圧縮ができてしまうのです。これはすごいことで、readやwriteに伴うバッファ間のデータコピーを節約できる時点で、空間効率だけでなく時間効率をも向上させられる可能性を示しています。ディスクI/Oを伴う規模の探索や更新ではなおさらです。

LZOのAPIは大変使いやすく、Cはもちろん、Perlなどのスクリプト言語からも簡単に使うことができます。あんまり有名じゃないみたいですけど（私も圧縮に詳しい人に教えてもらえるまで聞いたこともなかった）、もっと流行してくれればなと思います。

TCへの組み込み方法

さて、LZMAやLZOもTCに組み込もうかと思ったのですが、この調子で各種の圧縮アルゴリズムをサポートしていくと私の首が回らなくなるのは明らかです。そこで、デフォルトでサポートするのはZLIBとBZIP2までにして、あとは外部モジュールとして組み込んでもらうようにしました。圧縮用の関数と伸長用の関数のポインタをTCのパラメータとして実行時に渡す方式です。例えばこんな感じで使います。

void *my_compress(const void *ptr, int size, int *sp, void *op){
  return lzma_compress(ptr, size, sp);
}

void *my_decompress(const void *ptr, int size, int *sp, void *op){
  return lzma_decompress(ptr, size, sp);
}

int main(int argc, char **argv){
  TCBDB *bdb;
  bdb = tcbdbnew();
  tcbdbsetcodecfunc(bdb, my_compress, NULL, my_decompress, NULL);
  tcbdbopen(bdb, "casket", BDBOWRITER | BDBOCREAT);
  ...
  tcbdbclose(bdb);
  tcbdbdel(bdb);
}

my_compressとmy_decompressはmallocされた領域を返すものとし、その領域はTC内部で自動的にfreeされます。なお、この機構（tcbdbsetcodecfunc）はあまりにマニアックすぎるので、HTMLのドキュメントには乗せない「隠しAPI」にしています。詳細に関してはtcbdb.hなどのヘッダファイルをご覧ください。

性能比較

B+木の更新と探索に関する空間効率と時間効率を測定してみました。/usr/share/dict/wordsにある英単語98569語の各々をキーとして、各キーに0〜9999のランダムな値を割り当てたレコードを格納したB+木データベースを作り、その全件を探索するテストを行ったところ、結果は以下のようになりました。

圧縮をするとしないとではデータベースのサイズが全然違うということはおわかりいただけると思います。ZLIBだと43.7%、BZIP2だと39.1%、LZMAだと37.5%に圧縮できているわけです。Deflateだと更新処理は195%の時間がかかりますが、検索処理は138%で済んでいます。BZIPやLZMAはそれよりも空間効率重視だということがわかります。LZMAはBZIP2より圧縮率が高く、探索もBZIP2よりも高速であることが確かめられました。逆にLZOは空間効率はそれほど向上しませんが、更新処理は121%、検索処理は114%の時間で済むことが確かめられました。

LZMAは圧縮処理が遅すぎるので利用できるユースケースは限られると思いますが、キーワード検索やIMEの辞書などのデータベースを圧縮する用途ではLZMAはかなり有望だと思います。LZOは処理速度がほとんど劣化しないので、非圧縮にするくらいならいつもLZOを適用したいくらい活躍するかもしれません。

まとめ

B+木を圧縮して利用する、TCの圧縮B+木の使い方と性能について説明しました。要求される処理速度がそれほどタイトでない場合、圧縮B+木の使用を検討してみてください。更新が頻繁ならLZO、更新をほとんどしないならLZMA、その中間ならZLIBやBZIP2がおすすめです。

実はこのネタはQDBMの時代にもさんざんやっているのですが、やはり圧縮アルゴリズムをコールバック関数呼び出しにして外部化したところがTCのポイントかなと。外部化と言えば、B+木のストレージ層（現状ではハッシュDB）を外部化してTTなどに置き換えると分散B+木になるなんて話も考えていたりしますが、実用になるかどうかは謎です。

最後に蛇足ですが、ZLIBのパッケージをtar.gzで配布するのってちょっと意地悪ですよね。

ここしばらく、水面下でBrian Akerを代表とするMySQL/SUNのエンジニアたちや、業界のオープンソースハッカーたちとMySQLをスリムダウンさせたマイクロカーネルRDBMSを開発していたのですが、本日アナウンスされたので、日本語でご紹介させていただきたいと思います。

Drizzleとは？

Drizzleとは必要のないものは一切存在しない、最低限でパフォーマンス重視な「MySQLよりシンプルで、軽く、安定して、高速な」 MySQLのforkです。マイクロカーネルアーキテクチャを採用したので、必要のないものは後付けできる構成です。こういった目標もあり、現在、Drizzleの開発チームはMySQLをドラスティックにリファクタリングしています。

コミュニティベースのプロジェクト

Drizzleで大事な事は、Drizzleはコミュニティベースのプロジェクトであるという事です。Montyのブログエントリーでも語られていますが、Drizzleでは、MySQLに長年存在していた致命的なバグが迅速に直されたり、プロダクトの進化を待たずとも、パッチやアイデアを誰でも貢献できます。したがって、Drizzleの開発はBazaarなどのオープンソースソフトウェアを使って行われており、LaunchpadやFreenodeなどの公開されている場所で行われています。

MySQLの替わりではない

一つ明確にしておかなければならないポイントは、DrizzleはMySQLの替わりになるプロダクトではありません。Drizzleのターゲットはとても限られた、RDBMSのカスタマイズを必要とする中～大規模なウェブアプリケーションです。

例えば、中～大規模で使われるMySQLは、memcachedと同様、セキュアな環境で運用されると仮定されます。したがって、安全であるという割り切りで、ユーザ名とパスワードをシンプルに, “hoge”と”hoge”に設定したとします。この場合、運用者としてはユーザ名とパスワードに意味はありませんが、MySQLの内部では、適当なクレデンシャルでも、ACL関連のロックが適用され、パフォーマンスを影響する要素となります。また、Query Cacheに関しても、個人レベルのデータベースでは効果的ですが、アプリケーションの規模が少し大きくなると意味を成さないコンポーネントとなります。

中～大規模なアプリケーションの開発者たちは、これらの機能をカスタマイズしたいと思ったり、実際に自社用にカスタマイズしています。こういうった人たちの仕事を楽にするためにDrizzleがあるのであって、一般的な場面で使うRDBMSとしては、MySQLが正しい選択だと思います。

マイクロカーネル アーキテクチャ

ウェブ業界で働く方で、最近のMySQLには使うことのない機能が多々あると感じる方は少なくないと思われます。Drizzleでは取り急ぎ、Stored Procedures, Triggers, Prepared Statements, Views, Query Cache, Event Scheduler, ACL, UNIX Socketをサーバから取り外しました。替わりに、私達はこれらのコンポーネントをプラガブルにするマイクロカーネルなアーキテクチャを目指します。

マイクロカーネルなら、Query Cacheをmemcachedのプールで代用してデータベースサーバたちに共通のキャッシュを共有させる事も可能になります。

オープンソースのライブラリを積極的に使う

MySQLは現状、歴史的経緯によって自社製のライブラリを使って実装されています（my_*系)。ですが、自分たちだけで開発するよりは、これらのライブラリをglib、libxml2、libpcreなどのオープンソースコミュニティによって開発・メンテナンスされているものに置き換える事によって、不都合やパフォーマンス改善を迅速、かつ高いクオリティを維持する事が可能です。したがって、私たちは実績のあるオープンソースのライブラリを積極的に使おうという結論に至りました。

ダウンロードしたい！

Drizzleは絶賛開発中で、リリースの日程も未定ですので、リンク経由でダウンロードできるパッケージはありません。ですが、先ほど説明したようにDrizzleは公開されたリポジトリを使って開発しているので、bzrの使い方を少し覚えたらソースを入手できます。以下がLaunchpadのプロジェクトページへのリンクです：

• https://launchpad.net/drizzle

ちなみにbzrでは、trunkからbranchを切るのは、”bzr branch 親” だけで出来ます。

まとめ

今回はMySQLの中の人たちや、ウェブ業界のエンジニアたちが望む、ウェブに優れたRDBMの開発プロジェクトをご紹介させて頂きました。Drizzleが完成すると、デベロッパーはApacheの様に様々なプラグインを書いて、ある程度、「自分仕様」なRDBMSを構築することが可能になります。

後はDrizzleのＦＡＱを読んで頂けたらな、と思います。

アロハシャツとショートパンツとビーサンで出勤してスネ毛が美しくないと評判のmikioです。さて今回は、Tokyo Cabinet（TC）とTokyo Tyrant（TT）のそれぞれ最新版でサポートされた新機能についてご紹介します。

固定長データベース

最終ログイン時刻データベースをTTで管理する仕組みについての記事を以前書きましたが、それに対して「各レコードを固定長にすればlseek一発で参照できるよ」という趣旨のご指摘をいただきました。全くその通りで、最終ログイン時刻の値に必要な領域は各ユーザ毎に10バイトもあれば十分ですし、検索キーはユーザID（mixiにおいては1からの連番）なので、それを添字に使えば二次元配列としてデータベースを表現することができます。

ただし、yamazさんも指摘しているように、ログイン時刻データベースのスループット限界はwriteがブロックすることにより訪れるので、データ構造がハッシュ表でも二次元配列でもwriteの回数はほぼ同じことから、性能はそんなに変わらないとも考えられます。むしろ実運用上で問題になったのは、更新ログの記録のためのwriteが重いのと、cron駆動の別プロセスで更新ログを削除した際にファイルシステムが重くなってTTも重くなることでした（いろいろ試したところ、更新ログを小さい単位にしてコマメに消すのがコツらしいです）。したがって、現状では二次元配列にする必要はないのですが、まあ今後もユーザが増えて負荷が増大していくことを考えると、より効率が良い実装を準備しておくのが大人のマナーでしょう。

ということで「固定長データベースAPI」なるAPIをTCに追加しました。ハッシュデータベースとほぼ同じインターフェイスだけれども、中身は固定幅の多次元配列をmmapしたものです。実装はものすごく簡単です。キーをstrtollにかけて自然数を取り出して（0以下はエラーにする）、データベース作成時に指定してある各レコードの幅（最大長）にキーのIDを掛けたオフセットを算出し、そこに値を書き込むのです。実際には値の長さのための領域（255バイト以下なら1バイト、65535バイト以下なら2バイト、それ以上なら4バイト）がレコードの幅に足されることになります。

固定長データベースは「キーが連番に近い自然数で値が固定長以下である」という制約がありますが、それに該当するユースケースでは比類ない性能を発揮します。100万件の読み書きを行った以下のベンチマーク結果を見るとその爆速っぷりがおわかりいただけると思います。固定長データベースの読み込みは実に2738万QPSの性能なのです（単なる配列操作なんだから早いのも当たり前ですが）。

固定長データベースは並列処理性能も最強です。固定長データベースではレコードの位置を特定する計算において別のレコードの状態を勘案する必要がないので、ロックの粒度を完全にレコード単位にすることができるからです。ただし実装上は、レコードの数だけのmutexを準備するとメモリの無駄なので、ハッシュロックと呼んでいる手法を用います。例えば127個のmutexの配列を作っておいて、キーのハッシュ値に対応する要素をロックするというものです。127個もあれば衝突する可能性は十分低いですし、たとえ衝突したとしてもそのスレッドが一瞬ブロックするだけでスループットの大勢には影響がありません。

なお、TCの抽象データベースAPIにも固定長データベースAPIのラップ機能を持たせたので、自動的にTTからも固定長データベースを使えることになっています。もちろんmemcachedプロトコルでも利用できます。TCのPerl/Ruby/Javaバインディングからも利用できます。

さらに余談ですが、ハッシュやB+木には前方一致するキーの取得を行うfwmkeyという関数がありますが、その使い方が固定長データベースだとちょっと異なります。数には前方一致という概念がないので、前方一致パターンの代わりに区間記法を用います。例えば、10以上20以下は “[10,20]“、10以上20未満は “[10,20)"、10超20未満は "(10,20)"、10超20以下は "(10,20]” と指定します。

値の回転

TTの独自プロトコルにおいて、tcrdbputrttというメソッドが加わりました。これは、既存のレコードの値の後ろにデータを連結するtcrdbputcatメソッドの発展で、連結した結果として値の長さが一定を越えた場合には、前からそれを切り捨てるというものです。例えば、「ABCDEFGH」に「IJK」を連結して制限長8で回転させた場合、「DEFGHIJK」が新しい値になります。

値の回転は基本的には履歴の管理のような用途のためにあります。典型的なのはmixiの足あとデータベースです。各ユーザのIDをキーにして、そのユーザのページを訪れたユーザのIDを最大60個まで保存するというのが現状の仕様ですが、これはTTで管理することができます。新たにユーザが足あとをつける場合、そのユーザのIDと時刻それぞれ4バイトの整数としてpackした値を、8バイト*60個=480バイトの制限長で回転させればよいのです。制限長があるということは値は固定幅になるので、上述の固定長データベースと組み合わせればかなり効率的に処理が行えると考えられます。実際のところ、MySQLで問題なく管理できている現状の足あとデータベースをわざわざ置き換えるようなことはしないのですが、データマイニングの用途では回転は重宝することと思います。

no replyモード

memcached-1.2.5とCache::Memcached::Fast-0.10で追加されたno replyモードをTTでも実装しました。これは、setやdeleteなどの更新操作の際に、クライアント側にその成否を送信しないようにするものです。大量の更新を行う際にはno replyモードを利用するとパフォーマンスが非常によくなります。クライアントは一切recvすることなしにsendを繰り返すので、MTUが許す限りのリクエストを単一のパケットに詰め込んで送ることができるからです。実際にハッシュデータベースへのsetを100万回繰り返すベンチマークテストをしたところ、約25倍のスループットが出ることがわかりました。TTの独自プロトコルでもtcrdbputnrメソッドを呼ぶことでno replyモードを利用することができます。性能特性もmemcachedプロトコルとほぼ同じです。

　　　　　　time　　　QPS
default　35.936s　　 27827
noreply　 1.366s　　732064

なお、Cache::Memcached::Fastでは、newメソッドの引数で { servers => [{ address => "localhost:1978", noreply => 1 }] } などとすることでnoreplyモードを指定できますが、その上でさらにsetメソッドをvoidコンテキストで評価しないとno replyモードにならないことに注意してください。つまり、setメソッドの戻り値を評価しようとするとno replyモードでなく通常モードになってしまいます。これに関して個人的な見解を言わせてもらえば、sendのエラーはno replyモードであっても検出すべきなので、コンテキストでモードを切り替えるのはあまり良い設計ではないと思います。

非同期ロギング

最終ログイン時刻データベースのボトルネックに更新ログが関わっていることは既に述べましたが、TTでAIO（Asynchronous I/O）を利用することによってそれを軽減することができます。ttserverを実行する際に -uas オプションをつけるとAIO更新ログモードになります。

更新ログを記録する際には、その対象となる操作の順番とログの順番は、同一のレコードに対しては常に保証されなければなりません。したがって、データベースの更新とログの書き込みは同一のロックで保護する必要があります。また、更新ログは単一のファイルの末尾に追記していくので、普通にwriteやwritevで更新ログを書き込む方法だと、更新ログの書き込み操作はグローバルなロックで保護する必要があります。そうすると、結果的にデータベースの操作がグローバルなロックの中に入っているのと同じことになってしまうのです。

そこで、writeやwritevの代わりにaio_writeを用います。aio_writeは実際にデータがファイルに書き込まれるのをまたずに制御を返し、別スレッドで書き込みを行ってくれます。ここで重要なのは、追記モードで開いたファイルの場合、aio_writeを用いた順番と書き込まれるデータの順番が同じになるのが保証されることです。したがって、データベースの操作とaio_writeをレコード単位のロック（実際は上述のハッシュロック）で保護して実行すれば、各レコードに対する更新操作の順番と更新ログの順番が確実に一致するのです。

固定長データベースに別マシン2台から合計32スレッドでアクセスして、各100万回の書き込みを計3200万回行うテストをしてみたところ、以下のような結果になりました。すごく速くなるわけでもないみたいですが、クライアント数がもっと多い場合にはもっと効果があるかもしれません。

　　　　　time　　　QPS
default　 469s　　 68230
AIO mode　378s　　 84656

まとめ

TCやTTの最近の追加機能として、固定長データベースとno replyモードと値の回転と非同期ロギングについて紹介しました。かなりマニアックな機能ばかりですが、できるだけコストをかけずに高負荷に耐える仕組みを模索するとこうなりました。こういうad hocな機能追加をいちいちサーバ作者やライブラリ作者がやっているとキリがないので、CouchDBのようにサーバ側でJavaScriptなりのデータ処理言語を動かしたい欲求に駆られますが、そうするとシンプルかつチープに徹するというTTのコンセプトと矛盾してしまうので我慢しています。TTのエンハンスはこれくらいにして別のプロジェクトをまた考えようかな（Mac OS XとFreeBSD対応をやれよという声もちらほらありますが…）。

追伸、TTの独自プロトコルのRuby版クライアントが近々出るそうです。また、TCのErlangバインディングが出たらしいので、そちらもチェックしてみてください。

夏本番に向けて海に行ける体作りに励まないといかんなーと思いつつも、ついついDSのスターフォックスで遊んでしまうmikioです。さて今回は、人知れずリリースされている検索エンジンTokyo Dystopiaの概要と設計思想について述べます。

Hyper Estraierとの違い

Tokyo Dystopia（以下、TDと呼びます）は、新しい検索エンジンです。しかし、私が作ったもう一つの検索エンジンHyper Estraier（以下、HEと呼びます）の後継としては位置付けていません。

Hyper Estraierの製品コンセプトは、「検索システムの需要が生じる様々なシーンで手軽に導入できる」ことです。言い換えれば、「いわゆるシロウトの人でも、お高い商用システムを買えない個人や小組織でも、ちょっとの努力で自分の要求を満たすシステムを構築できる」ことです。そのために、様々なファイル形式に対応したテキストフィルタを用意したり、各種のスクリプト言語バインディングを用意したり、便利な管理ツールやCGIスクリプトを付属させたりしています。典型的な使い方のひとつであるWebサーバの検索システムの構築方法についてはマニュアルにチュートリアルとして書いていますし、ファイルサーバの検索システムを作るのも付属のコマンドを数回実行するだけです。

しかし、TDは違います。エンドユーザ向けではなく、完全にプログラマ向けのパッケージになっています。ツンデレどころか、ツンツンです。言語バインディングはないしフィルタもないしUNIX版しかないしマニュアルもそっけないし英語だし…といった具合です。TDの製品コンセプトは、「数年以上の実務経験のあるCプログラマが、mixiのような膨大なデータ量と尋常でないトラフィックに耐える各種の検索システムを、実サービスの要件を満たす最適化を施しながら、コードの8割程度を再利用して実装できる」ことです。

つまり、TDはいわば業務用検索エンジンであり、一般のユースケースには向いていません。個人で企業で学校で手軽に検索システムを構築するには相変わらずHEがオススメです。なお、「Dystopia」は「Utopia」（理想郷）の反意語だそうで、現実主義のツンツンな思想を表現するのに丁度いいかなと思って名づけました。

APIの構造

TDは、文字N-gram方式とタグ付け方式の2種類のインデックス型をサポートし、それぞれに低水準と高水準のAPIを定義しています。つまり4種類のAPIが提供されます。

文字N-gram（以下、単にN-gramと呼びます）方式とは、例えば「あぶらかだぶら」を解析して、「あぶ」「ぶら」「らか」「かだ」「だぶ」「ぶら」などの文字単位で分解したトークンをインデックスに格納する方式で、TDは2文字毎（2-gramあるいはbi-gram）に分割したトークンを扱います。「あぶら」を検索するには「あぶ」の直後に「ぶら」が来ることを確かめる必要があるため、インデックス内で各トークンに関連付ける位置情報（posting list）には、文書番号と文書内での出現位置の双方を持たせます。

タグ付け（分かち書き）方式は、例えば「あぶらかだぶら」を解析して、「あぶら」「か」「だぶら」などの単語単位で分解したトークンをインデックスに格納する方式で、TDでは単語分解はアプリケーションの責任にすることで、任意の言語解析器を利用したトークンを扱えるようにしています。単語そのものが検索キーになるので複数のトークンの連接を確認する必要がなく、インデックス内で各トークンに関連付ける位置情報は文書番号のみになります。

N-gram方式は、切り出すトークンの数がめちゃくちゃ多い（文字数と同じ数になる）ことと、各々の位置情報のデータ量が大きいことから、インデックスが肥大化して検索処理も遅くなりがちです。しかし、検索漏れが起きないという利点と、自然言語処理を伴わないのでどんな言語（さらに言えば言語である必要すらない）にも適用できるという利点があるため、広く使われています。一方でタグ付け方式も、インデックスが小さくて済むという利点と、言語処理による高い検索精度が期待できるという利点があるため、これまた広く使われています。

二つの方式のどちらがいいかは一概には言えず、ケースバイケースで使い分けるべきものです。TDでは両方のAPIを別個に実装して、アプリケーション側で使い分けるなり組み合わせるなりして最適なシステムを構築してもらうという方針にしました。HEでもN-gramとタグのハイブリッドの検索を実現していましたが、TDではその調合すらもアプリケーション側でできるようになったということです。検索用のインデックスの構造としては他にも逐次探索やサフィックスアレイやシグネチャなどの方式がありますが、それらと併用するのも一興です。

低水準APIと高水準API

N-gramとタグの違いは分かったとして、低水準APIと高水準APIの違いは何でしょうか。低水準APIは単なるインデックスであり、対象のレコードそのものを保存しません。例えば、「あぶら」が番号15のレコードにあることをつきとめることはできますが、それだけでは15のレコードの文字列が何なのかはわからないのです。したがって、レコードそのものはインデックスとは別のデータベースに保存しておくことが重要です。インデックスを更新する際にも元のレコードの文字列が必要となります。

一方で、高水準APIは索引付きデータベースであり、対象のレコードそのものを保存します。例えば、「あぶら」で検索して15番が該当することがわかったら、15番のレコードの「あぶらかだぶら」を取り出して提示することができます。ディスク容量を余計に食いますが、その方が管理は楽ですよね。

もうひとつの大きな違いは、低水準APIは単一のファイルに関連するデータをすべて格納しますが、高水準APIはディレクトリの中に複数のファイルに分けてデータを格納することです。高水準APIではスケーラビリティの確保について内部で工夫がされているので大規模なインデックスを手軽に構築することができますが、それらの工夫や分散処理をアプリケーション側で制御したい場合は低水準APIを利用するとよいでしょう。

上記以外にも、低水準APIでは文字列の正規化の責任はアプリケーション側が持つが高水準APIでは内部でよろしくやってくれるとか、高水準APIだと複合検索式があるけど低水準APIだとアプリケーション側の責任で論理演算を行うとかいった違いもあります。

実装

TDはC言語で実装され、内部ストレージとしてTokyo Cabinet（以下、TCと呼びます）を利用しています。コード量はテストコード含めて13,000行くらいなので、TCの薄いラッパーと捉えてもいいくらいの規模です。実行効率の大部分はTCの性能に頼っていると言っていいでしょう。

HEはQDBMを内部ストレージにし、TDはTCを内部ストレージにしているところが実装上の大きな違いではありますが、さらに根本的な違いとして、インデックスの構造が挙げられます。HEではハッシュ関数を利用したN.M-gram法と名づけた手法でインデックスの空間効率と検索処理の時間効率を向上させていたのですが、TDでは完全な位置情報付きのインデックスを使っています。なぜそうしたかと言えば、HEは比較的長いテキストを対象にする文書管理システムのような用途を主に考えていて、その場合にはN.M-gram法による高い圧縮率が期待できますが、TDではそれよりもかなり短いテキストを対象にする名簿検索のような用途を主に考えていて、その場合には前方一致検索や曖昧検索を可能とする位置情報を保持しておいた方が利点が多いと判断したからです。

また、HEではスコア情報をインデックス内に保持しますが、TDは位置情報のみを保持します。したがって、スコア情報はインデックスとは別途に保持する必要があります。例えばユーザ検索で最終ログイン時間が新しい順で結果を表示したい場合には、インデックス内のスコア情報ではなく最終ログイン時刻DBのキャッシュを引いて並び替えを行うことになります。

TDはネットワークサーバに組み込むことを想定しています。CGIスクリプトなどに組み込んでWebサーバ経由で呼び出すことももちろん可能ですが、その方法だと複数のプロセスが別個にインデックスをメモリ空間に載せることになるので、効率が悪くなります。それよりもインデックスと接続した単一のプロセスがマルチスレッドで並列処理できる方が効率的で、さらにそれを複数のマシンに分散させるのが現実的なソリューションになるでしょう。ネットワークサーバのプログラムを実装する難易度は決して低くはありませんが、Tokyo Tyrantやlibeventなどのユーティリティを使えば最近はだいぶ楽になりましたので、仕事で取り組むのも現実的な範疇だと思います。

まとめ

業務用検索エンジンTokyo Dystopiaの設計思想について述べました。大抵の検索システムはHEで構築できると思いますしその方が楽なのですが、自分でカリカリにチューンした検索システムを作りたい場合にはTDを使っていただけると幸せになれるかもしれません。

現在、TDをベースとしたmixi内の検索システムを絶賛開発中ですので、近々お披露目できると思います。公開した際にはその具体的な設計についてまた書かせていただきます。