# Manticore 中更快的 KNN 索引构建

Manticore 现在可以在保存 chunk、合并 chunk 和重建 KNN 数据时并行构建 KNN 索引。在一台 16 核机器上，为 100 万个向量构建 KNN 索引的时间从 8 分钟降到了 39 秒。

### 先说结论

过去，构建 KNN 索引一直是保存和合并带有向量属性的表时最慢的环节。自 [v27.1.5](/blog/manticore-search-27-1-5/) 版本起，Manticore 可在分块保存、`OPTIMIZE` 合并、自动优化以及 `ALTER TABLE ... REBUILD KNN` 过程中使用多个 CPU 核心来完成这项工作。在一台 16 核 Ryzen 9 5950X 上，为 100 万个 1536 维向量构建 KNN 索引的时间从 8 分钟降到了 39 秒。

## 为什么 HNSW 构建速度很重要

Manticore 使用 HNSW 图来支持对 `float_vector` 属性的 KNN 搜索。可以把 HNSW 图理解为一张地图，它帮助 Manticore 快速找到与查询向量接近的向量。

构建这张地图可能要花很长时间。对于没有 KNN 的表，保存或合并数据主要只是写入普通表数据。对于带 KNN 的表，Manticore 还必须把每个向量插入 HNSW 图，而这部分额外工作可能会主导总耗时。

这在大批量插入之后以及维护期间最明显。新数据会从内存保存到磁盘 chunk。已有 chunk 之后会被 `OPTIMIZE` 或自动优化合并。每个被保存或合并的 chunk 都需要自己的 HNSW 图，所以更快的图构建意味着批量加载后的等待更短、后台优化更快，以及维护操作耗时更少。

[磁盘 chunk](https://manual.manticoresearch.com/Creating_a_table/Local_tables/Plain_and_real-time_table_settings#Important-notes-about-RAM-chunks) 数量对搜索也很重要。Manticore 将 RT 表存储为磁盘 chunk，而每个 chunk 都有自己的 HNSW 图。一次 KNN 查询会搜索每个 chunk 并合并结果，所以 chunk 越少，通常 KNN 查询就越快。最快的布局通常是一个 chunk 配一张图。

[自动优化](https://manual.manticoresearch.com/Server_settings/Searchd#auto_optimize) 默认不会一路合并到只剩一个 chunk。它会在后台合并 chunk，但会在表达到目标 chunk 数时停止。对于普通表，目标值是 `2 * num_logical_cpus`；对于带 KNN 属性的表，这个值更低：`num_physical_cpus / 2`。在一台 32 线程 / 16 核主机上，这意味着 KNN 表是 8 个 chunk，而普通表是 64 个。KNN 的目标值更低，是因为额外的 chunk 对 KNN 搜索延迟的影响更大，但默认值仍然会保留多个图。要让自动优化收敛到单个 chunk，可以在全局、按表或运行时将 [optimize_cutoff](https://manual.manticoresearch.com/Server_settings/Searchd#optimize_cutoff) 设为 `1`，例如 `SET GLOBAL optimize_cutoff = 1`。你也可以手动使用 [OPTIMIZE TABLE ... OPTION cutoff = 1](https://manual.manticoresearch.com/Securing_and_compacting_a_table/Compacting_a_table) 来完成。

## 过去是怎么做的

新插入的文档会先累积在 RAM chunk 中。当这个 RAM chunk 达到 [rt_mem_limit](https://manual.manticoresearch.com/Creating_a_table/Local_tables/Plain_and_real-time_table_settings#rt_mem_limit) 时，默认值是 128MB，Manticore 就会把它保存成一个新的磁盘 chunk。对于带 KNN 属性的表，这次保存还包括根据 RAM chunk 中的向量构建一张新的 HNSW 图。

当磁盘 chunk 合并时，也会发生同样的 HNSW 构建。`OPTIMIZE TABLE` 和自动优化会从现有 chunk 读取有效行，写出一个新的合并 chunk，并为这个合并结果构建一张新的 HNSW 图。`ALTER TABLE ... REBUILD KNN` 以及添加或删除 `float_vector` 列的 ALTER 操作，也都会重建这张图。

在这次改动之前，每次单独的保存、合并或重建中的 HNSW 部分都只使用**一个 worker**：

- 从 RAM 到磁盘的 chunk 保存会逐个遍历 RAM chunk 各 segment 中的所有有效行，并把它们的向量插入同一张 HNSW 图。
- chunk 合并会逐个遍历输入磁盘 chunk 中的所有有效行，并把它们的向量插入新图。
- `ALTER TABLE ... REBUILD KNN` 会用一个 worker 重建每张图。

Manticore 之前在这些操作周围就已经有一些并行能力了。最多可以同时运行 2 个 RAM chunk 保存。优化器也可以同时运行多个 chunk 合并，由 [parallel_chunk_merges](https://manual.manticoresearch.com/Server_settings/Searchd#parallel_chunk_merges) 控制。如果主机有足够的 CPU 核心，默认值是 2。但在每一次单独的保存或合并内部，KNN 图构建仍然是单 worker。对于 KNN 密集型表，这个单 worker 往往决定了整个操作要花多长时间。

## 现在有什么变化

Manticore 现在把一次 KNN 图构建拆给多个 worker。每个 worker 处理一部分行，把对应向量插入同一个目标图，并独立完成。图构建库会协调这些并发插入，确保图保持有效。

具体拆分方式取决于操作：

- 在 RAM 到磁盘的保存过程中，worker 会从共享队列中获取 RAM segment，直到所有 segment 都处理完。
- 在 chunk 合并和 `ALTER TABLE ... REBUILD KNN` 期间，Manticore 会把有效行划分为大小相近的区间，以便均匀分摊工作。

### 单线程改进

这个版本还改进了单 worker 路径。即使将 `knn_parallel_build` 设为 `1`，下面的基准测试在加入并行之前也显示出 10% 的提升。这来自三项改动：

1. **两阶段邻居处理。** 插入向量时，算法会遍历候选邻居并计算距离。新代码把这一步拆成两阶段：第一阶段遍历邻居列表并预取向量数据，第二阶段计算距离。这样 CPU 就有时间在向量真正被使用前把它们装入缓存。
2. **一次处理两个比较。** 一些距离计算现在会把两个候选向量一起处理。这减少了内层循环中的重复工作，而这正是构建时间花费最多的地方。
3. **构建模式下的编译期距离分发。** 构建器现在会在构建开始时一次性选定正确的距离函数，例如内积还是 L2，以及原始 float 向量还是二值量化向量。这样就避免了每次距离调用都进行函数指针查找，并让编译器可以更激进地优化内层循环。

### 默认值和配置

新的 searchd 设置 [knn_parallel_build](https://manual.manticoresearch.com/Server_settings/Searchd#knn_parallel_build) 控制一次 KNN 构建最多可以使用多少个 worker。默认值是 `min(4, threads / 4)`，其中 `threads` 是 Manticore 的 [threads](https://manual.manticoresearch.com/Server_settings/Searchd#threads) 设置，也就是运行查询和后台任务的 worker 池大小，默认等于主机的逻辑 CPU 核心数。

从实际使用来看，这意味着在小型主机上默认只有一个 worker，而在较大的主机上最多默认四个 worker：4 线程主机得到 1 个 worker，8 线程主机得到 2 个，16 线程主机得到 4 个，更高配置也同样上限为 4。默认值偏保守，因为生产机器通常需要同时处理搜索、插入和后台工作。

通常你不需要修改它。当你在一台不承载线上流量的主机上重建或优化一个 KNN 密集型表时，可以考虑把它调高：

```sql
SET GLOBAL knn_parallel_build = 16;
```

如果你需要旧的单 worker 行为，可以把它设为 `1`：

```sql
SET GLOBAL knn_parallel_build = 1;
```

这个值也可以在 searchd 配置中设置，并通过 `SHOW VARIABLES` 查看。

### CPU 使用情况

多个保存和合并可以同时活跃，而每个操作最多可以使用 `knn_parallel_build` 个 worker。这些 worker 使用的是 Manticore 现有的 `threads` 池。它们不会创建无限数量的额外操作系统线程；如果池里的线程都忙着，额外工作会在队列中等待。

这就是默认值会保留余量的原因。在一台 32 线程主机上，默认每次 KNN 构建使用 4 个 worker。如果有两个 chunk 保存重叠，KNN 构建工作最多会占用 8 个 worker，从而为其他工作保留线程池中的其余部分。

## 基准测试

环境：

- AMD Ryzen 9 5950X（16 个物理核心 / 32 个逻辑核心）
- 数据集：[dbpedia-openai-1M](https://storage.googleapis.com/ann-filtered-benchmark/datasets/dbpedia_openai_1M.tgz) - 100 万个向量，1536 维，余弦距离
- 量化：1 位（二值）量化
- 数据先插入 RT 表，然后用 `OPTIMIZE` 合并为单个磁盘 chunk
- 测量项：`ALTER TABLE knn_data REBUILD KNN`，每个配置运行三次，单 chunk 以保证时间稳定
- HNSW 设置：默认值

之所以使用 `ALTER TABLE ... REBUILD KNN`，是因为它走的是和 chunk 保存及 chunk 合并相同的并行构建路径，同时又能提供稳定且容易复现的计时结果。

![ALTER REBUILD KNN wall time vs. knn_parallel_build](./knn-parallel-build/knn_parallel_build_walltime_chart.svg)

结果：

- 使用一个 worker 时，新代码已经比旧代码快 10%：492 秒降到 442 秒。
- 使用 16 个 worker 时，重建时间降到 39 秒，比新的单 worker 结果快了大约 11 倍。
- 从 16 个 worker 增加到 32 个 worker 帮助不大：39 秒变成了 36 秒。在这台机器上，有效上限接近 16 个物理 CPU 核心。
- 默认值是为共享的生产主机设计的。如果是在专用主机上做维护工作，提高 `knn_parallel_build` 可能很值得。

## 迁移

无需任何操作。现有表继续正常工作，而通过并行路径构建的 KNN 图在功能上与旧的单 worker 路径构建的图等价。

有一个细节对严格可复现性可能很重要：并行 worker 可能会以不同顺序插入向量，因此 Manticore 以 `.spknn` 扩展名保存的磁盘 KNN 图文件，不保证与单 worker 构建的文件逐字节完全一致。预计搜索质量和查询速度相同。如果你在意逐字节可复现性，请将 `knn_parallel_build` 设为 `1`。

## 结论

这一改动让维护 KNN 表中最耗时的部分之一快了很多。并行图构建缩短了保存分块、合并分块和重建 KNN 数据的时间，而改进后的单工作线程路径也让更小的系统受益。现有表无需任何修改即可继续使用，而需要更高构建吞吐量的用户，可以在维护工作负载有 CPU 资源可用时提高 `knn_parallel_build`。