美团外卖基于GPU的向量检索系统实践

到家搜索业务有个显著特点——数据量大、过滤比极高。要想在保住高召回率的同时把检索性能再往上推，到家搜索技术团队和基础研发机器学习平台团队一起，基于GPU搞了一套支持向量+标量混合检索的通用系统。结果呢？召回率和检索性能都上了一个大台阶。下面就来聊聊我们在建设这个系统时踩过的坑和解决思路，希望能给同行们一些参考。

• 1 背景
• 2 美团外卖向量索引的发展历程
• 2.1 HNSW（Hierarchical Na vigable Small World）
• 2.2 IVF （Inverted File）
• 2.3 IVF-PQ（Inverted File with Product Quantization）
• 2.4 IVF-PQ+Refine
• 2.5 基于地理位置的向量检索
• 3 目标与挑战
• 3.1 目标
• 3.2 解决方案探索
• 4 GPU向量检索系统
• 4.1 前置过滤实现方案选择
• 4.2 GPU向量检索引擎
• 4.3 向量检索系统工程实现
• 5 收益
• 6 展望

1 背景

大数据和人工智能时代，向量检索的应用场景越来越广。无论是检索系统、推荐系统还是问答系统，都能看到它的身影——通过计算文档和查询向量的相似度，快速找到用户需要的信息。在大语言模型和生成式AI场景里，向量索引作为底层存储，也扮演着关键角色。

如下图所示，向量检索主要分三步：第一步，把文本、图像、语音等原始数据经过特征抽取和模型预估，变成向量集合；第二步，把输入Query也变成同样的向量；第三步，在索引里找出与查询向量最相似的K个结果。最直接的方式是暴力检索——把每个向量都算一遍。但数据量大或维度高的时候，这个做法的耗时和资源消耗都巨大，现实场景根本扛不住。

为了解决这个问题，业界提出了ANN（Approximate Nearest Neighbor，近似最近邻）方案：通过构建有效索引，减少向量计算量，牺牲一点点召回精度来换取更快的检索速度。同时，用GPU的并行计算能力来加速向量相似计算，也是个热门方向。Facebook开源的Faiss库在GPU上实现了多种索引方式，跟CPU版比，速度能快5到10倍。开源的Milvus也基于GPU加速，检索性能提升了10倍以上。

目前，向量检索已经广泛应用于美团外卖的搜推业务。跟其他场景不同，美团外卖有一个很强的LBS（基于位置服务）特点——商家的配送范围决定了用户能点餐的商家列表。以商品向量检索为例，结果集必须经过“可配送商家列表”过滤。此外，不同业务场景还常需要根据商品品类、标签等标量属性做过滤。当前，美团外卖的向量检索基于Elasticsearch+FAISS搭建，支持十亿级别高维向量的标量+向量混合检索。为了在保证高召回率的同时进一步压缩检索时间，我们探索了基于GPU的向量检索，并最终实现了一套通用系统。

2 美团外卖向量索引的发展历程

在建设过程中，我们先后用了HNSW、IVF、IVF-PQ以及IVF-PQ+Refine等算法，基于CPU实现了向量检索能力。过去几年，我们对Elasticsearch做了定制，把相关算法集成进去，在复用Elasticsearch检索能力的同时，支持了标量-向量混合检索。下面简单梳理一下这四种技术的特点和演进路径。

2.1 HNSW（Hierarchical Na vigable Small World）

HNSW是一种专门用于大规模高维数据近似最近邻搜索的算法。它的核心思路是构建一个多层次的图结构，每一层都是一个导航小世界图——任意两点之间的路径都很短，查找非常快。搜索时从高层开始，快速定位到目标的大致位置，然后逐层向下细化，最终在底层找到最近邻。在通用检索场景中，HNSW表现相当亮眼。但问题在于，当过滤比很高时，性能会明显下降。在到家搜推这种强LBS过滤场景下，这个劣势就暴露出来了。业界有不少benchmark可以参考，比如Yahoo的Vespa博客，性能与召回率的趋势大致如下：

2.2 IVF （Inverted File）

IVF基于倒排索引，把高维向量空间分成多个簇（Cluster），每个簇对应一个倒排列表，存储属于该簇的向量索引。这样一来，搜索时只需要比较少量向量，速度就上来了。但缺点也很明显：必须存原始向量，而且要全量加载到内存，占用的空间非常夸张，容易把内存撑爆。

2.3 IVF-PQ（Inverted File with Product Quantization）

当候选集数量巨大时（比如商品向量检索场景），IVF的内存问题就压不住了。于是我们开始尝试IVF-PQ。它在IVF的基础上，用乘积量化（Product Quantization）来压缩向量——把高维向量切成多个子向量，分别做量化，大幅降低了内存消耗。代价是量化过程会引入误差，精度不如IVF，召回率可能达不到线上要求。所以它更适合对召回率要求不高的场景，对精度有要求的场景得另想办法。

2.4 IVF-PQ+Refine

为了弥补IVF-PQ的精度损失，我们进一步推出了IVF-PQ+Refine方案。在IVF-PQ的基础上，用SSD磁盘保存一份未经压缩的原始向量数据。检索时先通过IVF-PQ召回一个大候选集，然后从磁盘取原始向量做精确计算，精度就上来了。这个方法既保留了IVF-PQ的存储优势，解决了内存瓶颈，又保证了召回率，因此在实践中被广泛采用。

2.5 基于地理位置的向量检索

美团外卖跟普通电商有一个明显区别——LBS特征。用户和商家的距离会很大程度上影响最终选择。所以，在向量检索过程中加入地理位置因素，让离用户更近的商品优先被召回，就成了一个很自然的思路。具体做法是把经纬度编码成向量，以加权的方式加到查询和候选向量里。这样在计算相似度时，距离因素就能不同程度地影响结果，让向量索引具备LBS属性。加入地理位置信息后，召回率确实有了明显提升。

除了以上几种，常见的还有Flat（暴力计算），能做到100%召回，但因为计算量大，性能差，一般只在小规模数据上用。

3 目标与挑战

3.1 目标

这几个方案落地后，向量+标量混合检索、前置过滤、海量数据检索这些挑战基本都解决了，但检索性能和召回率离理想状态还有差距。考虑到美团外卖的业务特点，目标方案需要满足以下条件：

• 支持向量+标量混合检索
  ：向量检索基础上，支持复杂的标量过滤条件。

• 高过滤比
  ：标量过滤条件过滤比超过99%，过滤后候选集依然很大（比如外卖商品经过LBS过滤，候选向量仍超百万）。

• 高召回率
  ：召回率需要95%以上。

• 高性能
  ：满足高召回率的同时，检索耗时Tp99控制在20ms以内。

• 数据量
  ：支持上亿级别的候选集规模。

调研业界方案后，我们决定借助GPU的强大算力来突破性能瓶颈。目前大部分基于GPU的向量检索方案（比如Faiss、Raft、Milvus）都追求极致性能，但它们面向的是全库检索，不直接支持向量+标量混合检索，需要在已有基础上做改造。

3.2 解决方案探索

实现向量+标量混合检索，通常有两种方式：前置过滤（pre-filter）和后置过滤（post-filter）。前置过滤是先对标量数据做过滤，得到候选结果集，再在这个集合里做向量检索得到TopK。后置过滤则是先做向量检索，得到TopK*N个结果，然后做标量过滤，得到最终TopK（N是扩召回倍数，用于缓解过滤导致结果不够的情况）。

后置过滤可以尽量复用现有的全库检索框架，开发量小、风险低，所以我们优先考虑它。基于GPU的后置过滤快速实现了一版引擎，验证了召回率和性能。GPU上的成熟算法有Flat、IVFFlat和IVFPQ等，在不扩召回时召回率偏低，所以我们选了较大的扩召回倍数来提升召回率。

测试数据集来自线上真实的商品数据。统计显示，符合标量过滤条件的候选向量平均约250万。在单GPU上验证后置过滤的性能和召回率如下：

结果很清楚：这三种算法都没法同时满足我们对性能和召回率的要求。IVF和IVFPQ召回率偏低，Flat虽然召回率高，但需要和全部候选集算相似度，性能太差。

举个例子：假设候选向量1000万，维度D。Flat就是纯暴力计算，单条查询要做1000万*D次浮点运算，精度最高但慢。IVF通过倒排把候选集分成多个簇，只算部分簇。比如分成1024个簇，每次只查64个，计算量缩到Flat的1/16，也就是62.5万*D次。IVFPQ在IVF基础上用乘积量化，把D维向量切成M组（比如M=8），每组训练出256个聚类中心，计算量变成8*256*D次浮点计算 + 1000万*8次查表 + 1000万*8次加法。

在Flat基础上，我们考虑通过向量子空间划分来减少计算量。外卖搜索有强LBS属性，可以用GeoHash来做划分。构建索引时按商家经纬度算GeoHash，把全量数据分成多个子空间。检索时根据用户位置算GeoHash，扩展到附近9个或25个GeoHash块，用Flat在里面算。这样计算量少了，但有些距离稍远的商家可能被漏掉，最终召回率只有80%左右，不达标。

综上所述，后置过滤方案无法同时满足性能和召回率，而GPU版的Faiss又不支持前置过滤。考虑到业务对向量+标量混合检索的刚需，我们决定自研GPU向量检索引擎。

4 GPU向量检索系统

4.1 前置过滤实现方案选择

要在GPU上做前置过滤，通常有三种方案：

1. 所有原始数据都放在GPU显存，由GPU完成过滤和向量计算。
2. 原始数据放在CPU内存，CPU完成过滤后把过滤后的向量传给GPU做计算。
3. 向量数据放GPU显存，标量数据放CPU内存，CPU过滤后把结果的下标传给GPU，GPU根据下标从显存取向量计算。

方案1的显存占有大，过滤性能差，还发挥不了高过滤比的优势，直接排除。方案2和3的对比如下：

实验显示，方案2的数据拷贝阶段耗时严重，无法满足时延要求。因为美团外卖场景里过滤后的数据集仍然很大，CPU到GPU的传输带宽（A30显卡PCIe Gen4是64GB/s）成了瓶颈。最终我们选了方案3。

4.2 GPU向量检索引擎

4.2.1 数据结构

显存比内存贵得多，所以设计时尽可能把数据放在内存，只有需要GPU算的向量才放显存。内存中存所有标量数据，按列存储，通过位置索引可以快速定位到某条数据的各个字段。按列存储灵活性高、可扩展性好，也利于压缩和加速。对于需要过滤的标量字段，我们又在内存里建了倒排索引，倒排链存的是原始数据的位置索引。内存数据结构如下：

显存存所有向量数据，位置索引跟内存一一对应，可以快速通过位置索引取到向量：

4.2.2 检索流程

初始化时，在内存中构建标量过滤用的倒排索引，同时把向量数据从CPU内存拷贝到GPU显存，通过位置索引关联。

标量过滤在CPU内存进行。通过倒排索引，快速得到符合某个标量条件的原始数据位置索引列表。利用倒排索引的求交、求并等操作，可以支持多个条件的与/或组合，最终得到所有符合条件的位置索引列表。

相似度计算在GPU中完成。根据上一步的位置索引列表，从GPU显存读取候选向量，然后用常见的距离算法算出最相似的TopK个向量，把结果下标回传给CPU。

根据上一步的结果下标，在CPU内存中获取对应记录返回。

整体流程如下：

有些场景对性能要求更高，对召回率可以适当放宽，所以我们在GPU引擎上又支持了IVF近似检索。初始化时用向量数据训练出P个聚类中心，每个中心建一个局部倒排索引。索引结构跟Flat类似，区别是位置索引只存到最近的聚类中心下。

在CPU内存进行。先找到与query最近的N个聚类中心，再在这些中心下做标量过滤，得到N个候选位置索引列表，然后merge成最终列表。相比Flat，IVF减少了计算量，性能更好。

同Flat。

同Flat。

整体流程：

在单GPU上验证结果如下（数据集和后置过滤那轮一致）：

可以看到，无论是Flat还是IVF，在同一召回率下，前置过滤的性能都明显优于后置过滤。

4.2.3 性能优化

完成前置过滤功能后，我们又做了一系列优化。

• 高并发支持
  ：通过Cuda Stream让GPU并行处理多个查询，高并发压测下GPU利用率可达100%。

• GPU承担部分标量过滤
  ：在GPU上实现部分标量过滤，放到同一个Kernel里计算，充分利用GPU的并行能力（标量过滤本身是无状态操作，CPU受限于核数，但GPU可以支持上千线程并发，优势明显）。

• 资源管理优化
  ：采用句柄机制，资源预先分配，重复利用。每个句柄持有私有资源（可读写内存、显存、Cuda Stream），共享一份全局只读公有资源。初始化时创建句柄对象池，控制句柄数来调整服务端并发能力，避免被打爆。检索时从池里申请空闲句柄，用完后释放，实现回收复用。

优化后的单GPU性能与召回率如下（测试数据集同上）：

还可以把数据分片，用多GPU并行检索，减少单卡计算量来提升性能，同时也能支撑更大规模的向量数据。相比多机多卡的分shard架构，单机多卡能减少网络传输开销，索引加载也更简单，所以我们选了单机多卡方案——一台服务器部署多张GPU，检索时并行从本地多张GPU取数据，在CPU内存中合并。

为了支持更大规模数据检索，引擎还支持了半精度计算（FP16代替FP32），可以节省一半显存。经测试，Flat召回率从100%降到99.4%，依然满足需求。用半精度后，单机能加载近10亿数据，足够支撑一段时间的增长。

4.3 向量检索系统工程实现

工程化实现包括在线服务和离线数据流两部分，总体架构如下：

上线后实际性能数据（数据量1亿+）：

5 收益

到家搜索团队面向在线服务场景实现的GPU向量检索系统，目前已应用于外卖商品向量检索。向量召回链路的检索性能和召回率都有显著提升，满足了策略对召回扩量和迭代的需求。具体提升：

1. 向量索引召回率从85%提升到99.4%。
2. 向量索引检索时延TP99降低了89%，TP999降低了88%。

6 展望

• 目前GPU向量检索系统只支持T+1全量构建索引，后续计划支持实时索引。
• 目前支持FLAT和IVF检索算法，后续计划支持HNSW，在过滤比低的场景下提供更高的检索性能。
• 除了GPU，后续还计划在NPU等新硬件上做更多尝试。