从零构建现代搜索引擎（19）：用 HNSW 加速近邻搜索

上一篇用精确扫描完成了向量检索的基线。精确扫描遍历所有向量计算点积，结果是精确的，但复杂度 O(N×D) 不可扩展。1 万个 chunk 只需 5 毫秒，10 万就要 50 毫秒，100 万要半秒——远超搜索服务的延迟预算。

本篇引入 HNSW（Hierarchical Navigable Small World），一种基于图的近似最近邻算法。Lucene 10.x 内置 HNSW 实现，可以直接通过 KnnFloatVectorField 使用。

为什么需要近似搜索

精确最近邻搜索保证找到真正最近的 K 个向量，但时间复杂度是线性的。搜索服务的延迟预算通常在 50 毫秒以内（整个搜索流程，不只是向量检索），线性扫描在大规模数据上无法满足。

近似最近邻（ANN）牺牲少量精度换取数量级的速度提升。具体来说：精确 Top-10 中的某些结果可能在 ANN 的 Top-10 中排到了第 11 或第 12——被遗漏了。但 ANN 返回的 Top-10 中 95% 以上是正确的，搜索质量几乎无损。

HNSW 的分层图结构

灵感来源：跳表

回忆第 11 篇的跳表：底层是完整链表，上层是稀疏索引。搜索时从最高层开始，快速跳到目标附近，再逐层下降精确定位。

HNSW 把同样的思想搬到向量空间：

• 底层（第 0 层）：包含所有向量节点，每个节点与附近的 M 个邻居相连
• 上层：只包含部分节点（随机采样），每个节点与更远的邻居相连
• 搜索从最高层开始，在稀疏图上快速定位到目标区域，再逐层下降到稠密图精确搜索

图的构建

每个新向量插入 HNSW 时：

1. 随机生成层级 l = floor(-ln(random()) × mL)
   // mL = 1/ln(M)，大部分节点 l=0，少数在高层
2. 从最高层的入口点开始，贪心搜索找到每层的最近节点
3. 在第 l 层及以下的每层：
   a. 搜索 efConstruction 个最近候选
   b. 从候选中选择 M 个建立双向边
   c. 如果某个节点的边数超过 M，裁剪最远的边

void insert(float[] vector, int nodeId) {
    int level = randomLevel();
    int entryPoint = this.entryPoint;

    // 从最高层贪心下降到 level+1
    for (int l = maxLevel; l > level; l--) {
        entryPoint = greedySearch(vector, entryPoint, l, 1).get(0);
    }

    // 在 level 到 0 的每层建边
    for (int l = Math.min(level, maxLevel); l >= 0; l--) {
        List<Integer> neighbors = searchLayer(vector, entryPoint, l, efConstruction);
        List<Integer> selected = selectNeighbors(vector, neighbors, M);
        for (int neighbor : selected) {
            addEdge(nodeId, neighbor, l);
            addEdge(neighbor, nodeId, l);
            pruneIfNeeded(neighbor, l, M);
        }
        entryPoint = neighbors.get(0);
    }

    if (level > maxLevel) {
        this.entryPoint = nodeId;
        this.maxLevel = level;
    }
}

搜索过程

List<Integer> search(float[] query, int topK, int efSearch) {
    int entryPoint = this.entryPoint;

    // 从最高层贪心下降到第 1 层
    for (int l = maxLevel; l > 0; l--) {
        entryPoint = greedySearch(query, entryPoint, l, 1).get(0);
    }

    // 在第 0 层搜索 efSearch 个候选
    List<Integer> candidates = searchLayer(query, entryPoint, 0, efSearch);

    // 取 Top-K
    return candidates.subList(0, Math.min(topK, candidates.size()));
}

searchLayer 是一个贪心的 beam search：维护一个大小为 ef 的候选集，不断从候选集中取最近的节点，检查它的所有邻居，将更近的邻居加入候选集，直到没有更近的邻居为止。

List<Integer> searchLayer(float[] query, int entryPoint, int layer, int ef) {
    Set<Integer> visited = new HashSet<>();
    // candidates: 按距离升序（最近的优先出队）
    PriorityQueue<NodeDist> candidates = new PriorityQueue<>(
        Comparator.comparingDouble(NodeDist::dist));
    // results: 按距离降序（最远的优先出队，用于维护大小）
    PriorityQueue<NodeDist> results = new PriorityQueue<>(
        Comparator.comparingDouble(NodeDist::dist).reversed());

    float dist = distance(query, getVector(entryPoint));
    candidates.offer(new NodeDist(entryPoint, dist));
    results.offer(new NodeDist(entryPoint, dist));
    visited.add(entryPoint);

    while (!candidates.isEmpty()) {
        NodeDist nearest = candidates.poll();
        NodeDist farthestResult = results.peek();

        if (nearest.dist() > farthestResult.dist()) break;

        for (int neighbor : getNeighbors(nearest.id(), layer)) {
            if (visited.add(neighbor)) {
                float d = distance(query, getVector(neighbor));
                if (results.size() < ef || d < farthestResult.dist()) {
                    candidates.offer(new NodeDist(neighbor, d));
                    results.offer(new NodeDist(neighbor, d));
                    if (results.size() > ef) results.poll();
                }
            }
        }
    }

    return results.stream()
        .sorted(Comparator.comparingDouble(NodeDist::dist))
        .map(NodeDist::id)
        .toList();
}

关键参数

参数	含义	默认值	影响
M	每层每个节点的最大边数	16	越大 → recall 越高，内存越多，构建越慢
efConstruction	构建时的候选集大小	200	越大 → 图质量越高，构建越慢
efSearch	搜索时的候选集大小	可调	越大 → recall 越高，搜索越慢

M 和 efConstruction 在索引构建时固定，不能搜索时修改。efSearch 是查询时参数，可以动态调整。

Lucene 的 HNSW 集成

索引时

IndexWriterConfig config = new IndexWriterConfig(analyzer);
config.setSimilarity(new BM25Similarity(1.2f, 0.75f));
IndexWriter writer = new IndexWriter(directory, config);

Document doc = new Document();
doc.add(new TextField("body", chunkText, Field.Store.YES));
doc.add(new StringField("docId", docId, Field.Store.YES));
doc.add(new IntField("chunkIndex", chunkIdx, Field.Store.YES));

float[] normalizedVec = normalize(embedding);
doc.add(new KnnFloatVectorField("embedding", normalizedVec,
    VectorSimilarityFunction.DOT_PRODUCT));

writer.addDocument(doc);

KnnFloatVectorField 在 segment flush 时自动构建 HNSW 图。段合并时，两个 HNSW 图也会被合并。

搜索时

DirectoryReader reader = DirectoryReader.open(directory);
IndexSearcher searcher = new IndexSearcher(reader);

float[] queryVec = normalize(embeddingClient.embed(
    List.of(queryText), "query")[0]);

int k = 10;
Query knnQuery = new KnnFloatVectorQuery("embedding", queryVec, k);
TopDocs topDocs = searcher.search(knnQuery, k);

StoredFields storedFields = searcher.storedFields();
for (ScoreDoc sd : topDocs.scoreDocs) {
    Document doc = storedFields.document(sd.doc);
    System.out.printf("docId=%s chunk=%s score=%.4f\n",
        doc.get("docId"), doc.get("chunkIndex"), sd.score);
}

带过滤的向量搜索

Query langFilter = new TermQuery(new Term("lang", "zh"));
Query knnQuery = new KnnFloatVectorQuery("embedding", queryVec, k, langFilter);
TopDocs topDocs = searcher.search(knnQuery, k);

Lucene 在内部处理过滤：如果过滤后的文档集足够大，在过滤子集上运行 HNSW 搜索；如果过滤后文档太少，可能退化为精确扫描。

ANN Recall 的度量

定义

ANN Recall@K = Top-K 近似结果中有多少是真正的精确 Top-K：

double annRecall(List<Integer> annTopK, List<Integer> exactTopK) {
    Set<Integer> exactSet = new HashSet<>(exactTopK);
    long hits = annTopK.stream().filter(exactSet::contains).count();
    return (double) hits / exactTopK.size();
}

与搜索 Recall 的区别

ANN Recall 的对照基准是同一向量空间中的精确近邻，不是人工标注的相关性。

指标	对照基准	含义
ANN Recall@10	精确 Top-10 向量	近似搜索找回了多少精确最近邻
搜索 Recall@100	人工标注的相关文档	检索系统在 Top-100 中覆盖了多少相关文档

ANN Recall = 0.95 表示 10 个精确最近邻中有 9.5 个被找到了。它衡量的是近似算法的精度损失，不是搜索质量。搜索质量还要看向量本身的语义表示能力。

度量方法

对开发集中的每个查询，分别用精确扫描和 HNSW 搜索，比较 Top-K 的重叠：

void measureAnnRecall(IndexSearcher searcher, float[][] queryVecs,
                       float[][] allVecs, List<Chunk> allChunks, int k) {
    double totalRecall = 0;
    for (int q = 0; q < queryVecs.length; q++) {
        List<Integer> exact = exactTopK(queryVecs[q], allVecs, k);
        List<Integer> ann = luceneKnnTopK(searcher, queryVecs[q], k);
        totalRecall += annRecall(ann, exact);
    }
    System.out.printf("平均 ANN Recall@%d = %.4f\n", k, totalRecall / queryVecs.length);
}

efSearch 调优

efSearch 控制搜索时的候选集大小。越大，检查的节点越多，recall 越高，但延迟也越高。

实验

对同一组查询，用不同 efSearch 值测量 recall 和延迟：

void tuneEfSearch(IndexSearcher searcher, float[][] queryVecs,
                   float[][] allVecs, int k) {
    int[] efValues = {10, 20, 50, 100, 200, 500};
    for (int ef : efValues) {
        double recall = measureRecall(searcher, queryVecs, allVecs, k, ef);
        double avgLatency = measureLatency(searcher, queryVecs, k, ef);
        System.out.printf("efSearch=%3d → Recall@%d=%.4f  latency=%.1fms\n",
            ef, k, recall, avgLatency);
    }
}

预期趋势：

efSearch	Recall@10	延迟
10	~0.85	~1 ms
50	~0.95	~3 ms
100	~0.98	~5 ms
200	~0.99	~10 ms

选择 efSearch 的原则：Recall@10 > 0.95 且延迟 < 10ms。具体值取决于数据规模和分布。

过滤条件对 ANN 的影响

问题

加入过滤条件（如 lang=zh）后，HNSW 图中部分节点被排除。搜索路径上的邻居可能大部分被过滤掉，导致：

1. 实际搜索的有效邻居减少
2. 可能无法找到足够的 K 个候选
3. Recall 下降

度量

void measureFilterImpact(IndexSearcher searcher, float[][] queryVecs,
                          float[][] allVecs) {
    double recallNoFilter = measureRecall(searcher, queryVecs, allVecs, 10, null);
    double recallWithFilter = measureRecall(searcher, queryVecs, allVecs, 10,
        new TermQuery(new Term("lang", "zh")));
    System.out.printf("无过滤 Recall@10 = %.4f\n", recallNoFilter);
    System.out.printf("有过滤 Recall@10 = %.4f\n", recallWithFilter);
}

过滤越严格（通过率越低），recall 下降越明显。如果过滤后只剩 1% 的文档，HNSW 搜索可能退化为接近精确扫描的开销。

构建参数对索引的影响

M 的影响

M	图大小	构建时间	Recall@10
8	较小	快	~0.92
16	中等	中等	~0.96
32	较大	慢	~0.98
64	很大	很慢	~0.99

M 越大，每个节点的邻居越多，搜索路径的选择越丰富，recall 越高。但内存开销和构建时间也线性增长。M=16 是多数场景的默认值。

efConstruction 的影响

efConstruction 决定构建时每次插入搜索多少个候选。它影响图的质量（边的选择是否最优），但不影响搜索时的参数。

efConstruction	构建时间	图质量
100	快	一般
200	中等	好
400	慢	更好

构建只做一次（或每次段合并时重做），所以 efConstruction 可以设得比较高。

验证

场景	操作	预期
基本搜索	HNSW Top-10	返回 10 个结果，分数降序
ANN Recall	对比精确扫描	Recall@10 > 0.95
过滤搜索	加 lang=zh	所有结果的 lang 字段 = zh
过滤 recall	对比无过滤	记录 recall 下降幅度
延迟	1 万向量	< 10 ms
构建时间	1 万向量	< 30 s

当前局限

• 向量全部在内存中——Lucene 会 mmap 索引文件，但热数据仍需内存
• 没有量化——512 维 float32 占 2KB/向量，量化可以减到 512 字节（int8）或 64 字节（binary）
• 还没有与 BM25 融合——向量搜索和词汇搜索是独立运行的
• efSearch 的调优需要精确扫描基线——大规模数据上精确扫描本身很慢
• 段合并时 HNSW 图重建开销大——大段合并可能导致写入停顿

练习

1. 用 Lucene KnnFloatVectorField 索引所有 chunk 向量，确认段文件中包含向量数据
2. 对 10 个查询，分别用精确扫描和 Lucene HNSW 搜索，计算 ANN Recall@10
3. 将 lang=zh 作为过滤条件，比较有无过滤的 Recall@10 差异
4. 记录不同 efSearch 值下的 Recall 和延迟，画出 Recall-Latency 曲线
5. 测量 1 万个 chunk 的索引构建时间和最终索引文件大小

延伸阅读

• Malkov & Yashunin, “Efficient and Robust Approximate Nearest Neighbor using Hierarchical Navigable Small World Graphs”, 2018
• Apache Lucene: KnnFloatVectorQuery Javadoc
• Apache Lucene: Lucene100HnswVectorsFormat 源码
• ann-benchmarks.com — ANN 算法性能基准