はじめまして。開発部じゃない加藤和良です。

最近、mixi では Buildbot をつかった継続的インテグレーションをはじめています。安定版の mixi のソースコードにコミットすると Buildbot がそれを検知し、自動的にテストが走るようになりました。

ここでの「テスト」は Test::Simple や prove(1) をつかった、Perl でかかれた開発者テストを指しています。mixi の開発者テストをとりまく環境は、ここ数年でかなり改善されました。今回はその歩みをふりかえりながら、テストの無いコードベースをどこからどうやって変えていったかという話をしたいと思います。

開発環境

はじめに、前提となる mixi の開発環境について説明します。mixi では複数人の開発者がひとつのマシンで作業を行います。それぞれの開発者は、あらかじめ割り当てられたポートで Apache を起動し、自分の好きなエディタでソースコードを編集しながら生活しています。

memcached は各マシンに一台。そして、沢山の MySQL 群や、数台の Tokyo Tyrant, Shindig などは社内のほぼ全員が同じものを共有しています。

当然のことながら、これらのサーバーは皆さんがお使いの 本番の mixi で使っているものとは、別のものです。以下で「日記」とか「ボイス」とか書いてあるのは、開発者が開発環境でつくっているデータをさすことに、あらかじめ注意してください。

2007年4月 – t/ の追加と当時の問題

mixi のソースコードは以下のように配置されています。

lib/, t/ があるのは CPAN モジュールでもありがちですが、t/ の下に lib/ と同じような階層構造があるのは、ちょっと珍しいかもしれません。

• /
  • lib/
    • Mixi/Application/Object.pm
  • t/lib/
    • Mixi/Application/Object/leave.t
  • …

この t/ フォルダは、2007年4月ごろにレポジトリに追加されました。ここから mixi の開発者テストの歴史がはじまるわけですが、当時のテストまわりにはいくつかの問題がありました。

一般に、テストを書きやすいコードは、以下のような性質を持っていると思います。

• 結果を左右する入力をどこから与えるべきかわかりやすい
• 結果がどこに出力されているかわかりやすい
• それ以外の副作用が無い

たとえば、文字列のうち HTML 上で特殊な意味をもつものをエスケープする関数や

is(escape('foo & bar'), 'foo & bar');

スタックを表現するクラスなどは「テストを書きやすい」部類のコードと呼べます。

my $stack = Stack->new;
ok(! $stack->pop);
$stack->push(123);
is($stack->pop, 123);

しかし、当時の mixi のコードベースには、前述の性質をそなえていないものが多くありました。

• 入力として、どこかの環境変数を読んでいたり、どこかのデータベースの情報を読んでいたり、new しづらいクラスを使っている
• 出力が標準出力への print だったり、データベースのどこかへの更新や削除だったり、例外処理で exit してしまったりしている
• 副作用としてどこかのデータベースや memcached に更新や削除を行ってしまう

結果、テストを書くのがむずかしかったり、せっかく書いたテストが、誰かが日記を消したり、マイミク関係を解消したのをきっかけに突然失敗するようになったり、テストを実行したらどこかのボイスの投稿が消えるかも、みたいな不安で他人が書いたテストを動かしづらかったり、といったことが起こりがちでした。

2008年12月 – Mixi::Test::Fixtures

これらの問題を解決するべく、2008年12月ごろ Mixi::Test::Fixtures という新しいライブラリが追加されました。

Mixi::Test::Fixtures は、Rails や Django にある “fixture” の仕組みを、mixi のコードベースに導入するためのライブラリです。具体的には、以下のような動作を行います。

1. テストの実行直前に、一時的なデータベースを作成
2. 指定された YAML から、データベースに値を挿入
3. テストの実行
4. テストの実行直後に、いろいろ変更のあったデータベースを削除

mixi は OR マッパを使っていない部分もいろいろあり、手書きの SQL が MySQL を期待しているところが多々あります。そのため、一時的なデータベースにも SQLite のようなインプロセスのデータベースは使わず、MySQL をそのまま使っています。テストの実行前後に CREATE DATABASE / DROP DATABASE が走るのはなかなか富豪的です。

Mixi::Test::Fixtures の導入によって

• テストが、いつ変わるかわからないデータベース上の情報に依存している
• テスト実行後にデータベース上に様々なデータが作成・削除され、2回目以降の実行では前提となる条件が変わってしまう

といった問題は回避できるようになりました。

その後、何度かのバージョンアップがあり、現在ではデータベース以外に

• memcached
• メールの送信
• 外部への HTTP アクセス

も Mixi::Test::Fixtures で差し替えが可能です。これらの動作を模倣するのはデータベースに比べるとずっと簡単なので、インプロセスで代替のコードが動くようになっています。

2009年4月 – ブラックリストの導入

Mixi::Test::Fixtures 導入以後、新しいテストについては、だれでもいつでも安心して実行できるようになりました。ただ、古いテストのなかには、まだ fixture への移行がすんでいないものもあり、気軽に実行するのは不安がありました。

一方で、すべてのテストを実行したいという要求もありました。コードの変更が予想外の部分をこわしていないかを確かめるためには、なるたけ多くのテストを実行したほうが安心です。

この中途半端な状態をなんとかするために2009年4月ごろ導入されたのが、ブラックリストと、それを使って「ホワイトな」テストを列挙する仕組みです。

まず t/blacklist.yaml に

patterns:
 - "^t/lib/Mixi/Official/Member/.*$"
files:
 - t/lb/Mixi/Application/DB/Ad.t
...

と、だれもが気軽に実行するのがまだ難しいテストを列挙していきます。これを元に list-tests というスクリプトが

% ./script/devel/list-tests
t/lib/Mixi/Application/Object/leave.t
...
%

t/ 以下をなめて blacklist.yaml にマッチしないテストの一覧を出力します。これを

% prove -lv `./script/devel/list-tests`
....

といった感じで prove(1) にわたすことで、誰もが何時でも実行できるテストだけを、簡単に実行することができます。列挙までして prove(1) の実行は行わないのは

% prove -lv `./script/devel/list-tests | grep Application`
....

のように他のソフトウェアとの連携を考えてのものです。

ブラックリストの導入に関しては

1. 実行に注意が必要なテストはだめなので、修正するか消す
2. t/, xt/ などテストをいれるフォルダを二つに分ける
3. 個々のテストに plan skip_all => ‘…’; みたいなものを記述する

というやりかたもあったと思います。

ただ、1 は修正が完了するまでテストの全実行をあきらめなくてはいけないこと、かといって締切を設定し、それまでに修正されないテストは消す、となるとテストが消えすぎること、そもそも「実行に注意が必要なテストはだめ」というのが微妙で、書いた人しか実行できないテストでもないよりはマシなことを考えて、無しになりました。

2 は、ファイルの移動に Subversion が弱いことと、2つの分割ですまなくなったときにどうしよう、というのが不安なところでした。

3 については、柔軟で良さげなので、将来的にはここに落ち着くんじゃないかと思っています。いまになって思えば、最初からこれでも良かったかもしれないですね。

2009年5月 – Test::Apache2

Mixi::Test::Fixtures とブラックリストは mixi 全体にかかわる部分でした。ここからは、各々のコードに関わる細かな部分に目をむけてみようと思います。

Test::Apache2 は mod_perl ハンドラのテストを書くためのライブラリです。目的だけみれば Apache::Test によく似ていますが、本物の Apache を立ち上げないでインプロセスで動くところが大きなちがいです。mod_perl 特有の細かな状況 (具体的にはあんまり把握していません) についてテストを書くのには向きませんが、反面、実行速度が速く準備も簡単です。

Test::Apache2 は2009年の5月ごろに mixi の安定版で使えるようになりました。現在では mixi から切り出して CPAN 上で配布しているので、mixi の外でも使えます。

既存の mod_perl ハンドラの挙動をとりあえずテストで囲いたい、みたいなときに、ちまちま Test::MockObject で Apache2::RequestRec を模倣するよりは便利だと思うので、ぜひ試してみてください。

2009年12月 – Test::Exit

Test::Exit は exit の呼び出しをテストするためのライブラリで、Andrew Rodland さんが開発されています。

...
exits_nonzero {
  invalid_op(); # なかで exit(1) する
};
done_testing;

こんなふうにつかえます。mixi では例外処理のなかで exit してしまう CGI ノリのコードがごくまれにあり、そういうものに対処するために2009年12月ごろにつかいはじめました。

Test::Exit には当時 exit($status); のみ対応していて exit; のような引数なしの呼び出しをうまく扱えないバグがあったのですが、これはパッチを送って 0.03 で直してもらいました。

こういうごくニッチなところにも先人がいるのは、CPAN というか Perl のすごいところだなあと思います。

まとめ

というわけで、mixi の開発者テストのいままでの歩みをふりかえってみました。今年に入ってからは Buildbot の設定をいろいろ詰めているのですが、これはまだ固まりきっていないので、紹介はまた次の機会に。

mixi の開発者テストまわりの仕組みは、基本的に「テストのことを考えずにだらだらコードを書いても、後から挽回できるように」できています。できているというか、そうせざるをえなかった、というのが実際のところです。

そのため、ださいところや、無理矢理なところも多々ありますし、実行速度も結構遅かったりします。ただ「テスト書きたいのは山々なんだけど、既存コードに手をいれるのはきつくて、次の機会をうかがっている」というありがちな状況からは一歩抜け出せました。「おれ、新しいフレームワーク (or ライブラリ or 言語) がきたら、次はテスト書くんだ」なんてのは、良くない類のフラグを立てているだけであると、個人的には思います。

はじめに

３月８日(月)に「言語処理学会第１６回年次大会」が開催されます！言語処理学会年次大会って何？という方もいらっしゃると思うので簡単に解説いたしますと，１年に１回主に自然言語処理学に関するたくさんの発表や講義が行われるカンファレンスです．

自然言語処理学というとなんとくむずかしそう．．．ってイメージがあるかもしれません．しかし，かならずしも専門的な知識がなくても楽しめる内容がたくさんあるのです！例えば，文書検索やレコメンデーション，テキストマイニングなど最近話題の技術は自然言語処理学の研究成果が多く使われているのです．また，最近では多くのウェブアプリケーションなどでも自然言語処理学の研究成果が使われています．今大会でもこれら加え，とても興味深い研究成果が多く発表されます！

以下に今回の開催内容を書きましたが，これだけのボリュームがあっても，なんと今大会は参加料が無料なのです！ぜひこれを機に自然言語処理学にご興味を持って参加していただける方がいらっしゃいましたら幸いです！

大会開催概要

言語処理学会第１６回年次大会は情報処理学会共催創立５０周年記念全国大会と共催で開催されます．

• 日時 2010年3月8日(月)～3月11日(木)
• 場所 東京大学 本郷キャンパス

詳しくはこちらの大会ウェブページをご参照ください．
※ご参加いただく際はなるべく事前予約をお願いいたします．

今大会はミクシィも様々な自然言語処理技術を利用させていただいていることもあり，協賛させていただくことになりました．

プログラム概要

今大会も幅広い分野の発表が行われます．概要の図を示します．
場所や時間を示した詳しい情報はこちらの言語処理学会第１６回年次大会 プログラムをごらんください．

招待講演

普段ほとんどお話を聞けるチャンスのない著名な先生による講演です．とても貴重な経験になることと思います！今大会では以下の招待講演が実施されます．

• 「これからの言語処理とその応用」
  長尾 真氏 (国立国会図書館 館長)
• 「総合学術オントロジー」
  橋田 浩一氏（産業技術総合研究所 サービス工学研究センター 次長）
• 「MASTARプロジェクト&ALAGINフォーラム」
  中村 哲氏（情報通信研究機構 知識創成コミュニケーション研究センター 副研究センター長）
• 「The Challenge of the Multicores」
  Fran Allen女史（IBM名誉フェロー） *チューリング賞受賞者

詳しくはこちらのPlenary sessionをご参照ください．

チュートリアル

３月８日に開催されるチュートリアルでは，自然言語処理学に関する多くの功績を挙げられている先生や，実社会で自然言語処理を応用している企業の方などによる研究紹介や技術紹介を講義していただきます．各講義とも基礎から応用まで詳しく解説していただく内容となっているので，ぜひご興味がございましたらご参加ください！

「自然言語処理と関連領域」

「自然言語処理と関連領域」では主に実社会での需要を考慮したトピックが選ばれています．自然言語処理学の技術を実社会での諸問題にどのように応用するか，また，実社会ならではの出てくる問題についても解説していただきます．自然言語処理と関連領域では以下のご講義を行っていただくことになっています．

• 「推薦システム -機械学習の視点から-」
  神嶌 敏弘氏（産業技術総合研究所）
• 「並列テキスト処理のための環境・ツール(EC2上での並列処理体験付き)」
  田浦 健次朗氏（東京大学）
• 「はてなで利用している言語処理技術」
  伊藤 直也氏（株式会社はてな)

「自然言語処理学基礎論」

「自然言語処理学基礎論」では主に学術的な要素が強い自然言語処理学のトピックについて講義していただきます．自然言語処理学に関する研究者の皆様が今後研究にお役立ちできるような構成を目指しました．自然言語処理学基礎論では以下のご講義を行っていただくことになっています．

• 「超高速テキスト処理のためのアルゴリズムとデータ構造」
  岡野原 大輔氏（東京大学）
• 「NICT発の言語資源－ALAGINフォーラムの活動を中心に－」
  風間 淳一氏，橋本 力 氏，山田 一郎 氏（情報通信研究機構）
• 「『現代思想』と言葉――脳・認知から遠く離れて」
  影浦 峡氏 (東京大学)

チュートリアルに関する詳しい情報はこちらのページをご参照ください．

まとめ

今回は言語処理学会第１６回年次大会について紹介させていただきました．普段あまり学会発表などを聞きに行く機会が無い方もぜひこれを機に参加していただけたら幸いです．特にテキストマイニングや検索エンジンなどの業務に携わっている方は，新しい知見が得られるかもしれません．今年は情報処理学会全国大会と共催ということもあってとても盛り上がると思います．私も開催に携わっている身ではあるのですがとても楽しみです．

都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。

Bayesian Setsとは

Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に”Inspired by Google Sets”と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、

クエリ	出力
apple, banana	chocolate, strawberry, vanilla, cherry, …
apple, macintosh	software, windows, mac, computer, …

どちらのクエリにも”apple”という言葉が含まれていますが、1つ目のクエリは”banana”と一緒に検索しているため、果物のapple, bananaに関連するアイテムが得られていることが分かります。また2つ目のクエリでは”macintosh”と共に検索しているため、コンピュータ関連のアイテムが結果として得られています。このように入力されたアイテムと同じ概念の集合をオンデマンドに特定し、その集合中の他のアイテムを取得することができます。

Bayesian Setsについてより詳しくは、以下のページをご参照ください。

• Bayesian Setsの原著論文(PDF)
• Bayesian Setsの詳細な解説記事

またBayesian Setsを使った他のシステムには連想検索エンジンReflexaがあり、はてなブックマークの関連エントリなどに使用されているようです。

関連文書検索システムStupa

Bayesian Setsを使用した関連文書検索システムとして、Stupa(ストゥーパ)というシステムを作成しました。昔アジアを旅行したときに見た仏塔(ストゥーパ)から取ったもので、特に検索には関係ありません。

• Stupa – C++ implementation of Bayesian Sets
• チュートリアル

StupaはBayesian Setsにより類似する文書を高精度に検索し、また転置インデックスを構築することで高速に検索を実行できます。登録された文書データや転置インデックスは圧縮して保持しているため、メモリの使用量も少なく実行できます。

例として日本語版Wikipediaから作成したデータ(約61万エントリ)を使用して、Stupaのコマンドラインツールで関連エントリを検索した結果を以下に示します。結果のリストには、関連するエントリの名前と関連度が1行1エントリで表示されます。

• 「トヨタ自動車」で検索

% bsmgr search /path/wikipedia.tsv
Read input documents ...
Query> トヨタ自動車
トヨタ・プリウス        62.243313
トヨタ・トヨエース      56.777371
トヨタ・コロナ  54.229831
張富士夫        53.586574
トヨタ・ハイラックス    51.514397
トヨタ・プロボックス    49.165956
トヨタ・パブリカ        49.076950
中村健也        47.865204
奥田碩  45.499038
特別仕様車      45.440519
...
(search time: 3.21ms)

• 「かめはめ波」と「ドラゴンボール」で検索

Query> かめはめ波       ドラゴンボール
かめはめ波      263.980312
トランクス (ドラゴンボール)     72.204788
ミスター・サタン        69.037348
ドラゴンボールのアニメオリジナルの登場人物      65.560679
ドラゴンボールZ 超悟空伝 -突激編-       62.634941
ベジット        62.190804
ドラゴンボールZ 燃えつきろ!!熱戦・烈戦・超激戦  54.983379
ダーブラ        53.873965
ギニュー特戦隊  51.688147
ドラゴンボールZ この世で一番強いヤツ    51.597809
...
(search time: 3.95ms)

上記は「トヨタ自動車」で検索した場合と、「かめはめ波」「ドラゴンボール」の2つで検索した場合の結果ですが、両方とも関連するエントリが取得できています。検索にかかった時間は3ミリ秒ほどと比較的高速に実行できていることも分かります。

Stupaは入力された文書データや転置インデックスをメモリ上で保持して動作するため、頻繁に文書の追加・削除が行われるようなリアルタイム性の高いアプリケーションでの利用を主に想定して開発しています。例えばTwitter上で、自分の発言に関連するTweetを即座に検索する、といったアプリケーションが作れるかもしれません（Twitterだと1発言あたりの文章が短すぎて精度が悪くなってしまうかもしれませんが）。

またオプションで登録できる文書の最大数を指定すると、最大登録数を超えた場合に古い文書から削除していくようになるため、使用リソースを一定に抑えつつ、常に最新の文書から関連しているものを検索することができます。

Thriftによる検索サーバ

StupaにはC++ライブラリとコマンドラインツールが含まれているのですが、これ以外にThriftを使用した検索サーバも配布しています。Perlのクライアントも同梱されていますので、Webサービス等に実際に導入することも可能だと思います。

また現在クライアントはPerl実装しかないのですが、Thrift用のインタフェース定義ファイルがパッケージに含まれていますので、RubyやPythonなど他言語のクライアントを生成することも可能です。より詳しくはThriftのマニュアルをご参照下さい。

まとめ

関連文書検索システムStupaをご紹介させていただきました。StupaはBayesian Setsを使用して、高精度かつ高速に検索を実行することが可能です。今後はmixi上での応用を考えつつ、パフォーマンスの向上等を行っていきたいと思います。もしご興味がある方がいらっしゃいましたら、ぜひご利用下さい！

皆さんこんにちは。プラットフォーム開発を担当しています、よういちろう です。今回は、最近リリースした非常に興味深い機能を紹介したいと思います。

mixiアプリ、楽しんでいますか？

mixiは昨年の8月24日にプラットフォーム化を遂げました。既に多くの方々が、何らかのmixiアプリに触れ、ソーシャルアプリケーションという新しいジャンルを楽しんでいるかと思います。

mixiアプリの特徴は、何と言っても「マイミクとのちょっかいの出し合い」です。

• 虫を付けたら付け返す
• 掃除をしてくれたらお礼をする
• 旧友と出会い当時の先生の話で盛り上がる

などなど、ソーシャルグラフを使ったアプリケーションならではの多様なコミュニケーションを、mixiアプリを通じて体験することができます。電車に乗っていて「昨日虫いっぱい付けたでしょー」など、リアルな場においてもネタとしてmixiアプリのことが話されているのを聞いて、最近はニヤッとすることも多くなりました。

アイテム課金

さて、そんなmixiアプリですが、既にアイテム課金を始めているアプリも多くなってきました。マイミクへのお礼として、気持ちを込めるためにちょっとお金を出してもいいかな、という思いをきっと持ったことがあると思います。mixiアプリでの課金に関しては、例えば自分の装備を強化するためではなく、あくまでマイミクとのコミュニケーションを取るための一形態として、アイテムの購入が行われることを期待しています。

昨年の11月5日より、既にモバイル向けmixiアプリにてmixiポイントを使った決済を行うための課金APIをご提供していますが、先日の21日より、PC向けmixiアプリ課金APIをリリースいたしました。今までPC向けmixiアプリでは外部の決済サイトを使った課金処理に頼る必要がありましたが、PC向けmixiアプリ課金APIを使うことで、mixi内で決済を完了することができるようになります。

このPC向けmixiアプリ課金APIを利用するためには、そのmixiアプリがPC/モバイル両対応であり、モバイル向けmixiアプリが既にカテゴリ掲載されていることが求められます。詳しくは、以下のページを参考にしてください。

http://developer.mixi.co.jp/appli/mixi_payment_program/summary

OpenSocial Virtual Currency API

さて、PC向けmixiアプリで利用できる課金APIですが、これは「OpenSocial Virtual Currency API」という仕様に準拠して実装されています。これは、OpenSocialに準拠したコンテナ上で課金APIの標準化を行いましょう、というかなり意欲的な仕様です。海外では既にHi5や51.comなどがこの仕様をサポートしています。

http://code.google.com/p/opensocial-virtual-currency/
http://docs.google.com/View?id=dhsg598c_994hdb9pwcf (日本語訳)

OpenSocial Virtual Currency APIでは、現在ガジェット向けのJavaScript APIが策定されています。この仕様をベースとして、PC向けmixiアプリ課金APIを策定しています。ただし、完全にそのままではなく、決済情報をより安全にやり取りするために、いくつか独自の拡張を行っています。

必要となる記述を全てここで紹介することは難しいのですが、課金APIを利用するためのコードでJavaScriptで記述する部分は、以下のようになります。

var params = {};
params[opensocial.Payment.Field.AMOUNT] = 150; // 金額
params[...] = ...; // その他パラメータをセット
var payment = opensocial.newPayment(params); // Paymentの生成
opensocial.requestPayment(
    payment, // Paymentオブジェクト
    "http://example.com/payment/handler", // SAP側サーバのハンドラURL
    function(response) {
        var result = response.getData();
        if (result.isComplete()) {
            // 決済結果に対する処理
        }
    }
);

実際にはmixi固有の記述やSAP側サーバでの実装が上記のコード以外にも必要となります。しかしこのコードは、基本的にHi5や51.comといったプラットフォームでも「ちょっとした修正のみで」動作するでしょう。OpenSocial Virtual Currency APIによって、ソーシャルアプリケーションのポータビリティが課金処理に関してももたらされることになるということですね。

まとめ

ソーシャルというキーワードは、今年もインターネットな世界のトレンドとして昨年以上によく聞く言葉になるでしょう。今回紹介した課金APIは、ソーシャルアプリケーションという新しいジャンルを一歩も二歩も前進させる、非常に注目すべきAPIです。ユーザ間の多様なコミュニケーションの中で課金APIを如何にうまく使うか、そしてOpenSocial Virtual Currency APIやOpenSocialそのものの先にある世界を舞台としたソーシャルアプリケーションプラットフォームをどう見据えていくか、それらの答えはこれから出てくると思います。

今後のmixi Platformにぜひご期待ください！

飲み屋に行くとかなりの確率で荷物を忘れて帰るmikioです。さて、今回はここ2ヶ月ほどで急ピッチで開発した軽量データベースライブラリ「Kyoto Cabinet」について紹介します。

開発の動機

以前から軽量データベースライブラリとしてご好評いただいているTokyo Cabinetですが、DBMとして必要十分な機能と性能を備えていてなかなか良いものだと自負しております。ただ、開発を進める中でいくつか不満な点があったのも事実です。端的に言えば、全てC言語で記述して、標準ライブラリ（とzlib/bzip2）以外の機能は全て自作しているので、最適化がしやすい反面、メンテナンスの難易度が高くなってしまっているというのが不満です。

そこで、多少性能が悪くなってもいいから、私自身としてお気楽に開発およびメンテナンスができて、移植性も高いような実装を作ってみようと思い立ったのが昨年10月頃。様々な検討を経てついにC++を採用し、STLを使って楽々にプログラミングしてみようということになりました。

特徴

KCの基本設計はTCのものを踏襲しているので、TCと同じく以下の点が優れています。

• プロセス組み込みなので、ネットワーク通信等のオーバーヘッドがない。
• 静的ハッシュの単純な構造なので高速で並列性も高い。
• データベースファイルが小さく空間効率が高い。
• オンメモリデータベースとファイルデータベースを使い分けられる。
• トランザクションによってACID属性を確保。
• 動的デフラグでデータベースの肥大化を抑止。
• APIが単純で使いやすい。
• 名前がかっこいい。

一方で、KCは実装上の工夫をさらに重ねて、TCに比べて以下の利点を獲得しています。

• さらに空間効率が高い。
• さらに並列性が高い。
• 下層の抽象化による非POSIX環境への対応。
• レコード操作の究極的な抽象化。
• 実装上の細かい改善。

KCの性能はTCに比べてかなり低く、現状では半分以下です。しかし、ユーザランドでの並列性は高いはずなので、OSやハードウェアの並列性が上がれば、並列処理で使った場合の全体のスループットがTCに勝つ日も来るかもしれません。

空間効率が高い

いかなるデータベースにおいても、レコードを管理するためのデータを記憶しておく必要があり、TCやKCではレコードに前置するヘッダとしてそれを表現しています。データベースの空間効率を高めるにはこのヘッダをできるだけ小さくすることが重要です。

TCでは通常モードで14バイト、ラージモードで22バイトのヘッダ領域をレコード毎に必要としていました。通常モードとラージモードの違いはレコードのアドレッシングのために4バイトの領域を使うか8バイトの領域を使うかの違いです。4バイトだと2^32=4GBまでの値を表せ、それにデフォルトアラインメントの16バイトを掛けた64GBまでのデータベースを扱えることになります。8バイトだと2^63=8EBまでのデータベースを扱えます。

今日の一般的な計算機環境を考えると、4バイトアドレッシングは非力すぎる一方、8EBのストレージなんてものも存在していません。そこで、KCではモードを統一して、6バイトアドレッシングを採用しています。6バイトだと2^48=256TBまでの値が扱え、デフォルトアラインメントは8なので、2PBまでのデータベースを扱えることになります。1台のデータベースで扱えるサイズとしては当面はこれで十分でしょう。なお、アラインメントは32768まで上げることができるので、ライブラリとしての最大データベースサイズはTCと同じく8EBまでとなります。

アドレッシングの幅が4バイトから6バイトに上がった分だけ空間効率が悪化するので、それが最小限になるように努力もしています。レコードを識別するためのマジックナンバをサイズ管理用の領域に押し込んだり、後述の二分探索木をバランスさせるためのキーを動的に再計算することで記憶領域をとらないようにしたりして、16バイトまで抑えました。TCの通常モード14バイトに比べると多少増えていますが、ラージモードの22バイトに比べるとかなり減っています。

TCやKCでは静的ハッシュ法によるインデックス（バケット配列）を管理することでレコードの探索を高速化していますが、バケット配列の要素が足りない場合でも著しく遅くならないようにするために、ハッシュ値の衝突管理を二分探索木で行って計算量を抑制しています。とはいえ、単一のマシンでどれだけのレコードを管理できるかはあらかじめ予測できるはずなので、きちんとチューニングすれば二分探索木の機構は不要とも言えます。そこで、きちんとチューニングできる人達のために、「線形モード」も用意しました。二分探索でなく線形リストとして衝突管理を行うことで子供のアドレスの6バイトを節約するのです。つまり、線形モードを使えば、バケット配列のサイズに対してセンシティブな性能特性にはなるけれど、ヘッダのサイズを10バイトにまで減らせるのです。

さらに、KCは使うけどデータベースサイズが32GB以下だと確実に分かっている場合には4バイトのアドレッシングで十分なので、「スモールモード」も用意しました。線形モードとスモールモードを併用するとレコード毎のヘッダは8バイトで済みます。ここまでやればTCに対して優位性を示せるでしょう。

並列性が高い

TCやKCではPthread（POSIXスレッド）パッケージでマルチスレッドの排他制御を行っています。例えばデータベースファイルのサイズというメタデータを更新するためには、mutexでロックをかけて、更新を行って、ロックを解除するという手順を踏んでいます。この構造自体は仕方ないことですが、変数一つを更新するためにmutexのロック/アンロックのオーバーヘッドがかかるのは非効率なので、できればもっと軽量な方法を使いたいところです。

うまいことに、GCCのバージョン4からはi386のアトミック演算機能を呼べる拡張機能がサポートされているので、それを使うことにしました。もちろんIntel系以外のCPUを使った環境やGCC以外のコンパイラでビルドする場合にはそれだとうまくいかないので、その場合はspinlockで該当の変数を保護する代替実装を適用するようにしています。

それ以外にも、並列性に着目してコード全体を見直して、ロックフリーとはいかないまでも、クリティカルセクション内でブロックし得るシステムコールを一切呼ばないというところまでは来ています。

TCと同じく、「pread/pwriteというシステムコールは明示的な内部状態（ファイル位置）を持たないので並列性が高いと言われつつも実際には期待外れな問題」に対処するためにmmapを積極活用しています。KCでは全てのファイルI/Oをmmap経由でやろうとも思ったのですが、諸事情で断念して、結局mmapとpread/pwriteを併用する実装になっています。

非POSIX環境への対応

TCでは最適化のためにモジュール化の原則を崩しまくっていわばモノリシックな構造になっているので、POSIX依存のコードをそうでないOS用に書き換えるのが絶望的に難くなっています。とはいえ、TCは主にWebサービスのバックエンドとして利用することを想定しているので、LinuxやFreeBSDやSolarisで動けば十分だという割り切りの上で設計をしていたので、これは問題ではありませんでした。いわゆる組み込み系やWindows等のデスクトップ環境で動く必要はないということです。

一方、KCは組み込み系やWindowsでも動くようにする予定です。よって、多少オーバーヘッドがあろうとも、処理系依存部分は徹底的にモジュール化して、C++03標準で定義されていないシンボルはハッシュDB本体の実装には一切現れないようにしました。主にファイルI/Oを抽象化するFileクラスとスレッド管理を抽象化Threadクラスがそれを担っています。

Windows版はまだ開発に着手できていませんが、数ヶ月以内にはリリースしたいと思っています。構造を単純化したのでPure Java版も作れるだろうとかDBフォーマットをRFCにできたら格好いいとか妄想は膨らみますが、多分口だけで終わると思います。

レコード操作の抽象化

KCを設計する際に、「KVSとは何だろう」「DBMとは何だろう」とかいう哲学的な部分を考察しました。その結果、KVSとは以下のメソッドを宣言したインターフェイスであるという仮説が導き出されました。

• set : キーと値の組を記憶し、後でgetできるようにする。
• get : キーを指定して、そのキーを伴って直前に記憶された組の値を取得する。
• remove : キーを指定して、そのキーを伴って直前に記憶された組の記憶から消す。
• open : 直前にcloseした際の記憶を復元する。
• close : setやremoveによって更新された論理構造を記憶装置に保存する。

KVSの「Key-Value」はset/get/removeを示し、「Store/Storage」はopen/closeを示す感じでしょうか。そして、DBMとは、上記KVSの実装形態の一つであり、実装として以下の条件を満たすものです。

• ファイル記憶 : 記憶状態をファイルシステム上のファイルに保存する。
• プロセス組み込み : ネットワーク通信を伴わず、関数呼び出しだけの低いオーバーヘッドでメソッドを呼び出せる。

これらはあくまでオレオレ定義にすぎませんが、KCはDBMであり、DBMはKVSなので、KCはKVSだと考えています。まあ、「分散しないものはKVSとは言えない」とか、「ACIDじゃないものはそもそもDBとは言えない」とかいうオレオレ定義をするのも自由なので、TCやKCを実際のところ何と呼ぶのかはユーザの皆様にお任せすることにします。

話を戻して、KVSインターフェイスの一実装であると認識されるKCですが、並列処理を想定した場合、キーと値の組に対する操作はset/get/removeだけでは済まないというのが課題になります。単一スレッドの直列処理の場合、レコードの状態をgetしてから、その内容やそれ以外の状況に応じてそのレコードをsetしたりremoveしたりすれば、キーと値の組に対するいかなる操作も実現することができます。一方で、並列処理の場合、getしてからset/removeするまでの間に別のスレッドがレコードの状態を変更してしまう可能性があるため、何らかの排他制御機能が必要となります。そのためには主に以下の二つの戦略があります。

• lock/unlockメソッドの定義 : 該当のレコードをlockしてから、任意の操作を行って、最後にunlockするのをアプリケーションの責任で行う。
• 各種の操作を全てライブラリ側で定義 : 上記の操作のひとつひとつをライブラリ側で実装する。

前者はライブラリ側の実装が簡素になるとともに、アプリ側で排他制御の有無や粒度を自由に設定できるという利点がある反面、実装が複雑になり、デッドロック等の酷いバグを生み出す原因になります。後者逆の特性で、アプリ側は不自由ながらも簡潔になる反面、ライブラリ側のメンテナンスは非常に大変になります。TCでは後者を採用して、putcatとかaddintとかaddbouleとか多数のメソッドを実装しまくるという苦労を味わっていますが、KCではその苦労を少しでも軽減したいものです。

ここでKVSの定義を再検討してみましょう。レコードに対するいかなる操作も、「特定のレコードの状態を調べて、それに応じて更新操作をしたりしなかったりする、という挙動をアトミックに行う」という風に抽象化できます。例えば、各種操作は以下のような言い換えが可能です。

• set : レコードの状態を調べるが、その状態の如何に関わらず新しい値に書き換えて更新する。
• get : レコードの状態を調べて、レコードがあれば値を返し、元の状態をそのまま残す。
• remove : レコードの状態を調べて、レコードがあれば削除して、なければ何もしない。
• increment : レコードの状態を調べて、レコードがあればそれを数値とみなして、なければ0とみなして、付与の値を足した値をもって、レコードの値を書き換える。
• append : レコードの状態を調べて、レコードがあればその値に、なければ空文字列に、付与の値を後置した値をもって、レコードの値を書き換える。

例えて言うなら、キーに対応するレコードの空間にアプリケーションの実行者を案内して、その値の読み書きを自由にさせるという操作を、その空間に限定してアトミックに行わせるということです。すなわち、KVSの仕様としては、操作の具体的な内容ではなく、アトミック性を保証する範囲が重要であるということになります。その考えに基づいてKVSを定義すると、以下のようになります。

• キーに対応する値の更新履歴を1世代以上記憶することができる。
  • openメソッドは記憶のある時点のスナップショットを復元する
  • closeメソッドは記憶のその時点のスナップショットを保存する
• キーに対応するレコードの状態の取得と更新をアトミックに行える
  • 付与のキーに基づくレコードがある場合、そのレコードの値を渡してコールバック関数を呼ぶ
  • 付与のキーに基づくレコードがない場合、何も渡さずコールバック関数を呼ぶ
  • 上記のコールバック関数が値を返したなら、その値を元のキーに対応する値として記憶する

具体的なAPI

ここまでの議論で新たに認識したKVSインターフェイスをC++のAPIに落とし込んでみましょう。

class DB {
  // レコードの空間を訪問する操作主体のクラス
  class Visitor {
  public:
    // 訪問時、更新が必要ない（no operation）の場合に返す値
    static const char* const NOP;
    // 訪問時、そのレコードを削除したい場合に返す値
    static const char* const REMOVE;
    // 仮想デストラクタ
    virtual ~Visitor() {}
    // 既存のレコードを訪問した場合に呼ばれるコールバック関数
    virtual const char* visit_full(const char* kbuf, size_t ksiz,
                                   const char* vbuf, size_t vsiz, size_t* sp) = 0;
    // 存在しないレコードを訪問した場合に呼ばれるコールバック関数
    virtual const char* visit_empty(const char* kbuf, size_t ksiz, size_t* sp) = 0;
  };
  // 訪問者を受け入れる
  bool accept(const char* kbuf, size_t ksiz, Visitor* visitor, bool writable);
  // データベースを開く
  bool open(std::string& path, int mode);
  // データベースを閉じる
  bool close();
};

上記はKyoto Cabinetの実際のインターフェイスです。アプリケーションは、openでデータベースオブジェクトを利用可能にした後、DB::Visitorを実装した任意のクラスを定義して、それをデータベースオブジェクトのacceptメソッドに渡して操作を行い、最後にデータベースオブジェクトを閉じます。データベースから「hoge」というキーに対応する値を検索して表示するアプリケーションは以下のようになります。

DB db;
db.open("casket", DB::OREADER);
class : public DB::Visitor {
  virtual const char* visit_full(const char* kbuf, size_t ksiz,
                                 const char* vbuf, size_t vsiz, size_t* sp) {
    cout << string(kbuf, ksiz) << " has " string(vbuf, vsiz) << endl;
    return NOP;
  }
  virtual const char* visit_empty(const char* kbuf, size_t ksiz) {
    cout << string(kbuf, ksiz) << " is empty" << endl;
    return NOP;
  }
} visitor;
db.accept("hoge", 4, &visitor, false);
db.close();

毎回Visitorを実装するのは面倒なので、KCの実際のDBクラスには典型的な操作であるset/get/remove/append/incrementをacceptを使って実装したものがビルトインとして組み込まれています。ただ、レコードの操作は必ずacceptを経由するようにしているので、ライブラリ内の実装はとても簡潔で保守しやすくなっています。

詳細についてはKCのチュートリアルとAPI文書をご覧ください。

実装上の細かい改善

KCではハッシュ関数としてMurMur hashを採用しています。TCで採用していた各バイトを37倍して足すハッシュ関数だと、自然言語の単語のようなものをキーにする際にはとても効率がよいのですが、intなどのバイナリ表現をそのままキーにすると衝突率が高まるという弱点があります。TCでは主なユースケースのひとつとしては全文検索の転置インデックスを想定していたのでそれでもよかったのですが、KCではより汎用性を重視して、数値のバイナリでも偏りが出にくいという評判のあるMurMurを採用した次第です。MurMur hashと同じような特性を示すFNV hashも捨てがたいところで、自然言語の単語ではFNVの方がよさげでしたが、やはり数値バイナリでの安定性が上のような気がするMurMurを採用しました。とはいえ、ハッシュ関数はプラグインで入れ替えられるようにする予定です。

TCでは値の圧縮にgzipとbzip2を切り替えて使えるようにしていましたが、bzip2モードを使う人があまり多くない割に、libbz2-devパッケージをインストールしていなくてはまる人が多いので、bzip2は廃止しました。ただし、TCと同じく任意の圧縮関数をプラグインで入れ替えられるようにしているので、bzip2はもちろん、LZOやLZSSやLZMAを使うことも可能です。

特定のハッシュ関数や圧縮関数で作ったデータベースファイルは同じ関数のセットを組み込んだDBオブジェクトで開かないと不整合が起きるわけですが、チェックサム機構を備えることでそういった不整合を事前に検出できるようにもしています。

TCでは全レコードを横断的に参照するために内部イテレータ方式を採用していました。内部イテレータ方式は、データベースの内部にどこまで読んだかという情報を保持するので、アトミック性の確保が容易になり、実装も単純になる反面、同時に一つのイテレータしか使えないという弱点があります。KCでは内部イテレータと外部イテレータの両方をサポートしています。外部イテレータ方式は、どこまで読んだかという情報を保持するカーソルオブジェクトを生成してアプリケーション側で管理するものです。アトミックに全レコードを操作したい場合には内部イテレータを用いて、アトミック性はいらないから複数スレッドで並列にスキャンを行いたい場合には外部イテレータを使うとよいでしょう。

さらに、KCではイテレータによるレコードアクセスもacceptメソッドを経由して行うので、Visitorによる任意のアトミック処理ができ、そしてイテレーション中のレコードの書き換えも簡単に行うことができます。どうせならSTLのstd::map::iteretorと互換にしようともちらっと思いましたが、あまりに面倒なので挫折しました。

まとめ

Kyoto CabinetはTokyo Cabinetの後継の製品で、性能は悪化していますが、機能性と並列性と移植性と保守性は向上しています。まだまだアルファバージョンで、実用に耐える品質とは言い難い状態ですが、そこそこ使える状態まではもっていく所存です。

TCは不要なのかというのがFAQになりそうなのでここで答えておくと、そんなことはありません。おそらく、TCが使える環境ではTCを使い続けるのがよいでしょう。POSIX準拠でない環境（主にWindows）でDBMが欲しい場合にはKCが役立つと思います。そういう意味では、KCはTCの後継というより、QDBMを共通の親とするTCの兄弟と言った方が適切かもしれません。