💻 6月3日の MS Build で開催される VS Code Live に参加しましょう。

docfindの開発：RustとWebAssemblyによる高速なクライアントサイド検索

2026年1月15日 投稿者：João Moreno

最近VS Codeのウェブサイトを訪れた方なら、何か新しいことに気づいたかもしれません。それは、まるで一瞬で反応するような、高速でレスポンスの良い検索体験です。

その体験の裏側にあるのが、私たちが開発した検索エンジンdocfindです。これはWebAssemblyを使用し、ブラウザ内で完全に動作します。本稿では、10年前のオートマトン理論に関するブログ記事からWebAssemblyバイナリのパッチ適用に至るまでの、docfind誕生のストーリーを紹介します。

課題

現在、私はVS Codeチームのソフトウェアエンジニアリングマネージャーを務めており、最近はコードを書く時間はあまり取れません。書く機会があったとしても、慣れない領域を扱うことはほとんどありません。しかし、何らかの対策を講じるまで気になって仕方がない問題というものがあります。

つい最近まで、私たちのウェブサイトの検索機能は基本的なものでした。クエリを入力すると、従来の検索エンジンを利用した検索結果ページにリダイレクトされるという仕組みです。これは今日の開発者が慣れ親しんでいる体験とは言えません。私は、他の多くのウェブサイトと同様に、入力するたびに検索結果が即座に表示されるようにしたいと考えました。それはVS Codeの「クイックオープン」（Ctrl+P）のようにキビキビとしたものであるべきです。

同僚のNick Troghと共に代替案を調査しました。当時の状況は以下のようなものでした。

  • Algolia：検索アズ・ア・サービス（Search-as-a-Service）の最先端。しかし、私は純粋なクライアントサイドのソリューションを求めていました。
  • TypeSense：強力なオープンソース検索エンジンですが、Algoliaと同様にサーバーサイドのコードが必要です。さらに、保守・監視すべきサービスが増えてしまいます。
  • Lunr.js：JavaScriptによるクライアントサイド検索で、有望に思えました。私たちのドキュメント（約3MBのMarkdown）で試しましたが、インデックスファイルが10MB近くになってしまいました。大きすぎます。
  • Stork Search：WebAssembly駆動のクライアントサイド検索で、デモも優れていました。しかし、テストしてみるとインデックスは依然としてかなり大きく、プロジェクトのメンテナンスも止まっているようでした。

これらの選択肢はいずれも、「高速」「クライアントサイド」「コンパクト」「ホストと運用が容易」という理想のバランスを満たしていませんでした。そこで、自分たちで何か作れないかと考え始めました。

インスピレーション

クライアントサイド検索について考えていたとき、数年前に読んだブログ記事を思い出しました。それは、ripgrepの作者であるAndrew Gallant（burntsushi）氏による『Index 1,600,000,000 Keys with Automata and Rust』という記事です。約10年前に公開されたこの記事は、有限状態トランスデューサ（FST: Finite State Transducers）を使用して、膨大な文字列データを、正規表現や曖昧検索をサポートする高速ルックアップ可能なコンパクトなバイナリ形式でインデックス化する方法を解説しています。

重要な洞察は、FSTはソートされた文字列キーを、メモリ効率が良くクエリも高速なステートマシンに格納できるという点です。さらに幸運なことに、Andrew氏はこれを正確に実装したfstというRustライブラリを公開していました。

ドキュメントから抽出したキーワードをFSTでインデックス化したらどうだろうか？ ユーザーがクエリを入力したら、ブラウザ内でFSTを使ってキーワードを照合し、サーバーへのラウンドトリップなしで関連するドキュメントのリストを返すのです。

しかし、どうやってドキュメントのキーワードを取得するのか？ また、すべての文字列をメモリに載せるとなると、非常に大きなインデックスファイルになってしまわないか？ 圧縮を使って可能な限り小さなインデックスを作成できないか？ この疑問が、パズルの残り二つのピースへと導いてくれました。

  • RAKE (Rapid Automatic Keyword Extraction)：テキストから意味のあるキーワードやフレーズを抽出するアルゴリズムです。ドキュメントを渡すと、重要度順にランク付けされたキーワードが返されます。
  • FSST (Fast Static Symbol Table)：短い文字列に最適化された圧縮アルゴリズムです。ドキュメントのタイトル、カテゴリ、スニペットをメモリ内に格納する必要があるため、圧縮はインデックスを小さく保つのに役立ちます。

高速なキーワード検索のためのFST、キーワード抽出のためのRAKE、文字列圧縮のためのFSSTという技術的基盤が揃いました。あとは、本業の合間に捻出した限られた時間の中で、あまり経験のないRustという言語で実装するだけでした。

解決策

最終的に、私は「docfind」という単一のCLIツールを作成しました。これは、ウェブサイトをビルドするたびにドキュメントからインデックスファイルを生成するためのものです。このCLIツールのユーザーは、インデックスファイルを作成するためにdocfind以外の外部依存関係を必要としません。そのインデックスファイルは単一のWebAssemblyモジュールとなり、HTTP経由で訪問者に簡単に配信されます。訪問者がウェブサイトにアクセスすると、ブラウザがバックグラウンドでWebAssemblyモジュールをダウンロードし、検索機能の基盤として使用します。

インデックスの構築

docfindがドキュメントのコレクション（documents.json）をそれぞれのインデックスファイル（docfind_bg.wasm）に変換する仕組みを図示します。

A diagram showing the flow of data in docfind

Docfindはまず、ドキュメントの情報（タイトル、カテゴリ、URL、本文）を含むJSONファイルを読み取ります。各ドキュメントに対してRAKEを使用してキーワードを抽出し、関連性スコアを割り当て、キーワードからドキュメントインデックスへマップするFSTを構築します。すべてのドキュメント文字列はFSSTで圧縮されます。FSTと圧縮された文字列の両方がバイナリブロブに詰め込まれ、これが実際のインデックスとなります。

A visual explanation of what is a document, what are keywords and how are they represented in the index

インデックスを表すデータ構造は驚くほど単純です。

pub struct Index {
    /// FST mapping keywords to document indices
    fst: Vec<u8>,

    /// FSST-compressed document strings (title, category, href, body)
    document_strings: FsstStrVec,

    /// For each keyword index, a list of (document_index, score) pairs
    keyword_to_documents: Vec<Vec<(usize, u8)>>,
}

インデックスはキーワードを格納し、それらを keyword_to_documents 内のインデックスへマップします。各エントリは、関連性スコアを持つ関連ドキュメントを指します。ドキュメント文字列は圧縮された状態で格納され、表示に必要な場合にのみ解凍されます。

さて、このインデックスデータ構造をバイナリファイルに書き出し、ウェブサイトの訪問者に配信し、サイト上のWebAssemblyモジュールで解析してFSTライブラリを使って検索操作を行うことも可能です。しかし、ここで興味深い工夫をしました。インデックスを別のバイナリファイルとして出荷するのではなく、docfindはそれを検索ライブラリのWebAssemblyモジュールに直接埋め込みます。これにより、訪問者は検索する際に単一のHTTPリソースをフェッチするだけで済みます。

インデックスの検索

では、クライアントサイドでは何が起きているのでしょうか？ ユーザーがクエリを入力すると、WebAssemblyモジュールがメモリ（コードとドキュメントインデックス）にロードされ、FSTデータ構造をたどって検索操作としてクエリを実行します。私たちは、より関連性の高い一致を得るために、レーベンシュタイン・オートマトン（タイプミスの許容用）と前方一致を活用しています。最後に、複数の合致キーワードからのスコアを組み合わせ、必要なドキュメント文字列をオンデマンドで解凍し、ランキング結果をJavaScriptオブジェクトとして返すことで検索結果が生成されます。

課題

このプロジェクトで最も厄介だったのは、検索アルゴリズムやキーワード抽出ではなく、インデックスをWebAssemblyバイナリに埋め込むことでした。

単純なアプローチは、Rustの include_bytes! マクロを使用して、コンパイル時にインデックスをWebAssemblyモジュールに焼き付けることでしょう。しかし、それだとドキュメントが更新されるたびにWebAssemblyモジュールを再コンパイルする必要があります。そうではなく、CLIツールが更新されたインデックスをパッチできるような、プリコンパイル済みのWASM「テンプレート」が必要でした。

つまり、空のインデックスを持つWebAssemblyモジュールテンプレートを静的に作成し、それをdocfindに埋め込む必要がありました。そして、docfindが以下の処理を行うようにします。

  1. 埋め込まれたWebAssemblyモジュールを解析し、その構造を理解する。
  2. メモリセクションを見つけ、インデックスに必要な追加スペースを計算する。
  3. インデックスを新しいデータセグメントとして追加し、データカウントセクションを適切に更新する。
  4. プレースホルダーのグローバル変数の位置を特定し、実際のインデックス位置でパッチを適用する。
  5. 有効なWebAssemblyモジュールを書き出す。

WebAssemblyモジュールテンプレートは、特徴的なマーカー値を持つ2つのプレースホルダーグローバルを宣言しています。

#[unsafe(no_mangle)]
pub static mut INDEX_BASE: u32 = 0xdead_beef;

#[unsafe(no_mangle)]
pub static mut INDEX_LEN: u32 = 0xdead_beef;

実行時に、検索関数はこれらを使用して埋め込まれたインデックスを見つけ、生のバイト列から解析します。

static INDEX: OnceLock<Index> = OnceLock::new();

pub fn search(query: &str, max_results: Option<usize>) -> Result<JsValue, JsValue> {
    let index = INDEX.get_or_init(|| {
        let raw_index = unsafe {
            std::slice::from_raw_parts(INDEX_BASE as *const u8, INDEX_LEN as usize)
        };
        Index::from_bytes(raw_index).expect("Failed to deserialize index")
    });
    // ... perform search
}

CLIツールはWASMテンプレートのエクスポートセクションをスキャンしてこれらのグローバルを見つけ、グローバルセクションを読み取ってメモリアドレスを取得し、それらの 0xdead_beef 値を含むデータセグメントを実際のインデックスのベースアドレスと長さでパッチします。

// Patch the data if it contains the INDEX_BASE or INDEX_LEN addresses
if index_base_global_address >= &start && index_base_global_address < &end {
    data[base_relative_offset..base_relative_offset + 4]
        .copy_from_slice(&(index_base as i32).to_le_bytes());
    data[length_relative_offset..length_relative_offset + 4]
        .copy_from_slice(&(raw_index.len() as i32).to_le_bytes());
}

// Add index as new data segment
data_section.active(
    0,
    &ConstExpr::i32_const(index_base as i32),
    raw_index.iter().copied(),
);

控えめに言っても、これは単純なことではありませんでした。WASMバイナリフォーマットを理解し、グローバル変数がどのように格納され参照されるかを解明し、メモリオフセットを計算する。これらは簡単にサイドプロジェクトを挫折させるような種類の問題です。

ブレイクスルー

正直に言うと、GitHub Copilotエージェントを使わずにこのプロジェクトを完成させることはできなかったでしょう。日常的にコーディングをしていないマネージャーにとって、学習曲線が急峻で知られるRustでプロジェクトに取り組むのは野心的なことでした。私はRustの専門家ではありません。借用チェッカー（borrow checker）に対する筋肉反射もありません。そしてもちろん、WebAssemblyバイナリフォーマットに関する深い知識もありませんでした。しかし、全体としてどこを目指したいのかという一般的な方向感は持っていました。Copilotは、私が空白を埋め、困難な問題に取り組むのを助けてくれました。

調査と探索。 FST、RAKE、FSSTを評価していたとき、これらのライブラリの仕組みを理解したり、明確な質問をしたり、アイデアを出し合ったりするためにCopilotを使いました。まるで、いつでも相談できる知識豊富な同僚がいるような感覚でした。

効率的なRust開発。 これがおそらく最大の収穫です。CopilotのNext Edit Suggestions（次に行う編集の提案）のおかげで、私は生産的なRustプログラマーになれました。借用チェッカーと戦ったり、構文を調べたりすることに精神的なエネルギーを費やすことはなくなりました。Copilotが機械的な部分を処理してくれたので、私はロジックに集中することができました。

WASMターゲットの構築。 プロジェクトにWebAssembly出力ターゲットを追加するようCopilotに依頼したとき、設定を追加するだけでなく、私が検索関数をエクスポートしたいという意図を推測し、適切な wasm-bindgen アノテーションを備えた lib.rs 全体を構築してくれました。ビルドするためのコマンドまで教えてくれました。

docfindライブラリ。 Copilotは、docfindのリポジトリ構築を助けてくれました。これには、パフォーマンスの数字を表示する実用的なデモページの作成も含まれています。

困難な部分の突破。 WASMバイナリの操作が、このプロジェクトの技術的な核心でした。グローバル変数の特定、データセグメントのパッチ、メモリセクションの更新方法を理解するには、これまで遭遇したことのない詳細に踏み込む必要がありました。Copilotは、WASMバイナリフォーマットを理解し、適切な wasmparser や wasm-encoder APIを提案し、パッチを適用したバイナリが無効だった場合に問題のデバッグを助けてくれました。

Copilotがなければ、このプロジェクトにはかなりの時間がかかっていたはずです。途中で諦めていた可能性さえあります。時間的制約があり、専門外の分野で作業する場合、知識のギャップを埋め、ボイラープレートを処理してくれるAIアシスタントがいることは、単に便利というだけではありません。リリースできるか、諦めるかの分かれ目となるのです。

結果

現在、docfindはVS Codeドキュメントサイトの検索体験を支えています。現在のパフォーマンス指標はdocfindのREADMEで確認でき、そこには5万件のニュース記事をブラウザ内で完全に検索するインタラクティブなデモも含まれています。

VS Codeウェブサイトの場合（約3MBのMarkdown、見出しごとに分割された約3,700のドキュメント）

  • インデックスサイズ：非圧縮時 約5.9MB、Brotli圧縮時 約2.7MB
  • 検索速度：M2 MacBook Airで1クエリあたり約0.4ms
  • ネットワーク：単一のWebAssemblyモジュールで、ユーザーが検索する意図を示したときにのみダウンロード

保守すべきサーバーはありません。管理すべきAPIキーもありません。継続的なコストもかかりません。ただ、ビルド時に作成され、ブラウザ内で完全に実行される自己完結型のWebAssemblyモジュールがあるだけです。

ぜひ試してみてください

docfindをオープンソース化しました。あなたの静的サイトでも今日から使用できます。インストールは簡単です。

curl -fsSL https://microsoft.github.io/docfind/install.sh | sh

Windowsの場合も同様です。

irm https://microsoft.github.io/docfind/install.ps1 | iex

ドキュメントを含むJSONファイルを用意し、docfind documents.json output を実行すれば、サイトですぐに使える docfind.js と docfind_bg.wasm が得られます。検索結果を表示するためのクライアントサイドUIはご自身で用意する必要があります（GitHub Copilotを使えばいつでも作成できますよ 😉）。

docfindの開発は、私がそもそもなぜエンジニアになったのかを思い出させてくれました。それは、エレガントな技術で現実の問題を解決する喜びです。また、CopilotのようなAIツールがいかに可能性を広げ、時間や専門知識といった制約のもとでは到底手が届かなかったプロジェクトにも挑戦できるようにしてくれているかを証明するものでもありました。最後に、VS CodeでRustを扱うなら必須の拡張機能である rust-analyzer にも感謝を捧げます。

質問やフィードバックがあれば、お気軽にdocfindリポジトリでIssueを開いてください。どのように活用されているか、ぜひお聞かせください。

ハッピーコーディング！💙

© . This site is unofficial and not affiliated with Microsoft.