A Tiny, Static, Full-Text Search Engine using Rust and WebAssembly

2019-10-17

RustとWebAssemblyで作る小さな静的全文検索エンジン

静的サイトに追加できる、シンプルな検索モジュールを作りました。非常に軽量（gzip圧縮時で50kB〜100kB）で、Hugo、Zola、Jekyllで動作します。検索は単語単位の完全一致のみに対応しています。左側の検索ボックスからデモをお試しください。コードはGitHubで公開しています。

静的サイトジェネレーターは魔法のような存在です。動的コンテンツの柔軟さとパフォーマンスを両立してくれます。

このブログも長年、Jekyll、Cobalt、そして最近はZolaで運用してきました。

ただ、一つ気に入らなかったのが、静的サイトには「静的」な検索エンジンが付いてこないことでした。その代わりに、みんなカスタムGoogle検索やAlgoliaのような外部検索エンジン、あるいはlunr.jsやelasticlunrのような純粋なJavaScriptベースのソリューションに頼っています。

どれも多くのサイトでは問題なく動くのですが、どうもしっくりくる決定打には感じられませんでした。

Googleへの依存をこれ以上増やしたくありませんでしたし、レイテンシが増えプロプライエタリでもあるAlgoliaのような独立したバックエンドも使いたくありませんでした。

一方で、JavaScriptに大きく依存したサイトもあまり好きではありません。例えば、lunrが生成する検索インデックスだけでも数メガバイトになることがあります。今日の回線速度を考えても、かなり贅沢に感じます。さらに、JavaScriptのパース自体にも依然として時間がかかります。

私が求めていたのは、他の静的コンテンツと一緒にデプロイできる、シンプルで軽量、自己完結した検索でした。

その結果、結局ブログに検索機能を付けること自体を諦めていました。記事が増えるにつれて、目的のコンテンツを見つけるのがどんどん難しくなっているのに、残念なことでした。

アイデア

ずいぶん昔、2013年のことですが、「Bloom filterを使った全文検索エンジンの作り方」という記事を読みました。まさに目から鱗でした。

アイデアはシンプルでした。ブログの全記事をジェネレーターにかけ、✨Bloom Filter✨という魔法のようなデータ構造を使って、小さく自己完結した検索インデックスを作るというものです。

そもそもBloom Filterとは？

Bloom filterは、ある要素が集合に含まれているかを省スペースで判定するためのデータ構造です。

ミソは、要素そのものを保存するわけではないことです。過去に保存されたことを、ある程度の確信をもって知ることができるのです。今回のケースで言えば、ある単語が記事の中に含まれているかを、一定のエラー率で判定できます。

Bloom filterは生の入力そのものではなく、すべての入力値の「フィンガープリント」（いくつかのハッシュ値）を保存します。その結果、メモリ使用量の少ないデータ構造が実現します。これは入力が「hello」の場合の例です。

元記事から、各投稿のBloom filterを生成するPythonコードを引用します（Stavros Korokithakis氏提供）：

filters = {}
for name, words in split_posts.items():
  filters[name] = BloomFilter(capacity=len(words), error_rate=0.1)
  for word in words:
    filters[name].add(word)

error_rateによってごくわずかな誤検出を許容することで、メモリ使用量は極めて小さく抑えられています。

すぐに、これを自分のホームページで使いたいと思いました。Bloom filterと検索エンジン自体をそのままブラウザに届けるというアイデアです。これでついに、バックエンドなしで小さな静的検索を実現できると考えました。

壁にぶつかる

しかし、すぐに幻滅が訪れました。

生成したBloom filterをどうバンドルして最小化し、ましてやクライアント側でどう動かせばいいのか、まったく見当がつきませんでした。元記事でもこの点に少しだけ触れられています：

クライアント側でBloom filterアルゴリズムを実装する必要があります。転置インデックスの検索アルゴリズムより大幅に長くなることはないでしょうが、それでも少し複雑になるはずです。

自分のJavaScriptスキルではやり遂げる自信がありませんでした。2013年当時、NPMは登場からまだ3年、WebPackに至っては1年経ったばかりで、既存の解決策をどこに探せばいいのかも分かりませんでした。

次に何をすべきか分からず、このアイデアは夢のまま終わりました。

新たな希望

5年後の2018年、ウェブはまったく違う場所になっていました。バンドラーは当たり前になり、Nodeエコシステムも大きく発展していました。そして特に、私の小さな静的検索エンジンの夢を再び呼び覚ましたのがWebAssemblyでした。

WebAssembly（略称Wasm）は、スタックベースの仮想マシン向けのバイナリ命令フォーマットです。WasmはC/C++/Rustといった高水準言語のコンパイル先として設計されたポータブルなターゲットで、クライアントおよびサーバーアプリケーションをウェブ上で展開できるようにします。[出典]

これで、慣れ親しんだ言語でクライアント側のコードを書けるようになったのです。Rustです！🎉

私の挑戦は2018年1月のプロトタイプから始まりました。上で紹介したPython版をそのまま移植したものです：

let mut filters = HashMap::new();
for (name, words) in articles {
  let mut filter = BloomFilter::with_rate(0.1, words.len() as u32);
  for word in words {
    filter.insert(&word);
  }
  filters.insert(name, filter);
}

各記事のBloom filterを作ることには成功したものの、ウェブ向けにどうパッケージ化すればいいのかは依然として分かりませんでした。そんな中、2018年2月にwasm-packが登場したのです。

おっと、ブラウザにRustのコードを届けてしまいました

これでパズルのピースがすべて揃いました：

Rust — 使い慣れた言語
wasm-pack — WebAssemblyモジュール用のバンドラー
概念実証として動くプロトタイプ

このページの左側に見える検索ボックスがその成果です。WebAssemblyを使い、完全にRustで動いています（いわゆるRAWスタックです）。よければ今すぐ試してみてください。

もちろん、そこに至るまでにはいくつもの壁がありました。

Bloom Filterクレート

Bloom filterを実装したRustのライブラリ（クレート）をいくつか調べてみました。

最初にjedisct1氏のrust-bloom-filterを試しましたが、型がSerialize/Deserializeを実装していなかったため、生成したBloom filterをバイナリ内に保存してクライアント側で読み込むことができませんでした。

いくつか試した後、シリアライズに対応したcuckoofilterクレートを見つけました。挙動はBloom filterと似ていますが、違いに興味がある方はこちらのまとめをご覧ください。

使い方は次のとおりです：

let mut cf = cuckoofilter::new();

// Add data to the filter
let value: &str = "hello world";
let success = cf.add(value)?;

// Lookup if data was added before
let success = cf.contains(value);
// success ==> true

cuckoo filterを使って、私のブログの10記事分のフィルターをバンドルしたときの出力サイズを見てみましょう：

~/C/p/tinysearch ❯❯❯ l storage
Permissions Size User    Date Modified Name
.rw-r--r--   44k mendler 24 Mar 15:42  storage

44kBなら悪くないように聞こえますが、これは10記事分のcuckoo filterをRustバイナリとしてシリアライズしただけのサイズです。さらに検索機能やヘルパーコードが加わります。素のwasm-packでは、クライアント側のコード全体で216kBにもなってしまいました。多すぎます。

バイナリサイズの削減

初期プロトタイプで216kBという現実を突きつけられた後、バイナリサイズを抑えるための選択肢がいくつかありました。

まずはjohnthagen氏によるRustバイナリサイズ最小化のアドバイスに従う方法です。

Cargo.tomlでいくつかのオプションを設定することで、かなりのバイト数を削減できます：

"opt-level = 'z'" => 249665 bytes
"lto = true"      => 202516 bytes
"opt-level = 's'" => 195950 bytes

opt-levelをsに設定すると速度とサイズをトレードオフすることになりますが、当面はとにかくサイズを最小化したいところです。ダウンロードサイズが小さければ、結果的にパフォーマンスも向上します。

次に試せるのが、wee_allocという、.wasmのコードサイズを小さくする代替Rustアロケータです。

これは、最初に少数回の動的サイズ割り当てを行った後は、それ以上の割り当てなしで重い処理を行うコード向けに設計されています。このシナリオではアロケータ自体は必要ですが、割り当てのパフォーマンスと引き換えにコードサイズを小さくすることを喜んで受け入れます。

まさに求めていたものです。試してみましょう！

"wee_alloc and nightly" => 187560 bytes

バイナリからさらに4%削減できました。

好奇心から、codegen-unitsを1に設定してみました。これはコード生成に単一スレッドだけを使うという意味です。驚いたことに、バイナリがわずかに小さくなりました。

"codegen-units = 1" => 183294 bytes

次に、binaryenというWasmオプティマイザの存在を知りました。macOSならhomebrewで入手できます：

brew install binaryen

付属のwasm-optというバイナリを使うと、さらに15%削減できました：

"wasm-opt -Oz" => 154413 bytes

さらに、DOMへのバインドが不要なためweb-sysを削除しました。152858バイトです。

Wasmバイナリのコードサイズをプロファイルするtwiggyというツールがあります。次のような出力が得られました：

twiggy top -n 20 pkg/tinysearch_bg.wasm
 Shallow Bytes │ Shallow % │ Item
─────────────┼───────────┼────────────────────────────────
         79256 ┊    44.37% ┊ data[0]
         13886 ┊     7.77% ┊ "function names" subsection
          7289 ┊     4.08% ┊ data[1]
          6888 ┊     3.86% ┊ core::fmt::float::float_to_decimal_common_shortest::hdd201d50dffd0509
          6080 ┊     3.40% ┊ core::fmt::float::float_to_decimal_common_exact::hcb5f56a54ebe7361
          5972 ┊     3.34% ┊ std::sync::once::Once::call_once::{{closure}}::ha520deb2caa7e231
          5869 ┊     3.29% ┊ search

見たところ、バイナリの大部分は記事の生データセクションが占めています。次に多いのが関数ヘッダーや、おそらくデシリアライズ由来のfloatからdecimalへの変換ヘルパー関数です。

最後に、WebAssembly関数の本体をunreachableに置き換えるwasm-snipを次のように試しましたが、コードサイズは減りませんでした：

wasm-snip --snip-rust-fmt-code --snip-rust-panicking-code -o pkg/tinysearch_bg_snip.wasm pkg/tinysearch_bg_opt.wasm

cuckoo filterのパラメータを少し調整し、記事からストップワードを除去した結果、121kB（51kB gzipped）まで抑えることができました。ウェブ上の画像の平均サイズが約900kBであることを考えれば悪くありません。しかも検索機能は、ユーザーが検索フィールドをクリックしたときにだけ読み込まれます。

追記

最近、プロジェクトをcuckoofilterからXOR filterに移行しました。素晴らしいxorfプロジェクトを使ったのですが、serdeによるシリアライズが標準で備わっており、多くのカスタムコードを削除できました。

その結果、ペイロードサイズをさらに20〜25%削減でき、現在ブログでは99kB（49kB gzipped）まで小さくなっています。🎉

新しいバージョンはすでにcrates.ioで公開していますので、ぜひお試しください。

フロントエンドとグルーコード

wasm-packが、Wasmとやり取りするためのJavaScriptコードを自動生成してくれます。

検索UIについては、w3schoolsのJavaScriptとCSSを少しカスタマイズしました。キーボード操作にも対応しています！ユーザーが検索クエリを入力すると、各記事のcuckoo filterを順に調べて単語の一致を試み、ヒット数でスコアリングします。この部分を追加してくれた親愛なる同僚のJorge Luis Betancourt氏に感謝します。

（余談ですが、このアニメーションは非圧縮のWasm検索本体とほぼ同じサイズです。）

注意点

完全一致の単語のみが検索対象です。前方一致検索も追加したいのですが、試したところバイナリが大きくなりすぎてしまいました。

使い方

Wasmファイルを生成するスタンドアロンのバイナリはtinysearchという名前です。入力としてJSONファイルへのパスを1つ受け取ります：

tinysearch path/to/corpus.json

このcorpus.jsonには、インデックス化したいテキストが含まれます。フォーマットは非常にシンプルです：

[
  {
    "title": "Article 1",
    "url": "https://example.com/article1",
    "body": "This is the body of article 1."
  },
  {
    "title": "Article 2",
    "url": "https://example.com/article2",
    "body": "This is the body of article 2."
  }
]

このJSONファイルは、どの静的サイトジェネレーターでも生成できます。こちらはZola用の私のバージョンです：

{% set section = get_section(path="_index.md") %}

[
  {%- for post in section.pages -%}
    {% if not post.draft %}
      {
        "title": {{ post.title | striptags | json_encode | safe }},
        "url": {{ post.permalink | json_encode | safe }},
        "body": {{ post.content | striptags | json_encode | safe }}
      }
      {% if not loop.last %},{% endif %}
    {% endif %}
  {%- endfor -%}
]

Jekyll版もおそらく似たような形になるはずです。こちらが出発点になります。お使いの静的サイトジェネレーターで動作するものができたら、ぜひ教えてください。

所感

まだまだワイルドウェスト状態です。不安定な機能、nightly版のRust、ドキュメントはほぼ毎日古くなります。知恵を絞る覚悟で臨んでください！
良いアイデアをプロダクトに仕上げるのは大変な作業です。使いやすさ、汎用性、保守性、ドキュメントなど、多くの要素に気を配る必要があります。
Rustはデッドコードの除去が非常に得意なので、使わないもののコストを払うことは通常ありません。それでも、Wasmバイナリに追加する依存関係には非常に慎重になることをお勧めします。不要な機能を追加したくなりますが、それがバイナリサイズを肥大化させるからです。例えば私はテスト中にStructOptを使い、コマンドライン引数をパースするmain()関数を用意していましたが、Wasmには不要だったので後で削除しました。
誰もがRustを書きたいわけではないことは理解しています。習得は簡単ではありませんが、素晴らしいのは他のほぼどんな言語でも使えることです。例えばGoで書いてWasmにトランスパイルすることもできますし、PHPやHaskellがお好みかもしれません。すでに多くの言語がサポートされています。
WebAssemblyをおもちゃの技術だと切り捨てる人も多くいますが、それは大きな間違いです。私の考えでは、WebAssemblyはウェブをはじめとするプロダクトの作り方に革命をもたらします。2年前には非常に難しかったことが今では簡単になっています。あらゆる言語で書いたコードを、すべてのブラウザに届けられるのです。これからの未来がとても楽しみです。
会社のウェブサイト向けにスタンドアロンでセルフホスト可能な検索インデックスをお探しなら、sonicをチェックしてみてください。代替としてstorkもお勧めです。

試してみましょう！

tinysearchのコードはGitHubで公開しています。

以下の制限にご注意ください：

単語単位の完全一致のみ検索可能です。検索候補のサジェストはありません。前方一致検索は、メントスとダイエットコークのようにバイナリサイズを爆発させてしまうためです。
すべての記事の検索インデックスを1つの静的バイナリにまとめるため、小〜中規模のサイトでの利用をお勧めします。1記事あたり非圧縮で約4kBを目安にしてください。
コンパイル時間は現状ひどいものです（私の環境ではクリーンインストール後で約1分半かかります）。主な理由は、インデックスを再構築するたびにRustクレートをゼロからコンパイルしているためです。
追記：CephalonRho氏の素晴らしい取り組みによるPR #13のおかげで、これはほぼ解消されました。改めて感謝します！

最終的なWasmコードは、検索サーバーへの往復が不要なため超高速です。即時に結果が返るので、投稿を検索するというよりリストを絞り込んでいるような感覚です。完全オフラインでも動作するので、アプリにバンドルしたい場合にも便利です。