読者です 読者をやめる 読者になる 読者になる

mixi engineer blog

ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

DBMによるテーブルデータベース その四

algorithm

コアライブラリを一生懸命書くとユーティリティやバインディングなどの周辺機能がおろそかになり、逆も然りで、工数割り当てのジレンマが歯がゆいmikioです。今回は余談として、Tokyo Cabinetのテーブルデータベース(TCTDB)を作る途中で思いついた更新機能と性能検証について述べます。

アトミックな更新 再び

TCTDBで好評だったっぽいアトミックな更新機能をその他のデータベースでも実装してみました。例えばハッシュデータベース(TCHDB)では以下の関数が提供されます。

typedef void *(*TCPDPROC)(const void *vbuf, int vsiz, int *sp, void *op);

bool tchdbputproc(TCHDB *hdb, const void *kbuf, int ksiz,
                              const char *vbuf, int vsiz,
                              TCPDPROC proc, void *op);

関数tchdbputprocを呼び出す際には、kbufはキーのポインタ、ksizはキーのサイズ、vbufは初期値のポインタ、ksizは初期値のサイズを指定します。キーに該当するレコードがまだ無ければ、ここで指定したキーと値のレコードを新規に格納します。キーに該当するレコードが既に存在していた場合、procで指定したコールバック関数が呼ばれます。コールバック関数は、引数vbufとvsizで指定された既存の値を参照しつつ何らかの処理を行い、新しい値を記述した領域へのポインタを返します。その領域のサイズはspの参照先に格納します。引数opはtchdbputprocの引数opがそのまま渡ります。コールバック関数がNULLを返した場合、既存のレコードは変更されません。この一連の処理は全て該当のレコードに対してロックをかけてその中でアトミックに行われます。

...とかいう何だか複雑そうな話を聞いて便利そうだと思っていただける人がどれだけいるかわかりませんが、いわゆるCAS(compare and swap)という技法に使え、いわゆるセマフォをデータベース上で実現できるのがツボなのです。

ここで、「トイレの個室が空室か満室か」を管理する例を考えましょう。「満室ならば空室になるのを待ちつつ、空室ならば入って満室にし、用を足して、出て空室にする」とというフローを実装します。そして各々の個室が満室(full)か空室(empty)かの状態をTCHDBのレコードとして管理します。ここで重要なのは、「空室かどうか判断する」のと「入って満室にする」のをアトミックに行うことです。そうでないと、空室だと同時に判断した二人(2スレッド)が一つの個室に入るという悲劇が起こってしまいます。

void *enterroom(const void *vbuf, int vsiz, int *sp, void *op){
  if(vsiz == 4 && memcmp(vbuf, "full", 4) == 0) return NULL;
  *sp = 4;
  return strdup("full");
}

void poo(TCHDB *hdb, const char *room){
  int len = strlen(room);
  while(!tchdbputproc(hdb, room, len, "full", 4, enterroom, NULL)){
    printf("%s: waiting\\n", room);
    usleep(1000 * 1000);
  }
  printf("%s: Poo!\\n", room);
  tchdbput(hdb, room, len, "empty", 5);
}

実は、アクセス許可の二値(真偽)を管理したいのであれば、putprocを使わなくてもputkeep(無ければ作る)とout(消す)を利用するだけで実現可能です。しかし、三値以上の状態を管理したい場合や数値の範囲を条件にしたい場合にはputprocでないと勤まりません(もしくは外部にロックを持つしかない)。また、状態値にタイムスタンプを付与してデッドロックの検出に利用するのも一興でしょう。putprocはTCHDBだけでなくその他のDB(TCBDB/TCFDB/TCMDB/TCNDB/TCADB)にも実装してあるので、似たようなことにお悩みの方はぜひご活用くださいませ(とはいえ、ユーザが少なそうな機能なので「隠しAPI」扱いであり、ヘッダファイルにしか説明はありませんが)。

TT上でのテーブルデータベースの性能

TTのリモートデータベースAPI(TCRDB)に実装してあるテーブル拡張APIを使って、TT上のテーブルデータベースに対する各種操作の性能を計測しました。以前の記事に書いた通り、a,b,c,d,eの5つのコラムに文字列と数値を記録した100万件のレコードを格納し、その主キーによる取得と、文字列の完全一致による検索を実行します。サーバは「ttserver 'casket.tct#bnum=1000000#idx=str:lex#idx=num:dec#lcnum=4000」で立ち上げました。また、比較のために、ハッシュデータベースに対する100万件の読み書きの性能も測定しました。結果は以下になります。

TCTDBTCHDB
put102.04 (9800qps)41.12 (24319qps)
get50.97 (19619qps)41.01 (24384qps)
search53.80 (18587qps)-

この実験では、TTを経由するレコードの書き込みはTCHDBの40%程度のスループットになることがわかりました。一方でレコードの読み込みはTCTDBとTCHDBであまり差が出ないことがわかりました。また、検索クエリの実行とレコードの取得はほぼ同じスループットになることがわかりました。主キーによるアクセスではTCTDBとTCHDBの処理内容はほぼ同じであっても、レコードのサイズがTCTDBの方が大きくなる傾向にあるので、TCTDBの処理速度はTCHDBよりも遅くなるのが一般的です。TCを直接叩く場合にはread/writeやそれに伴うバッファリングのオーバーヘッドがレコード長に比例することによって両者に差が出ると考えられます。TTを経由する場合には、TCの層でのread/writeというよりもむしろ、TTの層でのsend/recvおよびそれに伴うバッファリングのオーバーヘッドがレコード長に比例することで差が出ると考えられます。

それにしても、TCTDBのTT経由の書き込み性能は読み込み性能に比べてよろしくないようです。多分、ttserverの実装がタコで、リクエストのデータが長い場合の処理効率をあまり考えていないことが原因だと思います。この点に関しては今後の課題として改善していくつもりです。

SSDで性能テストしてみた

近頃、HDD(Hard Disk Drive)に代わるストレージデバイスとしてSSD(Solid State Drive)が市場に出回って来ています。SSDはフラッシュメモリで作られているので、物理的に円盤とアームを動かすHDDに比べるとランダムアクセスの読み込みがとても速いらしいです。鬼のようにランダムアクセスを欲するDBMにはSSDはうってつけの技術ですよね。ということで、HDDに比べてどのくらい性能がよくなるのか調べてみました。

実施テスト内容
HASH-WRITE: ハッシュDBのシーケンシャル書き出し(tchtest write casket.tch ...)
HASH-READ: ハッシュDBのシーケンシャル読み込み(tchtest read casket.tch)
HASH-RANDOM: ハッシュDBのランダム書き出し(tchtest rcat casket.tch.rnd ...)
BTREE-WRITE: B+木DBのシーケンシャル書き出し(tcbtest write casket.tcb ...)
BTREE-READ: B+木DBのシーケンシャル読み込み(tcbtest read casket.tcb)
TABLE-WRITE: テーブルDBのシーケンシャル書き出し(tcttest write casket.tch ...)
TABLE-READ: テーブルDBのシーケンシャル読み込み(tcttest read casket.tch)
TABLE-RANDOM: テーブルDBのランダム書き出し(tcttest rcat casket.tch.rnd ...)
1000万レコードの結果
SSDHDDfile size
HASH-WRITE41.76661.560361,947,424
HASH-READ12.47312.511361,947,424
HASH-RANDOM124.1491525.510365,624,992
BTREE-WRITE9.6919.654244,107,264
BTREE-READ8.4578.452244,107,264
TABLE-WRITE83.492120.177717,176,384
TABLE-READ26.23925.962717,176,384
TABLE-RANDOM326.4326496.903795,370,720
1億レコードの結果
SSDHDDfile size
HASH-WRITE532.0141122.1103,602,657,584
HASH-READ147.523163.0963,602,657,584
HASH-RANDOM6864.622140365.0533,718,352,064
BTREE-WRITE104.700118.1662,063,838,208
BTREE-READ91.573103.1352,063,838,208
TABLE-WRITE1188.017(too slow)7,570,654,800
TABLE-READ422.496(too slow)7,570,654,800
TABLE-RANDOM15471.373(too slow)8,424,192,816

RAM容量が4GBのマシンで実験を行ったので、データベースファイルのサイズがファイルシステムのキャッシュとして使われる2GBくらいを越えたあたりで、ストレージデバイスへのアクセスが発生することになります。そして、1億レコードのTCHDBのランダムアクセス(上記のHASH-RANDOM)は、SSDだと14567qps、HDDだと712qpsでした。予想通り、巨大なDBMのランダムアクセスの性能において、SSDはHDDのおよそ20倍のスループットが出ることがわかりました。テーブルデータベースに関してもほぼ同じ傾向です。一方で、1億レコードのTCHDBのシーケンシャルアクセス(上記のHASH-WRITE)に関しては、SSDが2394292qps、HDDが1624431qpsということになりました。これも予想通りで、SSDが1.5〜2倍くらい速いという結果になっています。HDDが健闘している原因は、HDDの物理的特性がシーケンシャルアクセスに向いていて、またファイルシステムのキャッシュも有効活用されるためだと思われます。

ファイルシステムのキャッシュに乗らない規模のデータベースに対するランダムアクセスは、確実にストレージデバイスへのランダムアクセスを引き起こします。これは宿命であり、どんなに優れたアルゴリズムと実装をもってしても、1回のレコード参照は、1回以上のデバイスへのアクセスを伴います。この時点で、オンメモリの状態に比べると3桁の性能劣化になります。したがって、巨大なデータベースの性能を決めるのは、ストレージデバイスの性能です。ソフトウェアエンジニアとしては少し残念なことではありますが、DBMなどの単純な仕組みを採用してソフトウェア層を最適化する努力なんてのは、ハードウェア層の性能の前では誤差のようなものなのです。ということで、SSDサイコー! SSDとDBMのコンビでいろいろ遊べそうです。

まとめ

TCの新機能であるアトミックな更新について説明しました。アトミックな更新はセマフォに使えるので、並列処理のリソース管理を効率的に行うために有用です。また、TCTDBをTT経由で操作した場合の性能を測定しました。書き込みで10000qps弱、読み込みで20000qps弱のスループットが出ることがわかりました。SSDとHDDの比較も行いました。SSDを使うと、キャッシュに乗らない規模のハッシュデータベースでも15000qps弱のスループットが出ることがわかりました。

次回は、TTとテーブルデータベースを組み合わせて、保存期限付きのレコードを永続ストレージ上で管理する方法について説明します。