TrivagoのバックエンドエンジニアであるMatthias Endler氏が、クライアントサイドで動作する全文検索エンジンを公開した。Bloomフィルタを活用することで、メモリ効率の高い設計がされている。このTinysearchはRustで記述されており、WebAssemblyにトランスパイルされた後、ブラウザ内で使用される。50～100KBという小サイズをうたっており、フルワード(full word)のみをインデックスすることができる。
リリースを発表したブログ記事で、Endler氏は、Tinysearchの開発動機と設計目標を次のように述べている。
静的なWebサイトであっても、"静的"な検索エンジンは搭載されていません。[…] Google[検索]への新たな依存性を追加したり、AlgiliaのようなスタンドアロンのWebバックエンドを使って、レイテンシやプロプライエタリを増やすようなことはしたくありませんでした。[…] lunrが生成する個々[のインデックス]は、サイズが数メガバイトにもなります。[…] その上に、JavaScriptを解析する時間も必要です。
[…]
もっとシンプルかつリーンで、自己完結的な、静的コンテキストと一緒にデプロイできる検索機能が欲しかったのです。
Endler氏は2018年初め、Bloomフィルタを使った既存のPythonコードをRustに移植してプロトタイプを作成した。Bloomフィルタは、要素がセット内に存在するかどうかを、高速かつ高メモリ効率で計算するように設計されたデータ構造である。メモリ効率を向上するために、計算の正確性に対する要件は緩和されている — Bloomフィルタは、偽陰性(false negative)を防止する一方で擬陽性(false positive)を容認する、確率的データ構造なのだ。これはつまり、Bloomフィルタでは、要素がセットの中に厳密に存在しない(definitely is not)か、あるいは存在する可能性がある(may be)かを得ることができる、ということである。ある研究論文では、Bloomフィルタによって実現可能なストレージ効率性を、次のように評価している。
その見返りとして、Bloomフィルタは、非常にコンパクトなストレージ使用を実現しています — セット内の要素のサイズや数に関わらず、1パーセントの擬陽性を実現するために必要なデータ量は、要素毎に10ビット未満です。
この1パーセントの擬陽性率は、要素毎に5ビットを追加することで低減が可能である。セット内での要素の存在をチェックするために必要な時間は、セット内の要素数には依存せず一定である。
メモリ効率のよいインデックス作成は機能のひとつに過ぎない、とEndler氏は説明する。もうひとつはWebAssemblyを使って機能をブラウザ上に移したことであり、問題もいくつかあった。Bloomフィルタをベースとしたインデックスは1インスタンス44KBとコンパクトだが、バニラwasm-packを使用したクライアントサイドのコード(検索機能やヘルパコードを含む)は216KBというサイズになる。WebAsemblyはバニラJavaScriptに比べて、パースやコンパイルが高速であるという事実を考慮に入れても、このサイズは、ユーザエクスペリエンスを阻害するようなダウンロード時間につながる可能性がある。
さまざまなツールを使ってサイズを許容範囲にまで削減した方法について、Endler氏は詳しく説明している。まず、サイズ最適化が可能なコンパイルオプションを使用することで、wasmバイナリを196KBまで削減した。次に、Rustのアロケータwee_allocを使用して、さらに188KBまで削減した。さらに、Wasmオプティマイザのbinaryenを使用した結果、サイズは154KBになった。DOMアクセスのための不要なバインディングを含むweb-sysを削除することで、最終的なサイズを153KBにまで縮小することができた。
この時点で、Bloomフィルタがバイナリサイズの約半分を占めるようになった。さらなるサイズ削減は、Bloomフィルタのパラメータと、インデックスするボリュームの最適化で実現した。停止ワード(stop word)を削除してフルワードのみをインデックスするように決定したことで、最終的には全バイナリサイズ121KB、gzip後で51KBに到達した。
加えて、Tinysearchのダウンロードは、ユーザが検索フィールドをクリックして全文検索機能を実行した時にのみロードするように、遅延することが可能である。この方法により、検索フィールドを含むページをロードした時の、ユーザエクスペリエンスへの影響はさらに低減される。
Tinysearchは、現在のRust/Wasmスタックを使うことで、ブラウザ用にJavaScript以外の言語で記述された既存のソフトウェアの再利用を実現するという、可能性のひとつの例である。Endler氏の今回の例は、生成されたバイナリには最適化が必要な場合があることと、既存のさまざまなツールやテクニックでそれを実現できることを示すものだ。
Endler氏のブログ記事は、最適化作業の結果のまとめで締め括られている。
結果としてコンパクトな静的検索を、バックエンドの必要なく実現することができました！[…]
検索サーバとのラウンドトリップが不要になったことで、最終的なWasmコードは超高速に動作します。瞬間的なフィードバックループは、ファイルを検索するというよりも、リストをフィルタするような感覚です。
ブログ記事の全文はオンライン公開されており、最適化プロセスやTinysearchの機能が詳細に紹介されている。TinysearchはMITライセンスで、おもに静的Webサイトを対象として公開されている。