Groongaの開発に参加している須藤です。14.1.3で並列オフラインインデックス構築機能を実装したので実装内容を紹介します。
概要
Groongaは転置索引ベースのインデックスを実装しています。このインデックスを構築する方法としてオンライン（動的）な方法とオフライン（静的）な方法をサポートしています。
オンラインな方法はインデックスを使える状態（インデックスがオンラインな状態）を維持しながらインデックスを構築します。つまり、インデックス構築中でもインデックスを使って高速に検索できますし、インデックスに登録した情報はすぐに検索可能になります。Groongaは情報の鮮度を重視している全文検索エンジンなのでこれは非常に重要な機能です。
一方、オフラインな方法はインデックス構築中はインデックスを利用できません（オフラインになります）。インデックス構築中にインデックスを使えなくてもよいという前提で実装できるので、オンラインな方法では使えないアプローチを使えます。実際、オンラインな方法とオフラインな方法では別の実装になっていて、オンラインな方法よりも高速に構築できるようになっています。
オンラインな方法の方が難しかったり、速度を出しにくかったりするので、オフラインな方法のみをサポートしている全文検索エンジンもあります。（でも、Groongaは情報の鮮度が大事！！！派なので、オンラインを頑張っているのです！）
オンラインな方法では並列化して高速にするのが難しい（並列化によるオーバーヘッドの方が大きくなりがち）のですが、オフラインな方法では高速にしやすいです。そのため、今回はオフラインな方法を並列化して高速にしました。データにも依りますが、数倍から10倍くらいは速くなります。
転置索引の構築方法
転置索引は元のデータを転置して作ります。たとえば、次のようなデータがあるとします。各ドキュメントに複数のトークンが紐づいているデータです。
document1: token1, token2, token3
document2: token1, token4
document3: token3, token5, token6
これの転置索引は次のようになります。
token1: document1, document2
token2: document1
token3: document1, document3
token4: document2
token5: document3
token6: document3
各トークンに複数のドキュメントが紐づいていますね。このように転置索引では元のデータの関係が反対になります。この書き方だとよくわからないとは思いますが、実は、紐づいたドキュメントはソートされています。一般的には各ドキュメントに一意な数値を割り当ててそれでソートします。
これをオンラインな方法で構築すると次のようになります。違いがわかりやすくなるようにdocument3→document2→document1という順番で追加されたとします。どの状態でもインデックスを使えます。
document3を追加。
token3: document3
token5: document3
token6: document3
document2を追加。
token3: document3
token5: document3
token6: document3
token1: document2
token4: document2
document1を追加。
token3: document1, document3 ← document3,document1じゃなくてソートされている！
token5: document3
token6: document3
token1: document1, document2 ← document2,document1じゃなくてソートされている！
token4: document2
token2: document1
一方、オフラインな方法で構築すると次のようになります。オフラインな方法では対象のドキュメントがすべてある状態で処理できるので、必ずドキュメントがソートされた順番で処理できます。つまり、document1→document2→document3の順で処理できます。
document1を追加。
token1: document1
token2: document1
token3: document1
document2を追加。
token1: document1, document2 ← ソート済みで処理しているので最後に追加するだけ！
token2: document1
token3: document1
token4: document2
document3を追加。
token1: document1, document2
token2: document1
token3: document1, document3 ← ソート済みで処理しているので最後に追加するだけ！
token4: document2
token5: document3
token6: document3
オンラインな方法とオフラインな方法での構築方法の違いがわかりましたね。それでは、オフラインな方法をどうやって効率的に並列化するのかを説明します。
オフラインな方法の並列化
先の例では小さな文書集合を使ったのですべてインメモリーで処理することが可能ですが、多くの場合はそれなりのサイズの文書集合になります。小さな文書集合ではインデックスなしでシーケンシャルに検索しても十分高速だからです。
そのため、実際の実装では一時ファイルも活用して処理しています。ある程度はインメモリーで処理して、溜まってきたら一時ファイルに書き出してメモリーを解放するということを繰り返しています。ファイルに書き出すと遅そうですが、ランダムアクセスではなく追記のみなのでそうでもありません。すべて処理したら書き出した内容を先頭から読み込んで最終的な転置索引を構築します。これにより大きな文章集合でも一定のメモリー使用量で高速に構築できます。
より性能がでるように並列化するには、各並列処理が共有リソースに書き込まなくてもすむようにすることが重要です。共有リソースへの書き込みが発生すると、ロックなどの同期処理が必要になり、性能が落ちやすいからです。たとえば、オフラインな方法での場合は、一時ファイルへの書き出しは共有リソースへの書き込みになります。つまり、各ワーカーが一時ファイルに書き出す、というように処理を分割するべきではないということです。
今回の実装ではインメモリーである程度のトークン・ドキュメントのマッピングを集めるところを並列化し、それらを一時ファイルに書き出すところは並列化しませんでした。インメモリーで集める処理をA、一時ファイルに書き出す処理をBとすると、並列化しないときは次のようなフローになります。
A1→B1→A2→B2→...
これを次のようなフローにしました。
↓だけ並列で、Bは直列
|A1|→ B1
|A2|→ B2
|A3|→ B3
...
インメモリーで集める処理（A）は共有リソースへの書き込みが発生しないため、それぞれのびのびと処理をでき、並列化で高速になりやすいです。
あ、今、あなた、本当に共有リソースへの書き込みが発生しない？と思いましたね？さすがですね！先の例では省略しましたが、全文検索用の転置索引ではトークナイズという処理があります。トークナイズという処理では文書をトークンという単位に区切って、それぞれのトークンにIDを割り振ります。すべてのトークンに一意なIDを割り振る必要があるということです。そんなことをするためには共有リソースへの書き込みが発生するんじゃないか？と思いましたよね。
実は、インメモリーで集める処理にはすでにこれに関連する別の最適化が入っているのでした。トークンとIDのマッピングを管理するテーブルを語彙表（lexicon）と言いますが、実は、インメモリーで集める処理は最終的な語彙表を使うのではなく、インメモリーに置いた一時的な語彙表を使っています。最終的な語彙表は永続化するためにファイルに紐づいています。そのため、IOが走る可能性があり、語彙表の操作（トークンを追加してIDを発行するとか）が遅くなりやすいです。一方、インメモリーに置いた語彙表はメモリー上で処理が完結するので、永続化される語彙表よりも高速に動作します。一時ファイルに書き出す処理（B）の中で一時的な語彙表でのIDから最終的な語彙表でのIDに変換しています。インメモリーで集める処理の中では何度も語彙表を参照する必要がありますが、一時ファイルに書き出す処理では各トークンを1度だけ処理すれば十分なので、このアプローチを使うことによりキャッシュを使ったような効果が得られます。
ということで、すでに既存の実装で共有リソースへの書き込みが不要になっていたため、並列化の実装では処理を切り出して並列化していい感じに待ち合わせるだけですみました。
なお、並列化のための汎用的なルーチンはすでに整備していたため、今回は単にそれを使うだけですみました。このルーチンは、Apache Arrow C++にあるスレッドプール実装をバックエンドにしていて、GroongaのAPIになじむようにラップしたようなやつです。そのため、Apache Arrowサポートを有効にしていないとこの並列化も動きません。注意してください。
まとめ
Groonga 14.1.3で実装した並列オフラインインデックス構築機能の中身をあまり詳細に立ち入らないレベルで紹介しました。速いは正義！なので、新しいGroongaにアップグレードしてぜひこの機能を活用してください！ここでは詳細を紹介しませんが、GroongaをベースにしているMroonga・PGroongaでも恩恵を受けられます。
Groongaをもっと高速にしたい！という場合はGroongaサポートサービスを提供していますのでお問い合わせください。
