I Built a Snappy Static Full-text Search With WebAssembly, Rust, Next.js, and Xor Filters | by Daw-Chih Liou | Mar, 2022

  • πŸ¦€ There is a rich toolkit for developing WebAssembly with Rust. It’s fun!
  • 🀝 WebAssembly and Next.js play fairly well together, but be aware of the known issues.
  • πŸ§‘β€πŸ”¬ Xor filters are data structures that provides great memory efficiency and fast lookup for value existence.
  • πŸ§‘β€πŸ³ WebAssembly’s performance and code size is not guaranteed. Make sure to measure and benchmark.

I always knew I wanted a full-text search feature for the articles in my portfolio to provide the visitors with quick access to the content they are interested in. After migrating to Contentlayer, it doesn’t seem to be so far-fetched anymore. So I started exploring.

After some research, I found a search engine called tinysearch. It’s static search engine built with Rust and WebAssembly (Wasm). The author Matthias Endler wrote an amazing blog post about how tinysearch came about.

I loved the idea of ​​constructing a minimalistic search engine at build time and shipping it in optimized low-level code to the browsers. So I decided to use tinysearch as the blueprint and write my own search engine to integrate with my Next.js static site.

I highly recommend reading tinysearch‘s codebase. It’s very well-written. My search engine’s implementation is a simplified version of it. The core logic is the same.

Very simple:

  • Users type anything in the search input.
  • Search engine searches the key words in all the contents and finds the most relevant articles.
  • UI displays a ranked search result list.

You can try out the search function at the Articles page!

At the time of writing this article, there are:

  • 7 articles (more to come)
  • 13,925 words
  • 682KB of data files (generated by Contentlayer)

For the full-text search to work for static sites that are priming for speed, the code size has to be small.

Most of the modern browsers now support WebAssembly. They are able to run native WebAssembly code alongside JavaScript.

The concept for the search function is straightforward. It takes in a query string as parameter. In the function, we tokenize the query into search terms. We then give a ranking score to each article based on how many search terms does it contain. Finally, we rank the articles by relevancy. The higher the score, the more relevant it is.

The flow looks like this:

Scoring the articles is where the most computing comes in. A naive approach would be transforming each article into a HashSet that contains all the unique words in the article. We can calculate the score by simply counting how many search terms are in the HashSet.

You can image that this is not the most efficient approach with HashSet. There are better data structures to replace it: xor filters.

Xor filters are relatively new data structures that allow us to estimate whether a value exists or not. It’s fast and memory efficient so it’s very suitable for the full-text search.

Instead of storing the actual input values ​​like HashSet, xor filters store fingerprints (L-bit hashed sequence) of input values ​​in a specific way. When looking for whether a value exists in the filter, it checks if the fingerprint of the value is present.

However, Xor filters have a couple of trade-offs:

  • Xor filters are probabilistic and there’s a chance false-positive can happen.
  • Xor filters are not able to estimate the existence of partial values. So in my use case, the full-text search will only be able to search for complete words.

Since I had the article data generated by the Contentlayer, I constructed the xor filters by feeding them with the data before the WebAssembly is built. I then serialized the xor filters and stored it in a file. To use the filters in the WebAssembly, all I needed to do was to read from the storage file and deserialize the filters.

The filter generation flow looks like this:

xorf crate is a good choice for xor filters implementation because it offers serialization/deserialization and a few features that improve memory efficiency and false-positive rate. It also provides a very handy HashProxy struct for my use case to construct a xor filter with a slice of strings. The construction written in Rust roughly look like this:

If you are interested in the actual implementation, you can read more in the repository.

Here’s how I integrated the xor filter generation script and WebAssembly inside Next.js.

The file structure looks like this:

my-portfolio
β”œβ”€β”€ next.config.js
β”œβ”€β”€ pages
β”œβ”€β”€ scripts
β”‚ └── fulltext-search
β”œβ”€β”€ components
β”‚ └── Search.tsx
└── wasm
└── fulltext-search

To support WebAssembly, I updated my Webpack configuration to load WebAssembly modules as async modules. To make it work for static site generation, I needed a workaround to generate the WebAssembly module in .next/serverdirectory so that the static pages can pre-render successfully when running the next build script.

The code for next.config.js is given below:

webpack: function (config, { isServer }) {
// it makes a WebAssembly modules async modules
config.experiments = { asyncWebAssembly: true }
// generate wasm module in ".next/server" for ssr & ssg
if (isServer) {
config.output.webassemblyModuleFilename =
'./../static/wasm/[modulehash].wasm'
} else {
config.output.webassemblyModuleFilename = 'static/wasm/[modulehash].wasm'
}
return config
},

That’s all there is for the integration✨

To build the WebAssembly module from the Rust code, I use wasm-pack.

The born .wasm file and the glue code for JavaScript are located in wasm/fulltext-search/pkg. All I needed to do was to use next/dynamic to dynamically import the them. Like this:

Without any optimization, the original Wasm file size was 114.56KB. I used Twiggy to find out the code size.

Shallow Bytes  β”‚ Shallow % β”‚ Item
───────────────┼───────────┼─────────────────────
117314 β”Š 100.00% β”Š Ξ£ [1670 Total Rows]

Compared with the 628KB of raw data files, it was so much smaller than I expected. I was happy to ship it to the production already but I was curious to see how much code size I could trim off with The Rust And WebAssembly Working Group’s optimization recommendation.

The first experiment was toggling LTO and trying out different opt-levels. The following configuration yields the smallest .wasm code size:

# Cargo.toml[profile.release]
+ opt-level = 's'
+ lto = true
Shallow Bytes β”‚ Shallow % β”‚ Item
───────────────┼───────────┼─────────────────────
111319 β”Š 100.00% β”Š Ξ£ [1604 Total Rows]

Next I replaced the default allocator with wee_alloc.

// wasm/fulltext-search/src/lib.rs+ #[global_allocator]
+ static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
Shallow Bytes β”‚ Shallow % β”‚ Item
───────────────┼───────────┼─────────────────────
100483 β”Š 100.00% β”Š Ξ£ [1625 Total Rows]

Then I tried the wasm-opt tool in Binary.

wasm-opt -Oz -o wasm/fulltext-search/pkg/fulltext_search_core_bg.wasm wasm/fulltext-search/pkg/fulltext_search_core_bg.wasmShallow Bytes  β”‚ Shallow % β”‚ Item
───────────────┼───────────┼─────────────────────
100390 β”Š 100.00% β”Š Ξ£ [1625 Total Rows]

That’s a 14.4% off from the original code size.

At the end, I was able to ship a full-text search engine in:

  • 98.04 KB raw
  • 45.92 KB gzipped

Not bad.

I profiled the performance with web-sys and collected some data:

  • number of searches: 208
  • min: 0.046 ms
  • max: 0.814 ms
  • mean: 0.0994 ms ✨
  • standard deviation: 0.0678

On average, it takes less than 0.1 ms to perform a full-text search.

It’s pretty snappy.

After some experiment, I was able to build a fast and lightweight full-text search with WebAssembly, Rust, and xor filters. It integrates well with Next.js and static site generation.

The speed and size come with a few trade-offs but they don’t have a big impact on the user experience. If you are looking for a more comprehensive search functionality, here are a few cool products available:

SaaS Search Engines

Static Search Engines

Server-based Search Engines

In-browser Search Engines

Leave a Comment