Inside Tokyo Cabinet その参
この連載のように小難しい記事が続くと、読者の皆さんだけでなく執筆陣まで引いてしまうのではないかと心配している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とかありますし。
