【Zig 日报】Vind: A tiny embeddable full-text search engine

[jiacai2050]

Vind 是一个用 Zig 编写的极其轻量且可嵌入的全文搜索引擎，无需安装任何依赖。

为什么选择 Vind

Vind 真的非常小巧且速度极快。它相当灵活，支持多种使用场景：

• 命令行工具
• C 语言库
• 适用于任何带有 FFI 的语言的高级绑定（Python、Ruby、Perl、Raku、Javascript、PHP 等）
• WASM 模块（可在浏览器中原生运行！）
• HTTP 服务

它零依赖、内存高效且性能极高。

---

Vind 如何工作

作为服务

构建索引，然后通过 HTTP 提供服务：

vind build index.idx --from manifest.jsonl
vind serve index.idx --port 8181

使用 GET 请求进行搜索：

curl "http://localhost:8181/search?q=invoice&tags=finance&limit=10"

响应包含耗时、匹配数量和命中结果：

{"search_time_ms":0.12,"found":1,"hits":[{"id":1001,"score":7,"filename":"invoice.pdf","description":"April invoice","date":"2024-04-15","tags":["finance"]}]}

• 服务器在与索引相同的内存中运行查询，因此没有进程间通信 (IPC)。
• 工作线程读取只读索引，因此请求可以跨多核扩展而无需加锁。

作为库

Vind 暴露了 C ABI，因此任何带有 FFI 的语言都可以驱动它。其生命周期为：构建、完成、查询，然后序列化：

vind_index_t *idx = vind_index_create();

// 标签和内容词元 (tokens) 会被驻留 (interned) 为 id，然后作为数组传递。
uint32_t finance = vind_intern(idx, "finance");
uint32_t tags[] = { finance };

// date 是自 Unix 纪元以来的天数。19828 对应 2024-04-15。
vind_index_add(idx, 1001, "invoice.pdf", "April invoice", 19828,
               tags, 1, NULL, 0);
vind_index_finalize(idx);

// vind_query 将 JSON 数组写入缓冲区并返回字节数。
// 如果缓冲区太小，它什么也不写并返回所需的尺寸大小。
char out[4096];
size_t n = vind_query(idx, "{\"text\":\"invoice\",\"tags\":[\"finance\"]}",
                      (uint8_t *)out, sizeof out);
fwrite(out, 1, n, stdout);

// 序列化为 blob，释放，稍后重新加载。
size_t size = vind_serialize_size(idx);
uint8_t *blob = malloc(size);
vind_serialize(idx, blob, size);
vind_index_free(idx);

vind_index_t *loaded = vind_deserialize(blob, size);
vind_index_free(loaded);
free(blob);

相同的 ABI 可以通过 zig build wasm 编译为 WASM。在浏览器中，vind_alloc 和 vind_dealloc 在模块的线性内存中分发缓冲区，用于进出的 JSON，js/wrapper.js 展示了这种模式。匹配是按字节进行的，因此在字符串进入之前将其规范化为 NFC，否则文本将无法自身匹配。

从命令行

CLI 包装了该库，用于离线索引和脚本编写。build 读取 JSONL 并写入 blob。query 对 blob 运行单个 JSON 查询并打印 JSON。stats 和 dump 用于检查索引。

vind build index.idx --from manifest.jsonl
vind query index.idx '{"text":"invoice","tags":["finance"],"limit":10}'

---

清单（Manifest）

每行一个 JSON 对象：

cat > manifest.jsonl <<'EOF'
{"id":1001,"filename":"invoice.pdf","description":"April invoice","date":"2024-04-15","tags":["finance","client"],"content_tokens":["invoice","april","acme"]}
{"id":1002,"filename":"notes.txt","description":"Kickoff notes","date":"2024-05-02","tags":["work"],"content_tokens":["kickoff","planning"]}
EOF

id 是调用者拥有的稳定无符号标识符。date 是 ISO YYYY-MM-DD 字符串或自纪元以来的天数整数。content_tokens 包含预先分词的文本（通常来自 OCR），这些文本无需出现在文件名或描述中即可被搜索。除 id 外，其余所有字段都是可选的，缺失的日期默认为 0。

---

查询

查询是一个 JSON 对象，所有字段均可选：

{"text":"invoice","tags":["finance"],"date_from":"2024-01-01","date_to":"2024-12-31","limit":20}

• text 会被匹配并评分。
• tags 进行 AND（与）过滤。
• 日期范围是包含边界的（inclusive），接受 ISO 字符串或整数天数。
• limit 默认为 20。

通过 HTTP，对应的查询参数为 q、tags（逗号分隔）、date_from、date_to 和 limit。结果包含 id、score、filename、description、date 和 tags。

---

工作原理

搜索作为一个流水线（pipeline）运行。

• 索引将文本转换为三元组（trigrams）。Vind 将字节折叠为小写 ASCII，在它们上面滑动一个三字节的窗口，并使用 FNV-1a 将每个窗口哈希为一个数字。每个三元组拥有一个 CRoaring 位图（bitmap），列出了包含它的文档。标签的工作方式相同，每个标签一个位图。
• 文本查询也变成三元组。Vind 查找每个查询三元组的位图，将它们 OR（或）在一起形成一组候选文档，然后根据每个候选文档包含多少个查询三元组来对其进行评分。求并集（Union）是有意为之的。要求每个三元组都匹配（AND）会在单个拼写错误时失效，而 OR 加上计算重叠度的分数可以保留微小的失误并首先对最接近的匹配项进行排序。分数就是重叠计数，没有别的。这里没有 BM25 或 TF-IDF，因为位图不记录三元组出现的频率，并且在这个规模下，计数已经足够好地进行排名了。
• 过滤器修剪候选集。每个标签与它的位图求交集，未知的标签会提前结束查询且不返回结果。日期存储在按日期排序的单独列表中，因此范围查询变成对边界的二分查找以及与候选集的交集。
• 没有文本的查询会完全跳过评分。Vind 直接从标签位图、日期范围或完整集合中读取文档 id，并在达到限制时停止。这就是为什么标签或浏览查询能在微秒级返回的原因。代价是这些结果按插入顺序返回而不是按评分排序，因为没有文本分数可供排序。
• 排名在扫描时维护一个最佳匹配的有界堆（bounded heap），因此查询前二十个结果时，永远不会做超过需要的排序。
• 持久化仅存储文档和驻留字符串。三元组位图、标签位图和日期列表是通过在加载时重新读取文档来重建的。blob 保持很小，存储的数据永远不会与从它构建的索引发生冲突。重建一百万个文档大约需要三秒钟。

---

性能

在笔记本电脑上的合成语料库，单线程：

• build：约 310k 文档/秒
• load：约 315k 文档/秒
• blob：约 143 字节/文档（100 万文档占 143 MB）

请记住：匹配的文档越多，查询越慢。
因此，值得一提的是与大小无关的性能指标：

• 评分文本：约 740M 倒排记录/秒（一个 posting 指的是一个词条列表中的一个文档）
• 日期过滤：约 35M 文档/秒
• 标签，全匹配：$O(\limit)$，在任何语料库规模下都是几十纳秒

每个查询的成本（显示两种语料库规模以展示扩展性）：

操作	50k 文档	1M 文档
全匹配 (match all)	0.00003 毫秒	0.00002 毫秒
仅标签 (tag only)	0.00008 毫秒	0.0001 毫秒
罕见文本 (rare text)	0.003 毫秒	0.04 毫秒
常见文本 (common text)	0.22 毫秒	4.5 毫秒
日期范围 (date range)	0.21 毫秒	4.9 毫秒
文本 + 标签 + 日期	0.18 毫秒	5.6 毫秒

理解这些指标：
快速形态保持平坦，因为它们直接从位图读取 id 并在限制处停止。其余部分随着语料库的增长而增长，因为它们扫描语料库的一个切片。它们在这里看起来很慢，主要是因为这个合成语料库很密集：整个集合中大约有 1500 个不同的三元组和 8 个标签，因此一个常见的词条会匹配每个文档很大一部分。真实的文本有更多不同的词条，因此常见的查询更具选择性，并且更接近罕见文本行。这也是单线程数字。HTTP 服务器同时跨核心运行查询，因此它提供的吞吐量高于上述延迟倒数。

---

对比 Typesense

看起来 Typesense 是这个市场的主要玩家，所以我利用 Typesense 的基准测试设置进行了对比，为每个引擎创建一个容器，限制在相同的 CPU 预算下，使用 k6 进行测试。

测试了以下场景：全文、全匹配、单个标签过滤、带过滤器的文本以及日期范围过滤。
Typesense 做了一些 Vind 没有做的事情：排序、分面（faceting）、分组（grouping）。这些都被排除了（Typesense 的日期部分执行了排序而 Vind 没有，我将来会更准确地执行此测试）。

来自 k6 的原始统计数据：

Vind（4 核）：

• 检查通过率：100.00% ✓ 1,868,506 ✗ 0
• 吞吐量：5,412.34 请求/秒
• 延迟：平均 11.51ms，中位数 5.11ms，p95 35.87ms，最差 1.78s
• 搜索处理时间：平均 1.46ms，p95 5.15ms
• 错误率：0.00%（0 个失败）

Typesense（4 核）：

• 检查通过率：52.79% ✓ 1,128,947 ✗ 1,009,398
• 吞吐量：3,421.31 请求/秒（但只有约 53% 成功，即约 1,800 个有效响应/秒）
• 延迟：平均 16.97ms，中位数 5.34ms，p95 24.94ms，最差 4.69s
• 搜索处理时间：平均 12.63ms，p95 40ms
• 错误率：47.20%（1,009,398 个请求报错）

核心结论：

1. Vind 更可靠、更有韧性：
   • Vind：0.00% 的请求失败。所有 1,868,506 个请求都得到了真实的答案。
   • Typesense：47.20% 的请求失败。在 2,138,345 个请求中，有 1,009,398 个报错。Typesense 丢弃了近一半的流量，而 Vind 没有丢弃任何请求。
2. Vind 具有更高的吞吐量且不丢包：
   • Vind：5,412/秒，全部成功。
   • Typesense：3,421/秒，但只有约 53% 成功（约 1,800 个有效响应/秒）。换句话说，Vind 做了大约 3 倍的有效工作。
3. Vind 快 8 倍到 13 倍：
   • 平均搜索耗时：Vind 为 1.46ms，而 Typesense 为 12.63ms。Vind 平均快约 8 倍，最差情况（165ms 对 2,163ms）好约 13 倍。
4. 关于 Typesense 稍微好看一点的 p95 延迟：那只是因为它丢弃了一半的请求。当流量失败且通常瞬间失败（连接拒绝或重置）时，存活下来的请求看起来人为地变快了，而被丢弃的慢请求从未被计入。Vind 的 p95 是在干净的 100% 成功率下测得的，没有任何隐藏。

**简而言之：**在相同硬件和相同负载下，Vind 回应了每一个请求，搜索速度快了约 8 倍，而 Typesense 则崩溃并失败了一半的流量。

---

构建

zig build            # CLI 和共享库
zig build wasm       # WASM 模块
zig build test       # 测试
zig build bench -Dbench-docs=100000

需要 Zig 0.16.0 或更高版本，无需其他。

---

它不支持什么

没有 BM25 或 TF-IDF。没有增量更新，只有完全重建。没有排序、分面或分组。没有词干提取（stemming）或停用词。大小写折叠仅支持 ASCII，因此非 ASCII 字母仅在其被索引的大小写形式下才能匹配。查询格式就是上面的 JSON，没有别的。存储、加密和压缩由调用者处理，在浏览器中这通常意味着使用 Web Crypto 和 CompressionStream 包装 blob。

加入我们

Zig 中文社区是一个开放的组织，我们致力于推广 Zig 在中文群体中的使用，有多种方式可以参与进来：

1. 供稿，分享自己使用 Zig 的心得
2. 改进 ZigCC 组织下的开源项目
3. 加入微信群、QQ 群、QQ 频道、Telegram 群组、Google Groups 与更多 Zig 爱好者交流