mixi engineer blog

*** 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers *** ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

Kyoto Cabinet 1.0.0リリース!

夏が近づくとウキウキしてくるmikioです。昨日ついにリリースされたKyoto Cabinet 1.0について今回は報告します。

1.0の位置づけ

コミュニティ毎や製品毎にバージョン番号割り当ての方針は異なるわけですが、私の個人的なポリシーでは、1.0には特別な意味があります。すなわち、0.xのバージョンはbeta版的な位置づけで、「実サービスに使うのはちょっと待った方がいいですよ」ということを意味します。一方で、1.xはstable版的な位置づけで、「よろしければ実サービスでも使ってみてください」ということを意味します。私がstable版に設定する原則を以下に列挙します。

  • 安定稼働を至上命題とする(バグがあればその修正を最優先する)
  • APIを変更しない(変更するとしても後方互換性を維持する)
  • DBファイルのフォーマットを変更しない(変更するとしても後方互換性を維持する)
  • なるべく機能追加しない(追加するとしてもモジュールを分割して行う)
  • テスト追加とリファクタリングと文書執筆は継続的に行う。
  • 余剰工数でなるべくユーザサポートを行う。

安定性というのは永遠の課題です。1.0になったからってバグがないと言いきれるわけでもない(見つかったバグはもちろんすべて潰しているが、見つかっていないバグがもう無いということは証明できない)ので、あくまで気持ちの問題にすぎません。しかし、結構テストを書いたのでポピュラーな環境とユースケースでは普通に動くとは思います。

特徴のおさらい

1.0になった今や、Kyoto Cabinetは以下の特徴を備えます。いつの間にかWindowsがサポートされているあたりが激アツですね。

  • 時間効率:ハッシュDBはO(1)、ツリーDBはO(logN)の時間計算量。更新能力は100万qps以上。
  • 空間効率:レコードあたりのフットプリントが、ハッシュDBだと8〜16バイト、ツリーDBだと2〜4バイト。
  • 並列性:ハッシュDBはレコード単位のread-write lockのみ、ツリーDBはツリーDBはページ単位のread-write lockのみ。
  • 利便性:Visitorパターン風インターフェイスによるレコード操作の一般化。多相DBによるアルゴリズムの動的変更。
  • 堅牢性:手動トランザクション、自動トランザクション、自動リカバリ等の実装。
  • 移植性:UNIX系(Linux、FreeBSD、Solaris、Mac OS X)だけでなくWindows(VC++)もサポート。
  • 他言語バインディング:C++がコアだが、C, Java、Python、Ruby、Perlのバインディングも提供。

Tokyo Cabinetに比べると、KCは特に並列性と利便性と移植性に優れています。ただしシングルスレッドでの時間効率はTCの方が2倍くらいよいです。とはいえ、マルチコア・メニーコアが主流となってくる2010年代ではTCよりもKCの方が活用できると思いますので、ぜひKCの採用を検討していただきたいと思います。なお、TCの保守も継続してバグ修正等の対応はします。

他(多)言語バインディングのススメ

バージョン1.0を出すための条件として、ポピュラーなプログラミング言語の中で私がサポートできるもののバインディングは揃えてしまおうと考えていました。その理由は主に2つあります。ひとつは、バインディングを書く過程でコア側のAPIをいくつか変更したくなることは容易に予想できたからです。もうひとつは、各種の言語のインターフェイスを設計しながら個々の言語の視点でコア側を眺めると、C/C++視点では見つけられなかった設計上の問題がいろいろ検出できるので、それに事前に対応しておきたかったからです。

上記はTCとそのバインディングを書いた時の経験則ですが、おそらくDBM以外のC/C++ライブラリに関しても同じことが言えると思います。他言語バインディングを書く時には特にスレッド対応の点で苦労します。JavaやRubyなどのガベージコレクションを前提とする言語では、言語処理系側に所有権を預けたオブジェクトのデストラクタが制御できないタイミングで呼ばれるので、デストラクタの呼び出しタイミングについて何らかの前提条件を設定していた場合に困ったことになります。今回の例で言うと、あるDBオブジェクトに対して作ったカーソルオブジェクトの生存期間よりもDBオブジェクトの生存期間は長くなければいけないという前提があったのですが、GCでオブジェクトを破棄する場合にはその順序は制御できないのです。そういう場合には、カーソルクラスをラップした「カーソルデポジット」クラスを容易して、DBの生存期間に関連づけてカーソルを破棄するようにしなければなりません。

他にも、Java1.1やRuby1.8やPerl5などにおけるスレッド実装のように、グリーンスレッド(ネイティブスレッドを使わずにユーザ空間でスレッドを実装するモデル)の場合には、C/C++側で使っているネイティブスレッドのロック機構やTLS(スレッドローカルストレージ)が全く機能しないので、個々の処理系のロック機構やTLSを使って排他制御を実装しなおさなければならないという問題があります。この問題に関してはKCでは対応できていません。今後すげー暇になったら対応するかもしれませんが、利得が低いので多分やらないと思います。

他言語バインディングを書く上でスレッドの次にハマるのが、文字列の扱いについてです。JavaやPython3のように文字列クラス(JavaのString、Python3のUnicode)とバイト配列クラス(Javaのbyte[]、Pytohn3のbytes)が分離されている処理系もあれば、PerlやRubyのように双方を同じ型として統合して扱う処理系もあります。分離脳で考えている時に統合スタイルを見ると、別概念を無理やり一緒にしちゃっている感じがして気持ち悪いですが、一方で統合脳で考えている時に分離スタイルを見ると、似たような概念をわざわざ別クラスに分けたおかげで手間が2倍になる気がして気持ち悪いです。個人的には分離でも統合でもなくバイト列だけあればいい派で文字列なんてものがなければいいと思っているのですが、まあいずれも好み(および主想定ユースケース)の問題なんで、郷に入れば郷に従えというのが結論です。

KCとしては、分離スタイルの言語では、ライブラリへの入力(set等のメソッドの引数)としては文字列もバイト列もポリモーフィックに両方受け付けて、内部的にバイト列に変換した上でコアに渡します。ライブラリから出力(get等のメソッドの戻り値)としては、基本的にバイト列を返し、メソッド名に「_str」という接尾辞をつけたメソッドを呼び出した場合には文字列を返すようにしています。一方で統合スタイルの言語では、文字列はUTF-8前提で解釈して暗黙的にバイト列と相互変換して扱うようにしています。

といった感じで、ある言語の世界にどっぷり浸かりながら別の言語に触れると、奇妙に見える点を見つけてはdisってしまうのが人情というものですが、いくつかの言語のバインディングを通して書いてみると見方が変わってきます。こと歴戦の猛者達が議論の限りを尽くして設計している言語処理系に限っては、それぞれにちゃんとした理由があってやっていることがほとんどなのだなぁと実感できるのです。また、自分の実装が特定の言語でしか通用しない前提条件を設けてしまっていることに気づいて修正する機会を得ることができます。TCもKCも他言語バインディングの実装とそれに伴うコアの修正によって製品の品質(と自分の偏狭さ)がかなり改善したので、機会があればぜひ皆さんもC/C++実装+他言語バインディングという開発スタイルに挑戦してみてください。

Perlバインディング

Perlの会社に勤めているので、Perlバインディングについて宣伝しておかないと恰好がつきませんね。どの言語でもできることは基本的に変わらないのでRubyバインディングの記事を見ていただければ機能性については理解したいただけるとは思いますが、いちおうPerlの文脈で書き直してみます。

まずは基本的なユースケースですね。ライブラリを取り込んで、データベースオブジェクトを作成して、データベースを開いて、いくつかレコードを格納して、検索してみて、さらに全レコードの一覧を取得してみて、最後にデータベースを閉じます。

use KyotoCabinet;

# データベースオブジェクトを作る
my $db = new KyotoCabinet::DB;

# データベースを開く
if (!$db->open('casket.kch', $db->OWRITER | $db->OCREATE)) {
    printf STDERR ("open error: %s\n", $db->error);
}

# レコードを格納する
if (!$db->set('foo', 'hop') ||
    !$db->set('bar', 'step') ||
    !$db->set('baz', 'jump')) {
    printf STDERR ("set error: %s\n", $db->error);
}

# レコードを検索する
my $value = $db->get('foo');
if (defined($value)) {
    printf("%s\n", $value);
} else {
    printf STDERR ("get error: %s\n", $db->error);
}

# レコードの一覧を取得する
my $cur = $db->cursor;
$cur->jump;
while (my ($key, $value) = $cur->get(1)) {
    printf("%s:%s\n", $key, $value);
}
$cur->disable;

# データベースを閉じる
if (!$db->close) {
    printf STDERR ("close error: %s\n", $db->error);
}

TIEHASH

KCでは、言語共通の機能の他に、各言語独自のスタイルでもごにょごにょできるようにしています。Perl独自といえばやはりtieですよね。こんな風に使います。

use KyotoCabinet;

# ハッシュ変数をデータベースに結びつける
my $db = tie(my %db, 'KyotoCabinet::DB', 'casket.kch');

# レコードを格納する
$db{'foo'} = 'hop';   # 文字列が基本
$db{bar} = 'step';    # キーの引用符は省略できるよ
$db{3} = 'jump';      # 数字だって使えちゃう

# レコードを検索する
printf("%s\n", $db{'foo'});

# トランザクション内で更新する
$db->transaction(sub {
    $db{'foo'} = 2.71828;
    1;  # 真を返せばcommit、偽を返せばabort
});

# Visitorパターンでレコードの値を2倍にする
$db->accept('foo', sub {
    my ($key, $value) = @_;
    $value * 2;  # 戻り値が新しい値になる
});

# 標準イテレータでレコードの一覧を得る
while (my ($key, $value) = each(%db)) {
    printf("%s:%s\n", $key, $value);
}

# KC独自イテレータでキーの値を大文字にする
$db->iterate(sub {
    my ($key, $value) = @_;
    uc($value);
});

# カーソルでレコードの一覧を得る
$db->cursor_process(sub {
    my ($cur) = @_;
    $cur->jump;
    while ($cur->accept(sub {
            my ($key, $value) = @_;
            printf("%s:%s\n", $key, $value);
            KyotoCabinet::Visitor::NOP;
        })) {
        $cur->step;
    }
});

# 関連付けを破棄してデータベースを閉じる
undef($db);
untie(%db);

tieしたハッシュ変数を介してはハッシュインターフェイスのメソッドしか呼び出せません。そこで、ここではトランザクション等のKC独自インターフェイスも同時に使うために、tieの戻り値である元来のオブジェクトも利用しています。

my $db = tie(my %db, 'KyotoCabinet::DB', 'casket.kch');

上記で、$dbがKC元来のDBオブジェクトの参照を保持する変数で、%dbはハッシュ変数です。$db{"hoge"} とした時にはハッシュ変数の方が評価され、$db->hogeとした時には元来のオブジェクトの参照変数の方が評価されますが、両者はあくまで別個の変数です(紛らわしいようならば別の名前にするのもよいでしょう)。なので、スコープ内で破棄する時には別個に破棄する必要があります。

undef($db);
untie(%db);

もちろん、ハッシュ互換インターフェイスしか使わないのであれば、tieの戻り値を何にも代入しないでOKです(その場合は当然最後のundefも必要ありません)。

メモリ使用量

tieがあることで組み込みハッシュの省メモリな代替としてKCを使えるわけですが、実際どのくらいメモリ使用量が少なくなるかを見てみましょう。100万レコードを格納した際のメモリ使用量と時間を計ってみました。

メモリ使用量 経過時間
標準ハッシュ 99.332 MB 1.683 秒
KC(オンメモリDB) 53.262 MB 5.431 秒
KC(ファイルハッシュDB) 40.031 MB 7.315 秒
KC(ファイルツリーDB) 60.258 MB 6.486 秒

ということで、KCのオンメモリDBを使えば、時間効率が多少落ちる代わりに、メモリ使用量を半減させられます。ファイルハッシュDBやファイルツリーは上記のテストではデフォルトの設定ですが、チューニング次第でメモリ使用量をさらに減らすこともできます。例えばファイルハッシュDBで 'casket.kch#msiz=0' とすればメモリ使用量は3.5MBまで減らせますし、ファイルツリーDBで 'casket.kct#msiz=0#pccap=0' としても同じく3.5MBまで減らせます。

経過時間が、KCだといずれも標準ハッシュより大きく劣っていますね。KCのコア自体は100万レコード格納を1秒未満で終わらせる能力があるので、多くの時間をPerl層で食ってしまっているようです。その要因としてはバインディングのXSUB関数を直接呼ぶのでなくPerlコードを一回噛ませてしまっていることと、さらに関数呼び出しの際にスカラのコピーが行われていることが考えられます。おそらく、pm層を省けばあと1秒くらい縮められ、インターフェイスをリファレンス渡しに変更すればさらに1秒以上は縮められると思います。でもそれらのメリットよりはデメリットの方が大きいのでおそらくやらないでしょう。

JavaとPython

KCはどちらかと言えばサーバサイドのさらにバックエンド寄りのユースケースを第一目的として作っているので、その層でC++と並んでよく使われるJavaのバインディングもサポートしました。PythonやRubyやPerlは処理系自体の並列性がないのでKCの並列性能を生かしにくいのですが、JavaVMの並列性はかなり良好なので、C++以外でKCを使うとしたらまずJavaをオススメします。

Google App Engineに採用されるなどで日本でも人気の出てきたPythonのバインディングもサポートしました。個人的にはPythonのプログラミング経験がほぼゼロだったのですが、とりあえずC用のAPI文書だけを読んでPythonバインディングを実装することができました。対象の言語を書いたことがなくてもバインディングは書けるというのは本当です。PythonバインディングではRubyバインディングと同様に「並列モード」を用意してあるので、KCコードの実行時に処理系のロックを外して並列処理を行うことができます(ただしPython処理系に比べてKCが高速すぎるので現状では意味はないです)。なお、現状ではPython3のみのサポートとなっていますが、Python2用のバインディングもいずれは書く予定です。

まとめ

Kyoto Cabinetの正式バージョンたる1.0がリリースされました。計画されていた全機能を実装し、コマンドラインユーティリティやテストツールも付属しています。各種言語バインディングも提供されているので、ぜひ試してみてください。

当初の計画ではLuaバインディングも作る予定だったのですが、ちょっと延期します。テーブルDBやKyoto Tyrantの方が需要がありそうなのでそちらの検討をする所存です。