我寫了一個可以加到靜態網站上的基礎搜尋模組。它非常輕量（經 gzip 壓縮後僅 50kB–100kB），可搭配 Hugo、Zola 與 Jekyll 使用。目前僅支援完整單字的搜尋。請試試左側的搜尋框以查看示範。程式碼已放在 Github 上。

靜態網站產生器非常神奇。它們兼具兩者的優點：無需犧牲效能就能擁有動態內容。

這些年來，這個部落格先後採用過 Jekyll、Cobalt，最近則是使用 Zola。

不過，我一直不太喜歡的一點是，靜態網站卻沒有「靜態」的搜尋引擎。取而代之的是，大家往往仰賴Google 自訂搜尋、像 Algolia 這類外部搜尋引擎，或是純 JavaScript 的解決方案，例如 lunr.js 或 elasticlunr。

這些方案對大多數網站來說都堪用，但總覺得不是最終的解答。

我不想再對 Google 增加一層依賴；也不想使用像 Algolia 這種獨立的後端服務，它不僅會增加延遲，而且是專有軟體。

另一方面，我也不太喜歡過度仰賴 JavaScript 的網站。舉例來說，光是 lunr 產生的搜尋索引就可能高達數 MB。即使以現今的頻寬標準來看，也顯得相當奢侈。除此之外，解析 JavaScript 仍然相當耗時。

我想要的是一個簡單、精簡且自給自足的搜尋功能，可以跟其他靜態內容一起部署。

因此，我乾脆完全沒有在部落格上加入搜尋功能。這其實很可惜，因為隨著文章數量不斷增加，要找到相關內容也變得越來越困難。

構想

早在 2013 年的許多年前，我讀到了一篇名為 “Writing a full-text search engine using Bloom filters”（《使用 Bloom filters 編寫全文本搜尋引擎》） 的文章——那讓我茅塞頓開。

構想很簡單：把我所有的部落格文章丟進一個產生器，利用這個神奇的資料結構——✨Bloom Filter(布隆過濾器) ✨——來建立一個微小且自給自足的搜尋索引。

等等，什麼是 Bloom Filter？

Bloom filter 是一種以節省空間的方式來檢查某個元素是否屬於某個集合的方法。

訣竅在於，它並不會儲存元素本身；它只是以一定的信心程度知道這些元素曾被儲存過。以我們的情境來說，它能以一定的錯誤率判斷某個單字是否出現在某篇文章中。

以下是原文中用來為每篇文章產生 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 才剛滿三歲，WebPack 也才剛滿一歲，因此我也不知道該去哪裡尋找現成的解決方案。

不知下一步該怎麼走，這個想法就一直只是個空想。

一線曙光

五年後的 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，但我仍然不知道該如何將它打包以用於網頁……直到 wasm-pack 在 2018 年 2 月問世。

哎呀！我把一些 Rust 程式碼送進你的瀏覽器了。

現在，我已經集齊了拼圖的所有碎片：

• Rust——我所熟悉的語言
• wasm-pack——用於 WebAssembly 模組的打包器
• 一個可運作、作為概念驗證的原型

你在本頁左側看到的搜尋框就是成果。它完全透過 WebAssembly 以 Rust 運行（也就是所謂的 RAW 技術堆疊）。喜歡的話，現在就試試看吧。

一路上遇到了不少障礙。

Bloom Filter 相關 Crates

我研究了幾個實作 Bloom filter 的 Rust 函式庫（crates）。

一開始我嘗試了 jedisct1 的 rust-bloom-filter，但其型別並未實作 Serialize／Deserialize。這意味著我無法將產生的 Bloom filter 儲存於執行檔內並在客戶端載入。

嘗試了其他幾個之後，我找到了支援序列化的 cuckoofilter crate，其行為類似於 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 為十篇文章打包過濾器時的輸出大小：

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

44kB 聽起來還不錯，但這只是十篇文章的 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

接著我移除了 web-sys，因為我們不需要綁定到 DOM：152858 bytes。

有一個名為 twiggy 的工具可用來分析 Wasm 執行檔的程式碼大小。它印出了以下輸出：

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

就我所見，執行檔中最大的一塊是存放文章原始資料的區段。接下來是函式標頭，以及一些浮點數轉十進位的小工具函式，這些很可能來自反序列化。

最後，我嘗試了 wasm-snip，它會像這樣把 WebAssembly 函式的主體替換為 unreachable，但並未縮減程式碼大小：

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

在稍微調整 cuckoo filter 的參數並從文章中移除停用詞之後，我將大小降至 121kB（經 gzip 壓縮後 51kB）——考慮到網路上圖片的平均大小約為 900kB，這已經相當不錯了。除此之外，搜尋功能只有在使用者點擊搜尋欄位時才會載入。

更新

最近我將專案從 cuckoofilter 遷移至 XOR filters(XOR 過濾器)。我使用了非常棒的 xorf 專案，它內建了 serde 序列化，讓我得以移除大量自訂程式碼。

藉此，我又將承載大小再縮減了 20–25%。現在我的部落格已降至 99kB（經 gzip 壓縮後 49kB）。🎉

新版本已經在 crates.io 上發布，歡迎試用。

前端與膠合程式碼

wasm-pack 會自動產生用來與 Wasm 溝通的 JavaScript 程式碼。

至於搜尋介面，我從 w3schools 自訂了一些 JavaScript 與 CSS 片段。它甚至支援鍵盤操作！現在當使用者輸入搜尋查詢時，我們會逐一透過每篇文章的 cuckoo filter 嘗試比對單字，並依命中次數對結果進行評分。感謝我親愛的同事 Jorge Luis Betancourt（豪爾赫·路易斯·貝當庫） 新增了這個部分。

（有趣的是，這段動畫的大小與未經壓縮的 Wasm 搜尋本身差不多。）

注意事項

僅會比對完整單字。我很想加入前綴搜尋，但嘗試後發現執行檔會變得過大。

使用方式

用來產生 Wasm 檔案的獨立執行檔名為 tinysearch。它需要一個指向 JSON 檔案的路徑作為輸入：

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 將徹底改變我們為網路及更廣泛領域打造產品的方式。兩年前還非常困難的事，現在已變得輕而易舉：以任何語言撰寫的程式碼都能配送到每個瀏覽器。我對它的未來感到無比興奮。
• 如果你正在為公司網站尋找獨立、自架的搜尋索引，不妨看看 sonic。也可以參考 stork 作為替代方案。

試試看！

tinysearch 的程式碼在 Github 上。

請留意以下限制：

• 僅搜尋完整單字。沒有搜尋建議。原因是前綴搜尋會讓執行檔大小像曼陀珠加可樂一樣爆炸性膨脹。
• 由於我們將所有文章的搜尋索引打包進同一個靜態執行檔中，我僅建議將其用於中小型網站。每篇文章大約會佔用 4kB（未壓縮）。
• 目前編譯時間非常糟糕（在我的機器上全新安裝後約需 1.5 分鐘），主要原因是每次重建索引時都要從頭編譯 Rust crate。
  更新：這在很大程度上已透過 CephalonRho 在 PR #13 中的出色工作獲得修正。再次感謝！

最終的 Wasm 程式碼極為快速，因為我們省去了與搜尋伺服器之間的來回往返。即時的回饋循環感覺更像是篩選清單，而非在文章中搜尋。它甚至可以完全離線運作，如果你想將它與應用程式一起打包，這會非常方便。