Next.js 中使用 WebAssembly、Rust 和 Xor 过滤器的静态全文搜索经过@dawchihliou
3,424 讀數

Next.js 中使用 WebAssembly、Rust 和 Xor 过滤器的静态全文搜索

2022/04/08
经过 @dawchihliou 3,424 讀數
tldt arrow
ZH
Read on Terminal Reader

太長; 讀書

🦀 有一个丰富的工具包用于使用 Rust 开发 WebAssembly。好有趣! 🤝 WebAssembly 和 Next.js 配合得很好,但要注意已知问题。 🧑‍🔬 Xor 过滤器是一种数据结构,可提供出色的内存效率和快速查找值的存在。 🧑‍🍳 WebAssembly 的性能和代码大小无法保证。确保进行测量和基准测试。

Companies Mentioned

Mention Thumbnail
Mention Thumbnail

Coin Mentioned

Mention Thumbnail
featured image - Next.js 中使用 WebAssembly、Rust 和 Xor 过滤器的静态全文搜索
Daw-Chih Liou HackerNoon profile picture

@dawchihliou

Daw-Chih Liou

學到更多
LEARN MORE ABOUT @DAWCHIHLIOU'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

TL;博士

  • 🦀 有一个丰富的工具包用于使用 Rust 开发 WebAssembly。好有趣!
  • 🤝 WebAssembly 和 Next.js 配合得很好,但要注意已知问题。
  • 🧑‍🔬 Xor 过滤器是一种数据结构,可提供出色的内存效率和快速查找值的存在。
  • 🧑‍🍳 WebAssembly 的性能和代码大小无法保证。确保进行测量和基准测试。

我一直都知道我想要为我的投资组合中的文章提供全文搜索功能,以便访问者快速访问他们感兴趣的内容。迁移到 Contentlayer 后,它似乎不再那么牵强了。于是我开始探索🚀

tinysearch启发:WebAssembly 全文搜索引擎

经过一番研究,我找到了一个名为tinysearch的搜索引擎。这是一个使用RustWebAssembly (Wasm) 构建的静态搜索引擎。作者 Matthias Endler 写了一篇关于tinysearch是如何产生的精彩博客文章。

我喜欢在构建时构建一个简约的搜索引擎并将其以优化的低级代码发送到浏览器的想法。所以我决定使用tinysearch作为蓝图,编写自己的搜索引擎来与我的Next.js 静态站点集成。

我强烈推荐阅读tinysearch的代码库。它写得很好。我的搜索引擎的实现是它的简化版本。核心逻辑是一样的。

搜索功能是什么样的?

image

很简单:

  • 用户在搜索输入中键入任何内容。
  • 搜索引擎搜索所有内容中的关键字并找到最相关的文章。
  • UI 显示一个排名的搜索结果列表。

您可以试试文章页面的搜索功能!

一点点统计数据

在撰写本文时,有:

  • 7 篇文章(更多内容🚀)
  • 13,925 字
  • 682KB 的数据文件(由 Contentlayer 生成)

为了使全文搜索适用于追求速度的静态站点,代码大小必须很小。

WebAssembly 全文搜索功能如何工作?

大多数现代浏览器现在都支持 WebAssembly 。他们能够与 JavaScript 一起运行本机 WebAssembly 代码和二进制文件。

搜索功能的概念很简单。它接受一个查询字符串作为参数。在函数中,我们将查询标记为搜索词。然后,我们根据每篇文章包含的搜索词数为每篇文章打分。最后,我们根据相关性对文章进行排名。分数越高,它的相关性就越高。

流程如下所示:

image

对文章进行评分是计算量最大的地方。一种简单的方法是将每篇文章转换为包含文章中所有唯一单词的哈希集。我们可以通过简单地计算哈希集中有多少搜索词来计算分数。

您可以想象,这不是哈希集最节省内存的方法。有更好的数据结构来代替它: xor 过滤器

什么是异或过滤器?

Xor 过滤器是相对较新的数据结构,它允许我们估计一个值是否存在。它速度快,内存效率高,因此非常适合全文搜索。

xor 过滤器不是像散列集那样存储实际输入值,而是以特定方式存储输入值的指纹(L 位散列序列)。在查找过滤器中是否存在某个值时,它会检查该值的指纹是否存在。

但是,Xor 过滤器有几个取舍:

  • Xor 过滤器是概率性的,有可能发生误报。
  • Xor 过滤器无法估计部分值的存在。所以在我的用例中,全文搜索将只能搜索完整的单词。

我是如何使用 Rust 构建 Xor 过滤器的?

因为我有 Contentlayer 生成的文章数据,所以我通过在构建 WebAssembly 之前向它们提供数据来构建 xor 过滤器。然后我序列化了异或过滤器并将它们存储在一个文件中。要在 WebAssembly 中使用过滤器,我需要做的就是从存储文件中读取并反序列化过滤器。

过滤器生成流程如下所示:

image

xorf crate 是实现异或过滤器的不错选择,因为它提供了序列化/反序列化以及一些提高内存效率和误报率的功能。它还为我的用例提供了一个非常方便的HashProxy结构来构造带有字符串切片的异或过滤器。用 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) }

如果您对实际实现感兴趣,可以在存储库中阅读更多内容

把它们放在一起

image

在 Next.js 中集成 WebAssembly

这是我在 Next.js 中集成 xor 过滤器生成脚本和 WebAssembly 的方法。

文件结构如下所示:

 my-portfolio ├── next.config.js ├── pages ├── scripts │ └── fulltext-search ├── components │ └── Search.tsx └── wasm └── fulltext-search

为了支持 WebAssembly,我更新了我的 Webpack 配置以将 WebAssembly 模块加载为异步模块。为了使它适用于静态站点生成,我需要一种解决方法来在.next/server目录中生成 WebAssembly 模块,以便在运行next build脚本时静态页面可以成功预渲染。

next.config.js

 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 },

这就是集成的全部内容✨

在 React 组件中使用 WebAssembly

为了从 Rust 代码构建 WebAssembly 模块,我使用wasm-pack

生成的.wasm文件和 JavaScript 的胶水代码位于wasm/fulltext-search/pkg中。我需要做的就是使用next/dynamic动态导入它们。像这样:

组件/Search.tsx

 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

优化 WebAssembly 代码大小

未经任何优化,原始 Wasm 文件大小为114.56KB 。我使用Twiggy找出代码大小。

 Shallow Bytes │ Shallow % │ Item ───────────────┼───────────┼───────────────────── 117314 ┊ 100.00% ┊ Σ [1670 Total Rows]

628KB的原始数据文件相比,它比我预期的要小得多。我很高兴已经将它交付到生产环境中,但我很想知道使用Rust 和 WebAssembly 工作组的优化建议可以减少多少代码大小。

第一个实验是切换 LTO 并尝试不同opt-level 。以下配置产生最小的.wasm代码大小:

货运.toml

 [profile.release] + opt-level = 's' + lto = true
 Shallow Bytes │ Shallow % │ Item ───────────────┼───────────┼───────────────────── 111319 ┊ 100.00% ┊ Σ [1604 Total Rows]

接下来,我用wee_alloc替换了默认分配器。

wasm/全文搜索/src/lib.rs

 + #[global_allocator] + static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
 Shallow Bytes │ Shallow % │ Item ───────────────┼───────────┼───────────────────── 100483 ┊ 100.00% ┊ Σ [1625 Total Rows]

然后我尝试了 Binaryen 中的wasm wasm-opt工具。

 wasm-opt -Oz -o wasm/fulltext-search/pkg/fulltext_search_core_bg.wasm wasm/fulltext-search/pkg/fulltext_search_core_bg.wasm
 Shallow Bytes │ Shallow % │ Item ───────────────┼───────────┼───────────────────── 100390 ┊ 100.00% ┊ Σ [1625 Total Rows]

这比原始代码大小减少了14.4%

最后,我能够在以下位置发布全文搜索引擎:

  • 98.04 KB 原始
  • 45.92 KB 压缩包

还不错😎

它真的很活泼吗?

我用web-sys分析了性能并收集了一些数据:

  • 搜索次数:208

  • 分钟:0.046 毫秒

  • 最大值:0.814 毫秒

  • 平均值:0.0994 毫秒✨

  • 标准差:0.0678

平均而言,执行全文搜索所需的时间不到 0.1 毫秒。

真是太爽了😎

最后的想法

经过一些实验,我能够使用 WebAssembly、Rust 和 xor 过滤器构建一个快速、轻量级的全文搜索。它与 Next.js 和静态站点生成很好地集成。

速度和大小带来了一些权衡,但它们对用户体验没有太大影响。如果您正在寻找更全面的搜索功能,这里有一些很酷的产品可供选择:

SaaS 搜索引擎

静态搜索引擎

基于服务器的搜索引擎

浏览器内搜索引擎

参考


这篇文章也发表在道智的网站上

相關故事

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa