先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。

なぜdynamic hashingを使わないか

Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレードオフを調整する必要があるということです。

それに対してdynamic hashingは、バケット数を動的かつインクリメンタルに調整できる手法で、NDBM、SDBM、GDBM、BDBでそれぞれ変種が使われています。関連する手法は数多く提案されているのですが、例えば最も典型的なlinear hashingという手法は、バケット配列の使用率がある閾値を越えた段階で、別の領域（典型的にはファイルの末尾）にバケット配列を追加するというものです。元来のバケット配列の要素からリンクされていたレコード群は、ポインタを進めながら少しずつ新しいバケットとの割り当てをやりなおしていって、それが終わった時に元来のバケットと新しいバケットを結合することになります。

兄弟達がdynamic hashingを頑張っているにもかかわらず、QDBMやTCはなぜ古めかしいstatic hashingを使い続け、チェーンを二分探索木にしたくらいで誤魔化しているのでしょう。率直にいえば、面倒く…、いやいや、実装が簡潔になり、高速に動作するからです。結局のところ、dynamic hashingを使ったとしても、（まじめなユースケースでは）最適な性能を出すためには初期値のバケット数を適切に設定することになるし（例えばBDBのset_h_nelem）、初期値を算定する際の予測の誤りは更新性能の劣化となってユーザを悩ませることになります。ということで、どうせレコード数を予測しなきゃならないなら、簡潔で高速な実装の方がいいと判断したものです。

といいつつ何で二分探索木を併用しているのかといえば、レコードあたりたった5バイトのオーバーヘッドで手軽に O(log n) を保証できるからです（木が偏らないための工夫もしてあります）。5バイトが大きいか小さいかはユースケースによるわけですが、B+木や転置インデックスなどの上位構造の基盤としてハッシュデータベースを用いることを想定しているTCの場合、5バイトはかなり小さいと言えるでしょう。また、二分探索木には、バケット容量が十分な場合にも発生しうる衝突のコストを下げるという利点もあります。

なぜページ管理をしないのか

たまにメーリングリストに投げられたり直接メールで箴言されることとして、なぜページ管理をしないのかというのがあります。QDBMやTCではレコードが直接ファイルに書かれてその位置はバケット配列の要素にそのまま記録されますが、NDBM、SDBM、GDBM、BDBでは複数のレコードを格納した「ページ」がファイルに書かれ、バケット配列の要素もページの位置を指し示すように記録されます。レコード毎ではなくページ毎にデータを読み書きするとreadやwriteといった重いシステムコールを呼ぶ回数が減らせるというわけです。ページのサイズをファイルシステムのブロックサイズに合わせるとI/Oの効率が最適化されるのも利点です。

では、QDBMやTCではなぜレコード単位でI/Oを行うのでしょうか。例によって実装を簡潔にして高速化したいという理由もありますが、空間効率を上げたいというのが最大の理由です。各ページに該当するレコードのサイズの合計とページサイズが必ずしも近いとは限らないので、ページサイズが大きすぎると馬鹿にならない無駄が発生してしまいます。逆に、ページサイズを小さくしすぎると、I/Oの効率が悪くなるとともに、ページサイズより大きいレコードがあった場合のワークアラウンドに伴うオーバーヘッドが馬鹿にならなくなります（BDBのset_pagesizeが参考になります）。レコード数の予測ですら面倒くさいのに、ましてや1ページに入るレコードの数やその合計サイズを予測するのなんて勘弁ですよね？

なお、TCが持つアラインメント機能は、ファイルシステムのブロックサイズに近い単位でI/Oを最適化する点でページ管理に近いと言えるかもしれません。ただし、TCのアラインメントは個々のレコードの典型的なサイズを予測すればよいので、ページサイズの設定よりは気楽に行えるはずです。また、複数のレコードをまとめて管理しないことの利点として、ページ内での位置を記録するための空間と時間のオーバーヘッドが節約できるということも挙げられます。B+木や転置インデックスなどの上位層でその層での論理的なレコードをまとめる処理がやられていることを考えると、ハッシュデータベースの層でのページ管理は二度手間とも考えられます。

非同期更新モード

ページ管理をすればreadやwriteの回数を減らして効率化できるということは既に述べましたが、TCでも複数のレコードを一括して書き込むモードがあります。putの対象になったレコードをディスク上でのフォーマットに合わせて直列化して、そのデータをメインメモリ上のバッファに連結していき、バッファのサイズが閾値を越えた時点で一気に書き込みます。writeの回数が抑えられるので高速化する一方で、更新がすぐにファイルに反映されない点で非同期であるというわけです。

バッファ上で直列化されたデータは変更しにくい（不可能ではないが、コストが大きすぎる）ので、ハッシュ値が衝突した際のセパレートチェーンがバッファ上のレコードを通る場合は、バッファがファイルに書き込まれないと新規のレコードを追加できないことになります。そこで、そのようなレコードは遅延用のサブバッファに格納していき、メインのバッファが書き込まれた後に追加することにします。

非同期更新モードがあるのに非同期検索モードはないわけですが、それは仕方ないのです。新規に追加されるレコード群はファイルの末尾に一括して書き込む余地があるのですが、既存のレコードの探索はその対象がファイル全体に散らばってしまうので、まとめてreadすることはできないし、ブロック毎にreadしてキャッシュしておくのもヒット率が低すぎて現実的ではありません（むしろレコード毎のキャッシュの方が効率的）。この観点からも、ハッシュデータベースにページ管理機能をつけるのは避けたくなりますよね。

なお、非同期モードというとLinux 2.6からサポートされたAIO（Asynchronous I/O）を想像されるかもしれませんが、それとは全く関係ありません。AIOはレプリケーションや更新ログの保存にかかる処理を並列化するのには便利ですが、データベースの通常運用で使うにはちょっと面倒すぎました。

フリーブロックプール

削除されたり移動されたりしたレコードの領域はフリーブロックとして再利用されると以前の記事で述べましたが、その管理方法にも結構な工夫が求められます。フリーブロックは位置（ファイル上の先頭からのオフセット）とサイズの構造体ですが、それを管理するフリーブロックプールに求められる機能は以下のものです。

• 新しいフリーブロックを追加する
• これから格納するレコードのサイズより大きい、最適なサイズのフリーブロックを探索する
• データベースファイルが閉じた際に自身を直列化してファイルに記録する
• データベースファイルが開かれた際に自身をファイルから読み出して復元する

上の二つから検討してみましょう。フリーブロックを追加する操作は自明ですが、最適なサイズを割り当てる操作における「最適」とはどんな基準なのでしょうか。勘のよい人は気づいたと思いますが、フリーブロックの割り当てに対する要求はC言語のメモリマネージャが提供するmallocと全く同じものです。フリーブロックの追加がfreeで、追加されるレコードに割り当てる領域を取得するのがmallocに相当します。そこでメモリ管理の手法を参考にして考えます。領域を割り当てる戦略の主なものとしては以下の5つがあります（出典：Tanenbaum先生のMinix本）。なお、フリーブロックプールを探索しても適当なサイズの領域がなかった場合は、隣接したフリーブロックを連結してより大きな領域をつくり出そうとし、それでもダメならファイルのサイズを増やして新しい領域を作ることになります。

• ファーストフィット：先頭から全体を逐次探索して、指定サイズより大きくて最初に見付かったものを選ぶ。
• ネクストフィット：さっき探索を終了した場所から全体を逐次探索して、指定サイズより大きくて最初に見付かったものを選ぶ。
• ベストフィット：先頭から全体を逐次探索して、指定サイズより大きくて最も小さいものを選ぶ。
• ワーストフィット：先頭から全体を逐次探索して、最も大きいものを選ぶ。
• クイックフィット：よく使われるサイズ毎に分けたリストに対して探索を行う。

ファーストフィットやネクストフィットは探索がやや高速になる反面、実際に使われるサイズよりもかなり大きいフリーブロックを割り当てて無駄が生じる可能性が高くなります。ベストフィットは無駄が生じる可能性は低いですが、探索に時間がかかります。さて、ワーストフィットは無駄が多くてしかも遅いやんけと思ったアナタ、私と同類ですね。でもそういうわけではなくて、余った領域をフリーブロックプールに戻すことでベストフィットよりも無駄がなくなるというカラクリなのです。ベストフィットでも余った領域を戻せばいいわけですが、そうすると断片化されて小さすぎる領域ばかりがフリーブロックに溜るのでよろしくないのです。そして最後のクイックフィットは、探索は速いし無駄も少ないのですが、リストが分けられているおかげて隣接したフリーブロックをひとつに連結する操作が遅くなるという弱点があります。要するにどれも一長一短ということです。

TCではフリーブロックプールは配列で実装されています。新しいフリーブロックは配列の末尾に加え、割り当てて削除されたフリーブロックの要素には末尾の要素を補填します。その上で、割り当てのアルゴリズムには以下のような折衷案を採用しました。

• 基本的にはファーストフィットを用いる。
• たまに、フリーブロックを小さい順でソートする。そうするとファーストフィットだけどベストフィット的な具合に近づく。
• 割り当てたフリーブロックが要求されたサイズの2倍以上ならば、余った領域をフリーブロックプールに戻す。
• 要求されたサイズの割り当てに失敗する頻度が増えたら、隣接したフリーブロックを連結する。

フリーブロックプールの時間効率や空間効率はどのようなレコードをどのような順番で格納するかに依存するので、おそらく決定版は存在しないでしょう。したがって、とりあえず私が想定するユースケースであるB+木や転置インデックスのストレージとして良好な結果が出るように調整しています。すなわち、少数の巨大なレコードと多数の小さいレコードが混在し、各レコードは高い頻度と偏った確率でサイズが拡張していくという状況で、時間効率が目に見えて落ちない範囲で空間効率を最大化すべく設計しました。

レコード圧縮

比較的冗長なデータ（特にテキスト）をデータベースに格納することも多いと思います。例えばmixiでは、日記IDをキーとして日記の本文を値とするレコードを格納するような使いかたをするでしょうが、日記の本文のテキストはかなりパターン（記号）の出現頻度に偏りがある冗長なデータです。そのようなデータは圧縮してからデータベースに格納すると空間効率が劇的に改善します。アプリケーション側の責任で圧縮と復元をする運用でももちろんOKなのですが、putする直前に圧縮してgetした直後に復元するのは決まりきっているので、ライブラリ側でサポートしてもバチは当たらないでしょう。

ということで、TCでは二種類の圧縮方式をサポートしています。ひとつはDeflateで、これはzlibを利用して実現しており、LZ77という圧縮アルゴリズムを使ってデータサイズを小さくします。Deflateはテキストでも画像などのバイナリでも大抵の非圧縮データに対してかなりよい圧縮率を実現し、それでいて高速に動作します。

もうひとつはTCBS（Tokyo Cabinet Block Sorting）で、bzip2を参考に私が実装したものです。TCSBは圧縮率も速度もzlibやbzip2に負け負けなのですが、256バイトやそれ未満といった小さいデータに対して効率的であるという特徴があります。BWT→MTFという前処理をしてから圧縮するところはbzip2と同じですが、圧縮にHuffman符号でなくElias Gamma符号を使って辞書分のオーバーヘッドを節約しています。この話をBrianさんにしたら、レコード間で共通した辞書を別の領域に保存すればいいはずで、MySQLではその機能があるとのアドバイスをいただいたのですが、それは今後の研究課題にしておきます。そういえば、Apacheのログを検索可能な状態のままいかに圧縮して保持するかみたいな課題がありますが、圧縮データをDBMに入れて頑張るってのもアリかもですね。

レコード圧縮をわざわざライブラリ内で実現しているもうひとつの理由は、B+木などの上位層における「ページ」をレコードとして保存する際に、冗長なデータを圧縮してからファイルに記録する方が明らかに有利だからです。一般的にデータ圧縮は時間効率を犠牲にして空間効率を稼ぐという位置付けですが、ファイルI/OやネットワークI/Oを伴う場合は、空間効率を高めることでI/Oにかかる時間も減らせるので時間効率もよくなるという、ちょっと不思議で嬉しい事態になります。

壊れにくくする

QDBMにおいては、データベースを開いているアプリケーションが異常終了した場合、もしくはデータベースを適切に閉じずに終了した場合は、データベースが壊れるようにしていました。それらは明白なバグであり、アプリケーションの作者やそれを使うことを選択したユーザに何らかの意識的な対処を求めることが適切であると考えたからです。データベースを修復するユーティリティがQDBMに付属しているのでそれを使って修復作業を行うことはできるのですが、そのコストとリスクは因果応報として受け入れてもらいます。

しかし、上記のような理想主義と「上から目線」では現実の問題に対処できないことを近ごろ感じはじめました。マナーを守らない/守れないユーザやユースケースも結構な割合で存在するのが現実なのです。したがって、TCは、マナーを守らないアプリケーションやそのユーザにも宥和する戦略に転換しました。すなわち、たとえ重要なデータベースを開いているにもかかわらず適切なシグナルハンドラを書いていないアプリケーションがあっても、そしてたとえそのようなアプリケーションをSIGTERMやSIGINTで殺すユーザがいても、あるいはアプリケーションがSIGSEGVを発生させて自滅しても、データベースがなかなか壊れないようにしました。だって、いま挙げたプレーヤは全て私ですから。

前回の記事で挙げた並列性の議論を思い出していただきたいのですが、データベースファイルが壊れる事態は、クリティカルセクション内で処理が停止した場合に発生します。つまり、単一のクリティカルセクション内でファイルの書き込みを複数回にわたって行う際に、最初の書き込みは成功したが最後またはそれ以前の書き込みが失敗した場合には、データベースファイルの状態に不整合が起きることになります。例を挙げてみましょう。

• putで、レコードの実体をwriteしてファイルサイズが増えたのに、そのメタデータをwrite（実際はmmap領域の更新）していない。
• putやoutで、レコードの実体やフリーブロックをwriteしてレコード数が増減したのに、そのメタデータをwrite（実際はmmap領域の更新）していない。
• putやoutで、レコードの実体やフリーブロックをwriteしてバケット配列が変更されたのに、その要素をwrite（実際はmmap領域の更新）していない。
• putやoutで、レコードの実体やフリーブロックをwriteしてチェーンが変更されたのに、その親のヘッダをwriteしていない。
• putやoutで、フリーブロックプールが更新されているのに、それを書き戻していない。
• putやoutで、そもそもwriteの途中で失敗した。

ファイルサイズのメタデータが狂う件については、statで問い合わせて修復すればよいでしょう。レコード数のメタデータが狂う件については、壊れていることは確かですが、格納したレコードの情報が失われているわけではないから許容することにしましょう（最適化の際に再計算すれば修復可能）。バケット配列が更新されない件については、そのレコードのputやoutは無かったことにすればその他の整合性は確保できるでしょう。チェーンの件も同様です。フリーブロックプールの書き戻しができていない件については、フリーブロックプールをなかったことにすることで対処できるでしょう（再利用できないフリーブロックが出るが、まあ気にしない）。最後に挙げた、writeの途中で失敗したケースは判断が難しいのですが、レコード実体やフリーブロックのwriteで起こることがほとんどでしょうから、その場合はバケット配列やチェーンの更新も行われないので、更新が無かったことにすれば整合性が確保できるでしょう。

重要なのは、レコードのエントリポイント（そのレコードに辿り着くポインタ）の更新を、レコードの実体を更新した後に行うということです。エントリポイントの更新は1回のwriteで済むので（バケット配列直下の場合は0回）、途中で失敗する確率は低いし、エントリポイントを更新する前に落ちても不正状態になるのはそのレコードだけで済むからです。もちろん本気で耐障害性を考えるなら更新ログを記録しないといけませんけどね。

ということで、現状では、データベースを閉じないでプログラムが落ちたとしても、大抵の場合でデータベースファイルは壊れないようになっています（非同期更新モードの場合はその限りではありません）。とはいえ、やはり開いたデータベースファイルをきちんと閉じているかどうかを確認して安心したいでしょうから、データベースファイルにフラグを設けています。データベースファイルが書き込みモードで開かれた時にそのフラグは立てられ、正常に閉じられた時にそのフラグは降ろされます。つまり開いたままプロセスが死ぬとフラグが立ったままになるので、次に開いた時にそのフラグを確かめることで意識的な対処が可能になるわけです。

超まとめ

Tokyo Cabinetは時間効率と空間効率がそれなりによくて使いやすいDBMです。CDBには負けるけどそれに近いくらい速く小さく頑健で、そして更新可能なDBMです。今まで述べた工夫の他にも、細かいトリックをたくさん入れて効率を稼いでいます。文章で説明されてもおそらくわかりにくいでしょうから、ご興味のある方はぜひソースをご覧ください（結論）。コアの部分は3000行に満たないくらい小さいので、比較的理解しやすいと思います。何かアドバイスがあればコッソリ教えてくれると嬉しいです。

今後はB+木などの上位層の実装と、更新ログやトランザクションなどの機能強化を行っていきたいと思います。なので、いずれまた連載を再開するかもしれませんし、しないかもしれません。それでは、Happy DBM Hacking!!

秘密鍵やプライベートな情報などを秘匿するためにパスワードでデータを暗号化・復号したい場合があります。このとき、暗号化と復号するアプリケーションが同じであれば簡単ですが、例えばCで暗号化してJava、Perl、Rubyで復号するといった風に異なるプラットフォームで暗号データをやりとりする場合には、いくつか気 をつけなければいけないポイントがあります。

OpenSSLによる暗号化

OpenSSLはWebサーバのSSL/TLSサポートに利用されますが、その他にも付属しているopensslコマンドから基本的な暗号アルゴリズムを利用できます。次のような簡単なコマンドで、パスワードを使ってデータを暗号化したり復号したりすることができます:

$ echo 'Hello World!' | openssl enc -e -aes-128-cbc  > cipher.txt
enter aes-128-cbc encryption password: ********

この例では、文字列 “Hello World!”を暗号化してファイル cipher.txt に出力しています。また、暗号化に際して次のパラメータを使用しました:

• 暗号アルゴリズムはAES
• 秘密鍵の長さは128bit
• 暗号利用モードはCBCモード
• 秘密鍵はパスワードをもとにopensslコマンドが自動生成

ファイルchiper.txtを復号してメッセージを取り出す場合は:

$ openssl enc -d -aes-128-cbc < cipher.txt
enter aes-128-cbc decryption password:********
Hello World!

あたりまえですが、暗号化したときに使ったパスワードとパラメータは、復号するときにも同じものを使用します。

ちなみに、この場合のopensslコマンドは次のような書式で暗号文を出力します。

'Salted__' + Salt(8 byte) + CipherText(16 x n byte)

ヘッダとして文字列 “Salted__”、続いてランダムに生成された8バイトのsalt、最後に暗号文本体が続きます。

別のプラットフォームで復号する

それでは、暗号化したデータをPerl, Ruby, Javaで復号する例を順番に見てみます。

Perlで復号する

Perlにはopensslコマンドと暗号文をやりとりできるCrypt::CBCモジュールがあります。こんな感じ:

#!/usr/bin/perl

use strict;
use Crypt::CBC 2.13;

my $pbe = Crypt::CBC->new(
     -key     => 'my secret password',
     -cipher  => 'Crypt::Rijndael',
     -keysize => 128/8,
#    -salt    => 1,          # use random salt
#    -header  => 'salt',     # use OpenSSL-compatible salted header
#    -padding => 'standard', # use PKCS#5 PBES1|2 padding
);
my $cipher_text = scalar <>;
my $plain_text = $pbe->decrypt($cipher_text);
print $plain_text;

Crypt::CBCは-keyで与えられたパスワードを、暗号アルゴリズムが要求する形式の秘密鍵に変換して使用します。

Rubyで復号する

RubyにはOpenSSLのcryptoライブラリをwrapしたOpenSSL::Cipherクラスがあります。PerlのCrypt::CBCと異なり、明示的にpkcs5_keyivgenメソッドでパスワードを秘密鍵に変換して使用します。

#!/usr/bin/ruby

require 'openssl'
include OpenSSL::Cipher

# 'Salted__' | SALT(0..7) | CIPHER-TEXT
@cipher_text = gets.unpack("a8a8a*")
pbes = Cipher.new("aes-128-cbc")
pbes.pkcs5_keyivgen(
     "my secret password",
     @cipher_text[1],                 # salt
     1                                # iteration count
#    ,OpenSSL::Digest::MD5.new()      # Hash function
)
pbes.decrypt()
plain_text = pbes.update(@cipher_text[2]) + pbes.final
print plain_text

Javaで復号する

Javaの場合サードパーティの暗号化サービスプロバイダを導入せずに、Sun JDK付属の暗号化サービスプロバイダのみを使用すると、次のようになります:

import javax.crypto.*;
import javax.crypto.spec.*;
import java.io.*;
import java.security.*;

public class DecryptOpensslPBES {
    private static boolean openSSLBytesToKey(Cipher type, MessageDigest md,
                                             byte[] salt, char[] password,
                                             int ic, byte[] key, byte[] iv) {
        int keyLen =  key.length;
        int ivLen  =  type.getBlockSize();
        byte[] dk = new byte[keyLen+ivLen];

        try {
            byte[] pw = new String(password).getBytes("UTF-8");
            int pos = 0;
            int hashLen = md.getDigestLength();

            while (pos < dk.length) {
                md.update(dk, 0, pos);
                md.update(pw);
                md.update(salt);
                md.digest(dk, pos, hashLen);
                for (int i = 1; i < ic; i++) {
                    md.update(dk);
                    md.digest(dk, pos, hashLen);
                }
                pos += hashLen;
            }
        }
        catch (DigestException e) {
            return false;
        }
        catch (UnsupportedEncodingException e) {
            return false;
        };

        for (int i = 0; i < keyLen; i++)
            key[i] = dk[i];
        for (int i = 0; i < ivLen; i++)
            iv[i] = dk[keyLen + i];
        return true;
    }

    public static void main(String[] args) throws Exception {
        byte header[]     = new byte[8];
        byte salt[]       = new byte[8];
        byte cipherText[] = new byte[8142];
        int  cipherLength;
        PBEKeySpec spec;
        SecretKeySpec key;
        IvParameterSpec param;
        byte rawKey[] = new byte[16];
        byte iv[]     = new byte[16];
        byte plain_text[];

        /* 'Salted__' | SALT(0..7) | CIPHER-TEXT */
        if (System.in.read(header, 0, header.length) <= 0)
            return;
        if (System.in.read(salt, 0, salt.length) <= 0)
            return;
        if ((cipherLength = System.in.read(cipherText,
                                           0, cipherText.length)) <= 0)
        {
            return;
        }

        Cipher cbc = Cipher.getInstance("AES/CBC/PKCS5Padding");
        if (!openSSLBytesToKey(cbc, MessageDigest.getInstance("MD5"),
                               salt, "my secret password".toCharArray(),
                               1, rawKey, iv))
        {
            System.out.println("Cannot execute PBKDF");
            return;
        }
        key = new SecretKeySpec(rawKey, "AES");
        param = new IvParameterSpec(iv);
        cbc.init(Cipher.DECRYPT_MODE, key, param);
        plain_text = cbc.doFinal(cipherText, 0, cipherLength);

        System.out.print(new String(plain_text));
    }
}

「Sun JDKにもパスワードベース暗号のPBE系エンジンがバンドルされているのになぜ使わないのか？」と疑問がわいてきます。残念ながらSun JDK付属の暗号化サービスプロバイダは、AESなど128bitブロック暗号を使う場合、opensslコマンドと互換性のある鍵変換処理をもつPBE系エンジンが用意されていません。そのために次のような手続きを自前で記述しています:

1. パスワードを鍵に変換する処理を自前で実装する
2. 鍵の前半128bitを秘密鍵に使い
3. 鍵の後半128bitをCBCモードのInitialization Vectorに使い暗号化する

ただ、私はJavaを使っていないので、根本的な間違いやもっとシンプルな方法があれば教えてください。(それを言ったらRubyもですね…)

鍵導出関数

ここまで漠然と「パスワードを鍵に変換する」と書いてきたので、具体的にどう変換するのか補足します。

一般的なブロック暗号の秘密鍵は、アルゴリズムによって128bitや256bitなどと長さが決まっています。通常パスワードは長さが定まってない文字列なので、秘密鍵として使うには一定の長さに変換したりする処理が必要です。この変換処理を鍵導出関数(KDF – Key Derivation Function)と言います。

鍵導出関数には様々な方式が考えられますが、一般的にはPKCS #5で定めるPBKDF1 (Password-Based Key Derivation Function 1)やPBKDF2が広く利用されているようです。

これらの鍵導出関数は、暗号化用の鍵を得るためのパラメータとして

• パスワード
• ランダムに生成したsalt
• 変換処理のくり返し回数(iteration count)
• 出力する鍵の長さ

をとります。PBKDF1とPBKDF2の概要をそれぞれ表にまとめました:

使用するハッシュ関数や疑似乱数生成器が異なっていたり、変換処理のくり返し回数が異なったりすると、同じパスワードとsaltを入力しても同じ鍵を得られず正しく復号できません。そのため使用する鍵導出関数の仕様とそのパラメータも、暗号の相互運用のためには重要な情報と言えます。

さらにPKCS #5では鍵導出関数の他にも、

• 暗号化と復号の手続き(Encryption Scheme)を定めるPBES1, PBES2
• メッセージ認証コード計算の手続き(Message Authentication Scheme)を定めるPBMAC1

が定義されています。このうちPBES1はPBKDF1とペアで使用され、Sun JDK付属のPBEもopensslコマンドもPBES1の手続きに沿って実装されています。PBES1は

1. PBKDF1で128bitの鍵を導出する
2. 導出した鍵の前半64bitを秘密鍵に使用し
3. 導出した鍵の後半64bitをCBCモードのInitialization Vectorに使用して
4. CBCモードで暗号化する

という手続きを実行します。ただしPBES1は暗号アルゴリズムとしてDESかRC2のみを使用し、秘密鍵は56〜64bitの秘密鍵を使うという仕様なので、AESなど鍵長が128bit以上でブロック長も128bitの暗号アルゴリズムには利用できません。
このためopensslコマンドでは、大枠ではPBES1およびPBKDF1と互換性をもたせつつ、AESなどを使用する場合はPBKDF1をベースに最大384bitの鍵を出力できるよう独自の拡張を行い、

1. PBKDF1を拡張した鍵導出関数で鍵を導出する
2. 導出した鍵の前半128〜256bitを秘密鍵に使用し
3. 導出した鍵の後半128bitをCBCモードのInitialization Vectorに使用して
4. CBCモードで暗号化する

といった感じに処理を実行しています。つまりこのOpenSSLの独自拡張に対応させるために、Sun JDKのみを使う例で鍵導出関数を別途実装する必要が生じたわけです。

まとめ

パスワードベースで暗号文をやり取りする場合は、

1. 使用する暗号アルゴリズム
2. 暗号利用モード
3. パディングルールなどのパラメータ
4. 鍵の導出手段

の情報を共有・一致させる必要があり、特に鍵の導出手段はライブラリに隠れて詳細が解らない場合があったりでなにげに注意が必要です。アプリケーションによっては暗号文にこれらの情報を埋め込む場合もありますが、なんにせよどのように共有するか把握する必要があります。

ちなみにopensslコマンドは鍵導出関数に繰り返し回数”1″を指定しているので、辞書攻撃や総当たり攻撃に対して比較的不利な鍵が導出されているのは秘密です。いちおう64bitのsaltがあるので、攻撃1回あたりのコストは2の64乗倍に増加しますが、世間的には繰り返し回数を1,000〜5,000回以上にするのがお勧めみたいです。

あと、ここから重要なオチなんですが、PBKDF1はけっこう前から新規開発するアプリケーションでの採用を推奨されていません。現在は代わりにPBKDF2の採用が推奨されています。これに限らず暗号のアプリケーションまわりの話題は陳腐化が激しいので、定期的に棚卸ししておくと夢見が良さそうですね。

涼しさに夏の終わりを感じてなんだか寂しくなるも、新しいオフィスから見えるパノラマの空の高さに癒されているmikioです。秋は気が変わりやすいこともあり、今回は唐突にDBMの並列性についての考察を記してみます。

並列性って何?

最近はマルチコアのプロセッサが当り前になってきて、そのパワーを100%引き出すために、並列性をできるだけ高めることが求められるようになってきました。それについて考える前に、まずは用語の整理をしておきましょうか。

• 並行性 : 二つ以上のタスクを一緒に進めること。必ずしも同時に処理を行うとは限らず、Aを少しやってからBを少しやって、それからまたAを少しやって、またBをやって…といった、いわゆるタイムシェアリングで実現してもよい雰囲気。
• 並列性 : 二つ以上のタスクを同時に進めること。タスクを複数のマシンに割り当てたり、複数のCPUに割り当てたり、CPU内の複数のコアに割り当てたりして、とにかくマジで同時に処理をやっていく感じ。
• マルチプロセス : OSがメモリ保護や実行権限を割り当てる単位であるプロセスを複数使ってタスクを進める趣向。
• マルチスレッド : 単一のプロセス内で作業メモリを共有した複数のスレッドを使ってタスクを進めるニュアンス。
• スレッドセーフ: マルチスレッドのプログラムから呼び出す場合にそれほど気をつかわなくていいような関数やライブラリの売り文句。
• リエントラント : スレッドセーフを名乗る前提として、グローバル変数やstaticな内部変数やそれらに依存する関数を使わないようにした関数の気取った言い方。
• アトミック : あるスレッド（またはプロセス。以下同）が変更中のデータを他のスレッドが参照してしまうと不完全な状態に基づいて処理を進めてしまうおそれがあるので、そういう不完全な参照がないように一連の変更を不可分にやること。つまり変更中の状態があたかも存在しないように見せる努力。

これ以上詳しく説明すると識者の方々から厳しめのツッコミが来そうなのでほどほどにしますが、とにかく、ユーザが定義する様々なタスクの中でのDBMに対する操作である「格納」「削除」「取得」などの並列性を上げたいのです。

マルチプロセスでの並列性向上策としては、ファイルロックを使っています。データベースファイルを開く際に読み込み専用の「リーダ」と読み書き両用の「ライタ」を指定できるようにして、リーダ同士は複数のプロセスが同時にデータベースファイルを開けるが、ライタとしてデータベースファイルを開いたプロセスが一つでもある場合はそのプロセスがデータベースファイルを閉じるまで他のプロセスは同時に接続できないようにします。接続できないといっても、エラーになるわけではなく、接続できるようになるまで待たされる（ブロックする）というのがポイントです。各プロセスがDBMに対する一連の操作が終わった時に行儀よくファイルを閉じるようにすれば、少なくとも読み込みは並列に処理できますし、書き込みと読み込みは並行に処理できます。

ただし、細かい操作の都度データベースファイルを開いたり閉じたりするのはオーバーヘッドが大きいので、個人のユースケースではそれでも十分なことが多いかもしれませんが、mixiのような大規模なサイトではその戦略は現実的ではありません。そこで、マルチスレッドを重視することになります。データベースに接続したままのひとつのプロセスがいわゆるサーバの役割を果たし、アプリケーションから渡されるクエリを並列に処理するのです。今、サーバの役割といいましたが、実際にクライアント/サーバ方式でDBMサーバをバックエンドに持つシステムを設計することもできますし、アプリケーションのプロセス自体にDBMを組み込んだ場合でも、DBMオブジェクトにあたかも並列処理能力のあるサーバのように振る舞わせるというのが理想でしょう。

マルチスレッドで使うライブラリは、もちろんスレッドセーフでないといけません。一言にスレッドセーフといっても解釈が曖昧ではありますが、ここでは、APIの関数がリエントラントである上に、それらに渡すパラメータであるDBMオブジェクトの状態変更がアトミックであり、すなわちAPIの関数をアプリケーション側で排他制御することなしに呼び出せるということをゴールに設定します。前回述べたように、グローバル変数に依存しないAPIを設計し実装したことでリエントラントを達成するのは比較的容易だったTCですが、DBMオブジェクトのアトミック性をいかに確保するかについてこれから考えていくことにしましょう。

クリティカルセクション

DBMオブジェクトはもちろん状態を持つものですから、スレッドセーフにするには、オブジェクトの更新はアトミックに行わねばなりません。更新をアトミックにするには、他のスレッドが同時に更新処理をできないように、更新する前にロックを獲得し、更新した後にそのロックを解放するという排他制御を行うことになります。このように排他制御した区間をクリティカルセクションと呼びます。UNIX上では、ロックはmutexというオブジェクトを使うことで実現できます。

最も簡単にアトミック性を確保するには、全てのAPI関数をクリティカルセクションに入れるというのが考えられます。つまり、関数の最初と最後でオブジェクトに対してロックをかけるのです。それはこんな風な実装になります。

static bool tchdblockobj(TCHDB *hdb){
  return pthread_mutex_lock(&hdb->mutex) == 0;
}  

static bool tchdbunlockobj(TCHDB *hdb){
  return pthread_mutex_unlock(&hdb->mutex) == 0;
}  

bool tchdbput(TCHDB *hdb, const char *kbuf, int ksiz,
    const char *vbuf, int vsiz){
  if(!tchdblockobj(hdb)) return false;   // ロックをかける
  ... // ここで関数の処理を行う
  if(!tchdbunlockobj(hdb)) return false; // ロックを解放する
}  

char *tchdbget(TCHDB *hdb, const char *kbuf, int ksiz, int *sp){
  if(!tchdblockobj(hdb)) return NULL;    // ロックをかける
  ... // ここで関数の処理を行う
  if(!tchdbunlockobj(hdb)) return NULL;  // ロックを解放する
}

putは更新処理を伴うのでクリティカルセクションを張るのはもちろんですが、getも更新中の状態にアクセスしてはならないので、putなどが同時に動いていないことを保証するためにgetにもクリティカルセクションを張るのがポイントです。なお、ロックが取得できないとか解放できないとかいう事態は稀で、ほとんどバグによるものですが、いちおうエラーチェックも忘れてはいけません。

上記のようにlockとunlockを書きまくればスレッドセーフは実現できるわけで、QDBMはそうして「スレッドセーフです」と言い張っているわけですが、これは並列性という意味ではダメダメなアプローチと言わざるを得ません。同時に1スレッドしかDBMの具体的な処理をできないようにしているわけで、複数のスレッドを並列実行できる最近のプロセッサのパワーを使いきることができないからです。

ああ、面倒くさい。しかし、せっかく64ビット対応してディスクの大容量化というトレンドについていけるようになったのだから、マルチコアのトレンドにもついていかないといけません。そのためには、複数のスレッドが真の意味で同時にputやgetを実行できるようにしないといけないのです。うぉー。やっぱ面倒くさい。

粒度を見極める

同時に読み書きするといけない状態のことをレースコンディションと呼びますが、実際にはDBMオブジェクト全体がレースコンディションを持つわけではありません。DBMオブジェクトの内部状態の要素をもっと細かく分類した上で、関係あるグループ毎に、それを参照するコードにクリティカルセクションを張っていくことにします。

内部状態の代表選手はバケット配列ですね。バケット配列の個々の要素はlong int型（またはlong long int型）の変数なので、プロセッサの単一の命令でアトミックに読み書きできそうです。また、個々の要素は相互に依存しないので、同時に読み書きしても問題なさそうです。したがって、バケット配列はレースコンディションの心配はないと判断し、その操作にはクリティカルセクションは設けないこととします。

次に、put/out/getがバケット配列の後に参照することになるセパレートチェーンはどうでしょうか。これはレースコンディションありまくりです。二分探索木の親子関係を操作するにあたって、「子供を移動させる」「親からのチェーンをつなぎ変える」という大きな処理が行われますが、それらは全てアトミックでないといけません。となると更新も探索も並列にはできないじゃないかと思うかもしれませんが、そうではありません。幸いなことにチェーンの依存関係は同じバケット要素から連なるレコード間でしか生じないので、バケット要素単位でロックをかければレースコンディションは回避できそうです。同じバケットのレコードを同時に操作する確率は低いでしょうから、バケット要素単位のロックなら並列性は十分と言えるでしょう。ただし、mutexオブジェクトを作るオーバーヘッドも馬鹿にならない（私の環境では各24バイト）ので、バケット数の分だけmutexオブジェクトを作るわけにはいきません。そこで、バケットのインデックスを256くらいで割った数でグループ化してmutexオブジェクトを割り当ててロックをかけることにしましょう。

バケットとチェーンの操作が並列に行えることで、put/out/getは同時に実行できるようになったでしょうか。いやいや、まだ他にもレースコンディションは潜んでいます。DBMオブジェクトが持つメタデータとしてレコード数やファイルサイズなどがありますが、それらに依存する処理はオブジェクト単位のロックをかける必要があります。フリーブロックプールも同様にオブジェクト単位のロックが必要です。ただ、それらの操作はディスクI/Oと関係なく一瞬で終わるので、遠慮なくロックかけてもそれほど問題ではないでしょう。

さらに忘れてならないのは、データベースファイルそれ自体がレースコンディションを持つということです。なぜなら、ファイルの読み書きを行う際の位置（オフセット）はファイルディスクリプタに関連づけられた内部状態としてOSが管理しているからです。すなわち、lseek/readおよびlseek/writeの組み合せはアトミックにしないといけません。

最も上層に操作単位の排他制御も必要となります。open/closeなどのデータベースそれ自体への操作は、put/get/outなどの終了を待ってから行わねばならないからです。

最後の課題は「エラーコード」です。エラーコードはDBMオブジェクトに問い合わせる形になっていますが、それだと他のスレッドのエラーを拾ってしまう可能性があるのでよろしくないです。これはTSD（thread specific data）にすることで回避するしかありません。つまりスレッド毎に変数のコピーを用意して、単一の変数にアクセスしているつもりで別々の領域を参照させるのです。

以上をまとめると、以下の種類のロックを用意して、多重にクリティカルセクションを張ることになります。

• メソッドロック : データベース操作に対するロック
• レコードロック : バケット要素をいくつかにグループ分けした単位のロック
• オブジェクトロック : オブジェクトそれ自体にかけるロック
• I/Oロック : ファイルのI/Oに伴うロック

デッドロック対策

妻は自分の髪を売った金で夫へのプレゼントとして時計のチェーンを買い、夫は自分の時計を売った金で妻へのプレゼントの櫛を買うという話がO.Henryの短篇にありますが、スレッドプログラミングで同様の行き違いが起きた場合は本当の悲劇になってしまいます。すなわち、スレッドAはスレッドBの持つロックの解放を待ち、スレッドBはスレッドAの持つロックの解放を待つことで、処理が永遠に停止してしまうという、いわゆるデッドロックの問題です。

デッドロックを防ぐには、クリティカルセクションを多重化したとしても再帰しないようにすることが重要です。ということで、putを題材にして、ロックの構造をXML的に疑似コードに入れるとこんな感じになります。

put(){
    <method_lock>
        check_db_is_open;
        <record_lock>
            scan_chains(){
                <io_lock>
                    lseek_read;
                </io_lock>
            }
            write_records(){
                <object_lock>
                    check_meta_data;
                        <io_lock>
                            lseek_write;
                        </io_lock>
                    update_meta_data;
                </object_lock>
            }
        </record_lock>
    </method_lock>
}

ここでとってもとっても重要なのは、「メソッドロック＞レコードロック＞オブジェクトロック＞I/Oロック」という関係を常に成立させ、それを逆転させないことです。ただし、scan_chainsの中でレコードロックの直下でI/Oロックをかけていますが、これはI/Oロックのクリティカルセクションは最下位なので自明にアトミックとみなせるからOKなのです。さらに、I/Oロックのクリティカルセクションがアトミックならばその直上位であるオブジェクトロックのクリティカルセクションもアトミックとみなせ、そうするとその直上位であるレコードロックのクリティカルセクションもアトミックとみなせ、最終的に最上位であるメソッドロックのクリティカルセクションもアトミックとみなせるというわけです。長げー。

リードライトロック

get/put/outの間でレコードロックをしないといけないのはわかりましたが、get同士であれば更新がないので排他制御をしなくてもいいような気がします。そのような場合には、リードライトロックが役に立ちます。これはmutexとほぼ同じ挙動をするのですが、ロックの際にリードロック（共有ロック）モードとライトロック（排他ロック）モードが選べるのが特徴です。そして、リードロックは他のスレッドのライトロックのみをブロックし、ライトロックはリードロックもライトロックもブロックします。マルチプロセスのところで説明したファイルロック機構と同じカラクリですね。ということで、レコードロックに層にて、getはリードロックをかけて、outとputはライトロックをかけるようにするとよいでしょう。

メソッドロックでもリードライトロックが活用されます。open/closeはライトロックで、put/out/getはリードロックです。メソッドロックが普通のmutexだったら全く並列性がないですもんね。

まとめ

DBMの並列性を「読み込みや書き込みを同時に行える能力」と定義して、特にマルチスレッド環境での並列性を引き出すための設計について述べました。レースコンディションをクリティカルセクションで包むためにロックを配置していくという考え方で設計を進めたものです。

ちなみにこの設計はまだ実装していません。ぶっちゃけ、TCは十分に高速なんで、メソッドロックをリードライトロックで運用するだけでも十分だと思うし、ロックをたくさん入れることによる性能劣化を考えるとメソッドロックのみにする誘惑にかられます。ロック絡みのバグって本当につぶしにくいから、複雑なロック機構を入れると保守性も下がるんですよね。うー。悩みます。皆さんどう思います？

次回はたぶん最終回で、TCのその他の工夫について言い残したことを消化します。

今日は米SNSのFacebookが提供している開発者向けのFacebook Platformに関して語ろうかと思います。もちろん、軽く使い方やサンプルコードなども紹介します。もともとは息抜きに遊び感覚で触ってみたのですが面白くて興奮気味になってしまいました。

そもそもFacebook Platformとは？

Facebook（以後、FB）の持つSNSならではの巨大ソーシャルグラフを利用した第三者のウェブアプリケーション開発を実現した基盤（プラットフォーム）の事です。このプラットフォームを使って開発されたアプリケーションを使っていないFBユーザはいないと言える程、熱い代物です。数多くの有名なウェブ系企業もオフィシャルFBアプリをリリースして参戦してたりしてます。

アプリケーションのスクリプトはFBのサーバでホストするのではなく、開発者側のサーバでホストします。アプリケーションに対するリクエストが生じた際、FBは開発者の指定したリモートのスクリプトを見に行く仕組みになっています。基本構成は簡素で良い感じですね。

使う前の準備

まず、FBが提供しているDeveloper Applicationを自分のFBアカウントにインストールします。次に提供されているClient API Libraryをダウンロードします。この記事を書いた時点で本家がサポートしている言語はPHPとJavaだけですが、非公式の他言語用クライエントライブラリもダウンロードページにて紹介されています。

PHP用のクライエントライブラリアーカイブをダウンロードしたと仮定して、アーカイブをPHPから呼び出せる場所に解凍してあげます。私の場合、アーカイブ内の”client”というディレクトリにしか興味がなかったので、そのディレクトリとファイル達だけを/var/www/html/includesの下に置きました。ちなみにfootprintsというディレクトリの中にはFBが提供しているデモアプリケーションのソースが入ってます。

最後にアプリケーションをDeveloper Applicationから登録してAPI KEYを入手します。この登録は完成したアプリを登録するのではなく、作る前に予め登録するというステップです。登録する課程で色々とフォームを記入する必要がありますが、恐らく悩みの種になるのはCallback URLかと思います。Callback URLにはアプリのスクリプトの場所を指定してあげます（例えば、http://貴方のドメイン/fb/my_fb_app/index.php等）。

アプリの登録が完了したら準備は整いました。

コードを書いてみよう

FB PlatformではFBML(Facebook Markup Language)とFQL(Facebook Query Language)という独自の言語があり、これらを使う事によってFBのデータベースから様々なデータをフェッチします。アプリを開発するには登録したアプリのAPI KEYとSECRET値が必要です。これはDeveloper ApplicationのMy Applicationsというリンクの先に表記されています。不慣れながらPHPでFBMLとFQLを使ったサンプルを書いてみました。

例えば自分の全ての友人の名前をPHPとFBMLでFBから引き出すとしましょう：

<?php
include_once('/includes/client/facebook.php'); 

$api_key = "foo"; //入手したAPI KEYを使う
$secret  = "hoge"; //入手したSECRET値を使う 

$facebook = new Facebook($api_key, $secret);
$facebook->require_frame();
$user = $facebook->require_login(); 

// FB APIで友人の配列をフェッチ
$friends = $facebook->api_client->friends_get();
foreach($friends as $friend) {
    // FBMLを出力する
    echo "<fb:name uid=\"$friend\"/><br/>";
}
?>

次にFQLで自分の所属しているグループ、グループ紹介文、グループ写真、最新ニュースを引くqueryを調合してFBに投げてみました：

<?php
$query = "
    SELECT name, description, pic, recent_news
    FROM group
    WHERE gid IN (
        SELECT gid FROM group_member WHERE uid = $user
    )
"; 

$result = $facebook->api_client->fql_query($query); 

foreach($result as $rec) {
    echo "<p>";
    echo "<img src=\"$rec[pic]\" /><br/>";
    echo "グループ名: $rec[name] <br/>";
    echo "紹介文: $rec[description] <br/>";
    echo "最近のニュース: $rec[recent_news] <br/>";
    echo "</p>";
}
?>

FQLのコードを展開するとこんな感じになりました：

てな感じで比較的楽にFBからデータを引き出す事が可能です。又、スクリプト自体は自分でホストするためMySQLなどのRDBMSやHyper Estraierなどの検索エンジンを使って複雑なものを作る事も可能です。正直な話、PHPはあまり得意でないので次にやる気が出たらDavid Romanoさんが書かれたPerl用のクライエントライブラリを使ってもうちょっと色々遊んでみようと思います。

思うにこれ、インフラが気になりますよね。きちんと設計しないとcacheうんぬん以前にDisk I/Oにいじめられそう。恐らく比較的に低コストのスレーブを何十台かPlatform用に分けて、そのクラスタに異常が起きても本サービスには影響しない分離された構成にしてるのかなー？と思うのですがどうなんでしょうね？

最後に一言

ユーザが何千万人もいながらこういうエンジニアにしか成し遂げることの出来ない壮大なものを実現してしまうとはエンジニア”魂”を感じますね。世の中にはこういった刺激あるものがどんどん生み出されています。私も取り残されないよう色々と他社のサービスも参考にしながら頑張って面白おかしくmixiと自分をよりよいものにしていきたいと思います。

この連載のように小難しい記事が続くと、読者の皆さんだけでなく執筆陣まで引いてしまうのではないかと心配しているmikioです。いやいや、いいんです。ハッキングから夜のオカズまでバラエティに富んだブログを目指すべく、私は私なりの記事を、たとえマイノリティ向けだとしても臆さず書いてゆくのです。今回はTCの実装の詳細についてお届けします。

QDBMとどう違うの?

QDBMもTCと同様にDBMの一実装で、小さくて速くて使いやすいをモットーに作りはじめて、それなりに目標を達成できたと自負しているプロダクトです。しかし、今思えばいろいろと気に入らない点がいくつかありました。TCはそれを克服すべく一から書き直したものです。具体的には以下の点が違います。

• 空間効率の向上 : データベースファイルのサイズがもっと小さい
• 時間効率の向上 : 読み書きにかかる時間がもっと短い
• 耐障害性の向上 : データベースファイルが壊れにくい
• 64ビット対応 : 64ビットシステムでは2GB以上（8EBまで）のデータベースファイルを作れる
• バイトオーダ独立 : バイトオーダが異なる環境でデータベースファイルを共有できる
• マルチスレッドセーフ : マルチスレッド環境でも特別な注意なしに安全に動作する
• C99への準拠 : 移植性・保守性・可読性が向上

最も気にしたのは空間効率です。レコードごとのヘッダを圧縮したり、更新を繰り返すことによるフラグメンテーションを軽減したりするための工夫を思いつく限りでしてみました。典型的な利用シーンではQDBMに比べると90%くらいのデータベースサイズになっていると思います。そして、64ビット環境が気軽に手に入るようになった昨今の事情を踏まえて、いわゆる2GBの壁を突破できるように（そしてそれでもヘッダが大きくならないように）してみました。データベースサイズが8EB（8エクサバイト）までである理由は、2の63乗が9,223,372,036,854,775,808だからです（64ビット中の最後の1ビットは別の用途で使います）。メガマックとかテラマックとかいうレベルじゃないですね。そんなでかい記憶装置は持っていないので、残念ながら8EBは理論値に過ぎませんが、48GB（10億レコード）のデータベースファイルを作ってもきちんと動作することは確認しています。

時間効率に関しては、実はプログラムが複雑になった分だけ命令数も増えてやや悪化しているのですが、空間効率が上がってデータベースのサイズが小さくなったおかげでほぼ同じくらいに仕上っています。しかし、それだと悔しいので、後述する非同期更新モードを使うことで、更新処理の時間効率を著しく向上させることも可能にしました。そのおかげで、実用上の更新速度に関してはQDBMの1.5倍以上になっていると思います。

バイトオーダ独立に関しては、MacがIntel CPUに乗り換えた時点でどうでもいいと思っていましたが（SPARCとかPA-RISCとか個人じゃ買えないし）、後でクレームが入ってからコンバータを書く苦労を考えて、予め対応しておくことにしました。といっても、これまたテスト環境がないので「理論的には」ということですが。

C99準拠に関しては私の趣味がちょっと変わったことによります。PerlやJavaに慣れてくると、コードと変数宣言を混在させるのが普通になってきてしまって、C89的にブロック先頭に宣言を集めるのがおっくうになってきたのです。また、int64_t（long long）や可変長配列を堂々と使えるのもC99の魅力でしょうか。あと、あんまり関係ないですけど、Windows対応は当面見送ることにしました。面倒だしテストしきれないという個人的な理由と、いわゆるサーバ用途を重視したいというビジネス的な理由からです。

ちなみに、ライセンスはQDBMと同じでLGPL（GNU Lesser General Public License）です。オープンソースのライブラリとしては一般的なので、気がねなく使えると思います。言うまでもなく、商用/非商用を問わず、TCを製品に組み込んで配布することができます（組み込み系などでTC自体を改変する場合はまた別の話ですが）。なんでオープンソースなのかという理由は長くなるので割愛しますが、ひとことで言えば、フィードバックをもらって品質を上げていきたいからです。

数値データの型

TCでは、レコードの位置や、キーおよび値の長さなどの数値データは、2種類の型で表されます。固定長型と可変長型です。固定長型は8ビット/16ビット/32ビット/64ビットのどれかの長さを持ち、それぞれ変域が0〜256/0〜64K/0〜4G/0〜9Eになります。つまり、変域が予めわかっている場合は、その変域を収めるのに十分な長さの固定長型を用います。一方、可変長型は、値が0〜127なら1バイト、128〜16383なら2バイト、16384〜2097151なら3バイト、2097152〜268435456なら4バイトといった可変長の領域で128進法の数値を表すものです（残り1ビットを区切りに使う）。可変長型の特徴は、変域の最大値が制限されないことと、小さい値ほど短い長さで表現できることです。したがって、「おそらくほとんどは小さい値が入るだろうがたまに大きい値が来るかもしれない」ような数値データには可変長を用います。

固定長と可変長をうまく使い分けて領域が無駄にならないようにするのが重要です。それでは、レコードのヘッダに使われる数値データの実際の型を見てみましょう。

• マジックナンバ : レコードかフリーブロックかを識別 : 値が2種類なので8ビット固定長
• 第2ハッシュ値 : チェーンの進路決定に用いる : 第1ハッシュ値の衝突数が少ないことを前提とすれば256種類もあれば十分なので8ビット固定長
• 左チェーンと右チェーン : 子供のレコードの位置はDBサイズに比例して大きくかつ均等に分散されるので、32ビット固定長。64ビットモードの場合は64ビット固定長。
• パディングサイズ : パディングバイトのサイズ。後述するアラインメントにより変域が0〜65536以内になるので16ビット固定長。
• キーサイズ : キーの実データのサイズ。多くのケースでは短いが長い時もあるので可変長。
• 値サイズ : 値のキーの実データのサイズ。多くのケースでは短いが長い時もあるので可変長。

データベースが小さい場合は左チェーンや右チェーンを可変長にした方が効率がいいじゃないかいう意見があろうかと思いますし、実際に私も最初はそのように設計したのですが、それは落とし穴です。チェーンはデータベースが更新される時に結構な頻度で繋ぎ変える必要が生じますが、子レコードの位置が移動した場合に親レコードのチェーンを書き換えてそのサイズが変わった場合に、親も移動するはめになることがあり、連鎖的にかなりの数のレコードを移動させねばならない自体が発生するからです。

16ビット以上の固定長データ型では、バイトオーダの問題についても考えておく必要があります。耳にタコな話ではありますが、数値の上位ビットを先に配置して下位ビットを後に配置する方式はビッグエンディアン、数値の下位ビットを先に配置して上位ビットを後に配置する方式はリトルエンディアンと呼ばれ、プロセッサによって異なります。変数の領域の内容をmemcpyやwriteなどでそのまま書き出すと、プロセッサのバイトオーダに依存したファイルが作られることになるので、バイトオーダが異なる環境にそのファイルを転送したり、NFSなどの仕組みで複数のマシンでファイルを共有する際に相手のプロセッサのバイトオーダが同じでないといけないという制限が発生してしまうのです。

バイトオーダを気にしないようにするためには、ファイルに書き出す時にはつねにバイトオーダをそろえるようにすればよいのです。TCでは固定長データ型は全てリトルエンディアンで扱うことにしました。なぜなら私のマシンや弊社にあるマシンのほとんどはリトルエンディアンだからです。ビッグエンディアンの環境では、数値を書き出す時には以下のようなマクロによってバイトオーダを変換しています。

#define TCSWAB32(TC_num) \
  ( \
   ( (TC_num & 0x000000ffUL) << 24 ) | \
   ( (TC_num & 0x0000ff00UL) << 8 ) | \
   ( (TC_num & 0x00ff0000UL) >> 8 ) | \
   ( (TC_num & 0xff000000UL) >> 24 ) \
  )
#if defined(_MYBIGEND) || defined(_MYSWAB)
#define TCHTOIL(TC_num)   TCSWAB32(TC_num)
#else
#define TCHTOIL(TC_num)   (TC_num)
#endif

そのプログラムが動いているプロセッサ（とおそらく一致するであろうコンパイル環境のプロセッサ）のバイトオーダを判定する仕事は、ビルド時の configure にやらせています。実行時に判定することもできなくはないのですが、そうすると分岐命令を増やすことになるのでオーバーヘッドが馬鹿になりません。やっぱりマクロは手放せませんね。ちなみにビッグエンディアン（ネットワークバイトオーダ）との相互変換に用いるhtonlとかntohlとかいう関数を使ってもよかったのですが、今回はリトルエンディアンにしたかったので自分で書いた次第です。

アラインメント

アラインメントといってもロウとかカオスとかの話ではなくって、レコードの位置を一定の数の倍数に揃えるという話です。例えば、4の倍数で揃えると決めた場合、位置の数値を4で割った余りは必ず0になります。したがって、4で割った商を記録しても情報は失われないのです（読み出した時に4をかければ復元できるから）。可変長型は小さい値であるほどサイズが小さくて済むということは既に述べましたが、アラインメントを使うと位置情報のための領域をかなり節約できることがおわかりいただけると思います。

レコードのヘッダとキーと値のサイズの合計がアラインメントの倍数であるとは限らないので、そこでパディングが登場するわけです。特に意味の無いデータをレコードの末尾につけておくことで、次のレコードが必ずアラインメントの倍数で始まるように調整するのです。アラインメントを大きくするとヘッダのサイズは縮小されるのですが、逆にパディングが大きくなるので、大きくすればいいってものではないことには注意してください。デフォルトのアラインメントは16というかなり低目の設定なのですが、これはヘッダのサイズがだいたい16バイトくらいで、キーと値が8バイトずつといったユースケースを想定したものです。ところで、パディングのサイズのデータ型は16ビットの固定長にしているのですが、これはアラインメントの変域を1〜65536に制限していることによります。それ以上大きなアラインメントはまず必要ないですよね。

バケット配列の各要素は32ビットモードだと4バイト、64ビットモードだと8バイトの固定データ型になります。アラインメントの嬉しい副作用のひとつは、32ビットのバケットにも4GB以上の位置情報を格納できることです。例えばアラインメントが64ならば、32ビットモードで128GBまでのデータベースファイルが扱えることになるわけです。32ビットモードでのテストは16GBまで行いましたが、問題なく動作しました（ちなみに、OSの設定が32ビットでもプログラムのビルド時に「_LARGEFILE64_SOURCE」マクロを定義しておくと2GB以上のファイルが扱えます）。

ファイルシステムのブロックサイズとアラインメントを合わせておくというのも戦略のひとつです。ほとんどのファイルシステムではファイル上の任意のオフセットと長さをバイト単位で指定してデータの読み書きができるのですが、ファイルシステムより下の世界での実際の読み書きは常にブロックサイズを単位としてしか行われません。例えば私の環境ではブロックサイズは4096バイトですが、あるファイルの6432バイトの部分に300バイトのデータを書き込むとしましょう。そうすると、6432/4096 = 1余り2336 の計算で、1ブロック目（0から数えて）のオフセット2336の位置に300バイトを書き込もうとします。ただし、実際にはそのブロックの既存のデータを読み出して4096バイトのバッファを用意してから、そのバッファの2336バイト目から2636バイト目までを上書きして、そしてそのバッファを書き戻すという処理を行うことになります。つまりブロックサイズより小さい領域に書き込みをしたり、ブロックサイズをまたがった書き込みをしようとすると、無駄に読み込みが発生してよろしくないということです。したがって、レコードのサイズがある程度大きい場合は、ブロックサイズとレコードのアラインメントを合わせておくことで時間効率を上げられることがおわかりいただけると思います（その分、空間効率は犠牲になります）。

プログラムの動作環境が何ビット設定なのか、ファイルシステムのブロックサイズが何バイト設定なのかといったことはきちんと把握しておいた方がいいことは言うまでもありませんが、それを調べるのって意外に面倒ですよね。TCではそれを補助するユーティリティがあります。以下のコマンドを実行してみてください。C言語での各種の数値型のサイズや、OSの各種の設定がずらずらと出力されてちょっと便利です。

$ tcucodec conf

API

APIもQDBMでの反省を反映してかなり使いやすくなっていると思います。QDBMで最も後悔しているのはコンストラクタとデストラクタで、そのシグネチャは以下です。

DEPOT *dpopen(const char *name, int omode, int bnum);
int dpclose(DEPOT *depot);

何がいけないかっていうと、まずファイルのオープンに失敗した場合にNULLが返ってきてオブジェクトが作られないことです。つまり、エラー処理のパラメータにそのオブジェクトが使えないということです。「put」や「get」などの操作のエラー処理はオブジェクトにエラーコードを問い合わせてゴニョゴニョするといった形で統一することができますが、「open」に失敗した場合だけはオブジェクトがないので別系統で処理しないといけないのです。標準ライブラリのFILEハンドルを真似てそうしたのですが、今から考えるとナンセンスです。C++やJavaやPerlやRubyのラッパーを作る際にもif文をいっぱい書かなければならなくて泣きが入りました。

そしてさらなる後悔は、エラーコードの問い合わせだけ無理矢理統一した手順で行えるようにするために、グローバル変数にエラーコードを格納していることです。これはGDBMを真似ているわけですが、どう考えてもナンセンスです（そりゃもうライブラリの中でstderrにエラーメッセージを吐いてるくらいナンセンスです）。なぜならグローバル変数にアクセスする全ての処理をシングルトンのmutexで保護しないとスレッドセーフにならないからです。苦肉の策で今度は「errno」を真似て、「#define dpecode (*dpecodeptr())」などとして、「dpecodeptr」にTSD（Thread Specific Data）へのポインタを返させるようにしてスレッドセーフを演出しましたが、これはもはや誤魔化しの範疇です。

今は反省して、TCではコンストラクタは何もせずに初期化したオブジェクトを返すようにして、「open」は別のメソッドとして独立させました。同様に、デストラクタと「close」も別個のメソッドになりました。それらのシグネチャは以下です。

TCHDB *tchdbnew(void);
bool tchdbopen(TCHDB *hdb, const char *path, int omode);
bool tchdbclose(TCHDB *hdb);
void tchdbdel(TCHDB *hdb);

何もしないということは失敗もしないということです。「new」と「del」は絶対に失敗しません。そして「open」と「close」の失敗は真偽値で通知されるとともに、詳細はオブジェクトに対して「ecode」メソッドを発行すればわかります。奇妙なマクロでグローバル変数風な挙動を演出せずとも済む、クリーンでハッピーな世界が実現できました。

二番目の後悔は「get」です。そのシグネチャは以下です。

char *dpget(DEPOT *depot, const char *kbuf, int ksiz,
  int start, int max, int *sp);

「ksiz」はキーのサイズが指定できるのですが、それが負数の場合は「strlen(kbuf)」を内部で読んでくれるという仕様になっています。これは一見してユーザフレンドリーのようですが、バグの発見が遅れるという副作用があります。確かに文字列をキーにすることは多いのですが、気軽に-1を指定してしまうおかげで、ゼロ終端していないバッファを指定して後後になってメモリ破壊が起きたり、変数の初期化ミスをしていても正常っぽく動いてしまったりと、ろくなことがありません。この問題は「get」だけでなく「put」や「out」でも同様です。今は、文字列用は文字列用の関数を独立させるのが正解だと断言できます。

さらに、「start」とか「max」とかが意味わかりませんね。これは取り出すべきデータのオフセットと長さを指定するパラメータです。例えば、「dpget(depot, “hoge”, 4, 8, 3, &size)」などとすると、「hogeに対応するレコードの値の8バイト目から11バイト目まで」をバッファにコピーして返します。通常は0と-1を指定することでレコード全体を取り出します。設計当初はこれらのパラメータは「あったら便利かな」と思っていたのですが、しかし、自分で作っておきながら、使ったことは今の今まで一度もありません。全くナンセンスです。どうせならレコードの値の領域をmmapしたポインタを返す方がユースーケースがあったでしょう。

三番目の後悔は「put」です。そのシグネチャは以下です。

int dpput(DEPOT *depot, const char *kbuf, int ksiz,
  const char *vbuf, int vsiz, int dmode);

問題は「dmode」です。これはレコードのキーが重複した際に、上書きするか、既存の値を残すか、既存の値の後ろに連結するかを選択するためのパラメータです。それぞれ、DP_DOVER、DP_DKEEP、DP_DCATという列挙子で指定するのですが、これがtype safeでないために何度もバグを仕込んだものです。「上書きしたい」ので「TRUE」を指定してしまうミスを連発。しかもこの手のミスは何度コードを読み直しても気づかないのです。そうですね。これも関数を分けるのが正解だと断言します。80%以上のユースケースではDP_DOVERを使っているので、DP_DOVERが「put」で、DP_DKEEPを「putkeep」で、DP_DCATを「putcat」としてシグネチャを切るのがよいでしょう。その上で実装は適切な粒度で共有すればよいのです。

ということで、「put」と「get」に関連するメソッドはTCでは以下のように定義されています。書きやすさと読みやすさと性能のバランスを考えると、私としてはこれが最も落ち着く形です。

bool tchdbput(TCHDB *hdb, const char *kbuf, int ksiz,
  const char *vbuf, int vsiz);
bool tchdbput2(TCHDB *hdb, const char *kstr, const char *vstr);
bool tchdbputkeep(TCHDB *hdb, const char *kbuf, int ksiz,
  const char *vbuf, int vsiz);
bool tchdbputkeep2(TCHDB *hdb, const char *kstr, const char *vstr);
bool tchdbputcat(TCHDB *hdb, const char *kbuf, int ksiz,
  const char *vbuf, int vsiz);
bool tchdbputcat2(TCHDB *hdb, const char *kstr, const char *vstr);
char *tchdbget(TCHDB *hdb, const char *kbuf, int ksiz, int *sp);
char *tchdbget2(TCHDB *hdb, const char *kstr);

「put2」や「get2」の「2」はちょっとわかりにくいなと自分でも思いますが、「s」だと複数形や三単現の活用なのかと思われてしまうし、「str」だと長くなってsyntax sugarの意味がなくなるので妥協しました。UNIXでもdup2とかwait3とかありますし。

まとめ

TCは基本的なアルゴリズムはQDBMのものを踏襲していますが、データフォーマットを工夫することで空間効率を向上させるとともに、巨大なデータベースも扱えるようにしています。可変長型とアラインメントの利用がそのキモですね。そして64ビット対応ができたとこで大規模なデータベースも扱えるようになり、いわゆるエンタープライズ用途での活躍の場も増えてくることが期待できます（といいつつ組込み系でも動くように軽量の実装を心がけてます）。

また、APIを洗練させてよりオブジェクト指向な感覚で使えるようにしました。使いやすいということは、使いにくくないということです。そもそもインターフェイスの良し悪しもユーザの好みに依存するので最良なんてないわけですが、オブジェクト指向風味の操作体系とUNIX風味の命名規則を徹底しているので、それらに親しんでいる人には使いやすいと感じていただけるのではないかと思います。

あまりに長くなったので、フリーブロックプールや非同期書き込みモードの話は次回以降に持ち越します。この次もサービスサービス。