The World's First Middle-Out Compression for Time-series Data - Part 1

UPDATE: アルゴリズムは現在 WTFPLv2 でライセンスされています。ソースコードは https://github.com/schizofreny/middle-out.

Middle-out compression は、もはや HBO の番組 Silicon Valley の架空の発明ではありません。このテレビ番組と新しいベクトル命令セットの両方に触発されて、私たちは時系列データ用の新しい可逆圧縮アルゴリズムを考え出しました。圧縮は常に速度と比率の妥協点であり、これらのトレードオフのバランスをとることは決して容易ではありませんが、ミドルアウトのコンセプト全体により、ワイズマンスコアをさらに押し上げることができます。現在の値を計算するために以前の値が必要な場合、すべての先行する値が必要です。しかし、チャンクの複数の位置から処理を開始する場合、このフラグメント内の先行値にのみ依存します。これにより、たとえば SIMD 命令を効果的に使用できます。

How Does it Work?

原理的には、このアルゴリズムは新しい値と前の値の XOR を計算します。この方法で、値間の差のようなものが得られ、この差だけを保存することができます。時系列データセットでは、この差分は通常、先頭または末尾のゼロの数を持っています。したがって、格納する必要のある情報は通常大幅に少なくなりますが、先行ゼロのカウントとゼロ以外の XOR 断片の長さも格納する必要があります。

これらの概念は、現在の圧縮アルゴリズム、たとえば Facebook の Gorilla .NET などで一般的に使用されています。圧縮効率のために、Gorillaはビット単位で操作しますが、これらの操作はかなり広範囲に及びます。私たちは、できるだけ高速に圧縮できるように設計しているので、ビットからバイトの粒度に移行しました。ミドルアウトに関しては、圧縮はデータのブロックに対して行われますが、時系列データベースはいずれにせよブロックを使用するため、これは問題ではありません。最初のシナリオは、一連の倍精度 (0.1, 0.2, 0.3, …) を取り、繰り返されるポイントの部分に応じて圧縮率を測定するものです。比較のために、FacebookのGorilla圧縮を使用します。 Gorillaはデフォルトで、時系列データの値とタイムスタンプの両方を圧縮する。

データセット C と D は InfluxData のベンチマークツールを使用して生成されます : ディスク書き込みと Redis メモリ使用量を表します。データセットAの場合、Gorillaは我々のアルゴリズムよりもわずかにデータを圧縮し、その比率は1.45対1.3でした。その他の整数のデータセットでは、我々のアルゴリズムの方が圧縮率が高いです。最大の違いはデータセットDで、Middle-outの圧縮率が3.3であるのに対し、Gorillaは1.84で圧縮することができる。圧縮率は入力データに大きく依存するため、あるアルゴリズムが他のアルゴリズムより優れているデータセットがあることは明らかである。

圧縮パフォーマンス

現在、私たちはこのアルゴリズムの 2 つの互換性のある実装を所有しています。 1 つは、Skylake-X CPU で利用可能な新しい AVX-512 命令セットを利用します。 2 番目の実装は、この命令セットをサポートしていないコンピューターを対象としています。

スループットは、2.0 GHz で動作する Skylake-X のシングルコアで測定されています。

次のグラフは、Facebook の Gorilla と比較した両方の実装の圧縮および解凍速度を示しています。

このグラフは、前述の 4 つのデータセットで測定した圧縮スループットと、値の繰り返しのそれぞれのパーセントがある系列のスループットを示します。

Gorilla 圧縮のスループットは 120-440 MB/s で平均速度 185 MB/s の間で変化しました。我々のスカラー実装の最も低いスループットは、繰り返し値の50%で約670MB/sに圧縮されます。これは、ブランチの予測ミスの比率が高いことが原因です。平均圧縮速度は1.27GB/sです。ベクトル命令を使用したアルゴリズムでは、分岐予測ミスに悩まされることなく、2.33GB/sから2.59GB/sまでデータを圧縮し、平均速度は2.48GB/sです。 6540>

Gorilla はこれらのデータを 100 MB/s から 430 MB/s の範囲で解凍することができました。しかし、ご覧のとおり、同じデータの解凍は、圧縮よりもさらに高速です。ベクトル化されていない解凍は、最小で2.36GB/秒、平均で2.7GB/秒の速度で動作します。ベクトル化されたコードは、3.4 GB/sからデータを伸長し、データセットDでは4.86 GB/sを記録しました。平均で4.0 GB/sでデータを伸長することができます。

圧縮に対する全体の平均速度向上は6.8x（スカラー実装）と13.4x（ベクトル化実装）でした。解凍の平均速度向上は、それぞれ 16.1 倍と 22.5 倍です。

我々について

Schizofreny では、パフォーマンスに専念し、限界は常にさらに押し上げることができると信じています。私たちはチャレンジが大好きで、お客様の HPC 問題のお手伝いをさせていただきます。

Part II

www.vldb.org/pvldb/vol8/p1816-teller.pdf

https://github.com/influxdata/influxdb-comparisons/