データベースにレコードを格納する際に可逆圧縮をかけると便利なことがある。 データベースファイルが小さくなり、また入出力のデータ量が減るので早くなることすらある。圧縮アルゴリズムを自分で実装するのは手に余るので、既存の実装を組み込むのが現実的だ。そうなると、数多ある実装からどれを選ぶかが重要になる。なので、圧縮率や処理速度について調査してみた。結論としては、LZ4とZSTDが非常に素晴らしいので、組み込む方向で検討する。
数年前の記事だが、OSS圧縮ツール選択カタログというのが参考になる。要約すると、定番のzlib（gzip）が優秀であり、それを圧縮率も速度も凌駕するZSTDが大注目であり、速度重視ならLZ4が良さげということだ。
圧縮率に関しては手元でも実験してみた。Tkrzwのソースコードをcatしたファイルに各種アルゴリズムを適用してみる。
| サイズ | 圧縮率 | |
| 無圧縮 | 2034233 | 1.0 |
| ZSTD | 260331 | 0.127 |
| GZIP | 274133 | 0.134 |
| LZ4 | 456705 | 0.224 |
| LZO | 523892 | 0.257 |
| BZIP2 | 192262 | 0.094 |
| LZMA | 174280 | 0.085 |
上述の記事で述べられているのと同じ傾向だ。確かにZSTDの方がgzipよりも圧縮率が高い。しかも、公式サイトによると、圧縮も伸長もgzipの5倍くらい早いそうなので、もはや新たにgzipを使う理由がないくらいだ。
速度重視のLZ4とLZOを比べると、LZ4の方が圧縮率が高かった。これで圧縮速度もLZOよりちょい早で、伸長速度はLZOより5倍早いそうなので、やはり新たにLZOを使う理由はない。LZOの速度には昔びっくりしたものだが、それよりさらに早いとは。しかもZSTDとLZ4の作者は同じ。天才かよ。
遅いが圧縮率がより高いbzip2と、超遅いが圧縮率最強のLZMA（XZ）は、確かに圧縮率の点では利点がある。しかし、bzip2はzlibに比べて圧縮も伸長も5倍くらい遅くて、LZMAはzlibより圧縮は20倍遅くて伸長は3倍くらい遅いって感じだ。データベースでレコードを出し入れする度に適用するには、どちらも遅すぎる。
とりあえず、事前調査の段階では、バランス最強のZSTD、速度最強のLZ4、普及状況からzlib、圧縮率最強のLZMAという感じになるか。BZIP2とLZOは位置づけが中途半端なので脱落かな。
実際の圧縮率や処理速度は入力データに強く依存する。そして、その実験データとしてはソースコードだけでは心もとない。ソースコードはインデントのための空白の連続が多いし、それ以外の文字も記号やら予約語やらて偏りが大きいので、非常に圧縮しやすいデータと言える。Wikipediaのデータで実験した上述のサイトの結果を見てもだいたい同じ傾向ではあるのだが、WikipediaのデータもXMLとWikiの記号が多いので圧縮はしやすい方だろう。
ここでは、もう少し圧縮しにくいデータを意図的に作って実験しよう。巡回文字方式と冗長文字方式というのを考えた。巡回文字方式では、以下の工程で10000文字のテキストを作る。
- 各文字において、普遍乱数で、1/8の確率で空白を選択する。
- ただし、空白は連続させない。
- そうでない場合で、偶数文字目の場合、英字26文字から、文字数を26で割った値で文字を選択する。
- 奇数文字目の場合、英字26文字から、文字数を25で割った値で文字を選択する。
結果として、以下のような文字列が生成される。同じ文字が連続する可能性は低いが、2文字の連続は26*25のパターンしかない。よって、一見すると圧縮が難しいように見えて、エントロピー符号が意外に効率的に効くと期待できるパターンである。似たパターンがよく現れるという点では、自然言語っぽいと言えるかもしれない。
kymbod ergtiv wl mzobqdsfuh ix ylbndpf gsiukwm nzpb cs tfv wiykbmdofq rit ulw xozqbsdufwhyjbldnfphrjtlvnxpzr scuewgyibkd engpirktm nw xq ratcvexgaickemgoi jrlt uowqysaucweygbidkfmhojqls tovqxszubwdyfb ci jflhnjpl msouqwsyuawcyebg hejglinkp qnspu vsxuzwb c dbfdhfjhljnlp qosquswuyw xbadcfehgji jmlonqpsrut uxwz aa b ceeggiikkm nnpprrttvvxxza bcd
さらに少し圧縮しにくいであろうパターンも考えた。この冗長文字方式では、以下の工程で10000文字のテキストを作る。
- 各文字において、普遍乱数で、1/8の確率で空白を選択する。
- ただし、空白は連続させない。
- そうでない場合は、普遍乱数で、等確率で以下のモードを選択する。
- モード1: 英字26文字から、平均2/26、標準偏差4/26の正規乱数で1文字を選択する
- モード2: "aeiou" の5文字の中から、等確率で1文字を選択する
- モード3: 直前の文字を選択する。ただし、空白は連続させない。
結果として、以下のような文字列が生成される。同じ文字が連続する確率は高いが、ランレングス符号で圧縮できるほどの連続性はない。各文字が乱数で選択されているのでパターンの抽出もしにくい。ただし、文字の種類が偏っているのでエントロピー符号が多少は効くかもしれない。総じて、一見すると圧縮しやすそうに見えて、実はあんまり圧縮できないパターンである。局所的に単調なデータが見られるが全体的に似たパターンが見出し辛いという点では、画像や音声のデータっぽいと言えるかもしれない。
iiiioemmiibqqqii qppaeeehkuuoonoau oo eaiihqoz ziuo jlibbuiso vopfffffteeeeiikkzoiieoqeoousaakkky kkkaopaq sisssiijjjfvo uuuercn bboajjouufttwwaboopppodaefff niuzqjjssiu f u vvvqqeerrvvo jnaqaadnnnnnnmipjooo giohuo uusam iri laoeqmmaappooswg gaiiii eyiii magii u cmm ao e lppp eeeuhhsfuuiiuuyuuuuj guonn qdddiggsiuu dnnn egaalhiiuprrddu gu eeeu
巡回文字方式（A）と冗長文字方式（B）の各々で生成した1000個のテキストを各10回ずつ圧縮し、またそれを伸長した際の処理にかかる時間を測定した。元のテキストと圧縮後のデータの比率である圧縮率も示す。各アルゴリズムにおいてデフォルト設定に加えて、低速高圧縮な設定と高速低圧縮な設定を試した。また、比較のために、mallocとmemcpyで元データを複製するだけの処理の時間も計測した。
| 圧縮時間A | 伸長時間A | 圧縮率A | 圧縮時間B | 伸長時間B | 圧縮率B | |
| malloc+memcpy | 0.041184 | 0.006695 | 1.000000 | 0.041068 | 0.006711 | 1.000000 |
| LZ4 (accel=5) | 0.220298 | 0.033432 | 0.650555 | 0.117992 | 0.032181 | 0.975616 |
| LZ4 (accel=1=default) | 0.261770 | 0.037090 | 0.537161 | 0.258777 | 0.042087 | 0.889691 |
|---|---|---|---|---|---|---|
| ZSTD (level=-1) | 0.443686 | 0.105906 | 0.457863 | 0.556443 | 0.061721 | 0.909109 |
| ZSTD (level=3=default) | 0.594659 | 0.140527 | 0.336566 | 0.941271 | 0.186778 | 0.541524 |
| ZSTD (level=10) | 3.243751 | 0.126796 | 0.307944 | 3.210026 | 0.168719 | 0.534938 |
| ZLIB (level=1) | 1.009819 | 0.357543 | 0.380572 | 1.644104 | 0.485414 | 0.567144 |
| ZLIB (level=6=default) | 1.648518 | 0.342064 | 0.318207 | 3.166035 | 0.507012 | 0.551420 |
| ZLIB (level=9) | 1.651914 | 0.342413 | 0.318111 | 3.19259 | 0.507663 | 0.551449 |
| LZMA (level=1) | 16.343645 | 1.761819 | 0.309047 | 20.210840 | 3.376035 | 0.573324 |
| LZMA (level=6=default) | 26.629511 | 1.779456 | 0.287569 | 25.029432 | 3.404315 | 0.515658 |
| LZMA (level=9) | 53.281816 | 1.904255 | 0.287569 | 73.729736 | 3.623408 | 0.515658 |
まず、どの実装でも、やはりデフォルト設定において、圧縮率と動作速度のバランスがとれていることが分かる。よって、デフォルト設定だけに着目して考察しよう。まず、ZLIBとZSTDを比較する。ZSTDの圧縮率は、どちらの入力パターンでも、ZLIBとほぼ同じだ。それでいて、圧縮速度も伸長速度も2.5倍以上早い。速度を取れば圧縮率が犠牲になるか、その逆であるかが普通なのだが、圧縮率はほぼ同じで速度が劇的に向上している。すごい。ZSTDはマジで凄い。ブレイクスルーとはこのことだ。ZSTDが使える環境ではZLIBを使う理由はない。
次に、ZSTDとLZ4の比較をする。LZ4の圧縮率は、ZSTDに比べると低い。同じようなパターンが頻出する巡回文字方式ではそれなりの圧縮率を示すが、大局的なパターンの偏りが少ない冗長文字方式では、圧縮率が低い。とはいえ、圧縮時間はZSTDの3倍早く、伸長時間は5倍早いので、速度が重視される場面では活躍するだろう。というか、ここまで早いと、memcpyの何倍かというスケールになってくる。ほとんどのプログラマにとって、memcpyの速度なんて音の速さのようなもので、意識することすら稀だ。そのたった7倍くらいの時間で伸長処理ができるというのは全く驚きだ。
LZMAは、圧縮率は確かに他よりいいのだが、ZSTDより50倍遅くなってまで使うシーンはあまりないだろう。とはいえ、保存しておくことに意義があるアーカイブ用途では有用なので、意味がないというわけではない。
この実験をするついでに、Tkrzwに圧縮関連のユーティリティを足しておいた。Compressorという統一的なインターフェイスで、たくさんのアルゴリズムを透過的に扱うことができる。次回は、それをデータベースに統合して、どんな性能や使い勝手になるかを検討していきたい。本当は圧縮データベースをサポートするつもりはなかったのだが、ZSTDとLZ4が素晴らしすぎるので、その恩恵に与ってみようじゃないかと。
追記：圧縮データベースの仕様を拡張して、AESとRC4をサポートする暗号データベースも実装した。その性能評価も行なったので、該当の記事をご覧いただきたい。
