圧縮データベースを使おう

チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。

圧縮B+木

B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree���とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基づいてレコードを走査したりできる利点もあります。TCでもB+木をサポートしていて、データマイニングや全文検索のインデックスなどの用途で私もよく利用しています。

B+木は空間効率においても優れています。ページ単位で記憶領域を管理するので、レコード毎のオーバーヘッドが小さく、記憶領域のフラグメンテーションも起きにくいからです。その上、B+木の各ページを圧縮すると、データベースとしての検索や更新などの機能を保ったままで、空間効率をさらに向上させることができます。この手法を圧縮B+木と呼ぶことにします。

ZLIBとBZIP2

TCは以前からZLIBによる圧縮B+木をサポートしていました。チューニングのオプションとしてBDBTDEFLATEフラグを指定するとB+木がZLIB（Deflate）圧縮B+木として作成されます。ZLIBはgzipコマンドやPNGなどでも使われている、圧縮も伸長もそこそこ高速で、圧縮率もそこそこ良い、いわばバランスのとれた圧縮手法です。内部的にはLZ77というスライド窓を使った符号化とハフマン符号化を用いているそうです。

最新バージョンのTCでは、BZIP2もサポートするようになりました（そのおかげで、ビルドする際にbzlib.hが必要になりましたが）。チューニングのオプションとしてBDBTBZIPフラグを指定するとB+木がBZIP2圧縮B+木として作成されます。BIP2はbzip2コマンドで使われている、圧縮も伸長もあんまり高速ではないが、圧縮率はZLIBを上回る、いわばアーカイブ用の圧縮手法です。内部的にはBWTという並び替え処理とMTFという置換処理をした上でハフマン符号化を用いているそうです。

正直なところ、TCで利用する分にはZLIBで十分だと思っており、BZIP2を使う必要性は個人的にはまったく感じていません。とはいえ人によっては過去ログの保存などで少しでもデータベースを小さくしたいこともあるでしょうから、ZLIBと並んでポピュラーになってきたBZIP2をつけておくのは別に悪いことでもないかなと。

LZMA

アーカイブ的なユースケース（更新はあんまりしないが検索はたまにする）を考えるならば、極右的なLZMA（Lempel-Ziv-Markov chain-Algorithm）というアルゴリズムがあります。圧縮にものすごい時間がかかるが、圧縮率はBZIP2をさらに上回り、伸長はBZIP2よりも高速だという特徴があります。LZMAは7zipというアーカイバに組み込まれていて、SDKも公開されています。

しかし、このSDKがびっくりするほど使いづらいです。圧縮処理はC++で実装していながら伸長処理はCで実装していたり、C用のライブラリでは伸長処理しかできなかったり、APIの使い方がドキュメントを読んでもよくわからなかったりします。ということで、あんまり細かいことを考えずにメモリ上でLZMA圧縮およびその伸長を行うためのラッパーライブラリを作りました。zlibに倣って、lzmalibと名づけて公開いたします。こんな風に使います（ビルド時のリンカオプションには-llzmaをつけてください）。

#include <lzmalib.h>
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv){
  char *orig_buf, *comp_buf, *decomp_buf;
  int orig_size, comp_size, decomp_size;

  orig_buf = "A thin wrapper library of LZMA";
  orig_size = strlen(orig_buf);

  comp_buf = lzma_compress(orig_buf, orig_size, &comp_size);
  printf("compressoin: from %d to %d\n", orig_size, comp_size);

  decomp_buf = lzma_decompress(comp_buf, comp_size, &decomp_size);
  printf("decompression: from %d to %d\n", comp_size, decomp_size);

  free(decomp_buf);
  free(comp_buf);

  return 0;
}

ついでに、LZMAのPerlモジュールが外部コマンド呼び出しのものしかCPANになかったので、上述のlzmalibを使ったPerlモジュールも作りました。Compress-LZMA-Simpleとして公開しておきます。

LZO

リアルタイム的なユースケース（更新も検索もヘヴィにする）を考えるならば、極左的なLZO（Lempel-Ziv-Oberhumer）というアルゴリズムがあります。これは圧縮率は他の方式に負けますが、圧縮速度も伸長速度も爆速で、なんとmemcpyの2倍程度の時間で圧縮ができてしまうのです。これはすごいことで、readやwriteに伴うバッファ間のデータコピーを節約できる時点で、空間効率だけでなく時間効率をも向上させられる可能性を示しています。ディスクI/Oを伴う規模の探索や更新ではなおさらです。

LZOのAPIは大変使いやすく、Cはもちろん、Perlなどのスクリプト言語からも簡単に使うことができます。あんまり有名じゃないみたいですけど（私も圧縮に詳しい人に教えてもらえるまで聞いたこともなかった）、もっと流行してくれればなと思います。

TCへの組み込み方法

さて、LZMAやLZOもTCに組み込もうかと思ったのですが、この調子で各種の圧縮アルゴリズムをサポートしていくと私の首が回らなくなるのは明らかです。そこで、デフォルトでサポートするのはZLIBとBZIP2までにして、あとは外部モジュールとして組み込んでもらうようにしました。圧縮用の関数と伸長用の関数のポインタをTCのパラメータとして実行時に渡す方式です。例えばこんな感じで使います。

void *my_compress(const void *ptr, int size, int *sp, void *op){
  return lzma_compress(ptr, size, sp);
}

void *my_decompress(const void *ptr, int size, int *sp, void *op){
  return lzma_decompress(ptr, size, sp);
}

int main(int argc, char **argv){
  TCBDB *bdb;
  bdb = tcbdbnew();
  tcbdbsetcodecfunc(bdb, my_compress, NULL, my_decompress, NULL);
  tcbdbopen(bdb, "casket", BDBOWRITER | BDBOCREAT);
  ...
  tcbdbclose(bdb);
  tcbdbdel(bdb);
}

my_compressとmy_decompressはmallocされた領域を返すものとし、その領域はTC内部で自動的にfreeされます。なお、この機構（tcbdbsetcodecfunc）はあまりにマニアックすぎるので、HTMLのドキュメントには乗せない「隠しAPI」にしています。詳細に関してはtcbdb.hなどのヘッダファイルをご覧ください。

性能比較

B+木の更新と探索に関する空間効率と時間効率を測定してみました。/usr/share/dict/wordsにある英単語98569語の各々をキーとして、各キーに0〜9999のランダムな値を割り当てたレコードを格納したB+木データベースを作り、その全件を探索するテストを行ったところ、結果は以下のようになりました。

	作成時間合計	探索時間合計	サイズ
元データ	-	-	1413434
非圧縮	0.164	0.097	1586432
DEFLATE	0.321	0.134	692992
BZIP2	0.460	0.312	620544
LZMA	2.429	0.299	594944
LZO	0.200	0.111	1003264

圧縮をするとしないとではデータベースのサイズが全然違うということはおわかりいただけると思います。ZLIBだと43.7%、BZIP2だと39.1%、LZMAだと37.5%に圧縮できているわけです。Deflateだと更新処理は195%の時間がかかりますが、検索処理は138%で済んでいます。BZIPやLZMAはそれよりも空間効率重視だということがわかります。LZMAはBZIP2より圧縮率が高く、探索もBZIP2よりも高速であることが確かめられました。逆にLZOは空間効率はそれほど向上しませんが、更新処理は121%、検索処理は114%の時間で済むことが確かめられました。

LZMAは圧縮処理が遅すぎるので利用できるユースケースは限られると思いますが、キーワード検索やIMEの辞書などのデータベースを圧縮する用途ではLZMAはかなり有望だと思います。LZOは処理速度がほとんど劣化しないので、非圧縮にするくらいならいつもLZOを適用したいくらい活躍するかもしれません。

まとめ

B+木を圧縮して利用する、TCの圧縮B+木の使い方と性能について説明しました。要求される処理速度がそれほどタイトでない場合、圧縮B+木の使用を検討してみてください。更新が頻繁ならLZO、更新をほとんどしないならLZMA、その中間ならZLIBやBZIP2がおすすめです。

実はこのネタはQDBMの時代にもさんざんやっているのですが、やはり圧縮アルゴリズムをコールバック関数呼び出しにして外部化したところがTCのポイントかなと。外部化と言えば、B+木のストレージ層（現状ではハッシュDB）を外部化してTTなどに置き換えると分散B+木になるなんて話も考えていたりしますが、実用になるかどうかは謎です。

最後に蛇足ですが、ZLIBのパッケージをtar.gzで配布するのってちょっと意地悪ですよね。