Compressing an Inverted Index
MygramDBのインデックスが1GBを超えた。100万件のWikipedia記事を取り込んだ時点で、n-gramの転置インデックスが予想以上にメモリを食っていた。
転置インデックスとは
本の巻末にある「索引」を思い浮かべてほしい。「東京」→ p.12, p.45, p.198 のように、単語からそれが出現するページ番号の一覧を引ける。転置インデックスはこれと同じ発想だ。「東京」→ [文書1, 文書5, 文書42, 文書1003] のように、単語から、その単語が出現する文書のID一覧へのマッピングを保持する。「転置」と呼ばれるのは、通常のデータ（文書 → その中の単語）とは逆方向（単語 → それを含む文書）の索引だから。全文検索エンジンの核をなすデータ構造であり、Elasticsearch、Solr、MySQLのFULLTEXTインデックス——検索機能を持つほぼすべてのシステムがこの構造に依存している。
検索時は、この転置インデックスからポスティングリスト（IDの一覧）を引く。「東京 タワー」で検索するなら、「東京」のリストと「タワー」のリストの両方に含まれる文書IDを探す——つまりリスト同士の積集合を取る。構造はシンプルだが、問題はサイズだ。
n-gramとは
テキストをN文字ずつずらしながら切り出した断片。「東京都」なら「東京」「京都」の2-gram（バイグラム）になる。辞書が不要で、どんな言語にも適用できるのが強み。たとえば英語なら「search」→「se」「ea」「ar」「rc」「ch」。日本語の形態素解析のように言語固有の処理が要らない。MygramDBは漢字に1-gram（1文字単位）、ASCIIに2-gram（2文字単位）を使うハイブリッド方式を採用している。
100万件の文書に対して、頻出する単語——たとえば英語の「the」や日本語の「の」——のポスティングリストには数十万件の文書IDが並ぶ。1件あたり4バイト（uint32_t、32ビット符号なし整数）として、40万件なら1.6MB。そういうリストが数万本ある。素朴に配列で持てば、メモリは際限なく膨らむ。
これは全文検索エンジンの古典的な問題であり、30年以上にわたって圧縮手法が研究されてきた。MygramDBはインメモリで動く全文検索エンジンだ。ディスクに逃がせない以上、メモリ上のインデックスを圧縮することは生死に直結する。
デルタエンコーディング——まずソートする
ポスティングリストのIDは昇順にソートされている。これは検索時に積集合を効率よく計算するためだが、圧縮にも効く。ソートされた整数列には、ひとつの自明な性質がある——隣接する値の差（デルタ）は、元の値より小さい。
[10, 15, 20, 50, 51, 52] を [10, 5, 5, 30, 1, 1] に変換する。先頭の値はそのまま保持し、以降は「前の値からいくつ増えたか」だけを記録する。元のIDが10万や50万といった大きな値でも、デルタ値は数十〜数百程度に収まることが多い。値が小さくなれば、少ないビット数で表現できる。
VByte（Variable Byte Encoding）——デルタの相棒
デルタエンコーディングと組み合わせてよく使われるのがVByte（可変長バイトエンコーディング）だ。通常の整数は固定4バイト（32ビット）で表現されるが、VByteは値の大きさに応じてバイト数を変える。
仕組みはシンプルだ。1バイトの最上位ビットを「まだ続くか」のフラグに使い、残り7ビットで値を表現する。127以下の値なら1バイトで済む。128〜16383なら2バイト。デルタ値は小さいことが多いので、大半が1〜2バイトに収まる。固定4バイトと比べて、メモリ使用量は半分以下になる。
Lucene（Elasticsearch/Solrの基盤エンジン）はVByteの変種を長年使ってきた。Google検索の初期実装もVByteベースだったと言われている。シンプルで、デコードが速く、圧縮率もそこそこ。転置インデックス圧縮の「まず試すべき手法」として、30年近い実績がある。
MygramDBではVByteは採用せず、デルタ値をuint32_tのまま保持している。圧縮率は落ちるが、理由がある。後述する。
デルタエンコーディングの美点は単純さだ。エンコードもデコードも、前の値に差分を足すだけ。実装ミスが入り込む余地が少ない。全文検索エンジンにとって、インデックスのデコード処理にバグがあることは検索結果が壊れることを意味する。単純さは正義だ。
ビットマップ——発想の転換
デルタエンコーディングには弱点がある。「the」のように文書の大半に出現する単語だ。100万件中80万件に出現するなら、80万個のデルタ値を保持することになる。値は小さくても、個数が多い。デルタ値がすべて1（連続するIDすべてに出現）であっても、80万個の「1」を格納するコストは馬鹿にならない。
ここで発想を変える。「どの文書に出現するか」をIDの列挙ではなく、ビットの列で表現する。
文書が100万件あるなら、100万ビットのビット配列を用意する。文書1に出現するならビット1を1にし、文書2に出現しないならビット2を0にする。80万件に出現するなら100万ビットのうち80万ビットが1になる。
ビットマップの直感的な理解
出席簿を思い浮かべるとわかりやすい。クラス全員分の枠があり、出席した人に○、欠席した人に×をつける。ビットマップもこれと同じだ。文書全件分の「枠」を用意し、その単語が出現する文書に1（○）、出現しない文書に0（×）をつける。出席者のリスト（ID列挙）を作る代わりに、全員分の○×表を持つ。
100万ビット = 125KB。80万個のuint32_t（3.2MB）と比べれば25分の1以下で、劇的に小さい。しかも、ビットマップ同士の積集合はCPUのビットAND命令一発で済む。IDの列をマージソートする必要がない。検索も速くなる。
ただし、スパースな（出現頻度が低い）ポスティングリストにビットマップを使うと逆効果になる。100万件中100件にしか出現しない単語に100万ビット（125KB）を割り当てるのは、100個のuint32_t（400バイト）より300倍以上大きい。ほとんどが0のビット列に大量のメモリを使うのは本末転倒だ。
密度が高ければビットマップ、低ければデルタ。どちらが最適かは、ポスティングリストの密度（全文書に対する出現文書の割合）によって決まる。問題は、ひとつの転置インデックスの中に、密度が高いリストと低いリストが混在していることだ。「の」のリストと「東京スカイツリー」のリストでは、最適な表現が全く違う。
Roaring Bitmap——2014年の発明
この「密度によって最適な表現が異なる」問題に、エレガントな解を与えたのがRoaring Bitmapだ。2014年にDaniel Lemireらが発表した。
Roaringの核心はコンテナの概念だ。まず、32ビットの整数空間を上位16ビットと下位16ビットに分割する。上位16ビットが同じ値を持つID群は、ひとつのコンテナにまとめられる。各コンテナは最大65,536個のIDを保持できる（下位16ビットの空間 = 2^16 = 65,536）。
たとえば、文書ID 0〜65535 は「コンテナ0」に、65536〜131071 は「コンテナ1」に入る。ID 100 と ID 200 は同じコンテナ0に、ID 100000 はコンテナ1に入る。
そして——ここがRoaringの真髄だが——各コンテナは、中身の性質に応じて3つの内部表現を自動で選択する。
まず基本の2つ。IDが少なければArray（ソート済みIDの配列）、多ければBitmap（ビット配列）。これはここまで議論してきたデルタ vs ビットマップの選択と同じ発想だ。境界は4096個。4096個 × 2バイト = 8KB。Bitmapも65536ビット = 8KB。ちょうどこの点でサイズが逆転する。
3つ目はRun（ランレングス）。IDが連続するケース——たとえば [100, 101, 102, ..., 199] のような場合——に効く。100個のIDを列挙する代わりに、「開始100、長さ100」の4バイトだけで表現できる。これはArrayでもBitmapでも非効率な、連番が大量に続くパターンに対応するための表現だ。時系列に近い形でIDが割り振られているデータや、バッチインポートで連続IDが生まれやすいワークロードで威力を発揮する。
| 表現 | 使う場面 | サイズ | 探索速度 |
|---|---|---|---|
| Array | IDが少ない（〜4096個） | 2バイト × ID数 | 二分探索 O(log n) |
| Bitmap | IDが多い（4097個〜） | 固定8KB | 直接参照 O(1) |
| Run | IDが連続する | 4バイト × ラン数 | 二分探索 O(log n) |
Roaringはこの3つの表現を、ひとつのデータ構造の中でコンテナ単位に混在させる。あるコンテナはArray、隣のコンテナはBitmap、その隣はRun——データの局所的な性質に合わせて、最適な表現が自動で選ばれる。
なぜRoaringがここまで普及したか
Roaring Bitmap以前にも圧縮ビットマップは存在した。WAH（Word-Aligned Hybrid）、EWAH（Enhanced WAH）、Concise。いずれもランレングス圧縮（連続する0や1をまとめて表現する手法）のバリエーションだ。
Roaringが勝った理由は、ランダムアクセスの速さだ。WAH/EWAHはシーケンシャルスキャン（先頭から順に舐める操作）には優れるが、「ID 42が含まれるか？」という点検索が遅い。先頭からランレングスを展開しながら目的のIDまで辿る必要がある。Roaringはコンテナの二分探索 → コンテナ内のArray/Bitmap探索で、O(log n)のランダムアクセスを実現する。
集合演算（AND、OR、XOR）も高速だ。同じ上位16ビットを持つコンテナ同士の演算に分解されるので、異なるコンテナ間の無駄な比較が発生しない。Bitmapコンテナ同士のANDはCPUのビットAND命令で一気に処理できる。
現在、Lucene、Apache Spark、Redis、Elasticsearch、Pilosa、Apache Druidなど、主要な検索・分析基盤がRoaringを採用している。Daniel Lemireが公開したCRoaringライブラリ（C/C++実装）はSIMD最適化が施されており、AVX2やNEON命令を活用した高速な集合演算を提供する。
MygramDBのハイブリッド戦略
MygramDBでは、ポスティングリストごとにデルタエンコーディングとRoaring Bitmapを自動で切り替える。ひとつの転置インデックスの中に、デルタ圧縮のリストとRoaringのリストが混在している。
閾値は密度18%。文書全体の18%以上に出現するn-gramのポスティングリストはRoaringに変換される。18%未満はデルタのまま。
18%という数字は経験的に決めた。理論的な最適値は、デルタ配列のバイト単価とRoaringコンテナのオーバーヘッドから計算できるが、実際にはワークロード依存だ。Wikipediaの日本語記事と英語記事では、頻出n-gramの分布がかなり違う。日本語は漢字1-gramなので「的」「年」「は」のようなn-gramが高密度になりやすい。英語は2-gramなので分散しやすい。最適な閾値が言語によって異なるため、チューニング可能なパラメータ（roaring_threshold）として設定に出している。
ヒステリシス——振動を防ぐ
密度がちょうど閾値付近にあるポスティングリストは厄介だ。文書の追加・削除のたびに密度が18%を行ったり来たりすると、デルタとRoaringの間で変換が繰り返される。変換のたびにメモリ確保とデコード・エンコードが走るので、CPUとメモリアロケータに無駄な負荷がかかる。
ヒステリシスとは
入力が増えるときと減るときで閾値を変える制御手法。身近な例はエアコンのサーモスタットだ。「25℃を超えたら冷房ON、25℃を下回ったら冷房OFF」だと、室温が25℃付近をうろうろするとON/OFFが繰り返される。「26℃を超えたらON、24℃を下回ったらOFF」にすれば安定する。行きと帰りで閾値をずらす、それがヒステリシスだ。
MygramDBでは、Roaringに変換する閾値は18%だが、デルタに戻す閾値は9%（18% × 0.5）にしている。密度が17%に下がっただけではRoaringのまま。9%を下回って初めてデルタに戻る。この非対称な閾値により、閾値付近での振動が防がれる。
RCUで最適化する——検索を止めない
圧縮形式の変換は重い処理だ。数万件のIDをデコードして別の形式にエンコードし直す。しかし、MygramDBはインメモリDBとして、この間も検索リクエストに応答し続けなければならない。「最適化中なのでお待ちください」は許されない。
RCU（Read-Copy-Update）とは
並行プログラミングのパターンのひとつ。データを更新するとき、元のデータをロックするのではなく、コピーを作って更新し、更新が終わったらアトミック（不可分）に差し替える。読み手はコピー作成中も元のデータを読み続けられるので、読み取りがブロックされない。Linuxカーネルで広く使われている手法だ。
MygramDBの最適化処理は3ステップで動く。
①で最適化スレッドがインデックスのスナップショットを取る。ここでのロックはごく短い——ポスティングリストへの参照をコピーするだけだ。②ではロックを一切持たずに、コピーしたデータに対して圧縮形式の変換を行う。この間、検索スレッドは元のデータで自由に検索を続けられる。③で最適化済みのデータをアトミックに差し替える。
ただし、②の間に別のスレッドがそのポスティングリストを更新している可能性がある。ポスティングリストにはバージョンカウンタがあり、①の時点と③の時点でバージョンが変わっていたら、スワップをスキップする。古いスナップショットで上書きして最新の書き込みを消す事故を、これで防いでいる。
最適化処理は1万件のn-gramをバッチ単位で処理する。バッチとバッチの間には他の処理が割り込めるので、数十万件のn-gramがあっても検索レイテンシへの影響は最小限に抑えられる。
圧縮の歴史を追体験する
転置インデックスの圧縮手法は、情報検索の歴史そのものだ。
1990年代、初期の検索エンジンは素朴な整数配列を使っていた。デルタエンコーディングとVByteが導入されて、メモリ使用量が劇的に減った。2000年代にはビットパッキング（PForDelta、Simple9/16）が登場し、SIMDを活用したバッチデコードで速度と圧縮率の両方を改善した。2010年代にRoaring Bitmapが現れ、「密度に応じた自動最適化」という新しい設計パラダイムを確立した。
MygramDBのハイブリッド戦略は、この歴史を一つの実装に圧縮したものだ。スパースなリストにはデルタ（1990年代の知恵）、デンスなリストにはRoaring（2014年の発明）。VByteを採用しなかったのは、デルタ値をuint32_tのまま持ったほうがデコードが速く、Roaringへの変換も単純だから。圧縮率を犠牲にして（VByteなら半分以下になり得る）、実装の単純さとデコード速度を取った。
30年分の研究を振り返ると、最適な圧縮手法は「データの性質による」という当たり前の結論に行き着く。だからRoaringが強い。データを見てから表現を選ぶ、というアプローチは、事前に一つの手法を決め打つよりも、ほぼ常に正しい。