一个使用Rust和WebAssembly的小型静态全文搜索引擎

静态站点生成器非常神奇。它们结合了两个领域的优点：动态内容而不牺牲性能。

然而，有一件事我一直不喜欢，那就是静态网站也不会附带静态搜索引擎。取而代之的是，人们求助于定制的Googlessearch、外部搜索引擎(如Algolia)或基于pureJavaScript的解决方案(如lunr.js或lamticlunr)。

对于大多数网站来说，所有这些都工作得很好，但它从来都不是最终的答案。

我不想再增加对谷歌的依赖；我也不想使用像Algolia这样的独立网络后端，它增加了延迟，而且是专有的。

另一方面，我并不是大量使用JavaScript的网站的狂热粉丝。例如，仅LUNR创建的搜索索引就可能是数兆字节大小，这感觉很奢侈--即使以今天的带宽标准来衡量也是如此。最重要的是，解析JavaScript非常耗时。

我想要一些简单、精简和独立的搜索，可以放在我的其他静态内容旁边。

因此，我完全没有给我的博客添加搜索功能。这是不幸的，因为随着文章数量的增加，找到相关内容变得更加共享和困难。

多年前，也就是2013年，我读到“使用Bloomfilter编写全文搜索引擎”，这让我大吃一惊。

这个想法很简单：让我们通过一个生成器运行所有的文章，这个生成器使用一种叫做✨Bloom filter✨的神奇数据结构来创建精巧的、自包含的搜索索引。

粗略地说，Bloom过滤器是检查元素是否在集合中的一种节省空间的方法。

诀窍在于，它并不存储元素本身；它只是在一定程度上确信它们以前是存储过的。在我们的例子中，它可以以一定的错误率说出一个词在一篇文章中。

下面是原始文章中的Python代码，它为每个帖子生成Bloomfilter(StavrosKorokithakis提供)：

FILTERS={}表示名称，SPLIT_POSTS中的单词。Items()：Filters[名称]=BloomFilter(Capacity=len(字)，Error_Rate=0。1)对于Word中的Word：Filters[名称]。添加(单词)。

由于使用了ERROR_RATE，内存占用非常小，允许的误报数量可以忽略不计。

我立刻知道我想要这样的东西放在我的主页上。我的想法是把Bloom Filters和搜索引擎直接带到浏览器上。我终于可以在不需要后端的情况下进行一次小型的静态搜索了！

我不知道如何捆绑和最小化生成的Bloom过滤器，更不用说在客户机上运行它们了。最初的文章简要地谈到了这一点：

您需要在客户端实现Bloom Filter算法。这可能不会比倒排索引搜索算法长很多，但仍然可能稍微复杂一些。

我对自己的JavaScript技能没有足够的信心来做到这一点。早在2013年，npm只有三岁，webpack刚满一岁，所以我也不知道到哪里去寻找现有的解决方案。

五年后的2018年，网络变成了一个不同的地方。捆绑包无处不在，Node生态系统欣欣向荣。特别值得一提的是，有一件事唤醒了我对这个小小的静态搜索引擎的梦想：网络汇编。

WebAssembly(缩写为Wasm)是一种用于基于ASTACK的虚拟机的二进制指令格式。WASM被设计为编译C/C++/Rust等高级语言的可移植目标，支持客户端和服务器应用程序在Web上的部署。[来源]。

这意味着我可以使用我熟悉的语言来编写客户端代码-RuST！🎉。

我的旅程始于2018年1月的一个原型。它只是Python版本的一个直接移植：

让mut filter=HashMap：：new()；for(name，words)在文章中{let mut filter=BloomFilter：：with_rate(0.1，words.。Len()as u32)；对于单词中的单词{filter.。插入(&；Word)；}筛选器。Insert(名称，筛选器)；}。

虽然我设法为每一篇文章创建了Bloom过滤器，但我仍然不知道应该如何将其打包到Web上……。直到2018年2月wasm-pack出现。

您在此页面顶部看到的搜索框就是结果。它完全运行在Rust上，使用WebAssembly(也称为RAW堆栈)。如果你愿意，现在就试试吧。

首先，我尝试了jedist1的rust-bloom-filter，但是类型没有实现序列化/反序列化，这意味着我不能将生成的Bloom过滤器存储在二进制文件中，也不能从客户端加载它们。

在尝试了其他几个之后，我找到了支持序列化的杜鹃过滤箱。其行为类似于Bloom Filter，但如果您对差异重新感兴趣，您可以查看此摘要。

让mut cf=cuckoofilter：：new()；//将数据添加到过滤器let值：&；str="；hello world；；let Success=cf。add(Value)？；//查找是否在Success=cf之前添加数据。CONTAINS(值)；//SUCCESS==>；true。

让我们在使用布谷鸟过滤器捆绑我博客上10篇文章的过滤器时检查输出大小：

~/C/p/tinysearch❯l存储权限大小用户日期修改名称。rw-r--r--44k Mendler 24 Mar 15：42存储。

44kB听起来不太破旧，但这些只是十篇文章的杜鹃过滤器，序列化为铁锈二进制。最重要的是，我们必须添加搜索功能和助手代码。总体而言，客户端代码使用普通的wasm-pack，大小为216kB。太多。

在我们的初始原型的216kB的第一个令人警醒的结果之后，我们有几个选项来降低二进制大小。

通过在Cargo.toml中设置几个选项，我们可以减少相当多的字节：

"；opt-level='；z'；"；=>；249665字节"；lto=TRUE"；=>；202516字节"；opt-level='；s'；"；=&>；195950字节。

将opt-level设置为s意味着我们用大小来换取速度，但无论如何，我们最初都对最小大小感兴趣。毕竟，较小的下载大小也可以提高性能。

它适用于进行少量初始动态大小分配的代码，然后在没有任何进一步分配的情况下执行繁重的任务。这个场景需要存在一些分配器，但是我们非常乐意用分配性能来换取较小的代码大小。

出于好奇，我尝试将codegen-unit设置为1，这意味着我们只使用单个线程生成代码。令人惊讶的是，这导致了一个稍微小一些的二进制大小。

然后我得到消息说有一个叫做二进制的Wasm优化器。在MacOS上，它可以通过自制软件获得：

然后我删除了web-sys，因为我们不必绑定到DOM：152858字节。

有一个名为twiggy的工具可以分析Wasm二进制文件的代码大小。它输出以下输出：

Item─┼─┼──│-n 20 pkg/tinysearch_bg.wasm浅字节数浅%│搜索。─79256┊44.37%┊Data[0]13886┊7.77%┊"；函数名称"；子节7289 core：：fmt：：float：：float_to_decimal_common_shortest：：hdd201d50dffd0509 core：：fmt：：float：：float_to_decimal_common_exact：：hcb5f56a54ebe7361 4.08%DATA[1]6888┊3.86%┊Search 6080┊3.40%┊Search5972┊3.34%┊Search 5869┊3.29%┊Search。

据我所知，我们的二进制文件中最大的一块被我们文章的原始数据部分占据，接下来，我们获得了函数头和一些浮点到十进制的帮助器函数，这些函数很可能来自反序列化。

最后，我尝试了wasm-snip，它将WebAssembly函数的主体替换为无法访问的主体，但它并没有减少代码大小：

在稍微调整了杜鹃过滤器的参数，并从文章中删除了停用的单词后，我达到了121kB(51kB Gzip)-考虑到网络上的平均图像大小约为900KB，这还不错。最重要的是，只有当用户点击搜索字段时，搜索功能才会加载。

对于搜索UI，我定制了几个来自w3学校的JavaScript和CSS代码，它甚至支持键盘！现在当用户输入搜索查询时，我们会通过每篇文章的布谷鸟过滤器来尝试匹配单词。结果是根据点击数打分的。感谢我亲爱的同事豪尔赫·路易斯·贝当古(Jorge Luis Betancourt)添加了这一部分。

只有完整的单词才会匹配。我很想添加前缀搜索，但当我尝试时，二进制文件变得太大了。

创建Wasm文件的独立二进制文件名为tinysearch，它需要一个指向JSON文件的单一路径作为输入：

这个corpus.json包含您想要索引的文本。格式相当简单：

[{"；Title"；："；第1"；，"；URL"；："；https://example.com/article1"；，"；Body"；："；}，{"；Title"；："；第2"；，"；URL"；："；https://example.com/article2"；，"；Body"；："；这是第2条的正文。"；}]。

您可以使用任何静态站点生成器生成此JSON文件。以下是我对左拉的描述：

{%SET SECTION=GET_SECTION(path="；_index.md"；)%}[{%-用于节中的开机自检。页面-%}{%(如果未发布)。草稿%}{"；标题"；：{{发布。title|striptag|json_encode|safe}}，"；url"；：{{post.。permalink|json_encode|Safe}}，"；正文"；：{{POST.。Content|striptag|json_encode|safe}}{%if not循环。最后%}，{%endif%}{%endif%}{%-endfor-%}]。

这仍然是狂野的西部：不稳定的特征，夜间生锈，纪录片几乎每天都会过时。带上你的思考帽！

从一个好的想法创造一个产品是一项繁重的工作。人们必须注意很多因素：易用性、通用性、可维护性、文档等等。

生锈非常擅长删除死代码，所以你通常不会为你不用的东西付钱。我仍然建议您对添加到Wasm二进制文件的依赖项非常保守，因为它很容易添加您不需要的功能，而这些功能会增加二进制文件的大小。例如，我在测试期间使用了Structopt，并且我有一个main()函数来解析这些命令行参数。这对于wasm来说不是必需的，所以我后来删除了它。

我知道并不是每个人都想写Rust代码。开始使用它很复杂，但最酷的是，你几乎可以用任何其他语言做同样的事情。例如，您可以编写Go代码并将其转换为Wasm，或者您可能更喜欢PHP或Haskell。已经有了对多种语言的支持。

很多人对WebAssembly不屑一顾，认为它只是一种玩具技术。他们离真相不能再远了。在我看来，WebAssembly将彻底改变我们为网络和其他领域构建产品的方式。仅仅两年前还很难的是新手：将任何语言的代码传送到每个浏览器。我对未来感到超级兴奋。

如果您正在为您的公司网站寻找独立的、自托管的搜索索引，请查看Sonic。

因为我们将所有文章的所有搜索索引捆绑到一个静态二进制文件中，所以我只建议将其用于低到中等规模的网站。预计每篇文章大约4kB(非压缩)。

目前的编译时间非常糟糕(在我的机器上重新安装大约1.5分钟后)，主要是因为我们每次重新构建索引时都要从头开始编译铁锈陨石箱。更新：多亏了CephalonRho在公关#13中出色的工作，这个问题现在已经基本解决了。再次感谢！

最后的Wasm代码是激光快速的，因为我们将往返保存到搜索服务器。即时反馈循环感觉更像是过滤列表，而不是搜索文件。

感谢Jorge Luis Betancourt、Mh84和SchalkNeethling对代码的贡献，感谢Esteban Barrios、Simon Brüggen和Luca Pizzamiglio审阅本文的草稿。