Indeed のようなデータドリブンなアプローチをとる組織には、優れたツールが必要だ。
クエリーの並列実行を管理するために、私たちは Imhotep を開発した。これは、インタラクティブなデータ分析のプラットフォームで、昨年リリースされたものである。
Imhotep におけるメモリ効率とパフォーマンスのバランスを取るために、私たちはベクトル化された可変バイト ( variable-byte を指す。 以下、VByte とする。) を復号化するテクニックを開発した。
差分符号化を使用した VByte
ソートされた整数のシークエンスを圧縮するのに、多くのアプリケーションが VByte や差分符号化を使用する。逆索引で最も一般的な圧縮方法は、この種類の符号化を使用している。このアプローチでは、整数自体の代わりに整数間の逐次差分を符号化してくれる。これは、小さな整数には少ないバイトで済むかわりに、大きい整数ではより多くのバイトを食ってしまう。
従来の VByte のデコーダは一度に１バイトだけを検証するので、スループットは制約される。また、各 input byte は１つのブランチを必要とするので、誤って予測されたブランチへ移動してしまう。
ベクトル化したVByteの復号化
自社開発したマスク済みの VByte のデコーダはもっと大きい塊の 12 バイトのインプットデータを一度に処理する。これは一度に1バイトを復号化するよりもずっと速い。 Indeed にとってこれは重要である。なぜなら Imhotep は CPU 時間の 40％ を VByte の整数のデコードに費やしているからだ。このアプローチについては、昨年行ったテックトーク Large Scale Analytics and Machine Learning at Indeed でも話している。
Jeff Plaisance ジェフ・プレザンス ( Indeed ) 、 Nathan Kurz ネイサン・カーツ ( Verse Communications ) 、 Daniel Lemire ダニエル・レミア ( LICEF ケベック大学 ) が、 Vectorized VByte Decoding （ベクトル化された VByte の復号化）という論文でマスク済み VByte のデコーダについて詳細に述べている。論文の概要を以下に引用する。
VByte 圧縮の遍在するテクニックについて考察する。これは、各整数を可変長のバイトのシークエンスとして、表すものとする。各バイトの下位７ビットは整数の部分を符号化し、各バイトの上位ビットは、継続フラグとして、保持される。
このフラグは、最後部分を除き全てのバイトに対し、１と設定される。そして各整数の復号は、上位ビット ０ を持つバイトが出てきたら完了する。
VByte の復号は、パフォーマンスのボトルネックになり得る。特に符号化された整数の予期せぬ長さが、しばしブランチの誤った予測を引き起こす。SIMD のベクトル命令を使用して VByte を加速させようとした先の試みは、失望する結果となった。パフォーマンスを重視するコードについて、Google などの検索エンジンを、より複雑だが高速にデコードする形式を使用するように促しただけだったからだ。
我々のデコーダ (MASKED VBYTE) は、通常のスカラーの VByte デコーダよりも、 2 倍から ４ 倍速く、速さの面でも再び競合できるものにしている。
Vectorized VByte Decoding は 2015 年の 6 月 2 日から 3 日に行われるウェブアルゴリズムの国際シンポジウム International Symposium on Web Algorithms (iSWAG) に受理された。 iSWAG は、ウェブアルゴリズムに関連するあらゆるトピックについて、学術分野および業界の研究を推進している。
大規模なインタラクティブツール
Imhotep についての詳細は、以下のテックトークやスライドからも調べることができる。
Large-Scale Analytics with Imhotep
Github でも Imhotep のソースやドキュメンテーションが閲覧可能である。