\
## TL;DR

* 🦀 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 provide great memory efficiency and fast lookup for value existence.
* 🧑‍🍳 WebAssembly's performance and code size are not guaranteed. Make sure to measure and benchmark.


---

I always knew I wanted a full-text search feature for the articles in my [portfolio](https://dawchihliou.github.io/) 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🚀

## Inspired by `tinysearch`: A WebAssembly Full-text Search Engine

After some researching, I found a search engine called `tinysearch`. It's a static search engine built with [Rust](https://www.rust-lang.org/) and [WebAssembly](https://webassembly.org/) (Wasm). The author Matthias Endler wrote [an amazing blog post](https://endler.dev/2019/tinysearch) 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](https://nextjs.org/).

\
*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.

## What Does The Search Feature Looks Like?

 ![](https://cdn.hackernoon.com/images/-dga32tk.gif.webp)

Very simple:

* Users type anything in the search input.
* The search engine searches the keywords in all the contents and finds the most relevant articles.
* UI displays a ranked search result list.

\
You can try out the search function on the [Articles page](https://dawchihliou.github.io/articles)!

## A Little Bit of Stats

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.

## How Does WebAssembly Full-text Search Function Work?

Most [modern browsers now support WebAssembly](https://caniuse.com/?search=webassembly). They are able to run native WebAssembly code and binary alongside JavaScript.

\
The concept for the search function is straightforward. It takes in a query string as a 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:

\
 ![](https://cdn.hackernoon.com/images/-syc326o.png)

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

\
You can imagine that this is not the most memory-efficient approach with a hash set. There are better data structures to replace it: **xor filters**.

## What are Xor Filters?

[Xor filters](https://arxiv.org/abs/1912.08258) 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 full-text search.

\
Instead of storing the actual input values like a hash set, xor filters store fingerprints (L-bit hashed sequence) of input values [in a specific way](https://web.stanford.edu/class/archive/cs/cs166/cs166.1216/lectures/13/Slides13.pdf#page=49). 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.

## How Did I Build the Xor Filters with Rust?

Since I had the article data generated by 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 them 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:

\
 ![](https://cdn.hackernoon.com/images/-5pd32dg.png)

`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 looks like this:

\
```rust
use std::collections::hash_map::DefaultHasher;
use xorf::{Filter, HashProxy, Xor8};

mod utils;

fn build_filter(title: String, body: String) -> HashProxy<String, DefaultHasher, Xor8> {
  let title_tokens: HashSet<String> = utils::tokenize(&title);
  let body_tokens: HashSet<String> = utils::tokenize(&body);
  let tokens: Vec<String> = body_tokens.union(&title_tokens).cloned().collect();

  HashProxy::from(&tokens)
}
```

\
If you are interested in the actual implementation, you can [read more in the repository](https://github.com/DawChihLiou/dawchihliou.github.io/blob/main/scripts/fulltext-search/src/storage.rs).

## Putting It All Together

 ![](https://cdn.hackernoon.com/images/-spe32sc.png)

## Integrating WebAssembly in Next.js

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](https://github.com/vercel/next.js/issues/25852) to generate the WebAssembly module in `.next/server`directory so that the static pages can pre-render successfully when running the `next build` script.

\
next.config.js

```javascript
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✨

## Using The WebAssembly in The React Component

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

The generated `.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 them. Like this:

\
components/Search.tsx

```typescript
import React, { useState, useCallback, ChangeEvent, useEffect } from 'react'
import dynamic from 'next/dynamic'

type Title = string;
type Url = string;
type SearchResult = [Title, Url][];

const Search = dynamic({
  loader: async () => {
    const wasm = await import('../../wasm/fulltext-search/pkg')

    return () => {
      const [term, setTerm] = useState('')
      const [results, setResults] = useState<SearchResult>([])

      const onChange = useCallback((e: ChangeEvent<HTMLInputElement>) => {
        setTerm(e.target.value)
      }, [])

      useEffect(() => {
        const pending = wasm.search(term, 5)
        setResults(pending)
      }, [term])

      return (
        <div>
          <input
            value={term}
            onChange={onChange}
            placeholder="🔭 search..."
          />
          {results.map(([title, url]) => (
            <a key={url} href={url}>{title}</a>
          ))}
        </div>
      )
    }
  },
})

export default Search
```

## Optimizing The WebAssembly Code Size

Without any optimization, the original Wasm file size was `114.56KB`. I used [Twiggy](https://github.com/rustwasm/twiggy) to find out the code size.

\
```javascript
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 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](https://rustwasm.github.io/docs/book/reference/code-size.html).

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

\
Cargo.toml

```yaml
[profile.release]
+ opt-level = 's'
+ lto = true
```

```bash

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

```rust
+ #[global_allocator]
+ static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
```

```bash
Shallow Bytes  │ Shallow % │ Item
───────────────┼───────────┼─────────────────────
        100483 ┊   100.00% ┊ Σ [1625 Total Rows]
```

\
Then I tried the `wasm-opt` tool in [Binaryen](https://github.com/WebAssembly/binaryen).

\
```javascript
wasm-opt -Oz -o wasm/fulltext-search/pkg/fulltext_search_core_bg.wasm wasm/fulltext-search/pkg/fulltext_search_core_bg.wasm
```

```bash
Shallow 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😎

## Is It Really Snappy?

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😎

## Final Thoughts

After some experiments, 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 more comprehensive search functionality, here are a few cool products available:

\
**SaaS Search Engines**

* [Algolia](https://www.algolia.com/)

**Static Search Engines**

* [tinysearch](https://github.com/tinysearch/tinysearch)

**Server-based Search Engines**

* [Meilisearch](https://www.meilisearch.com/)
* [Typesense](https://typesense.org/)

**In-browser Search Engines**

* [FlexSearch](https://github.com/nextapps-de/flexsearch)
* [MiniSearch](https://github.com/lucaong/minisearch)
* [Elasticlunr.js](http://elasticlunr.com/)

## References

* Article: [A Tiny, Static, Full-Text Search Engine using Rust and WebAssembly - Matthias Endler](https://endler.dev/2019/tinysearch)
* Article: [Writing a full-text search engine using Bloom filters - Stavros Korokithakis](https://www.stavros.io/posts/bloom-filter-search-engine/)
* Article: [Xor Filters: Faster and Smaller Than Bloom Filters - Daniel Lemire](https://lemire.me/blog/2019/12/19/xor-filters-faster-and-smaller-than-bloom-filters/)
* Article: [Shrinking .wasm Code Size - The Rust and WebAssembly Working Group](https://rustwasm.github.io/docs/book/reference/code-size.html)
* Article: [Building Better Next.js Static Sites with MDX and Contentlayer - Daw-Chih Liou](https://dawchihliou.github.io/articles/build-better-nextjs-static-sites-with-mdx-and-contentlayer)
* Article: [Next.js - Dynamic Import](https://nextjs.org/docs/advanced-features/dynamic-import)
* Website: [Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://arxiv.org/abs/1912.08258)
* Website: [Daw-Chih Liou's Portfolio](https://dawchihliou.github.io/)
* Website: [Meilisearch](https://www.meilisearch.com/)
* Website: [Typesense](https://typesense.org/)
* Website: [Algolia](https://www.algolia.com/)
* Website: [Elasticlunr.js](http://elasticlunr.com/)
* Website: [Rust](https://www.rust-lang.org/)
* Website: [WebAssembly](https://webassembly.org/)
* Website: [MDN WebAssembly](https://developer.mozilla.org/en-US/docs/WebAssembly)
* Website: [Next.js](https://nextjs.org/)
* Website: [Can I use WebAssembly?](https://caniuse.com/?search=webassembly)
* Lecture: [Approximate Membership Queries - Stanford](https://web.stanford.edu/class/archive/cs/cs166/cs166.1216/lectures/13/Slides13.pdf#page=49)
* Wiki: [Full-text Search](https://en.wikipedia.org/wiki/Full-text_search)
* GitHub: [Next.js & WebAssembly example](https://github.com/vercel/next.js/tree/canary/examples/with-webassembly)
* GitHub: [Minimizing Rust Binary Size](https://github.com/johnthagen/min-sized-rust)
* GitHub: [dawchihliou.github.io](https://github.com/DawChihLiou/dawchihliou.github.io/blob/main/scripts/fulltext-search/src/storage.rs)
* GitHub: [Webpack 5 breaks dynamic wasm import for SSR](https://github.com/vercel/next.js/issues/25852)
* Github: [tinysearch](https://github.com/tinysearch/tinysearch)
* GitHub: [Meilisearch](https://github.com/meilisearch/meilisearch)
* GitHub: [xorf](https://github.com/ayazhafiz/xorf)
* GitHub: [wasm-pack](https://github.com/rustwasm/wasm-pack)
* GitHub: [Binaryen](https://github.com/WebAssembly/binaryen)
* GitHub: [Twiggy](https://github.com/rustwasm/twiggy)
* GitHub: [Clippy](https://github.com/rust-lang/rust-clippy)
* GitHub: [web-sys](https://github.com/rustwasm/wasm-bindgen/tree/main/crates/web-sys)
* GitHub: [once_cell](https://github.com/matklad/once_cell)
* GitHub: [Bincode](https://github.com/bincode-org/bincode)
* GitHub: [wee_alloc](https://github.com/rustwasm/wee_alloc)
* GitHub: [Serde](https://github.com/serde-rs/serde)
* GitHub: [Anyhow](https://github.com/dtolnay/anyhow)
* GitHub: [Contentlayer](https://github.com/contentlayerdev/contentlayer)
* GitHub: [FlexSearch](https://github.com/nextapps-de/flexsearch)
* GitHub: [MiniSearch](https://github.com/lucaong/minisearch)


---

This article was also posted on [Daw-Chih’s website](https://dawchihliou.github.io/articles/i-built-a-snappy-full-text-search-with-webassembly-rust-nextjs-and-xor-filters).

Flow

Alongside

Glue

Mozilla

Target

2022 - HackerNoon Contributor of the Year - Leadership

2022 - HackerNoon Contributor of the Year - Learning

2022 - HackerNoon Contributor of the Year - Product Management

2022 - HackerNoon Contributor of the Year - Software Engineering

2022 - HackerNoon Contributor of the Year - Typescript

Coding Guru of 2022

Check out my website!

Nominated for 2022 - HackerNoon Contributor of the Year - Product Management

Nominated for 2022 - HackerNoon Contributor of the Year - Typescript

Nominated for 2022 - HackerNoon Contributor of the Year - Leadership

Nominated for 2022 - HackerNoon Contributor of the Year - Software Engineering

Nominated for Coding Guru of 2022

Nominated for 2022 - HackerNoon Contributor of the Year - Learning

Too Long; Didn't Read

Build an AI-based text classifier with Tensorflow & NoSQL

Static Full-Text Search in Next.js with WebAssembly, Rust, and Xor Filters

Static Full-Text Search in Next.js with WebAssembly, Rust, and Xor Filters

Too Long; Didn't Read

Companies Mentioned

Coin Mentioned

@dawchihliou

RELATED STORIES