走进 OceanBase 向量背后的算法库 —— VSAG
本文整理自《深入解读 VSAG——OceanBase 自研开源向量索引库》系列文章 摘要： 向量搜索技术，被认为是海量非结构化数据检索的关键技术之一，这会涉及到高维空间的搜索问题，通常会通过近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）的方式来在高维空间中进行检索，以此来找到满足要求的数据。 随着 AI 应用场景的发展，半结构与非结构化数据的涌现，向量数据库成为 AI 时代重要的数据基座。在 VectorDBBench 基准测试中，OceanBase 在同等环境下向量性能已达到业界主流开源向量数据库的最优水平。这一出色表现很大程度上得益于 OceanBase 向量背后的向量索引库 —— VSAG。 向量索引，作为影响向量检索准确率、查询性能的重要因素，是决定向量数据库性能的关键基础。当前，开源社区已经涌现许多算法库，每个算法库有不同的特点，适用于不同的向量检索场景，包括在相似性搜索领域最有名、维护时间最长的 FAISS 算法库 （facebookresearch/faiss）；由于高效、易于集成、单线程读写等特性广泛应用于搜索推荐系统的 hnswlib 算法库（nmslib/hnswlib）；以及本文将深入介绍的 OceanBase 开源向量索引库 VSAG。 VSAG 库通过引入了许多 SIMD、内存分配和布局、量化等方法，获得了卓越的近似 K 近邻图的搜索性能表现。受益于其资源管理模块，在系统中能够提供租户级细粒度的计算和存储资源管理，提供了超大规模下混合内存与磁盘的快速检索方案。VSAG 在 960 维的 GIST 数据集上表现出色，在 ANN-Benchmarks 测试中远超其他算法。 今天，让我们从最基础的概念讲起，一起走进 OceanBase 向量背后的向量索引库 VSAG，并揭秘其中各项硬核算法。 向量（Vector / Embedding）是一个数据结构，其中包含一个浮点数的数组。这是一个向量的示例： 向量在检索相似的图片、音频和文本等方面发挥着关键作用，这源于其数据属性和特征表示能力。在机器学习和数据科学领域，向量被广泛用于描述数据特征。以图片数据为例，我们可以将其表示为向量。在计算机中，图片本质上是由像素构成的二维矩阵。每个像素的亮度值可视为图片的一个特征，因此，我们可以将这些亮度值串联成一个高维向量，从而实现图片的向量化表示。 这种向量化表示使我们能够利用向量空间中的距离和相似度度量方法来比较不同图片之间的相似程度。例如，欧氏距离可用于衡量两个图片向量间的像素差异，而余弦相似度则可测量它们的方向差异。通过计算向量间的距离或相似度，我们可以量化评估不同图片之间的相似程度。 在实际应用中，图片除了像素亮度以外还有轮廓等更复杂的特征可以用于比对相似度，所以一般会使用神经网络来进行特征向量的提取，然后通过距离函数来衡量不同图片之间的相似度。这就是为什么向量可以被用来衡量非结构化数据的相似度。 当可搜索内容表示为向量时，查询可以在相似内容中找到接近的匹配项。用于向量生成的嵌入模型知道哪些单词和概念相似，并将生成的向量放置在嵌入空间中。例如，关于 “clouds” 和 “fog” 的向量化源文档更有可能显示在关于 “mist” 的查询中，因为它们在语义上相似，即使它们在词法上不匹配。 向量相似度有几种不同的度量方法，其中最常见的是欧式距离、点积距离和余弦距离。这些度量方法各有特点和适用场景。欧式距离直观地反映了向量在空间中的绝对距离，适用于需要考虑向量大小的情况。点积距离反映了向量的方向和大小，常用于机器学习中的权重计算。余弦距离则专注于向量间的角度，忽略大小差异，特别适合文本相似度等归一化场景。选择合适的度量方法对于提高相似度计算的准确性和效率至关重要，并且往往需要根据具体的应用场景和数据特征进行权衡。 在大规模数据集中，传统的精确最近邻搜索算法可能需要花费大量时间和计算资源。因此，近似最近邻检索（Approximate Nearest Neighbor Search，ANNS）技术的出现满足了对相似度搜索更快速和高效的需求。近似最近邻检索通过牺牲一定的搜索准确度，来换取更快的搜索速度。这种特性使得 ANNS 技术在需要快速检索大规模数据集中的相似对象时极具优势，特别是在诸如推荐系统、图像识别、自然语言处理和数据挖掘等领域。近似最近邻检索技术的应用范围非常广泛，它在提高效率的同时保持了对搜索结果准确度的要求，因此在大数据量情况下更能展现出其价值。 一般来说，近似最近邻搜索依赖对数据集提前构建好一个索引，搜索在索引上进行。通过使用索引，近似最近邻搜索一般能将耗时降低几个量级。常见的向量索引类型：基于树的索引结构、基于哈希的索引结构、基于图的索引结构、基于倒排的索引结构等。这些索引对于构建时间、批量查询、异构计算等场景分别有不同的优势，一般在业务场景中会根据实际需要来选用索引。 本文开头提到的 faiss，hnswlib，包括 vsag 都属于 ANNS 算法库。 虽然现在我们已经有了很多成熟的开源算法，但随着非结构化数据量的持续增长，以及更多 AI 应用的诞生，向量搜索技术被提出了更多的挑战。 更快的搜索速度是第一个挑战。对于更好性能的追求在业务中是一直存在的，更快的搜索速度意味着单位实例能够服务更多的用户请求，同时更快的搜索速度能够降低访问延迟提升体验。 更高的搜索精度是第二个挑战。向量召回作为搜索推荐链路的上游环节，搜索精度很大程度上影响到整条搜索链路的召回精度上界。通过提高向量召回的精度，能够给后续的排序环节提供更加高质量的输入。在 RAG 应用中同理，向量的召回率越高，能够输入给语言大模型的内容就越好，语言大模型的回答就越准确。 更低成本的搜索是第三个挑战。更低成本更多是企业从降本增效出发，希望在技术上获得收益。向量检索因为数据结构本身的特点，查询服务的成本本来就高于标量数据。而当前音视图文数据量的增长给系统带来的服务成本来增长迅速。近几年对于低成本的向量索引的探索更多被关注到，比较有名的是微软提出的 DiskANN 算法，而后续在学术界和工业界也涌现出更多相关的后续工作。 1.BSA（Bridging Speed and Accuracy）：在保证检索精度的前提下加速向量距离计算 背景与设计目的 现有向量检索算法（如 HNSW、IVF）经过多年优化，对索引结构的改进只能带来小幅度性能提升。向量检索算法的性能瓶颈在于“距离计算”这一操作：在 HNSW 中距离计算约占 80% 的总时间开销，在 IVF 中更是接近 90%。使用计算代价更低的近似距离代替精确的距离计算，例如乘积量化（product quantization），虽然可以大幅提高距离计算的效率，然而会导致检索精度的大幅下降，使其很难应用于高精度的向量检索场景。 因此，如何既利用近似距离的实现快速计算、又能够保持高检索精度，成为了 BSA 算法试图解决的关键问题。 核心技术与实现方案 BSA 算法将向量检索中的距离计算分为两类，其中第一类为需要精确距离计算（Label 0），第二类为不需要精确距离计算（Label 1），并利用近似距离、当前搜索过程中的队列阈值作为特征，训练一个线性二分类器，通过调整模型截距来保证分类器的分类精度达到检索要求。 在搜索过程中，如果线性分类器将当前距离计算分为第一类，则需计算当前点的精确距离并更新结果队列；如果线性分类器的分类结果为第二类，该次的距离计算则可以避免。 该算法不仅可以加速内存向量检索的距离计算，同时还可以避免磁盘方案的冗余 IO。 性能表现 以下展示了几种加速距离计算的方法在 GIST 和 DEEP 两个数据集上的性能表现。结果可见，BSA+OPQ 框架实现了原始 HNSW 最高 1.7 倍的检索性能提升，以及相对原始 IVF 最高 2.2 倍的提升，远超索引结构优化带来的性能提升。同时 BSA 方法不受索引结构的限制，可以应用于任意向量检索算法。 实战应用 当前，BSA 方法在内部的数据和实际应用场景均已进行验证和应用： 在 100w 数据集上，在召回率不降低的前提下，搜索耗时从 7.53ms 下降到4.85ms，降低 35.59% 。这意味着吞吐能够增加 55.25% 。 2. EnhanceGraph：动态增强的图索引构建，提升查询准确性 背景与设计目的 以 k-NNs Graph 为例，基于图的近似最近邻搜索（ANNS）算法以其优越的搜索性能和精确性成为主流。为了对其进行进一步优化，当前许多研究正在探索通过边的剪枝策略，减少索引的空间占用和提高搜索效率，然而此类策略往往会导致检索精度大幅下降。此外，由于传统基于图的索引在构建后将保持静态，所以在人脸识别等服务中经常会出现反复识别失败的情况。 面对上述挑战，EnhanceGraph 将搜索日志和构建日志用于辅助图索引的构建，从而有效利用历史查询数据和被丢弃的信息完善图索引，从而在保障查询性能的同时提升准确性。 核心技术与实现方案 EnhanceGraph 利用搜索日志和构造日志对图进行动态增强，前者可用于检测图结构中的缺陷，后者可用于补充近似图中缺失的 k-NNs，从而在可接受的空间成本增加的情况下显著提高查询的准确性。 与现有的索引在构建完成后即保持静态不同，EnhanceGraph 允许在搜索过程中实时进行反馈，基于用户的实时反馈或历史查询生成共轭图，用于维护所有反馈的召回信息。在线搜索时，第一阶段首先在近邻图进行搜索，第二阶段使用共轭图对搜索结果进行补充以增强召回表现。 具体来说，在构建图索引时，首先将近似图中被裁掉的边（构造日志）添加到共轭图中。在历史查询中，将失败查询时收敛到的局部最优解，与离线计算或者用户反馈的全局最优解结合，构成搜索日志。基于搜索日志，可以在共轭图中添加缺失的从局部最优解到全局最优解的边。这些边将在搜索的第二阶段补充搜索结果，以提高召回率，确保历史中失败的查询不会再次收敛到局部最优。 性能表现 如图所示为 EnhanceGraph 在若干主流数据集（GIST1M；SIFT1M；GloVe-100）和蚂蚁数据集上对召回率增强的表现。 结果显示，在部分数据集上，EnhanceGraph 能显著提高 Recall@1 的召回率，最高从 41.74% 提升到 93.42%。得益于从生成的查询和历史的查询得到的搜索信息，大幅度降低了未来的查询对 TOP1 最近邻的召回失败情况。对于OceanBase 数据集，即使是 Recall@1 非常高的情况下也能无损 QPS 提高召回率（从 99.8% 提升到 99.9%）。另外，使用构建信息对二阶段搜索进行补充也显著提升了 Recall@10。 实战应用 当前，EnhanceGraph 已在实际业务场景中进行了测试验证： 在 100w 数据集上，使用生成式方法，在几乎不降低 QPS 和使用少量额外存储空间（少于 7%），提升 HNSW 的 TOP-1 召回率从 99.8% 到 99.96% 。保证召回失败的人群有 80% 以上的概率不会再失败。 3. DFSANN：适配存算分离架构的低成本检索方案 背景与设计目的 当下的向量检索的研究主要关注纯内存向量索引的性能，较少关注海量数据的存储性能。然而，随着非结构化数据的快速膨胀，内存开销增加，数据的存储成本飙升，只使用压缩方法会显著降低精度；同时，存算分离架构中的共享存储相比起本地 SSD 会有更高的 IO 成本，这导致现有的基于 IO 的检索方案（例如DiskANN、SPANN等）不一定有比较高的性能。 因此，业界迫切地需要一种能够适配在存算分离架构系统上的低成本的检索方案。 核心技术与实现方案 现有磁盘方案中，搜索过程会产生频繁 IO，且重排阶段有较多不必要的精确距离计算，从而造成资源浪费。为此，DFSANN 先将搜索过程与 IO 过程进行解耦，再通过优化 IO 方案实现有效降本。一方面，通过减少 IO 次数和 IO 后的重排数据量来优化检索时间，另一方面，通过异步下放 IO 来减少总的 IO 时间： 缓存 Graph 与部分 IO： 将 Graph 缓存至内存，原始数据仍在底层存储中，在搜索过程中使用压缩向量进行快速检索，对近似距离进行排序，仅在结果重排阶段对最有可能的部分后续集进行 IO，从而降低少对磁盘的依赖。 优化 IO 方案： 边搜边 IO： 搜索中异步下发 IO 请求，获取全部候选集对应的精确向量，搜完后只计算部分候选集合的精确距离。该方法虽然需要全量 IO，但只计算部分集合，此外由于 IO 在搜索过程中下发，重排时无需等待，IO 的耗时开销几近于无。 搜完再 IO： 在搜索过程中积累 IO 请求，搜索完成后，根据近似距离排序结果将部分更有可能是最终结果的候选集对应的 IO 请求一次性异步下发，并计算精确距离。该方案可减少 IO 量，但搜索耗时会稍高一些。 进一步的成本优化：当前方案能够在较短的时间内实现较高召回率的检索。然而，受限于本地 SSD 的 IO 并发与图索引的构建成本，单机一般不会只构建一个大规模索引，导致单次检索产生巨大的 IO 开销。后续将采用预聚合（即，预先将部分点聚类成簇）的方式进一步降低存储成本和 IO 成本。 性能表现 在随机数据上的实验结果显示，DFSANN 的两套搜索模式都显著优于原始 DiskANN，特别当存储介质是 DFS 时，DFSANN 的吞吐显著优于 DiskANN。 4. HGraph：适配通用场景，支持平滑切换的六边形战士 背景与设计目的 现有的向量算法往往针对特定的需求，只能做到部分场景的适配。如果伴随业务需求调整，需要切换算法，则算法之间的异构特性会导致切换难度大，同时切换后存在各种不确定性的隐患。HGraph 致力于实现一套支持多种场景并且可以平滑切换的索引。 核心技术与实现方案 HGraph 基于组件化的分层架构，弹性化各个向量检索组件（量化器，IO 模块，图结构模块等），部分组件支持可插拔能力，通过不同组件的配置支持广泛的业务场景，且几乎保持同等性能。 HGraph的分层架构包括： 适配不同场景，HGraph 提供多种组装方案。例如纯内存场景、混合存储场景等，用户在使用上只需要修改配置参数即可实现不同索引类型，支持快速迭代落地。 此外，HGraph 还在算法兼容和工程层面实现了多项优化。算法兼容方面已实现对 BSA、EnhanceGraph、DFSANN 等算法的兼容；工程层面，通过优化算子调用开销、SIMD 混合加速、预取优化等方案，实现了性能对标专业领域索引，甚至有所超越。 典型场景配置 HGraph支持大部分应用场景，覆盖不同数据规格，不同精度诉求，尤其是希望一套索引支持多个场景和具备平滑切换能力的场景。 高性能，高精度场景（数据规模 1M-100M，内存资源充足，精度 99%+，性能要求高）：带重排和共轭图的纯内存方案；或单层 FP32 图，配合共轭图提升精度。 低内存，高性能场景（数据规模 100M-10B，内存资源紧张，精度 96%-98%，性能要求高）。 低成本，混合存储场景（数据规模 10B-1000B，内存资源十分紧张，精度和性能要求放宽） 欢迎访问 OceanBase 官网获取更多信息：https://www.oceanbase.com/
作者 | 金加宝、李昊天、王翔宇、杨鸣宇、钟萧遥（按姓名首字母排序）
OceanBase向量索引库VSAG通过引入SIMD、内存分配优化、量化等方法提升向量检索性能。其核心算法包括：BSA在保证检索精度的前提下加速向量距离计算；EnhanceGraph利用搜索日志和构造日志动态增强图索引，提升查询准确性；DFSANN适配存算分离架构，实现低成本混合存储检索；HGraph则通过组件化分层架构支持多场景平滑切换。向量是什么
如何衡量向量相似度
相似度搜索的一种方法：近似最近邻搜索（ANNS）
向量搜索的挑战在哪里
VSAG 硬核算法详解
在 1000w 数据集上，在召回率不降低的前提下，搜索耗时从 10.09ms 下降到7.33ms，降低 27.35% 。这意味着吞吐能够增加 37.64% 。
在 100w 数据集上，使用历史查询进行反馈，在几乎不降低 QPS 和使用少量额外存储空间（少于 3%），提升 HNSW 的 TOP-1 召回率从 99.8% 到 99.97% 。保证召回失败的人群有 85% 以上的概率不会再失败。
基础的算子层：包括量化器算子，IO访问算子等，支持新型的量化算法变更，支持多种数据访问方式；
数据组织层：提供算法核心能力，支持多种算法角度的数据结构管理、访问与计算能力；
接口抽象层：屏蔽底层的数据结构细节，提供统一的访问接口；
基础索引层：支持具体的索引算法结构，包含了构建、训练、检索的工作流，以及标签过滤、范围查询等特定功能。
