こんにちは、mixi開発部にてアプリケーション開発をしていますyouheiです。
今回は、MySQL-5.0.45のInnoDBで連番を管理するテーブルのパフォーマンス測定をしていたのですが、その際に少し変わったデッドロック問題に遭遇しましたので、そのあたりをネタとして書いてみたいと思います。

まずは、今回使用したデータベースのスキーマは下記のようなものです。

CREATE TABLE num (
    id bigint unsigned NOT NULL default '0'
) Engine=InnoDB;

AUTO_INCREMENTは使用していません。
そこに1レコードだけ登録します。

INSERT INTO num (id) values (1);

そして実際連番を取得する際には、

UPDATE num SET id = LAST_INSERT_ID(id+1);

といったクエリを発行しインクリメントしていき、最新のidはSELECTするのではなくUPDATE時のMySQL応答パケットに含まれるmysql_insertidを参照します。

上記のような内容をベンチマークテストのために同時接続を増やしながらテストしていると、350を超えたあたりで

ERROR 1213 (40001): Deadlock found when trying to get lock

というエラーが発生するという事態に遭遇しました（350という具体的な数値はハードウェアの性能などで変動すると思います）。ちなみに試験環境のOSやMySQLのバージョンは簡単ですが下記のような感じです。

• MySQL-5.0.45
• Linux-2.6.22

まずはWebで検索してみる

筆者の英語力不足という説もありますが、なかなか「コレ！」というものが見つけられませんでした。

パラメータやSQL文等を色々試してみる

• 1カラムしかないのが逆に良くないのかと思い、主キーカラムを追加しWhere句で指定　→　変化なし
• autocommitなのが良くないのかと思い、start transaction(またはbegin)とcommitを発行する　→　変化なし
• トランザクション分離レベルをserializableに変えてみる　→　変化なし
• innodb_table_locksパラメータを0にしてみる　→　変化なし

他にもいくつか試しました。また、それらを組み合わせてみたりもしましたが解決しません。なので、ソースを読んでみることにします。

静的デバッグ

MySQLのソースの取得・展開は済んでおり、ソース群のトップディレクトリにいるものとします。
エラー番号は1213と分かっているので、ヘッダファイルに対してgrepをかけてみます。

% find ./ -name \\*.h | xargs grep -rn 1213
./include/mysqld_error.h:217:#define ER_LOCK_DEADLOCK 1213
./include/mysqld_ername.h:216:{ "ER_LOCK_DEADLOCK", 1213 },

となるので、今度はER_LOCK_DEADLOCKを参照しているところを探してみます。

% global -r ER_LOCK_DEADLOCK
include/sql_state.h
libmysqld/handler.cc
libmysqld/lock.cc
sql/handler.cc
sql/lock.cc
sql/slave.cc

./sql/handler.cc か ./sql/lock.cc あたりが怪しそうです。そしてどちらを見てみても、

case HA_ERR_LOCK_DEADLOCK:
    textno=ER_LOCK_DEADLOCK;

となっているため、実際にはストレージエンジンレイヤーより HA_ERR_LOCK_DEADLOCK が返却された場合に前述のエラーが返却されるのであろうと予想がつきます（定数もファイル名もHA_(ha_)から始まるのは大体ストレージエンジンレイヤーです）。

というわけでinnodb関連のファイルで上記定数を使用しているところを探してみます。

% global -rx HA_ERR_LOCK_DEADLOCK
～略～
HA_ERR_LOCK_DEADLOCK  462 sql/ha_innodb.cc  return(HA_ERR_LOCK_DEADLOCK);
～略～

おそらくこのあたりであろうと思われます。というわけで実際に動かしながらのデバッグに移ります。

動的デバッグ

gdbやddd等を使って上記付近の場所にブレークポイントをはってみます。今回は458行目にはりました。

453     } else if (error == (int) DB_DEADLOCK) {
454         /* Since we rolled back the whole transaction, we must
455         tell it also to MySQL so that MySQL knows to empty the
456         cached binlog for this transaction */
457
458         if (thd) {
459             ha_rollback(thd);
460         }
461
462         return(HA_ERR_LOCK_DEADLOCK);

そして高負荷をかけてみて引っかかるのを待ちます。しばらく待ってみると…見事ひっかかりました！下記がその際のbacktraceです（引数の値やライブラリのパス等は伏せさせていただいてます）。

(gdb) bt
#0  convert_error_code_to_mysql at ha_innodb.cc:458
#1  0x0829656a in ha_innobase::index_read at ha_innodb.cc:3852
#2  0x08293143 in ha_innobase::index_first at ha_innodb.cc:4083
#3  0x08295ec8 in ha_innobase::rnd_next at ha_innodb.cc:4177
#4  0x08280bf3 in rr_sequential at records.cc:295
#5  0x0823ce9f in mysql_update at sql_update.cc:460
#6  0x081c61ac in mysql_execute_command at sql_parse.cc:3465
#7  0x081cb975 in mysql_parse at sql_parse.cc:6097
#8  0x081cdc2a in dispatch_command at sql_parse.cc:1812
#9  0x081cf08f in do_command at sql_parse.cc:1586
#10 0x081d0018 in handle_one_connection at sql_parse.cc:1197
#11 0x005e045b in start_thread ()
#12 0x004c223e in clone ()

正常時は#0のconvert_error_code_to_mysqlは通らないのですが、#1のha_innobase::index_read() は通るようなので、どうやらこの中でデッドロックか正常か分かれるようです。というわけで実行を一時中断して再度ソースコードに戻ります。ha_innobase::index_read() のリターン周辺をみてみると、

3836     ret = row_search_for_mysql((byte*) buf, mode, prebuilt, match_mode, 0);
3837
3838     innodb_srv_conc_exit_innodb(prebuilt->trx);
3839
3840     if (ret == DB_SUCCESS) {
3841         error = 0;
3842         table->status = 0;
3843
3844     } else if (ret == DB_RECORD_NOT_FOUND) {
3845         error = HA_ERR_KEY_NOT_FOUND;
3846         table->status = STATUS_NOT_FOUND;
3847
3848     } else if (ret == DB_END_OF_INDEX) {
3849         error = HA_ERR_KEY_NOT_FOUND;
3850         table->status = STATUS_NOT_FOUND;
3851     } else {
3852         error = convert_error_code_to_mysql((int) ret, user_thd);
3853         table->status = STATUS_NOT_FOUND;
3854     }

となっており、retの値、すなわち row_search_for_mysql()の戻り値により正常かデッドロックか分かれているようです。なので、row_search_for_mysql() を追ってみます。

% global -x row_search_for_mysql
row_search_for_mysql 3041 innobase/row/row0sel.c row_search_for_mysql(

内容は、

3040 ulint
3041 row_search_for_mysql(
3042 /*=================*/
3043                              /* out: DB_SUCCESS,
3044                              DB_RECORD_NOT_FOUND,
3045                              DB_END_OF_INDEX, DB_DEADLOCK,
3046                              DB_LOCK_TABLE_FULL, DB_CORRUPTION,
3047                              or DB_TOO_BIG_RECORD */
3048   byte*           buf,       /* in/out: buffer for the fetched
3049                              row in the MySQL format */
3050   ulint           mode,      /* in: search mode PAGE_CUR_L, ... */
3051   row_prebuilt_t* prebuilt,  /* in: prebuilt struct for the
3052                              table handle; this contains the info
3053                              of search_tuple, index; if search
3054                              tuple contains 0 fields then we
3055                              position the cursor at the start or
3056                              the end of the index, depending on
3057                              'mode' */
3058   ulint       match_mode,    /* in: 0 or ROW_SEL_EXACT or
3059                              ROW_SEL_EXACT_PREFIX */
3060   ulint       direction)     /* in: 0 or ROW_SEL_NEXT or
3061                              ROW_SEL_PREV; NOTE: if this is != 0,
3062                              then prebuilt must have a pcur
3063                              with stored position! In opening of a
3064                              cursor 'direction' should be 0. */
3065 {

というように DB_DEADLOCK を返却することがあるようなのですが、このファイル内にはDB_DEADLOCKという定数は現れません。なので、内部で何かの関数を呼び、そのreturnがDB_DEADLOCKで、それをそのままreturnしているのではないかと予想します。
なので、DB_DEADLOCKをreturnしてそうなところを探してみます。

% global -rx DB_DEADLOCK innobase/
DB_DEADLOCK  1850 innobase/lock/lock0lock.c return(DB_DEADLOCK);
DB_DEADLOCK  3557 innobase/lock/lock0lock.c return(DB_DEADLOCK);
DB_DEADLOCK   519 innobase/row/row0mysql.c  } else if (err == DB_DEADLOCK
DB_DEADLOCK  1420 innobase/srv/srv0srv.c    trx->error_state = DB_DEADLOCK;
DB_DEADLOCK  1514 innobase/srv/srv0srv.c    trx->error_state = DB_DEADLOCK;
DB_DEADLOCK   453 libmysqld/ha_innodb.cc    } else if (error == (int) DB_DEADLOCK) {
DB_DEADLOCK   453 sql/ha_innodb.cc          } else if (error == (int) DB_DEADLOCK) {

先頭2つが怪しそうです。見てみると、1850行目と3557行目を見てみると、両方とも lock_deadlock_occurs() の戻り値が真であればDB_DEADLOCKを返却するようです。なので lock_deadlock_occurs() の内部を更に追ってみます。

3190   ret = lock_deadlock_recursive(trx, trx, lock, &cost, 0);
3191
3192   if (ret == LOCK_VICTIM_IS_OTHER) {
3193     /* We chose some other trx as a victim: retry if there still
3194     is a deadlock */
3195
3196     goto retry;
3197   }
3198
3199   if (ret == LOCK_VICTIM_IS_START) {
3200     if (lock_get_type(lock) & LOCK_TABLE) {
3201       table = lock->un_member.tab_lock.table;
3202       index = NULL;
3203     } else {
3204       index = lock->index;
3205       table = index->table;
3206     }
3207
3208     lock_deadlock_found = TRUE;
3209
3210     fputs("*** WE ROLL BACK TRANSACTION (2)n",
3211       lock_latest_err_file);
3212
3213     return(TRUE);
3214   }

というわけで、lock_deadlock_recursive()のreturnがLOCK_VICTIM_IS_STARTの場合に真が返るようです。
少々疲れてきましたがさらに追います。以下が、lock_deadlock_recursive() の戻り値がLOCK_VICTIM_IS_START になる条件です。

3351                 if (too_far) {
3352
3353                     fputs("TOO DEEP OR LONG SEARCH"
3354                           " IN THE LOCK TABLE"
3355                           " WAITS-FOR GRAPHn", ef);
3356
3357                     return(LOCK_VICTIM_IS_START);
3358                 }
3359
3360                 if (ut_dulint_cmp(wait_lock->trx->undo_no,
3361                             start->undo_no) >= 0) {
3362                     /* Our recursion starting point
3363                     transaction is 'smaller', let us
3364                     choose 'start' as the victim and roll
3365                     back it */
3366
3367                     return(LOCK_VICTIM_IS_START);
3368                 }

いよいよ大詰めな感じです。ここで再度デバッガを使ってみましたところ、どうやらtoo_farフラグが立っているようで、3357行目のほうに引っかかります。too_farは、

3293             ibool   too_far
3294                 = depth > LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK
3295                 || *cost > LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK;

のようです。depthは本関数の引数で与えられ、再帰呼び出しの直前にインクリメントされる値です。また、これら2つの定数は同ファイルにて下記のように定義されています。

46 /* Restricts the length of search we will do in the waits-for
47 graph of transactions */
48 #define LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK 1000000
49
50 /* Restricts the recursion depth of the search we will do in the waits-for
51 graph of transactions */
52 #define LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK 200

too_farフラグが立った時、結局どちらの制限にひっかかっていたかというと、LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK のほうでした。

ここまで分かってから再度Webを検索してみるといとも簡単に見つかりました。
http://bugs.mysql.com/bug.php?id=12588 （リンク先はMySQL AB社のサイトです）

どうやらbug fixとして5.0.13以降で追加された定数・ロジックのようです。
高負荷時にロックが増加した際、デッドロック検出のための再帰呼び出しの深さが深くなりすぎてスタックを消費していきデーモンごと落ちてしまう、という問題を解決するために追加したようです。

まとめ

と、ここまで分かると次に気になるのは、この値をもう少し増やしてみたらどうだろうか、というところです。

ですが、結論からいいますと、サーバーのハードのスペックにもよりますが、今回の検証用環境では多少の増加は出来ましたが、さらに負荷を上昇させていくとロック待ち時間が増加し、その結果innodb_lock_wait_timeoutに引っかかり始めました。じゃあinnodb_lock_wait_timeoutも増加させればいいじゃないか、と考えもしましたが、ただ実際にはそれによりパフォーマンスが向上するわけではなく、「90秒や120秒待てばデッドロック扱いもタイムアウト扱いもせずSQLが完了します」というのは、MySQL的にはエラーでなくとも実際のシステム的にはエラーも同然ですのであまり意味がないのではないかと判断しました。というわけで、現在mysqldを動作させる一般的なハードウェア上では200という数字はそれなりに適切な値なのではないかと思いました。

ちなみにMyISAMではこのような問題は起こらず、パフォーマンスも良好な結果でした。システムの要件にもよりますが、MyISAMに変更しても問題ない場合はそちらも検討されるのも良いかと思います。

デッドロックになるはずのないSQL文でデッドロックだとエラーメッセージが返却された場合にこのような例もあったなということを思い出していただけると幸いです。

当エンジニアブログを私物化していると専らの評判のmikioです。ブログを書かないと死んでしまう病に冒されているのでしかたないですね。個人ブログ時代よりもわかりやすくする努力はしているんですけどね。さて、今回はソースコードの最適化による高速化について述べます。

ベンチマークテスト

TCはQDBMや他のDBMより高速であるという主張をしたいのですが、その根拠としてベンチマークテストの結果が必要となります。そこで、データベースに100万レコードを格納する処理と、そうして作ったデータベースから全てのレコードを探索する処理の時間を、各DBMで計測してみました（TCのパッケージのbrosというディレクトリにテストコードが入っています）。実行環境は、Thinkpad T60（Intel(R) Core2 CPU T7200 @ 2.00GHz）上のLinux version 2.6.16です。

このテストではたった100万件の読み書きしかしていないので、ほぼ全てののI/O要求がファイルシステムのキャッシュ上で完結しています。したがって、実運用環境において実メモリの容量を越えるような規模のデータベースを扱った場合の性能特性とはかなりずれたものになる可能性があることには注意してください。今回のテストではコード自体のミクロ視点の効率性を測るために100万件の読み書きという単純なテスト内容にしています。ちなみに実時間の測定は誤差（というか試行毎の偏差）が大きいので、20回測定して順位が真ん中の10個の平均を代表値にしました。

で、結果を見てみると、TCの性能はBerkeley DBには概ね勝っていますが、QDBMとはほぼ同じ性能だということがわかります。ハッシュwriteに関しては非同期モードのおかげで爆発的な性能が出ていますが、その他はQDBMの時代からあんまり進化していないように見えます。データフォーマットとAPIは変わりましたが基本的なアルゴリズムは全く同じなので、性能がだいたい同じになるのは予想通りです。

最適化の余地

しかし、個人的には納得いきません。TCのコーディングはQDBMの時以上に実行時のオーバーヘッドを気にしてやってきたからです。どこかで無駄なことをやっていて、その無駄を削ればもっと早くなるような気がするのです。実はその答えはわかっていて、QDBMで手動でやっていた各種のコード最適化をTCではまだやっていないのです。

これ以上早くすることに実用的な意味はほとんどないのですが、ベンチマークテストの見映えをよくするというのは市場競争の観点から言えばそれなりに重要なことです。コンパイラによる最適化以上の最適化をしようとすると手でソースコードを書き換えることになり、それは可読性と保守性を損なうリスキーな行為なのですが、それでも敢えてやるべきこともあるのです。

さて、闇雲に最適化をして回るとコードがめちゃくちゃになってしまうので、まずはどこに時間がかかっているかをプロファイルで見なければなりません。すなわち関数単位でのホットスポットの発見です。その上で、その関数自身とその関数を呼び出している周辺のみに絞って最適化を検討します。gccの-pgオプションを用いてライブラリとテストコマンド群（こんなこともあろうかテストツールを揃えておいてよかった）をビルドし、それらが出力したプロファイル情報をgprofコマンドで閲覧します。ちなみに、gprofによるプロファイルは実行時間やその割合などを結構細かい値で出力してくれるのですが、誤差もそれなりに大きいことには注意してください（傾向を見るのには十分ですが）。

ハッシュデータベースに500万レコードを格納した際（tchtest write casket 5000000 5000000）のプロファイルは以下です。tchdbwriterecはレコードを直列化してから書き込む関数で、tchdbbidxはハッシュ関数です。これら2つで約37%の時間を使っていることがわかります。

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 24.69      1.18     1.18  5000000     0.00     0.00  tchdbwriterec
 12.34      1.77     0.59  5000000     0.00     0.00  tchdbbidx
 11.72      2.33     0.56  5000000     0.00     0.00  tchdbputimpl
  6.69      2.65     0.32  6620023     0.00     0.00  tcseekwrite
  6.07      2.94     0.29  5000000     0.00     0.00  tchdbput
  5.23      3.19     0.25  6622585     0.00     0.00  tcwrite
  4.18      3.39     0.20  3379978     0.00     0.00  tchdbsetbucket
  4.18      3.59     0.20        1     0.20     4.78  procwrite
  3.35      3.75     0.16  5000000     0.00     0.00  tchdbgetbucket
  3.14      3.90     0.15  5000000     0.00     0.00  tchdbfbpsearch

ハッシュデータベースから500万レコードを取得した際（tchtest read casket）のプロファイルは以下です。tchdbwriterecはレコードを読み込んでから非直列化する関数で、tchdbbidxはハッシュ関数です。これら2つで約36%の時間を使っていることがわかります。

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 19.44      0.84     0.84  6864280     0.00     0.00  tchdbreadrec
 17.13      1.58     0.74  5000000     0.00     0.00  tchdbbidx
  9.03      1.97     0.39  5000000     0.00     0.00  tchdbgetimpl
  8.80      2.35     0.38        1     0.38     4.32  procread
  8.56      2.72     0.37  6864281     0.00     0.00  tcseekread
  6.94      3.02     0.30  5002510     0.00     0.00  tcreckeycmp
  5.79      3.27     0.25  5000000     0.00     0.00  tchdbget
  4.40      3.46     0.19  5000000     0.00     0.00  tcmemdup
  4.17      3.64     0.18  6864281     0.00     0.00  tcread

ハッシュデータベースに500万レコードを格納した際（tcbtest write casket 5000000）のプロファイルは以下です。tcbdbcmplexicalはB+木の比較関数で、tclistvalは配列リストの要素を参照する関数です。これら2つで約27%の時間を使っていることがわかります。

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 17.44      2.66     2.66 43035340     0.00     0.00  tcbdbcmplexical
 10.03      4.19     1.53 76005216     0.00     0.00  tclistval
  9.64      5.66     1.47  5000000     0.00     0.00  tcbdbleafaddrec
  9.57      7.12     1.46  5480393     0.00     0.00  tcmapmove
  8.52      8.42     1.30  5637861     0.00     0.00  tcmapget
  4.33      9.08     0.66 10234421     0.00     0.00  tclistpush
  3.41      9.60     0.52  5000000     0.00     0.00  tcbdbputimpl
  3.28     10.10     0.50  4843752     0.00     0.00  tcbdbgethistleaf
  3.08     10.57     0.47 15951567     0.00     0.00  tclistnum

B+木データベースから500万レコードを取得した際（tcbtest read casket）のプロファイルは以下です。tcbdbcmplexicalはB+木の比較関数で、tclistvalは配列リストの要素を参照する関数です。これら2つで約28%の時間を使っていることがわかります。

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 18.01      2.55     2.55 39135085     0.00     0.00  tcbdbcmplexical
 11.02      4.11     1.56  5468133     0.00     0.00  tcmapmove
 10.17      5.55     1.44  5000000     0.00     0.00  tcbdbsearchrec
  9.82      6.94     1.39  5704335     0.00     0.00  tcmapget
  9.32      8.26     1.32 44590215     0.00     0.00  tclistval
  4.87      8.95     0.69  5000000     0.00     0.00  tcbdbgetimpl
  4.45      9.58     0.63 15078730     0.00     0.00  tcmemdup
  4.45     10.21     0.63  5078123     0.00     0.00  tcbdbleafload
  3.46     10.70     0.49  5000000     0.00     0.00  tcbdbget
  3.32     11.17     0.47  4921875     0.00     0.00  tcbdbgethistleaf

QDBMとの対抗上では、ハッシュデータベースの格納をより高速化する必要があります。しかし、tcbdbwriterec関数は空間効率を向上させるためにQDBMよりも複雑な計算をせざるを得ず、かつ既に限界まで最適化しているので、今回は特にいじらないことにしました。tchdbbidx関数も同様です（以前話題にした37の掛算は (h<<5)+(h<<2)+h に展開されています）。

残るフロンティアはB+木データベースです。これはBerkeley DBと性能が拮抗している部分でもありますので、もうちょい頑張って突き放したいところです。しかも、よく見るとまだまだ最適化の余地がありそうです。特に、tcbdbcmplexicalやtclistvalの呼び出し回数が多いのがわかりやすいですね。tcbdbcmplexicalが4303万回、tclistvalが7600万回ですから、つまり1レコードあたり43回とか76回とか呼ばれているわけです。

インライン化しよう

システムコールの呼び出しが大きなオーバーヘッドになるというのはわかりやすいですが、通常の関数の呼び出しもなにげにオーバーヘッドが大きいのです。C99やC++ではそれを削減するために、関数のコードを呼び出し側に埋め込むインライン関数という機構があります。しかし、それには制限があって、同じコンパイル単位でないとインライン展開されなかったり、複雑過ぎるとインライン展開されなかったりします。そこで、インライン展開を確実にするために、古式ゆかしいマクロを使います。

tcbdbcmplexicalはデフォルトの比較関数なのですが、アプリケーション側から渡されるポインタを介して呼び出されるので、コンパイラの能力ではインライン化は絶対にできません。マクロ化にするにはまず、ポインタがtcbdbcmplexicalであることを調べてから、そうである場合にはtcbdbcmplexicalに相当するコードのマクロを実行するようにします。例は以下のような感じです。マクロをdo-whileで包んでいるのは、式ではなく文として使用することを強制するためです。

マクロ化以前:
int tcbdbcmplexical(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
  assert(aptr && asiz >= 0 && bptr && bsiz >= 0);
  int min = asiz < bsiz ? asiz : bsiz;
  for(int i = 0; i < min; i++){
    if(((unsigned char *)aptr)[i] != ((unsigned char *)bptr)[i])
      return ((unsigned char *)aptr)[i] - ((unsigned char *)bptr)[i];
  }
  if(asiz == bsiz) return 0;
  return asiz - bsiz;
}
...
  bdb->cmp = tcbdbcmplexical;
...
  int rv = bdb->cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, bdb->cmpop);

マクロ化以後:
#define TCCMPLEXICAL(TC_rv, TC_aptr, TC_asiz, TC_bptr, TC_bsiz) \
  do { \
    (TC_rv) = 0; \
    int _TC_min = (TC_asiz) < (TC_bsiz) ? (TC_asiz) : (TC_bsiz); \
    for(int _TC_i = 0; _TC_i < _TC_min; _TC_i++){ \
      if(((unsigned char *)(TC_aptr))[_TC_i] != ((unsigned char *)(TC_bptr))[_TC_i]){ \
        (TC_rv) = ((unsigned char *)(TC_aptr))[_TC_i] - ((unsigned char *)(TC_bptr))[_TC_i]; \
        break; \
      } \
    } \
    if((TC_rv) == 0) (TC_rv) = (TC_asiz) - (TC_bsiz); \
  } while(false)

int tcbdbcmplexical(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
  assert(aptr && asiz >= 0 && bptr && bsiz >= 0);
  int rv;
  TCCMPLEXICAL(rv, aptr, asiz, bptr, bsiz);
  return rv;
}
...
  bdb->cmp = tcbdbcmplexical;
...
  if(bdb->cmp == tcbdbcmplexical){
    TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
  } else {
    rv = bdb->cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, bdb->cmpop);
  }

実行時にif文が余計に入るのですが、それでも関数呼び出しのオーバーヘッドに比べればマシなようです。この改善（というか改悪というか）を行ってからまた性能測定をしてみたのですが、良好な結果が出ました。これだけでスループットが4%も向上したことになります。消費税が免除されたくらい家計に嬉しいですよね。

ひとまずの結果

tclistvalやその他のユーティリティAPI関数のインライン化も進めた結果、かなりの改善を見ることができました。改善後のプロファイルを見ると、当然ですが、インライン化された関数の呼び出しは消滅しています。余談ですが、writeの上位9位までの関数で実行時間の約80%を使っているのですが、その行数の合計はたった376行です。今回のテストに関連するコード（tctest.c, tcutil.c, tchdb.c, tcbdb,c）の合計は約11000行ですから、コードの3.5%で実行時間の8割が使われるというネタが得られました。

write:
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 26.89      2.92     2.92  5000000     0.00     0.00  tcbdbleafaddrec
 14.46      4.49     1.57  5637861     0.00     0.00  tcmapget
 13.44      5.95     1.46  5480393     0.00     0.00  tcmapmove
  6.91      6.70     0.75  4843752     0.00     0.00  tcbdbgethistleaf
  5.89      7.34     0.64    78125     0.00     0.00  tcbdbleafsave
  3.59      7.73     0.39  5000000     0.00     0.00  tcbdbputimpl
  3.59      8.12     0.39    78123     0.00     0.00  tcbdbleafdivide
  3.22      8.47     0.35   156250     0.00     0.00  tcbdbleafdatasize
  2.95      8.79     0.32    78124     0.00     0.00  tcbdbleafcacheout
  2.76      9.09     0.30        1     0.30    10.86  procwrite

read:
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 29.20      2.78     2.78  5000000     0.00     0.00  tcbdbsearchrec
 16.39      4.34     1.56  5704335     0.00     0.00  tcmapget
 14.08      5.68     1.34  5468133     0.00     0.00  tcmapmove
  8.51      6.49     0.81  5078123     0.00     0.00  tcbdbleafload
  5.46      7.01     0.52  4921875     0.00     0.00  tcbdbgethistleaf
  3.68      7.36     0.35   156248     0.00     0.00  tcbdbsearchleaf
  3.47      7.69     0.33  5000000     0.00     0.00  tcbdbget
  3.47      8.02     0.33        1     0.33     9.52  procread
  3.26      8.33     0.31    78124     0.00     0.00  tcbdbleafcacheout
  2.42      8.56     0.23  5000000     0.00     0.00  tcbdbgetimpl

そしていよいよ性能測定の結果発表です。結果は以下のようになりました。writeで18%、readで14%ほどスループットが向上したことになります。

現状のベンチマークテストの結果を、他のDBMの結果とも合わせて掲示します。

関数のインライン化やループのアンロールはやれば簡単にできるし際限なくやってしまいがちなのですが、もうこのくらいにしておかないと保守できなくなりそうです。インラインアセンブラとかいう声も聞こえてきそうですが、今は聞こえないことにします。

まとめ

手工芸的なコード最適化は、プロファイルをとった上で、有効な部分だけに絞って実施しましょう。関数の実行時間が大きいものから無駄がないか検討するのです。また、関数の呼び出し回数が多いものは、マクロなどを駆使してインライン化をすると有効です。TCでやってみたところ、最大約18%のスループット向上を達成することができました。

繰り返しになりますが、ベンチマークテストの結果に一喜一憂するのは愚かしいことです。アルゴリズムやデータ構造を見直すならまだしも、コード最適化による性能改善なんてのはたかが知れています（別の環境ではむしろ遅くなっているかもしれません）。ぶっちゃけて言えば、半分は見栄で、残り半分は自己満足にすぎないのです。むしゃくしゃしてやってしまいましたが、今は反省しています。

余談ですが、rskyさんによるTCのPHPのバインディングが出ました（パチパチパチパチ）。ミクシィ社内でTCを使う機会って実はそんなにないので、各種バインディングの登場で世の中でのユースケースが出やすくなるのは作者冥利につきますね。

世田谷の某所から原宿まで自転車通勤しているのですが、そろそろ寒くなってきたので電車に切り替えようかと悩み中のmikioです。今回はTokyo Cabinetのスクリプト言語バインディングについて述べます。

スクリプト言語バインディングとは

TCはC言語で実装されたライブラリで、C言語（C89、C99）およびC++言語のプログラムから利用することができます。CやC++は各種の計算処理やシステムコールの呼び出しを直接的に記述できるので高速に動作するプログラムを作ることができる反面、ポインタ演算やメモリ管理などで致命的なバグを潜ませやすいので非常に注意深くコーディングを進めなければいけません。つまり、プログラムの実行速度は速いが、開発速度は遅いということです。

それに対して、PerlやRubyをはじめとするいわゆるスクリプト言語は、実行速度はCやC++に劣るものの、高水準かつ直感的な文法と強力なライブラリ群によって楽に素早く開発を進めることができます。mixiのシステムの多くの部分がPerlで記述されているのはそのためです。

プログラムの実行時間の8割9割がコードの1割2割の部分（ホットスポット）で費されるという経験則は広く知られているところです。したがって、ホットスポットをCで記述して実行効率の改善を図り、ホットスポット以外をスクリプト言語で記述するという手法がよく行われています。そうすれば、実行速度と開発速度の双方を高めることができるのです。そこで、CやC++で書かれたモジュールを各種のスクリプト言語から呼び出せるようにする機構が必要になりますが、それをスクリプト言語バインディングと呼びます。

データベースを使うアプリケーションでは、ホットスポットはデータベースを操作する部分であることがほとんどです。DBMのアプリケーションもその例外ではありません。そこでTCのスクリプト言語バインディングの登場です。Cで書かれた高速なDBMをスクリプト言語で楽々操作するなんて、幸せなことじゃないですか。

基本的な構造

基本的に、C言語のプログラムは関数として記述されます。全ての処理は関数の中に書かれ、個々の処理は関数を呼び出すことで実行されます。コマンドラインで実行される場合も結局はmain関数が呼び出されることで処理が開始されるわけです。したがって、スクリプト言語の処理系からC言語のプログラムを実行する際にも、必ず関数を呼び出す形になります。この構造は、Perlから呼ぶ場合でも、RubyからでもJavaからでもPythonからでもPHPからでも同じなので、1つの言語でのバインディングの書き方を覚えれば、他の言語でも比較的楽に進めることができます。細かい手順については残念ながら各種の処理系でまちまちのノウハウを学ばなければなりませんが、既に公開されているパッケージを真似すればそれほど迷うことはないでしょう。特にDBMの言語バインディングは例として最適です。Rubyの拡張ライブラリのマニュアルでもDBMが題材として使われているくらいです。

スクリプト言語から何とかしてCの関数を呼ぶということはわかったとして、次に以下のことを学ぶ必要があります。各言語ごとにAPIが整備されているので、対象の言語で具体的にどういう手順になるかを下調べしておくとよいでしょう。

• Cの関数が入ったライブラリをロードする。
• Cの関数を呼び出す。
• 関数の引数として渡すために、スクリプト言語のオブジェクトをCのオブジェクトに変換する。
• 関数の戻り値を受け取るために、Cのオブジェクトをスクリプト言語のオブジェクトに変換する。
• Cのオブジェクトとスクリプト言語のオブジェクトのスコープと寿命を操作する。

その他に、作ったモジュールをインストールする方法やパッケージを作ったり配布したりする方法についても知っておく必要があります。

まずはPerlバインディング

正直言って私はPerlが苦手なのですが、Perlが強力な言語であり弊社や世の中の多くのシステムを支えている事実は個人的な好みを超越するところです。ということでTCのPerlバインディングの作成にまずは着手したわけですが、Perlの仕組みをCの側から見ることで、魔術的だと思っていた部分のカラクリがわかるようになり、少しずつPerlが好きになってきました。

Perlバインディングの作り方の全手順を紹介すると雑誌の特集並の分量になってしまうので、ここでは雰囲気がわかるくらいの説明を試みます。まずは、TCをPerlだけで書くつもりになって、インターフェイスだけをTokyoCabinet.pmというモジュールとして定義します。名前空間はTokyoCabinetにして、その中にHDB（ハッシュデータベース）とBDB（B+木データベース）のクラスを定義しましょう。HDBのコード例はこんな感じです。

package TokyoCabinet::HDB;
require XSLoader;
our $VERSION = '1.0';
XSLoader::load('TokyoCabinet', $VERSION);

sub new {
  my $class = shift;
  my $self = [0];
  $$self[0] = TokyoCabinet::hdb_new();
  bless($self, $class);
  return $self;
}

sub open {
    my $self = shift;
    my $path = shift;
    my $omode = shift;
    return TokyoCabinet::hdb_open($$self[0], $path, $omode);
}

sub close {
    my $self = shift;
    return TokyoCabinet::hdb_close($$self[0]);
}

リストへの参照にblessしてオブジェクトとして扱えるようにして、openとcloseというメソッドを定義しているというところはいたって普通ですね（スカラへの参照をblessしてもいいのですが、後で何か拡張したくなる予感がするのでリストを使っています）。見慣れないのは、XSLoaderというモジュールを取り込んで、そのload関数を呼んでいるところです。これはCで実装したライブラリのコードを呼び出せるようにする手順です。これによって、TokyoCabinet.soというライブラリを読み込んで、その中の関数を呼び出すことができるようになります。そして、TokyoCabinet::hdb_new() はTokyoCabinet.soの中にあるhdb_newという関数を呼び出すようになるわけです。

さて、ここからが本番です。Perlから呼び出すCの関数をXSUBと呼びます。XSUBは、XSというプリプロセッサの書式とCのコードを混在させて記述します。XSの主な仕事は、XSUBの呼び出し元であるPerlから渡されるPerlのオブジェクト（スカラや配列やハッシュ）をCのオブジェクトに変換することと、XSUBが終了した際にPerl側に返されるCのオブジェクトをPerlのオブジェクトに変換することです。hdb_newの例を見てみましょう。

void *
hdb_new()
PREINIT:
        TCHDB *hdb;
CODE:
        hdb = tchdbnew();
        tchdbsetmutex(hdb);
        RETVAL = hdb;
OUTPUT:
        RETVAL

TCのAPIを叩いてハッシュデータベースオブジェクトを作ってそのポインタをPerl側に返しています。先頭行の「void *」は「ポインタを返す」という意味です。その次の「hdb_new()」は「名前がhdb_newで、引数はない」という意味です。「PREINIT:」のセクションではXSUBの中で使うローカル変数を宣言しています。「CODE:」のセクションは実際のCのコードです。ここで「RETVAL」というのが唐突に出てきますが、これは冒頭で「void *」と宣言したCのオブジェクトをPerlで扱える状態で格納するための変数っぽいものだと思ってください。ここではデータベースオブジェクトのポインタを返したいのでそれをRETVALに入れます。そして最後に「OUTPUT:」のセクションでRETVALに入っているデータをPerl側に返すことを指示します。

hdb_newが返したポインタはPerlの世界では数値のスカラとして扱われるわけですが、それを他のメソッドに渡してまたCのポインタに戻せば、Cの世界ではそれをTCのAPIに渡して通常どおりにプログラミングができるわけです。次にhdb_openの例を見てみましょう。

int
hdb_open(hdb, path, omode)
        void *  hdb
        char *  path
        int     omode
CODE:
        RETVAL = tchdbopen(hdb, path, omode);
OUTPUT:
        RETVAL

Perl側でhdb_newの戻り値を$$self[0]に代入し、それがめぐりめぐってhdb_openの引数として渡されることになります。そしてXSの「void * hdb」の部分で1番目の引数をポインタとして扱うと宣言しておくことで、変数hdbには以前にhdb_newで作ったポインタがきちんと入っていることになるわけです。pathやomodeも、C側で期待する型を宣言しておけば、XSが勝手にそれっぽく変換た値を代入してくれます。あとは何事もなかったかのようにCでプログラムを書けばよいのです。ちなみにtchdbopenは処理の成否を真偽値で返すので、それをintとして返すことでPerl側のアプリケーションが処理の成否を判断できるようにしています。

念のためhdb_closeの例も見てみましょう。hdb_openの時と要領は同じですね。こんな感じで、その他のメソッドもバシバシ書いていけばよいのです（むしろ単調すぎる作業で、長時間やってると目がショボショボしてきます）。

int
hdb_close(hdb)
        void *  hdb
CODE:
        RETVAL = tchdbclose(hdb);
OUTPUT:
        RETVAL

XSで書いたプログラムは、TokyoCabinet.xsという名前にして、TokyoCabinet.pmと同じ場所に置いておきます。あとは通常のMakefile.PLを使ったパッケージングをすれば、めでたくTCのPerlバインディングの完成です。思ったより簡単ですよね？ びびんないでやってみれば案外できるもんなんです。作成したモジュールを使うサンプルアプリケーションはこんな風になります。

そしてRubyバインディング

Rubyの場合はもっと簡単で楽しいです。ガベージコレクタのおかげでPerlでてこずることになるオブジェクトの寿命管理（リファレンスカウント）の問題に煩わされずに済みます。しかも、PerlバインディングではPerlで書かれたpmファイルとC（とXSマクロ）で書かれたxsファイルを組み合わせていましたが、RubyバインディングはCだけで記述できます（Perlでも同様のことはできますが、より繁雑です）。rbファイルすらいらないんです。tokyocabinet.cというファイルにこんなようなことを書きます。

#include "ruby.h"
#include <tchdb.h>

VALUE mod_tokyocabinet;
VALUE cls_hdb;
VALUE cls_hdb_data;

static VALUE hdb_initialize(VALUE vself){
  VALUE vhdb;
  TCHDB *hdb;
  hdb = tchdbnew();
  tchdbsetmutex(hdb);
  vhdb = Data_Wrap_Struct(cls_hdb_data, 0, tchdbdel, hdb);
  rb_iv_set(vself, "ptr", vhdb);
  return Qnil;
}

static VALUE hdb_open(VALUE vself, VALUE vpath, VALUE vomode){
  TCHDB *hdb;
  const char *path;
  int omode;
  Check_Type(vname, T_STRING);
  path = RSTRING(vname)->ptr;
  omode = (vomode == Qnil) ? HDBOREADER : NUM2INT(vomode);
  vhdb = rb_iv_get(vself, "ptr");
  Data_Get_Struct(vhdb, TCHDB, hdb);
  return tchdbopen(hdb, path, omode) ? Qtrue : Qfalse;
}

static VALUE hdb_close(VALUE vself){
  VALUE vhdb;
  TCHDB *hdb;
  vhdb = rb_iv_get(vself, "ptr");
  Data_Get_Struct(vhdb, TCHDB, hdb);
  return tchdbclose(hdb) ? Qtrue : Qfalse;
}

int Init_tokyocabinet(void){
  mod_tokyocabinet = rb_define_module("TokyoCabinet");
  cls_hdb = rb_define_class_under(mod_tokyocabinet, "HDB", rb_cObject);
  cls_hdb_data = rb_define_class_under(mod_tokyocabinet, "HDB_data", rb_cObject);
  rb_define_method(cls_hdb, "open", hdb_open, 2);
  rb_define_method(cls_hdb, "close", hdb_close, 0);
}

一見複雑そうですが、部分部分を見ていけばわかりやすい構造になっています。まずは、hdb_initializeに着目してください。Rubyの世界のオブジェクトはCの世界では全てがVALUEという型のオブジェクトとして扱うことができます（美しい！）。引数のオブジェクトをvselfという変数で受けていますが、これはもちろんレシーバオブジェクトです。Data_Wrap_StructというのはCのオブジェクトへのポインタをRubyのオブジェクトとして扱えるようにするものです。ここでポインタとtchdbdelを関連付けているのが重要なところで、ガベージコレクタでRubyのオブジェクトが回収された際にポインタの先にあるCのオブジェクトもきちんと片付けるように指示できるのです。そして、rb_iv_setは、ポインタをラップしたオブジェクトを “ptr” という名前でレシーバのプロパティとして持たせて、後で使えるようにしています。

次にopenを見ましょう。引数としてレシーバの他にvpathとvomodeを受け取っています。vpathは文字列であることが期待されていますので、Check_Typeで文字列オブジェクトであることを確認して、それがわかったところで安心してRSTRINGというマクロでキャストしてCの文字列のポインタを取得しています。vomodeは数値であることが期待されているので、NUM2INTというマクロで数値を取り出しています（このマクロは同時に型チェックもやってくれます）。あとはhdb_initializeの時に “ptr” として持たせておいたデータベースオブジェクトを取り出して、TCのAPIを叩きます。

最後にInit_tokyocabinetを見てください。モジュール名の前に「Init_」をつけた関数がライブラリのロード時に呼び出されることになっています。中では、rb_define_moduleで”TokyoCabinet”というモジュールを定義した上で、その配下に”HDB”や”HDB_data”というクラスを定義しています。”HDB”はユーザに公開するクラスで、”HDB_data” はポインタをラップするための内部クラスです。そして、rb_define_methodでCの関数をクラスのメソッドとして関連付けています。

パッケージの方法も特に難しいことはなく、extconf.rbを使って楽々できます。C言語だけでRubyの処理系を使ったプログラムができるってのは、逆転の発想で何だか面白いですよね。作成したモジュールを使うサンプルアプリケーションはこんな風になります。

まとめ

実行時の性能が求められる部分は、最適なアルゴリズムをカリカリにチューンしたCで記述して悦に浸りましょう。それ以外の部分は、お好みのスクリプト言語で書きやすく読みやすいコードを記述して、人に愛されるソフトウェアをばんばん作っていきましょう。

TCのPerlバインディングとRubyバインディングは既にリリースしていますし、Javaバインディングも目下開発中です。それらは私がメンテナンスしていきます。私の知る限りでは、他にもPythonバインディングとPHPバインディングを書いている方々がおられますので、UNIX系のほとんどプログラマにはTCを使っていただけるようになると思います。

その他の言語バインディングも作ってやろうという方、大歓迎です。その際には、こちらのIDL（インターフェイス定義言語）を参考にしてAPIを設計していただけると、使い方が習得しやすくなってより喜ばれると思います。

そもそも「スクリプト言語バインディング」という言い方はC言語側からの視点で、スクリプト言語側から見れば「C言語による拡張モジュール」です。拡張モジュールを使うとプログラミングの世界がものすごく広がります。詳しいやり方は「プログラミングPerl」や「プログラミングRuby」でわかりやすく説明されているので、それらを見ながらぜひ挑戦してみてください。

追記：ほぼXSだけでモジュールを作るサンプルを小山浩之氏が作ってくれましたので、そちらも参考になるかと思います。

ミクシィ研究開発グループでは定期的に社内で人を集めて研究進捗などの情報共有と交流を目的とした会を開いています。

研究開発グループは全社的にブラックボックス的に見られる事があり、例えばときどき”トールさんってどんな事をしてる人なんですか？”とコーヒーをすすっている時に聞かれる事があります。こういった状況は言うまでもなくよくありません（組織内での情報共有がなっていない事を示すから）。こういった理由から友の会が開催されました。友の会の発表は純粋に技術系の話ばかりですが、参加はスタッフであれば誰でも自由です。これは技術者だけでなく営業部や企画部などの参加者の方達から技術者以外の視点からの貴重な意見が頂けたりするからです。こういった狙いもあり我々はこの会に真剣に取り組んでいます。

又、同じグループメンバーでも私の専門外である高度なNLPテクニックを解り易くした話を聞けたりして勉強と刺激になります。モチベーションの向上にもつながるし話を聞いているだけで技術屋としての血が騒ぎますね。

友の会で発表した内容は私の一存では公表できませんが、ちょっとだけ公表すると、今回はmikioさんが最近リリースしたTokyo Cabinetの開発過程でマルチコアのアーキテクチャに最適化した際の苦労話や、QDBMの反省点、そしてTokyo CabinetがなぜQDBMより優れているかなどの話がありました。その他にはNLPを専門とする仲間達から機械学習を用いた文書分類に関する研究の話がありました。私は少し前にTechTargetで取り上げられたバタラさんの話に出てくるRDBMSを使わない効果的なソリューションの追求に関する進捗発表をしました。ぶっちゃけ、ガンガンスケールアウトできて、memcached級のスピードで形式を問わずデータの出し入れ、且つデータを永続的に保存できてHigh Availabilityの要求を満たす代物の追求ですね。

とまあ将来的に友の会が更に発展して外の人に来て頂いたり外のセミナーやカンファレンスで発表したいな～と思う今日この頃です。

余談ですが弊社が運営するインターネット求人広告事業のFind Job !が10周年を迎えました！冷静に考えると笠原さんがFind Job !のコードを書いていた時、私は13歳。そう考えるとなんかすごいっすね。おめでとうございます！

http://www.find-job.net/10th/