圧縮データベースの性能評価

各種圧縮アルゴリズムの性能について前回の記事で検討したが、それを実際にデータベースライブラリに組み込んだ。Tkrzw-0.9.30から利用できる。今回は、実際に英和辞書のデータベースを圧縮してみて、どのくらい効果があるのかを確かめてみる。

結論としては、圧縮を適用するのであればZStdを使うのが良い。ハッシュ表のデータベースではファイルサイズが57%に減りつつ、29万QPSで伸長処理が行える。B+木のデータベースではファイルサイズが37%に減りつつ、12万QPSで伸長処理が行える。B+木とLZ4の組み合わせもなかなか有望で、52%の圧縮率を達成しつつ、性能劣化が非常に軽微で済む。

実験対象の英和辞書は、統合英和辞書のデータである。元来はHashDBM（ハッシュ表）のデータベースで、レコード数は246469だ。圧縮前のデータベースサイズは175MBだ。レコードの実データのみをTSVにすると171MBだ。レコードのキーは「apple」「have」などの英単語の文字列で、値は以下のようなJSON形式の語義説明だ。

[{"word":"Tokyo","pronunciation":"toʊ.ki.oʊ","item":[{"label":"wn","pos":"noun","text":"the capital and largest city of Japan; the economic and cultural center of Japan [-] [translation]: 東京, 日本の首都, 江戸 [-] [synonym]: Edo, Tokio, Japanese capital, capital of Japan, Yedo [-] [hypernym]: national capital [-] [synset]: 08923348-n"},{"label":"we","pos":"noun","text":"[translation]: (capital of Japan) 東京"},{"label":"we","pos":"noun","text":"The Japanese government."},{"label":"wj","pos":"noun","text":"東京。"}],"probability":".0016106","share":".911","translation":["東京","江戸","日本の首都"],"related":["Edo","Yedo","Tokio","Japanese capital","capital of Japan","national capital","Tokyoite"],"cooccurrence":["japan","japanese","university","tv","osaka","metro","metropolitan","prefecture","at","station","international","art","line","from","on","in"]}]

この辞書を各種のアルゴリズムで圧縮して、かかる時間と出力ファイルのサイズを調べる。データベースの再構築処理（tkrzw rebuild）コマンドを実行するわけだが、無圧縮の処理時間も調べる。また、元の無圧縮状態に戻すように再構築処理をかけて、それにかかる時間も調べる

	圧縮時間(全体)	圧縮時間(純粋)	復元時間(全体)	復元時間(全体)	サイズ	圧縮率
無圧縮	0.700	0.000	0.700	0.000	175089275	1.000
ZLib	10.737	10.037	1.942	1.242	94044925	0.537
ZStd	2.730	2.030	1.528	0.828	101286939	0.578
LZ4	0.937	0.237	0.739	0.039	127672575	0.729
LZMA	187.4	186.7	6.203	5.503	110281053	0.629

まず、圧縮率に着目する。意外にも、LZMAでなくZLibが最善という結果になった。レコード毎に圧縮するので、LZMAの利点が活かしきれないのだろう。ZStdはZlibにやや劣るという結果になった。LZ4の圧縮率はZLibやZStdよりもだいぶ劣る。

次に、処理時間に着目する。「圧縮時間（全体）」と「復元時間（全体）」は、再構築処理で実際にかかった時間である。無圧縮でかかった0.7秒は圧縮や伸長とは関係ない時間なので、それを差し引いたのが「圧縮時間（純粋）」と「復元時間（純粋）」の値である。レコード数246469をそれらの値で割ると、圧縮と伸長の時間性能がわかる。

	圧縮QPS	伸長QPS
ZLib	24556	198445
ZStd	121413	297667
LZ4	1039953	6319717
LZMA	4737	44788

圧縮や伸長の処理にはCPUパワーのみを使うので、CPUのコア数が増えるほどにスケールする。よって、マルチスレッドでの性能はコア数の分だけ上がるはずだ。一方で、I/Oはそれほど単純にはスケールしない。I/Oがボトルネックになる場合には、CPUは遊んでいるだけになるので、だったら圧縮した方が得になる。

ZStdが示す、圧縮12万QPS、伸長29万QPSというのは、デバイスのI/O性能（SSDの場合）と同じようなスケールで勝負している印象だ。実際のところ、ファイルサイズ175MBというのは実メモリに普通に乗る規模ではあるが、より大きな辞書や多数の辞書を同時に運用する場合には、キャッシュに乗り切れずにI/Oが頻繁に発生する可能性がある。圧縮12万QPSというのは、更新の要求QPSが12万よりも大分小さい場合にのみ利用可能であるということを意味している。伸長29万QPSというのは、検索の要求QPSが29万よりも大分小さい場合にのみ利用可能であるということを意味している。I/Oがボトルネックになる場合には、非圧縮でもそれらより遅くなる場合があるので、その際には圧縮した方がスループットが向上するかもしれない。

LZ4が示す、圧縮103万QPS、伸長631万QPSというのは、デバイスのI/Oの性能に比べて桁違いに速い。レイテンシに換算すれば、1/6319717秒なので、ほとんど無なのだ。圧縮率の0.729というのはあまり魅力的な数値ではないが、それでも、時間性能にほとんど影響を与えることなく、データベースファイルのサイズを減らせるのは嬉しいだろう。つまり、値のサイズがある程度大きいことが分かっている場合には、LZ4をつけて損はない。ちょっと遅くなると言っても、JSONのパースより速いだろう。ボトルネックにはなり得ない些末なオーバーヘッドなので、無視できる。

ZLibは意外にも圧縮率がLZMAを上回った。とはいえ圧縮速度も伸長速度もZStdに負けているので、あまり良いところがない。そして、下馬評通り、LZMAは圧縮速度がめちゃめちゃ遅い。復元速度はマシな方なので、一旦作ったらほとんど更新しないようなデータベースでは役立つかもしれない。とはいえ、今回の条件では、圧縮率がZStdに負けているので、LZMAの出番はない。

HashDBMだとレコード単位で圧縮を行うので、データベースならではの利点は薄い。アプリケーション側で圧縮したデータを格納しても同じ結果になるはずだからだ。圧縮や伸長のためのコードを書かなくて済むのは嬉しいが、逆に言うとその程度の利点でしかない。一方で、TreeDBMでの圧縮はより意味がある。ページ単位で圧縮伸長がなされるからだ。TreeDBMにおいて、B+木の各ノードはシリアライズされてHashDBMに格納されるのだが、その際に圧縮が適用されるのだ。すなわち、HashDBMが圧縮伸長をサポートしたことで、TreeDBMは圧縮B+木のデータベースとして機能するようになった。

ページ単位で圧縮伸長を行うということは、レコードにアクセスする度に、ページ全体の圧縮伸長をするということなので、空間効率が向上する代償に時間効率は悪化する。あるレコードにアクセスした際に、該当するページがTreeDBM内のキャッシュにヒットしなかった場合には、そのページがHashDBMから取り出されて、その際にページ全体の圧縮データの伸長処理がなされる。あるレコードが更新された場合、該当のページがHashDBMに書き戻されるわけだが、その際にページ全体のデータの圧縮処理がなされる。

圧縮B+木としてのTreeDBMの性能を測定していこう。例によって統合英和辞書の再構築処理の時間を測る。

	圧縮時間(全体)	圧縮時間(純粋)	復元時間(全体)	復元時間(全体)	サイズ	圧縮率
無圧縮	0.567	0.000	0.567	0.000	173908640	1.000
ZLib	5.950	5.383	1.302	0.735	62243656	0.357
ZStd	1.473	0.906	0.915	0.348	66003437	0.379
LZ4	0.662	0.095	0.625	0.058	91260509	0.524
LZMA	58.80	58.24	4.083	3.516	62662916	0.360

圧縮伸長処理のスループットは、ページ数の43143を「圧縮時間（純粋）」と「復元時間（純粋）」で割って算出する。

	圧縮QPS	伸長QPS
ZLib	8014	58697
ZStd	47619	123974
LZ4	454136	743844
LZMA	740	12270

予想通りの結果で、圧縮率が向上した代わりに、スループットは落ちている。それでも伸長のスループットはZStdで12万QPS、LZ4で74万QPSが出ているので、それで十分なユースケースも多いだろう。例えばデスクトップアプリ用の辞書であれば、検索クエリのレイテンシが8マイクロ秒増えることは全く問題にならないだろう。サーバ用途でも、マルチスレッド化してスループットが5倍くらいに増すことを前提とすれば、60万QPSや370万QPSがボトルネックになることはあまりないだろう。

TreeDBMではB+木のノードのサイズを調整できる。デフォルトでは8KBで分割するので、レコードをキーの順序で登録した場合、多くのページは4KBほどになり、圧縮もそのサイズのデータで行われる。これをもっと大きくすれば、圧縮率はより向上するが、ランダムアクセスの性能は低下する。アーカイブ用途の場合にはページをもっと大きくすべきで、参照や更新の頻度が高い場合にはページを小さくするべきだ。

LZMAは小さいデータの圧縮には不向きなので、今回の実験で示した平均4KBの圧縮というのは苦手なユースケースなのだろう。LZMAの名誉のために平均64KBのページサイズになるようにチューニングしてみたところ、圧縮率は0.236にまで向上した。同じ条件でZLibは0.263、ZStdは0.285、LZ4は0.408なので、LZMAの面目躍如といったところか。検索能力を保ったままサイズが1/4以下になるというのはなかなか凄い。

せっかく作った機能は使ってもらってなんぼなので、使い方を説明したい。まず、Pythonでの圧縮データベースの作り方。なお、圧縮モードは、正式には "RECORD_COMP_ZSTD" と指定することになっているのだが、接頭辞は無視できて、大文字小文字は区別されないので、"zstd" でも同じ意味になる。

import tkrzw

# B+木データベースを書き込み可能モードで開く。
dbm = tkrzw.DBM()
dbm.Open("casket.tkt", True, record_comp_mode="zstd")

# レコードを格納する。ページは勝手に圧縮される。
dbm.Set("apple", "赤くて甘酸っぱくて美味しい果物")
dbm.Set("banana", "猿が大好きな黄色い皮の滑りやすい果物")

# レコードを検索する。圧縮されていたページは勝手に伸長される。
print(dbm.GetStr("apple"))
print(dbm.GetStr("banana"))

# データベースを閉じる。
dbm.Close()

C++ではこんな感じになる。複数のデータベースクラスを単一のインターフェイスで操作する多相DBMのAPIを使ってみる。

#include <cstdio>
#include <tkrzw_dbm_poly.h>

int main(int argc, char** argv) {
  using namespace tkrzw;

  // B+木データベースを書き込み可能モードで開く。
  PolyDBM dbm;
  dbm.OpenAdvanced(
      "casket.tkt", true, File::OPEN_DEFAULT,
      {{"record_comp_mode", "zlib"}});

  // レコードを格納する。ページは勝手に圧縮される。
  dbm.Set("apple", "赤くて甘酸っぱくて美味しい果物");
  dbm.Set("banana", "猿が大好きな黄色い皮の滑りやすい果物");

  // レコードを検索する。圧縮されていたページは勝手に伸長される。
  std::puts(dbm.GetSimple("apple").c_str());
  std::puts(dbm.GetSimple("banana").c_str());

  // データベースを閉じる。
  dbm.Close();

  return 0;
}

コマンドラインツールでも同じことができる。

$ tkrzw_dbm_util create casket.tkt --record_comp zstd
$ tkrzw_dbm_util set casket.tkt "apple" "赤くて甘酸っぱい果物"
$ tkrzw_dbm_util set casket.tkt "banana" "黄色くて滑りやすい果物"
$ tkrzw_dbm_util get casekt.tkt "apple"
$ tkrzw_dbm_util get casekt.tkt "banana"

圧縮アルゴリズムは、データベースファイルを作る時に指定する。圧縮アルゴリズムの種類はファイル先頭にあるヘッダに記録される。既存のデータベースファイルを開く際には、truncateオプションを指定して初期化しない限り、圧縮アルゴリズムの指定は無視される。だから、一貫性のない圧縮アルゴリズムを指定してもデータベースが異常をきたすことはない。既存のファイルの圧縮アルゴリズムを変えるには、tkrzw_dbm_util rebuildコマンドやAPIのRebuildAdvancedメソッドを使ってデータベースの再構築を行う必要がある。

各種の圧縮アルゴリズムを利用するには、Tkrzwをインストールする前に、圧縮アルゴリズムのライブラリをインストールしておく必要がある。動作確認はzlib 1.2.11、libzstd 1.4.5、lilz4 1.9.2、liblzma 5.2.4でしているが、それより古いバージョンでも問題なく動くだろう。Ubuntu Linuxなら、以下のパッケージを入れることになる。ライブラリはオブジェクトファイルとヘッダファイルが別パッケージになっていることが多いが、ヘッダファイルの方を入れればオブジェクトファイルも入るので、大抵 "-dev" という接頭辞がついたパッケージを入れることになる。

• zlib1g-dev
• libzstd-dev
• liblz4-dev
• liblzma-dev

Tkrzwをビルドする際には、./configure --enable-most-features とすると、そのプラットフォームで利用可能なライブラリをできる限り組み込んでくれるので楽だ。--enable-zlibとかやって個別に有効にすることもできる。

Tkrzwをインストールした後に、そのアプリケーションのC++プログラムをビルドする際には、依存ライブラリのためのリンカオプションを指定する。Tkrzwをビルドした際に組み込んだライブラリをここでも指定することになる。Linux上では以下のようなコマンドになるはずだ。

$ g++ -std=c++17 -I/usr/local/include sample.cc -o sample \
  -L/usr/local/lib -ltkrzw -llzma -llz4 -lzstd -lz -lstdc++ -lrt -lpthread -lm -lc

ビルド用のオプションを機械的に指定するには、tkrzw_build_utilかpkg-configを使うと便利だ。

$ ./tkrzw_build_util config -i
-I/usr/local/include
$ ./tkrzw_build_util config -l
-L/usr/local/lib -ltkrzw -llzma -llz4 -lzstd -lz -lstdc++ -lrt -lpthread -lm -lc 
$ pkg-config --cflags-only-I tkrzw
-I/usr/local/include
$ pkg-config --libs tkrzw
-L/usr/local/lib -ltkrzw -llzma -llz4 -lzstd -lz -lstdc++ -lrt -lpthread -lm -lc

ちなみに、データベースファイルに適用される圧縮アルゴリズムの種類はファイルのヘッダの13バイト目の4ビット目から6ビット目までの3ビットで記録される仕様である。よって、8つの状態を取れるが、無圧縮を含めて5つの状態を既に使っているので、あと3つ使える。おそらく1つはユーザ定義の任意のアルゴリズムを注入できるモードにするだろう。そうすれば外部辞書を使った効率的な圧縮も可能になる。あとの2つは、将来的にZStdやLZ4を凌駕するものが出てきたときのために取っておこう。Brotliをサポートしようとも思ったが、あんまり高圧縮重視の需要はないと思うので、とりあえず見送っている。

余談だが、圧縮アルゴリズムの導入にあたって、HashDBMにおけるファイルの読み書きを最適化する処理を入れた。HashDBMでは、全てのデータベースアクセスは、Processというメソッドのラッパーとして実装されている。その中では、既存のレコードの値を読み出して、それをパラメータとして任意のコールバックを呼び、そのコールバックの戻り値を新たなレコードの値にする。この汎用性がTkrzwの売り文句の一つになっているのだが、この汎用性が非行率を生み出してもいた。Setメソッドは新しい値を設定するが、その処理には既存の値は必要ないにもかかわらず、わざわざ既存の値をファイルから読み込んでいた。同様に、Removeメソッドはレコードを削除するが、その処理にも既存の値は必要ない。さらに言うと、Getメソッドでも、既存の値を受け取るstringポインタをパラメータとして渡さずに、レコードの存在確認だけ行う場合には、既存の値は必要ない。不必要な値を読み込むということは、不必要な値の伸長処理も行うということなので、圧縮アルゴリズムを有効にした場合に無駄なCPU負荷をかけることにもなる。

そこで、新しいバージョンでは、GetとSetとRemoveには特殊化した実装を割り当てることにした。そこでは、不必要な場合には既存の値を読み込まない。レコードのメタデータとキーのみを読み込んで処理を進めるので、不要な伸長処理も起こらない。TreeDBMはHashDBMの上に構築されるので、この改善はTreeDBMの性能向上にもつながる。従来は既存のページを書き換えるのに既存のページ全体を読み込んで伸長処理をしていたが、それをしないで済むようになったので、更新性能が顕著に改善した。

まとめ。Tkrzwに圧縮データベースの機能をつけた、データベースを開く際にzstdのオプションをつけるだけで、勝手にレコードが圧縮されて格納されるようになる。英和辞書を扱う場合、ハッシュ表のデータベースで57%くらいにファイルが小さくなり、B+木のデータベースでは37%くらいにファイルが小さくなる。それでいて、29万QPSとか12万QPSで参照操作を行える。より高速な動作を所望するなら、B+木とlz4の組み合わせもおすすめできる。

実際にデータベースに組み込んだ場合でも、やはりZStdのバランスの良さと、LZ4の電光石火の速度が目を引く結果となった。圧縮しても十分に高速なので、よっぽど性能要求が高くない限りは圧縮して損はない。圧縮データベースの機能によって、「高速に検索できる圧縮アーカイブファイル」みたいな位置づけでDBMを使えるようになった。