论文状态:已完成

HARMONY: A Scalable Distributed Vector Database for High-Throughput Approximate Nearest Neighbor Search

发表:2025/06/18
原文链接PDF 下载
价格:0.100000
价格:0.100000
已有 1 人读过
本分析由 AI 生成,可能不完全准确,请以原文为准。

TL;DR 精炼摘要

本文提出Harmony,针对高吞吐量近似最近邻搜索(ANNS)设计的可扩展分布式向量数据库。采用新颖的多粒度分区策略,有效解决负载不平衡和通信开销问题,通过基于维度和基于向量的组合确保各节点间负载均衡,并引入提前停止剪枝机制,降低计算和通信成本,实验结果表明整体性能显著提高。

摘要

Approximate Nearest Neighbor Search (ANNS) is essential for various data-intensive applications, including recommendation systems, image retrieval, and machine learning. Scaling ANNS to handle billions of high-dimensional vectors on a single machine presents significant challenges in memory capacity and processing efficiency. To address these challenges, distributed vector databases leverage multiple nodes for the parallel storage and processing of vectors. However, existing solutions often suffer from load imbalance and high communication overhead, primarily due to traditional partition strategies that fail to effectively distribute the workload. In this paper, we introduce Harmony, a distributed ANNS system that employs a novel multi-granularity partition strategy, combining dimension-based and vector-based partition. This strategy ensures a balanced distribution of computational load across all nodes while effectively minimizing communication costs. Furthermore, Harmony incorporates an early-stop pruning mechanism that leverages the monotonicity of distance computations in dimension-based partition, resulting in significant reductions in both computational and communication overhead. We conducted extensive experiments on diverse real-world datasets, demonstrating that Harmony outperforms leading distributed vector databases, achieving 4.63 times throughput on average in four nodes and 58% performance improvement over traditional distribution for skewed workloads.

思维导图

论文精读

中文精读

1. 论文基本信息

1.1. 标题

HARMONY: A Scalable Distributed Vector Database for High-Throughput Approximate Nearest Neighbor Search(HARMONY:一种用于高吞吐量近似最近邻搜索的可扩展分布式向量数据库)

1.2. 作者

Qian Xu, Feng Zhang, Chengxi Li, Zheng Chen, Xiaoyong Du(中国人民大学);Lei Cao(麻省理工学院);Jidong Zhai(清华大学)。

1.3. 发表期刊/会议

未明确提及,但通常这类研究发表在计算机系统、数据库或人工智能相关领域的顶级会议或期刊上。

1.4. 发表年份

2025

1.5. 摘要

近似最近邻搜索(ANNS)是推荐系统、图像检索和机器学习等数据密集型应用的核心。在单台机器上处理数十亿高维向量的 ANNS 面临内存容量和处理效率方面的巨大挑战。为解决这些问题,分布式向量数据库利用多个节点并行存储和处理向量。然而,现有解决方案通常由于传统分区策略未能有效分配工作负载,导致负载不平衡和高通信开销。本文介绍了 Harmony,一个分布式 ANNS 系统,它采用新颖的多粒度分区策略,结合了基于维度(dimension-based)和基于向量(vector-based)的分区。该策略确保了所有节点上计算负载的均衡分布,同时有效最小化了通信成本。此外,Harmony 引入了一种利用基于维度分区中距离计算单调性的提前停止剪枝(early-stop pruning)机制,显著减少了计算和通信开销。我们在各种真实世界数据集上进行了广泛实验,结果表明 Harmony 优于领先的分布式向量数据库,在四节点配置下平均吞吐量提高 4.63 倍,对于偏斜工作负载,性能比传统分布提高了 58%。

1.6. 原文链接

原文链接: https://arxiv.org/abs/2506.14707 PDF 链接: https://arxiv.org/pdf/2506.14707v1.pdf 发布状态: 预印本(Preprint)。

2. 整体概括

2.1. 研究背景与动机

论文试图解决的核心问题: 在数据密集型应用中,近似最近邻搜索(ANNS)需要处理数十亿高维向量,这在单台机器上存在内存容量和处理效率的瓶颈。现有的分布式向量数据库解决方案在扩展 ANNS 时,常常面临负载不平衡和高通信开销的问题,因为传统的向量分区策略未能有效分配工作负载。

为什么这个问题在当前领域是重要的?现有研究存在哪些具体的挑战或空白(Gap)?

  1. 数据量爆炸式增长: 图像、视频、文本等非结构化数据被转换为高维向量后,其规模巨大,例如阿里巴巴双十一每天产生 500PB 数据,YouTube 每分钟上传 500 小时内容。这使得单机 ANNS 无法满足需求。
  2. 高维向量的特殊性: 高维向量的距离计算成本高昂,占 ANNS 搜索时间的 90% 以上,尤其是在基于聚类的索引中。传统的分区方法(如基于图的分区)在分布式环境中会引入跨机器的边,导致高延迟。
  3. 现有分布式方案的缺陷:
    • 负载不平衡: 传统的基于聚类或哈希的分区方法在面对偏斜(skewed)工作负载时,会导致某些机器处理过多的计算,而其他机器利用率不足,从而降低整体性能。
    • 高通信开销: 尽管分布式向量数据库会传输中间结果,其大小通常小于原始向量的 10%,但由于带宽差异(传输速度远低于计算速度),通信开销仍然显著,导致延迟。
    • 缺乏有效的剪枝策略: 尽管多机器环境提供了进行机间剪枝(inter-machine pruning)的机会,但设计轻量级的管道(pipelines)来有效剪枝并最小化开销仍然是一个挑战。

这篇论文的切入点或创新思路: Harmony 系统提出了一种新颖的多粒度分区策略,结合了基于维度(dimension-based)和基于向量(vector-based)的分区。同时,它引入了基于维度分区中距离计算单调性(monotonicity)的早期停止剪枝机制,以期在分布式 ANNS 中实现负载均衡、最小化通信开销并提高吞吐量。

2.2. 核心贡献/主要发现

论文最主要的贡献:

  1. 多粒度分区策略: 提出了结合基于维度和基于向量分区的混合索引构建框架,通过成本模型(cost model)动态适应查询特性和集群状态,优化资源分配,提高系统效率。
  2. 负载均衡优化: 通过结合维度分区(均衡计算负载)和向量分区(最小化通信开销),Harmony 解决了负载不平衡问题,在各种工作负载下保持高吞吐量和稳定性。
  3. 维度级剪枝机制: 引入了基于维度分区中距离计算单调性的早期停止剪枝技术。当部分向量维度计算的距离已超过当前最佳阈值时,可以提前终止后续计算,显著减少计算和通信开销。
  4. 柔性流水线执行引擎: 设计了一个灵活的流水线(pipelined)执行引擎,将向量级和维度级计算进行流水线处理,实现了分布式剪枝,减少了冗余计算和通信。

论文得出了哪些关键的结论或发现?

  1. Harmony 在四节点配置下,平均吞吐量比最先进的向量数据库(如 Faiss)提高了 4.63 倍。
  2. 对于偏斜工作负载,Harmony 的性能比传统分布提高了 58%。
  3. 维度级剪枝在后期切片(slices)中表现出极高的剪枝率,例如在第四个切片中高达 92.33%,显著减少了计算量。
  4. 负载均衡、流水线和异步执行以及剪枝技术都对性能提升有贡献,其中剪枝是提高吞吐量的关键优化手段。
  5. Harmony 能够随着数据集规模和维度增加而有效扩展,并且在某些情况下实现了超线性加速。
  6. 与传统分布式系统相比,Harmony 在索引构建时间和空间开销方面表现出相似甚至更优的效率,其额外的空间开销非常小。

3. 预备知识与相关工作

3.1. 基础概念

为了理解 Harmony,需要先了解以下几个核心概念:

3.1.1. 近似最近邻搜索 (Approximate Nearest Neighbor Search, ANNS)

ANNS 旨在在大规模数据集中高效地找到与给定查询向量最相似(或距离最近)的 K 个向量。与精确最近邻搜索(Exact Nearest Neighbor Search, ENNS)不同,ANNS 允许在搜索结果的准确性上进行一定程度的妥协,以换取显著的速度提升。在许多实际应用中,近似结果已经足够,例如推荐系统、图像检索等。ANNS 通常通过构建索引结构来加速搜索过程。

3.1.2. 高维向量 (High-Dimensional Vectors)

高维向量是指具有大量维度(通常数百到数千维)的向量。在机器学习和深度学习中,图像、文本、音频等非结构化数据经常被编码(嵌入)成高维向量表示。随着维度增加,距离计算的复杂性急剧上升,并且会出现“维度灾难”(Curse of Dimensionality)问题,使得在高维空间中进行精确搜索变得非常困难且计算成本高昂。

3.1.3. 分布式向量数据库 (Distributed Vector Databases)

分布式向量数据库是为了应对大规模高维向量存储和搜索挑战而设计的系统。它们通过将向量数据和计算任务分散到多个节点(机器)上,实现并行处理和存储,从而突破单机限制。这种架构旨在提高可扩展性(scalability)、吞吐量(throughput)和容错性。

3.1.4. 向量距离/相似度度量 (Vector Distance/Similarity Metrics)

在 ANNS 中,衡量向量之间“近”或“相似”的程度需要用到距离或相似度函数。论文中提到了两种常见的度量:

  1. 欧几里得距离 (Euclidean Distance): 衡量 dd 维空间中两点之间的直线距离。平方欧几里得距离的计算公式为: D _ { \mathrm { E u c l } } ^ { 2 } ( { \bf p } , { \bf q } ) = \sum _ { i = 1 } ^ { d } ( p _ { i } - q _ _ { i } ) ^ { 2 } 其中 p=(p1,,pd)\mathbf{p} = (p_1, \ldots, p_d)q=(q1,,qd)\mathbf{q} = (q_1, \ldots, q_d) 是两个 dd 维向量。
  2. 余弦相似度 (Cosine Similarity): 衡量两个向量在 dd 维空间中方向上的相似性,值域通常在 -1 到 1 之间。当向量预先归一化(即其 L2L_2 范数等于 1)后,余弦相似度等同于向量的点积(dot product): \mathbf { p } \cdot \mathbf { q } = \sum _ { i = 1 } ^ { d } p _ { i } q _ _ { i } 余弦相似度的完整公式为: CosineSimilarity(p,q)=pqpq=i=1dpiqii=1dpi2i=1dqi2 \mathrm{CosineSimilarity}(\mathbf{p}, \mathbf{q}) = \frac{\mathbf{p} \cdot \mathbf{q}}{\|\mathbf{p}\| \|\mathbf{q}\|} = \frac{\sum_{i=1}^{d} p_i q_i}{\sqrt{\sum_{i=1}^{d} p_i^2} \sqrt{\sum_{i=1}^{d} q_i^2}}

3.1.5. 维度灾难 (Curse of Dimensionality)

当数据的维度非常高时,数据点的分布变得稀疏,距离度量的有效性降低,并且许多算法的计算成本会呈指数级增长。这使得在高维空间中进行搜索和索引变得极其困难。

3.2. 前人工作

论文将 ANNS 的索引技术分为两类:

3.2.1. 基于图的索引 (Graph-Based Indexes)

这类方法通过构建一个图(graph),其中节点是向量,边表示向量之间的相似性或邻近关系。查询过程通常涉及在图上进行遍历(如广度优先搜索),以找到最近的邻居。

  • 代表工作: HNSW(Hierarchical Navigable Small World graphs)、NSG(Navigating Spreading-out Graph)、DiskANN 等。
  • 挑战: 在分布式环境中,图的边可能跨越不同的机器,导致高通信延迟。

3.2.2. 基于分区/聚类的索引 (Partition-Based Indexes)

这类方法将向量数据集分割成多个分区或簇(clusters),然后首先识别与查询向量相关的分区,再在这些分区内部进行更精细的搜索。

  • 子类别:
    • 基于聚类 (Cluster-based): 如 IVF(Inverted File Index)、Product Quantization 等。这些方法将向量聚类成若干组,每个组有一个质心(centroid)。查询时,首先找到与查询向量最近的几个质心,然后在这些质心对应的簇中搜索。
    • 基于哈希 (Hash-based): 如 LSH(Locality-Sensitive Hashing)。通过哈希函数将相似的向量映射到相同的哈希桶中,从而加速搜索。
    • 基于高维树 (High-dimensional Tree-based): 如 KD-tree、R-tree 等。通过树形结构将高维空间递归地划分为子区域。
  • 挑战: 虽然这类方法能提高单机查询速度,但通常需要存储完整维度的向量以确保距离计算准确性,从而引入额外的存储开销。在分布式环境中,如何有效分区以避免负载不平衡和高通信开销是关键问题。

3.2.3. 分布式数据管理系统 (Distributed Data Management Systems)

论文还提到了图数据库(如 Neo4j, TigerGraph, JanusGraph)和关系型数据库(如 Google Spanner, CockroachDB, F1)在分布式数据管理方面的经验。这些系统通过分区(sharding)策略将数据分散到多个机器上,以最小化节点间通信并平衡工作负载。分布式查询引擎(如 Presto, Spark SQL, Apache Drill)则利用大规模并行处理(MPP)和内存计算来降低查询延迟。

3.3. 技术演进

ANNS 技术从早期的基于树和哈希的方法,逐渐发展到基于图和基于聚类的索引。随着数据规模的增长,单机解决方案逐渐达到瓶颈,分布式 ANNS 成为了必然趋势。早期的分布式 ANNS 解决方案主要关注如何在多机环境下提高查询性能和保证准确性,但往往忽视了负载不平衡和通信开销的问题。例如,Milvus 和 Auncel 等系统采用了分布式架构,但它们的分区策略可能在面对偏斜工作负载时表现不佳。Harmony 正是在此背景下,通过结合多粒度分区和维度级剪枝,试图进一步优化分布式 ANNS 的性能和鲁棒性。

3.4. 差异化分析

特性/方法 传统基于向量分区 (Harmony-vector) 传统基于维度分区 (Harmony-dimension) Harmony (本文)
分区策略 将完整向量分配到不同节点 将向量维度空间分配到不同节点 混合多粒度分区(向量+维度),由成本模型动态决定
负载均衡 易导致负载不平衡,尤其在偏斜工作负载下表现差 能确保负载均衡,每个节点贡献相等 结合两者优势,通过成本模型实现高效负载均衡
通信开销 较低,每个节点只需与主节点通信两次 较高,需要多次通信聚合部分距离结果 通过流水线和维度级剪枝有效降低通信开销
剪枝能力 无法进行维度级早期停止剪枝 可进行维度级早期停止剪枝 可进行维度级早期停止剪枝,且通过流水线优化,减少开销
对偏斜工作负载的鲁棒性 差,性能急剧下降 强,性能稳定 强,通过自适应分区和剪枝保持高吞吐量
整体吞吐量 在均衡负载下可能较高,但稳定性差 稳定但绝对吞吐量可能受通信限制 在各种负载下均表现出高吞吐量和稳定性

Harmony 的核心创新在于认识到单一分区策略的局限性,并提出将向量分区和维度分区进行结合,并通过一个智能的成本模型来动态选择最适合当前工作负载的组合。更重要的是,它将维度分区带来的“距离计算单调性”这一特性,通过流水线执行和分布式剪枝机制发挥到极致,从而在降低计算量的同时,有效管理通信开销。

4. 方法论

Harmony 旨在解决现有分布式 ANNS 系统中负载不平衡和高通信开销的问题,通过引入多粒度分区策略和维度级剪枝机制来实现高吞吐量和鲁棒性。其核心设计包括一个细粒度查询规划器(Fine-grained Query Planner)和一个灵活的流水线执行引擎(Flexible Pipelined Execution Engine)。

4.1. 方法原理

Harmony 的核心思想是结合基于向量(vector-based)和基于维度(dimension-based)分区的优点,并利用维度分区带来的距离计算单调性进行早期停止剪枝。

  • 基于向量分区(Vector-based Partition): 将整个向量分配给不同的节点。优点是通信开销低,因为每个节点只与主节点进行两次通信(发送查询、接收结果)。缺点是容易出现负载不平衡,特别是当查询集中在某些“热点”向量或分区时。

  • 基于维度分区(Dimension-based Partition): 将向量的维度空间拆分,每个节点负责向量的一部分维度。优点是能确保负载均衡,因为每个节点对所有查询的距离计算都做出贡献。缺点是通信开销较高,因为需要多次通信来聚合各个节点的部分距离结果。

  • 维度级剪枝(Dimension-Level Pruning): 基于维度分区,距离计算具有单调性。对于欧几里得距离 DEucl2(p,q)D_{\mathrm{Eucl}}^2(\mathbf{p}, \mathbf{q}) 和余弦相似度 pq\mathbf{p} \cdot \mathbf{q} 的计算,它们可以分解为各个维度上的部分和。例如,欧几里得距离是各个维度平方差的和,总是非负的,因此累积的偏置距离是单调递增的。当累积的部分距离超过了当前最佳候选的距离阈值时,就可以安全地停止对该向量的进一步计算,从而剪枝。

    Harmony 通过一个成本模型来动态地在两种分区策略之间进行权衡,以适应不同的工作负载和集群状态。同时,它设计了一个流水线执行引擎,将维度级剪枝机制集成到分布式查询过程中,以最大化效率。

4.2. 细粒度查询规划器 (Fine-grained Query Planner)

查询规划器的目标是根据当前工作负载和集群状态,通过一个成本模型选择最优的分区策略(向量分区、维度分区或混合分区),并实现高效的查询负载分布。

4.2.1. 成本模型 (Cost Model)

成本模型量化了在给定分区计划 π\pi 下,系统的计算和通信开销以及负载不平衡程度。

  • 符号定义:

    • π\pi: 分区计划。
    • Bdim(π)\mathcal{B}_{\dim}(\pi): 在分区计划 π\pi 中,所有的维度块(dimension-based blocks)集合。
    • Bvec(π)\mathcal{B}_{\mathrm{vec}}(\pi): 在分区计划 π\pi 中,所有的向量块(vector-based blocks)集合。
    • bb: 单个维度块, bBdim(π)b \in \mathcal{B}_{\dim}(\pi)
    • ss: 单个向量块, sBvec(π)s \in \mathcal{B}_{\mathrm{vec}}(\pi)
    • ccompdim(b,q)c_{\mathrm{comp}}^{\dim}(b, q): 查询 qq 在维度块 bb 上处理时的计算成本。
    • ccommdim(b,q)c_{\mathrm{comm}}^{\dim}(b, q): 查询 qq 在维度块 bb 上处理时的通信成本。
    • ccompvec(s,q)c_{\mathrm{comp}}^{\mathrm{vec}}(s, q): 查询 qq 在向量块 ss 上处理时的计算成本。
    • ccommvec(s,q)c_{\mathrm{comm}}^{\mathrm{vec}}(s, q): 查询 qq 在向量块 ss 上处理时的通信成本。
    • Load(n,π)\operatorname{Load}(n, \pi): 在分区计划 π\pi 下节点 nn 的总工作负载。
    • I(π)I(\pi): 不平衡因子(Imbalance factor)。
    • α\alpha: 用户定义的权重,用于强调不平衡因子在总成本中的重要性。
  • 查询成本 (Query Cost): 对于每个查询 qQq \in \mathcal{Q}(其中 Q\mathcal{Q} 是查询向量集合),其总成本 Cq(π)C_q(\pi) 是所有维度块和向量块上计算和通信成本之和: Cq(π) = bBdim(π)[ccompdim(b,q) + ccommdim(b,q)]+sBvec(π)[ccompvec(s,q)+ccommvec(s,q)] C _ { q } ( \pi ) \ = \ \sum _ { b \in \mathcal { B } _ { \dim } ( \pi ) } \left[ c _ { \mathrm { c o m p } } ^ { \dim } ( b , q ) \ + \ c _ { \mathrm { c o m m } } ^ { \dim } ( b , q ) \right] \\ + \sum _ { s \in \mathcal { B } _ { \mathrm { v e c } } ( \pi ) } \Big [ c _ { \mathrm { c o m p } } ^ { \mathrm { v e c } } ( s , q ) + c _ { \mathrm { c o m m } } ^ { \mathrm { v e c } } ( s , q ) \Big ] 其中 Bdim(π,n)\mathcal{B}_{\dim}(\pi, n) 表示存储在节点 nn 上的维度块, Bvec(π,n)\mathcal{B}_{\mathrm{vec}}(\pi, n) 表示存储在节点 nn 上的向量分片。

  • 不平衡因子 (Imbalance Factor): 首先,定义节点 nn 的总工作负载 Load(n,π)\operatorname{Load}(n, \pi) 为其处理所有查询时,所有维度块和向量块的计算成本之和: Load(n,π)=qQ[bBdim(π,n)ccompdim(b,q)+sBvec(π,n)ccompvec(s,q)] \operatorname { L oad } ( n , \pi ) = \sum _ { q \in Q } \big [ \sum _ { b \in \mathcal { B } _ { \dim } ( \pi , n ) } c _ { \mathrm { c o m p } } ^ { \dim } ( b , q ) + \sum _ { s \in \mathcal { B } _ { \mathrm { v e c } } ( \pi , n ) } c _ { \mathrm { c o m p } } ^ { \mathrm { v e c } } ( s , q ) \big ] 不平衡因子 I(π)I(\pi) 通过所有节点负载的标准差(standard deviation)来定义: I(π) = 1Nn=1N[Load(n,π)L]2, where L=1Nn=1NLoad(n,π). I ( \pi ) \ = \ \sqrt { \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \bigl [ \mathrm { L o a d } ( n , \pi ) - \overline { { L } } \bigr ] ^ { 2 } } , \ \mathrm { w h e r e } \ \overline { { L } } = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \mathrm { L o a d } ( n , \pi ) . 其中 NN 是节点数量, L\overline{L} 是所有节点平均负载。不平衡因子越大,表示某些节点可能过载。

  • 总成本函数 (Overall Cost Function): 将查询成本和不平衡因子结合成一个单一的优化目标: C(π,Q) = qQCq(π) + αI(π). C \bigl ( \pi , Q \bigr ) \ = \ \sum _ { q \in Q } C _ { q } ( \pi ) \ + \ \alpha \cdot I ( \pi ) . 这里的 α\alpha 是一个用户定义的权重,用于平衡对负载偏斜的惩罚与对局部计算/通信效率的关注。成本模型通过估计轻量级指标(如聚类中心的数量、查询向量的维度)来计算,因此开销极小。

4.2.2. 查询负载分布 (Query Load Distribution)

Harmony 的查询负载分布过程分为以下几个步骤(参考 Figure 4):

  1. 确定分区计划 π\pi 成本模型分析工作负载并确定最优的分区计划 π\pi,这会得到一个维度划分网格 Bdim(π)\mathcal{B}_{\dim}(\pi) 和向量划分网格 Bvec(π)\mathcal{B}_{\mathrm{vec}}(\pi)
  2. 基础向量分布: 如图 4(a) 所示,数据集被划分为维度分区 {D1,D2,D3}\{D_1, D_2, D_3\} 和向量分区 {V1,V2}\{V_1, V_2\},这会产生一系列组合块 {V1D1,V1D2,}\{V_1D_1, V_1D_2, \ldots\}。集群中的每台机器(M1M_1M6M_6)负责存储其中一个这样的组合块,完成基础向量数据的分布。
  3. 处理查询向量: 当接收到查询向量时(如图 4(b) 所示):
    • 识别聚类质心: 客户端首先检索相关的聚类质心(cluster centroids),这是许多基于聚类的 ANNS 引擎的标准操作,将每个查询 qiq_i 映射到其关联的基础向量部分。例如,查询 Q1 映射到 V1
    • 映射查询到向量块: Harmony 确定每个查询应该访问哪些向量分区 Bvec(π)\mathcal{B}_{\mathrm{vec}}(\pi)
    • 结合维度划分并映射到机器: 确定向量分区后,Harmony 进一步根据维度分区 Bdim(π)\mathcal{B}_{\dim}(\pi) 拆分查询。例如,映射到 V1Q1 会被拆分成 Q1D1, Q1D2, Q1D3,分别对应维度分区 {D1,D2,D3}\{D1, D2, D3\}。这些查询块被路由到对应的机器进行部分距离计算。如图 4(b) 所示,像 V1D1, V1D2, V1D3 这样的块被分配给 M1, M2, M3。这确保了 Q1D1, Q1D2, Q1D3 在不同机器上并行处理。

优势:

  • 由于 Bdim(π)×Bvec(π)\mathcal{B}_{\dim}(\pi) \times \mathcal{B}_{\mathrm{vec}}(\pi) 中的块均匀分布在机器之间,查询能够充分利用所有节点。
  • 没有机器会处理不成比例的大量数据,从而实现负载均衡和高吞吐量。

复杂度分析:

  • 时间复杂度:

    1. 质心分配(计算开销): 对于 QQ 个查询向量, DD 维, NC 个基础质心,找到最近质心的成本为 O(QNCD2)O(Q \cdot NC \cdot D^2)。这是大多数 ANNS 引擎的常规操作,Harmony 没有引入额外开销。
    2. 查询分布(通信开销): 每个查询向量需要与 VV 台机器交互。在 Harmony 中,这个数量增加到 VBV \cdot B,其中 BB 是维度划分的数量 Bdim(π)\mathcal{B}_{\dim}(\pi)。然而,传输的总数据量保持不变,因为每个拆分的大小减少为 QD/BQ \cdot D / B。因此,尽管查询可能涉及更多通信,但总通信成本保持不变。 总体而言,Harmony 的查询分布与传统分区方案相比,没有增加额外的通信或计算开销。
  • 空间复杂度: Harmony 的空间需求极小,因为每个基础向量只存储在一台机器上,没有冗余。查询集通常相对于基础向量较小,因此存储和路由查询拆分的空间成本可忽略不计。每个 NB 个基础向量被拆分成 Bvec(π)×Bdim(π)\mathcal{B}_{\mathrm{vec}}(\pi) \times \mathcal{B}_{\dim}(\pi) 个块,因此每个块存储大约 NB×DBvec(π)×Bdim(π)\frac{NB \times D}{\mathcal{B}_{\mathrm{vec}}(\pi) \times \mathcal{B}_{\dim}(\pi)} 个元素,总存储量为 NBDNB \cdot D(无重复)。

4.3. 柔性流水线执行引擎 (Flexible Pipelined Execution Engine)

Harmony 的流水线执行引擎旨在解决分布式环境中部分距离计算隔离导致无法有效剪枝的问题,通过序列化和并行化的结合实现高效的分布式剪枝。

Algorithm 1: Harmony 的查询流水线算法

Function PrewarmHeap (QuerySet Q, int K):
    // 计算查询子集的部分距离,构建初始最大堆
    foreach q in Q_subset do
        dist ← ComputeDistance (q, randomVectors)
        heap_insert(q, dist, K)
    return heap

Function DimensionPipeline (q, DSet):
    // 顺序处理 DSet 中的每个维度块
    foreach d in DSet do
        partialDist ← ComputeDistance (q, d)
        if partialDist > q.currentThreshold then
            prune(q) // 剪枝该查询
            return
        UpdatePruning (q, partialDist) // 更新剪枝阈值

Function VectorPipeline (QueryBatch Qv, DSet):
    // 处理特定向量分区的一批查询
    foreach q in Qv do
        DimensionPipeline (q, DSet) // 对每个查询执行维度流水线
        if q.pruned == true then
            continue // 如果已剪枝,跳过
        UpdatePruning (q, finalDist) // 更新最终剪枝阈值

Function QUERYPIPELINE(QuerySet Q, VSetList VList, DSetList DList, int K):
    // 阶段 0: 预热 (Prewarming)
    heap ← PrewarmHeap (Q, K)
    // 阶段 I: 向量级流水线 (Vector-level pipeline)
    foreach vPart in VList do
        Qv ← filterQueries(Q, vPart) // 过滤出属于当前向量分区的查询
        VectorPipeline (Qv, DList) // 对该批查询执行向量流水线

算法详解:

  1. 预热阶段 (Prewarm Stage) - PrewarmHeap (Lines 1-5):

    • 目的: 在查询开始前,通过计算查询子集(通常是查询向量本身与一些随机向量或质心)的距离,预先填充一个大小为 KK 的最大堆(max-heap)。
    • 作用: 这个最大堆存储了当前已知的前 KK 个最近邻的距离,其堆顶元素提供了一个初始的早期剪枝阈值(q.currentThreshold)。任何后续计算中,如果一个候选向量的部分距离已经超过这个阈值,就可以直接被剪枝。
  2. 向量流水线 (Vector Pipeline) - VectorPipeline (Lines 13-18):

    • 目的: 以批次(batch)的方式处理属于特定向量分区的查询。
    • 流程: 遍历 VList 中的每个向量分区 vPart。对于每个 vPart,它会过滤出所有需要访问该分区的查询 Qv。然后,对 Qv 中的每个查询调用 DimensionPipeline 进行部分距离计算。在处理完每个查询后,如果查询未被剪枝,会更新全局的剪枝阈值。
    • 作用: 实现了粗粒度的剪枝。每个向量分区处理完毕后,全局剪枝阈值会变得更紧,后续的查询批次能受益于更严格的剪枝条件,减少不必要的计算。
  3. 维度流水线 (Dimension Pipeline) - DimensionPipeline (Lines 6-12):

    • 目的: 处理单个查询的每个维度块。
    • 流程: 对于给定查询 qq,它会顺序遍历 DSet 中的每个维度块 dd。计算 qqdd 上的部分距离 partialDist
    • 早期停止剪枝: 这是 Harmony 的关键创新点。如果 partialDist 已经大于 q.currentThreshold(来自预热堆或之前维度计算更新的阈值),则立即剪枝该查询(prune(q))并返回,不再处理后续维度块。
    • 更新阈值: 如果未剪枝,则更新 q.currentThreshold,将其调整为 partialDist,因为累积距离只会增加。
    • 作用: 实现了细粒度的剪枝。利用距离计算的单调性,在查询的维度计算过程中,一旦发现该向量不可能成为 Top-K 结果,就立即停止计算,从而显著减少计算量和通信量。

复杂度分析:

  • 时间复杂度:

    • 在理想的(集中式)场景下,一次 ANNS 查询的总操作数是 O(QNBnprobe/nlistD2)O(Q \cdot NB \cdot n_{\mathrm{probe}} / n_{\mathrm{list}} \cdot D^2),其中 QQ 是查询向量数,NB 是基础向量数,nlistn_{\mathrm{list}} 是总聚类数,nproben_{\mathrm{probe}} 是每个查询探测的聚类数,DD 是维度数。
    • 在 Harmony 中,工作被分布到 Bvec(π)×Bdim(π)\mathcal{B}_{\mathrm{vec}}(\pi) \times \mathcal{B}_{\dim}(\pi) 个机器上。在负载均衡的条件下,每台机器处理的计算量为: Q×(nprobe/nlist)×NB×D2Bvec(π)×Bdim(π). \frac { Q \times ( n _ { \mathrm { probe } } / n _ { \mathrm { list } } ) \times NB \times D ^ { 2 } } { \mathcal { B } _ { \mathrm { v e c } } ( \pi ) \times \mathcal { B } _ { \mathrm { d i m } } ( \pi ) } .
    • 因此,最终每台机器的成本规模为 O(QnlistNBD2nprobeBvec(π)Bdim(π))O \big( \frac { Q \cdot n _ { \mathrm { list } } \cdot NB \cdot D ^ { 2 } } { n _ { \mathrm { probe } } \mathcal { B } _ { \mathrm { v e c } } ( \pi ) \mathcal { B } _ { \mathrm { d i m } } ( \pi ) } \big)。计算量减少的程度与机器数量成正比。
  • 通信开销:

    • 平均而言,每个查询与 nprobe×Bvec(π)nlistn_{\mathrm{probe}} \times \frac{\mathcal{B}_{\mathrm{vec}}(\pi)}{n_{\mathrm{list}}} 个向量块进行交互,并与 Bdim(π)\mathcal{B}_{\dim}(\pi) 个维度块进行交互。
    • 通信次数增加了 Bdim(π)\mathcal{B}_{\dim}(\pi) 倍,但每次传输的数据量减少为 1/Bdim(π)1/\mathcal{B}_{\dim}(\pi)
    • 因此,查询分布的通信量与以下表达式成比例: (NBBvec(π))×(nprobe×Bvec(π)nlist)×DBdim(π)×Bdim(π), \left( \frac { N B } { \mathcal { B } _ { \mathrm { v e c } } ( \pi ) } \right) \times \left( n _ { \mathrm { probe } } \times \frac { \mathcal { B } _ { \mathrm { v e c } } ( \pi ) } { n _ { \mathrm { l i s t } } } \right) \times \frac { D } { \mathcal { B } _ { \mathrm { d i m } } ( \pi ) } \times \mathcal { B } _ { \mathrm { d i m } } ( \pi ) ,
    • 这表明 Harmony 的通信开销与纯粹基于向量的方案相同。维度更细粒度的划分并没有增加总传输数据量,只是将其重组为更小、可并行化的块。
  • 空间复杂度:

    • NB 个基础向量被拆分到 Bvec(π)\mathcal{B}_{\mathrm{vec}}(\pi) (向量) ×Bdim(π)\times \mathcal{B}_{\dim}(\pi) (维度) 个块中。因此,每个块大约存储 NB×DBvec(π)×Bdim(π)\frac { N B \times D } { \mathcal { B } _ { \mathrm { v e c } } ( \pi ) \times \mathcal { B } _ { \mathrm { d i m } } ( \pi ) } 个元素,总存储量为 NBDNB \cdot D(无重复)。
    • 中间查询结果相对于原始数据集很小,可以忽略不计。
    • 因此,空间成本仍为 O(NBD)O(NB \cdot D),与标准分布式系统匹配,没有额外的复制。

流水线与剪枝示例 (Figure 5 详解):

  • 向量级流水线与剪枝 (Figure 5a):

    • 查询被分批处理,每批对应一个向量分区。
    • 在 Stage A,查询 Q1-Q3 分配到 V1Q4-Q6 分配到 V2
    • 每批完成初始距离计算后,会更新全局剪枝条件,即优化最大堆阈值。
    • 例如,处理完 V1 后,系统会得到更严格的剪枝阈值,Stage B 中处理 Q4-Q6V1 时,就能受益于更紧的阈值,减少不必要的计算。这种迭代式优化在向量分区之间实现了高效剪枝。
  • 维度级流水线 (Figure 5b):

    • 每个向量的维度被分配到不同的机器上,确保没有多个维度同时处理。这种设计使得维度级计算以流水线方式进行,实现有效剪枝。
    • Stage X: 每台机器开始处理分配给查询的第一个维度块。例如,Q1 处理 D1M1 上,Q2 处理 D2M2 上,Q3 处理 D3M3 上。计算部分距离后,中间结果被累积并与全局剪枝阈值比较。如果累积距离超过阈值,查询立即被剪枝,避免后续维度计算。
    • Stage Y: 机器在尊重更新后的剪枝条件下处理下一个维度块。例如,Q1D2 发送到 M2Q2D3 发送到 M3Q3D1 发送到 M1。在此阶段,Stage X 计算的部分结果被重用并与当前维度块的新计算距离累加。再次检查剪枝阈值,确保不再对无希望的查询进行不必要的计算。
    • ** Stage Z:** 类似 Stage Y,继续处理剩余维度块。
    • 关键机制: 各个工作节点之间传输的是轻量级的中间结果。通过确保同一查询向量的不同维度在非连续阶段处理(例如引入额外的查询 Q7-Q9),部分结果传输不会阻塞关键计算路径。每个阶段独立进行,无需等待前一阶段完全结束,显著减少了通信开销。
    • 这种流水线确保了在每个阶段,给定查询的维度分布在不同机器上,消除了计算重叠。通过利用维度在节点间的分布,Harmony 避免了维度分区实现中通常所需的同步开销。这种方法最大化了剪枝,同时最小化了机器间通信和冗余计算。

负载均衡策略: 尽管初始分布确保了机器之间的负载均衡,但剪枝操作会随着时间引入不平衡。这是因为流水线中后处理的维度更有可能被剪枝,导致某些机器的计算量减少,而其他机器负载较重。为解决此问题,Harmony 会动态调整维度的执行顺序以减少负载不平衡。例如,如果负责 D1 的机器(如 M1)过载,后续查询(如 Q2)将被重新配置为最后处理 D1。由于剪枝在后期阶段更有效,这种调整显著减轻了过载机器的负担,确保没有机器成为瓶颈,维持了均衡的查询执行和提高的吞吐量。

5. 实验设置

5.1. 数据集

实验使用了 10 个不同大小和维度的开源数据集,这些数据集由各种类型的数据(时间序列、音频、图像、词向量和文本)嵌入而成。它们在 ANNS 系统和算法中被广泛评估。为了确保足够的数据量进行分布式处理,Star Light Curves 和 Hand Outlines 数据集被扩展。

以下是原文 Table 2 的结果:

Dataset Size Dim Query Size Data Type
Star Light Curves 823,600 1024 1,000 Time Series
Msong 992,272 420 1,000 Audio
Sift1M 1,000,000 128 10,000 Image
Deep1M 1,000,000 256 1,000 Image
Word2vec 1,000,000 300 1,000 Word Vectors
Hand Outlines 1,000,000 2709 370 Time Series
Glove1.2m 1,193,514 200 1,000 Text
Glove2.2m 2,196,017 300 1,000 Text
SpaceV1B 1,000,000,000 100 10,000 Text
Sift1B 1,000,000,000 128 10,000 Image

数据集选择理由: 这些数据集涵盖了不同的数据类型和维度,从小规模到大规模(例如 SpaceV1B 和 Sift1B 达到 10 亿级别),能够全面评估 Harmony 在各种场景下的性能、可扩展性和对高维数据处理的能力。

5.2. 评估指标

论文主要关注以下评估指标:

5.2.1. 每秒查询数 (Queries Per Second, QPS)

  • 概念定义: QPS 是衡量查询吞吐量(throughput)的指标,表示系统在单位时间内(通常是每秒)能够处理的查询请求数量。QPS 越高,系统处理查询请求的能力越强,表明系统效率越高。
  • 数学公式: QPS=总查询数总查询时间 \text{QPS} = \frac{\text{总查询数}}{\text{总查询时间}}
  • 符号解释:
    • 总查询数\text{总查询数}: 在测试期间系统处理的查询请求的总数量。
    • 总查询时间\text{总查询时间}: 处理所有查询请求所花费的总时间,通常以秒为单位。

5.2.2. 召回率 (Recall)

  • 概念定义: 召回率在 ANNS 中衡量搜索结果的准确性。它表示系统返回的 K 个近似最近邻中,有多少个是真正的 K 个最近邻(即在精确搜索中应返回的结果)。高召回率意味着近似搜索结果与精确搜索结果高度一致。
  • 数学公式: Recall@K=返回的 Top-K 结果真实的 Top-K 结果真实的 Top-K 结果 \text{Recall@K} = \frac{|\text{返回的 Top-K 结果} \cap \text{真实的 Top-K 结果}|}{|\text{真实的 Top-K 结果}|}
  • 符号解释:
    • 返回的 Top-K 结果真实的 Top-K 结果|\text{返回的 Top-K 结果} \cap \text{真实的 Top-K 结果}|: 系统返回的 KK 个近似最近邻中,与精确搜索结果重叠的向量数量。
    • 真实的 Top-K 结果|\text{真实的 Top-K 结果}|: 精确搜索得到的 KK 个最近邻的总数量,通常为 KK

5.2.3. 加速比 (Speedup)

  • 概念定义: 加速比用于衡量分布式系统相对于单机系统或基线系统在性能上的提升倍数。
  • 数学公式: Speedup=基线系统性能指标分布式系统性能指标Speedup=基线系统时间分布式系统时间 \text{Speedup} = \frac{\text{基线系统性能指标}}{\text{分布式系统性能指标}} \quad \text{或} \quad \text{Speedup} = \frac{\text{基线系统时间}}{\text{分布式系统时间}} 在论文中,通常指的是吞吐量或 QPS 的提升倍数。
  • 符号解释:
    • 基线系统性能指标\text{基线系统性能指标}: 单机或基线系统在特定评估指标(如 QPS)上的表现。
    • 分布式系统性能指标\text{分布式系统性能指标}: 分布式系统在相同评估指标上的表现。
    • 基线系统时间\text{基线系统时间}: 基线系统完成相同任务所需的时间。
    • 分布式系统时间\text{分布式系统时间}: 分布式系统完成相同任务所需的时间。

5.2.4. 剪枝率 (Pruning Ratio)

  • 概念定义: 剪枝率衡量在维度级流水线中,由于早期停止机制而跳过的距离计算的比例。高剪枝率意味着系统能够有效地识别并跳过不必要的计算,从而节省计算资源和时间。
  • 数学公式: Pruning Ratio=剪枝的计算量总潜在计算量 \text{Pruning Ratio} = \frac{\text{剪枝的计算量}}{\text{总潜在计算量}}
  • 符号解释:
    • 剪枝的计算量\text{剪枝的计算量}: 被 Harmony 的早期停止机制跳过的距离计算(例如,未完成的维度计算)总量。
    • 总潜在计算量\text{总潜在计算量}: 如果没有剪枝机制,需要执行的总距离计算量。

5.2.5. 索引构建时间 (Index Build Time)

  • 概念定义: 衡量构建 ANNS 索引所需的时间。包括训练聚类中心、添加基础向量和分配索引分片等阶段。
  • 评估目的: 评估系统在数据加载和预处理阶段的效率。

5.2.6. 索引空间开销 (Index Space Overhead) / 峰值内存使用 (Peak Memory Usage)

  • 概念定义: 衡量存储 ANNS 索引所需的内存或磁盘空间。峰值内存使用则特指在查询执行期间系统消耗的最大内存量。
  • 评估目的: 评估系统的存储效率和内存管理能力,尤其是在大规模数据集和高维向量场景下。

5.3. 对比基线

论文将 Harmony 与以下方法进行了比较:

  • Faiss: 作为最先进的单机 ANNS 查询引擎,Faiss 是一个重要的基线,用于衡量分布式方案相对于单机方案的性能提升。为了公平比较,所有方法都采用与 Faiss 相同的聚类算法和聚类数量。
  • Harmony-vector (纯向量分区): 模拟传统的分布式向量数据库的基于向量的分区策略。它将整个向量分配到不同的节点。
  • Harmony-dimension (纯维度分区): 模拟基于维度的分区策略。它将向量的维度空间拆分,每个节点处理一部分维度。
  • Auncel: 一个关注于在低搜索负载下提供误差边界保证的分布式 ANNS 系统。它采用固定分区策略,类似于 Harmony-vector。

6. 实验结果与分析

6.1. 核心结果分析

6.1.1. 均匀工作负载下的 QPS-召回率权衡

本节分析了 Harmony 与 Faiss 在均匀工作负载(uniform workloads)下 QPS 和召回率(recall)之间的权衡。实验在四节点集群上运行 Harmony,而 Faiss 作为单节点基线。对于 SpaceV1B 和 Sift1B 这种超大规模数据集,单节点 Faiss 和四节点 Harmony 均无法处理,因此使用了十六节点 Harmony 进行分布式搜索。

以下是原文 Figure 6 的结果:

Figure 6: Time-accuracy trade-off. 该图像是一个图表,展示了不同数据集(如StarLightCurves、Msong、Sift1M等)上Harmony与其他算法在不同召回率下的查询每秒(QPS)表现。图中可以看到,Harmony在各种召回率上均表现出更高的查询性能。

图 6: 时间-准确性权衡。

主要发现:

  1. 显著的加速比: 所有 Harmony 的三种分布式策略(Harmony、Harmony-vector、Harmony-dimension)都表现出比 Faiss 更高的性能,平均加速比达到 3.75 倍。这证明了分布式方法在处理大规模 ANNS 任务上的优势。
  2. 超线性加速: 在高召回率(高精度)条件下,Harmony 经常超过理论加速比(4 倍),达到了 4.63 倍的加速比。这主要归因于 Harmony 的剪枝(pruning)机制有效降低了计算开销。
  3. Harmony-Vector 在低精度下的优势: 当召回率低于 99% 时,Harmony-Vector 分区策略表现出最佳性能。这是因为在低精度要求下,Harmony-dimension 和 Harmony 引入的额外距离计算开销(例如,为了启用剪枝或维度间通信)对其性能造成了限制。

6.1.2. 偏斜工作负载下的搜索性能

本节在四节点上,对八个相对较小的数据集进行了实验,评估 Harmony 的三种策略在不同负载不平衡程度下的表现。通过操纵查询集来制造机器间不同的负载差异,并使用不平衡因子(Section 4.2.1 中定义)来量化这种不平衡。

以下是原文 Figure 7 的结果:

Figure 7: Impact of load distribution on query performance. 该图像是图表,展示了不同数据集上负载分布对查询性能的影响。图中显示了 Harmony、Harmony-vector 和 Harmony-dimension 三种方法在 StarLightCurves、Msong、Sift1M 等数据集上的平均查询每秒(QPS)随平均方差变化的趋势。

图 7: 负载分布对查询性能的影响。

主要发现:

  1. 传统向量分区的局限性: 传统的 Harmony-vector 分区策略对负载不平衡的适应性很差。随着负载不平衡程度的增加,其平均 QPS 平均下降了 56%。这证实了传统方法在实际偏斜工作负载下的脆弱性。
  2. Harmony 和 Harmony-Dimension 的鲁棒性: HarmonyHarmony-dimension 分区方法在处理不平衡负载时表现更优,在负载偏斜变化期间没有显示出明显的性能下降。
  3. Harmony 的混合方法优势: 尽管纯维度分区(Harmony-dimension)由于其绝对分区原则而更稳定,但 Harmony 的混合方法(自适应地平衡维度和向量分区)仍然更具优势。即使在负载极度不平衡的情况下,Harmony 的性能也比 Harmony-dimension 高出 91%。这突显了 Harmony 成本模型在结合两种分区优势方面的有效性。
  4. 对高维数据和大规模数据的优势: 对于更大规模或更高维度的向量数据集,Harmony 的优势更加明显。随着复杂性和分布偏斜的加剧,Harmony 的自适应策略能够持续利用维度拆分和向量拆分之间的协同效应,从而在不同程度的不平衡下提供稳健的性能。

6.2. 性能消融研究 (Performance Ablation Study)

6.2.1. 时间开销分解

本节分析了查询过程中不同阶段的时间花费,包括数据通信、计算和其他开销。

以下是原文 Figure 8 的结果:

Figure 8: The contribution of the three optimization techniques to Harmony's query throughput. 该图像是一个柱状图,展示了三种优化技术对Harmony查询吞吐量的贡献。图中列出了在Msong和Sift1M数据集上,不同方法通讯及计算所占用的归一化时间百分比。数据清晰地表明,Harmony-dimension方法在通讯和计算时间方面具有显著优势。

图 8: 三种优化技术对 Harmony 查询吞吐量的贡献。

主要发现:

  1. 通信开销:Harmony-vector 外,HarmonyHarmony-dimension 都会产生通信开销。其中,Harmony-dimension 由于维度切片更多,通信开销更高。 Harmony 的通信开销低于 Harmony-dimension,因为 Harmony 采用了较少的维度分区。
  2. 计算开销: 尽管 Harmony-dimensionHarmony-vector 的计算开销相似,但 Harmony 的计算开销最低。这归因于 Harmony 引入的剪枝模块,该模块能够有效减少不必要的计算。
  3. 通信与维度: 所有三种方法的主要开销都集中在通信和计算上。通信开销与维度无关。在维度较大的数据集中,通信开销显著低于计算开销。例如,在 128 维的 Sift1M 数据集中,通信开销明显高于 420 维的 Msong 数据集。

6.2.2. 优化技术的贡献

为了理解 Harmony 中每个组件的贡献,测量了平衡负载、流水线和异步执行、以及剪枝在四节点环境下的加速效果。

以下是原文 Figure 9 的结果:

Figure 9: The contribution of the three optimization techniques to Harmony's query throughput. 该图像是一个图表,展示了三种优化技术对Harmony查询吞吐量的贡献。分别显示了在Msong和Sift1M数据集上,不同优化策略(如平衡负载、流水线和异步执行、剪枝)所带来的吞吐量提升,最高达到3.27和3.21。

图 9: 三种优化技术对 Harmony 查询吞吐量的贡献。

主要发现:

  1. 各项优化技术的贡献: 平均而言,每项优化技术都提供了性能提升。平衡负载带来了 1.75 倍的提升,流水线和异步执行带来了 1.25 倍的提升,剪枝带来了 1.51 倍的吞吐量提升。
  2. 剪枝的显著影响: 性能提升主要来自剪枝,这与 Section 3.1 中的发现一致。这表明剪枝是提高 Harmony 查询吞吐量的一个重要优化技术。
  3. Sift1M 数据集的特殊性: 对于 Sift1M 数据集,平衡负载和流水线执行带来的性能提升不太明显。这可能是因为 Sift1M 的负载分布相对均匀,因此负载均衡和异步执行的效益有所降低。然而,剪枝仍然带来了明显的吞吐量提升,表明其在优化查询性能方面的鲁棒性,无论数据分布如何。

6.2.3. 剪枝率分解

本节评估了 Section 4.3 中讨论的剪枝策略在减少计算开销方面的有效性。实验对维度进行 4 等分,并应用剪枝策略。

以下是原文 Table 3 的结果:

Dataset First Slice (%) Second Slice (%) Third Slice (%) Fourth Slice (%) Average Pruning Ratio (%)
Msong 0.00 43.14 76.06 95.29 53.87
Glove1.2m 0.00 1.54 30.71 86.66 29.73
Word2vec 0.00 24.85 53.77 83.66 40.32
Deep1M 0.00 7.67 66.09 97.36 42.03
Sift1m 0.00 41.76 85.04 98.40 57.05
Star 0.00 81.24 95.23 99.05 69.14
Glove2.2m 0.00 5.14 30.70 81.18 29.76
Hand 0.00 63.54 91.62 98.10 63.83

主要发现:

  1. 后期切片剪枝率更高: 后期切片(later slices)展现出更好的剪枝率。第二切片的平均剪枝率为 33.61%,第三切片为 66.15%,第四切片为 92.33%。这是因为后续的查询切片受益于早期切片的结果累积,从而能够获得更严格的剪枝阈值。
  2. 数据集差异: 不同数据集的剪枝率差异显著。例如,Glove1.2M 数据集的第三切片剪枝率仅为 30.71%,而 Star 数据集则高达 95.23%。这主要归因于数据集分布的差异,某些数据集更容易被剪枝。
  3. 最终切片的极高剪枝率: 最终切片(fourth slice)的剪枝率始终超过 80%,表明绝大多数距离计算不需要使用最后一个维度。这与 Section 3.1 中的分析一致,突显了在到达最终切片时,大部分向量已被剪枝。

6.3. 索引构建实验

6.3.1. 索引构建时间

本节测量了使用 Harmony 和 Faiss 构建索引的时间和空间开销。首先关注时间开销,比较了 Harmony-vector(Vector)、Harmony-dimension(Dimension)在四节点环境下的索引构建时间,以及 Harmony 和 Faiss 在单机环境下的索引构建时间。索引构建分为三个阶段:训练聚类中心(Train)、将基础向量添加到聚类中心(Add)、以及将索引部分分配给不同机器的分布式特定操作(Pre-assign)。

以下是原文 Figure 10 的结果:

Figure 10: Harmony's index build time breakdown. 该图像是一个图表,展示了不同数据集上 Harmony 与其他方法在索引构建时的时间消耗。图中包含了训练时间、添加时间和预分配时间的比较,分别用不同颜色表示。通过对比可以看出,Harmony 方法在大多数情况下表现出较低的时间成本。

图 10: Harmony 的索引构建时间分解。

主要发现:

  1. Train 和 Add 阶段相似: 所有方法的训练(Train)和添加(Add)时间相似,这表明 Harmony 不需要修改索引结构,并且具有良好的可扩展性。
  2. Pre-assign 时间: Harmony-dimensionHarmony 的预分配(Pre-assign)时间比 Harmony-vector 长。这是因为这两种分布式方法需要先分配空间并初始化与距离计算相关的中间结果,这需要一定时间,并取决于数据大小。例如,Glove2.2m 数据集上的时间大约是 Glove1.2m 的两倍。
  3. 与维度成比例: 对于相同大小的数据集,训练和添加时间通常与数据集的维度成比例。这是因为训练和分布都与维度呈线性关系。

6.3.2. 索引空间开销

本节比较了 Harmony 的索引与 Faiss 和基线配置的索引空间开销。

以下是原文 Table 4 的结果:

Dataset Faiss Harmony vector Harmony dimension Harmony
StarLightCurves 3.2GB 788MB 815MB 798MB
Msong 1.6GB 411MB 418MB 413MB
Sift1M 497MB 126MB 131MB 128MB
Deep1M 986MB 245MB 253MB 250MB
Word2Vec 1.2GB 258MB 295MB 279MB
HandOutlines 6.1GB 1.50GB 1.54GB 1.51GB
Glove1.2M 921MB 227MB 238MB 233MB
Glove2.2M 2.5GB 660MB 697MB 686MB

主要发现:

  1. 与数据集规模和维度成比例: 索引开销与数据集大小和维度成比例。例如,Msong 使用的空间是 Sift1M 的 3.2 倍,这与其(维度 ×\times 数据集大小)的乘积一致。
  2. 分布式索引的效率: 所有三种分区方案(Harmony-vectorHarmony-dimensionHarmony)占用的空间大约是 Faiss(单机索引)的 1/4。这表明分布式索引不需要显著的额外空间开销。
  3. Harmony 额外开销小: HarmonyHarmony-dimension 会产生一些额外的空间开销,但这种开销非常小,仅占原始空间大小的约 2%。

6.4. 附加讨论

6.4.1. 维度和数据集大小对 Harmony 性能的影响

本节构建了遵循高斯分布的数据集,维度范围从 64 到 512,大小从 250K 到 1M,并在四节点上进行实验。

以下是原文 Figure 11 (a) 的结果:

Figure 11: Impact of pruning effectiveness and indexing parameters on search performance 该图像是图表,展示了修剪有效性与索引参数对搜索性能的影响。左侧为修剪比率与搜索探测数之间的关系,右侧展示了不同参数下的 subNN 索引结果,在多个工作节点之间的加速比。

图 11 (a): 剪枝效果和索引参数对搜索性能的影响。

主要发现:

  1. 随维度和数据集增大而性能提升: 随着数据集大小和维度同时增加,Harmony 的性能也随之提升。具体来说,维度每增加一倍,加速比增加 26.8%;数据集大小每增加一倍,加速比增加 25.9%。
  2. 超线性加速: 在大型数据集(1M,512 维)中,Harmony 显示的加速比超过了机器数量。这归因于剪枝技术,它减少了计算开销。
  3. 小数据集的性能瓶颈: 对于较小的数据集,Harmony 的性能表现不佳,这归因于通信开销在这些情况下占据了主导地位。

6.4.2. 可扩展性

为了验证 Harmony 的可扩展性,在 4、8 和 16 节点的不同机器配置下进行了实验。

以下是原文 Figure 11 (b) 的结果:

Figure 11: Impact of pruning effectiveness and indexing parameters on search performance 该图像是图表,展示了修剪有效性与索引参数对搜索性能的影响。左侧为修剪比率与搜索探测数之间的关系,右侧展示了不同参数下的 subNN 索引结果,在多个工作节点之间的加速比。

图 11 (b): 剪枝效果和索引参数对搜索性能的影响。

主要发现:

  1. 基于组的分区(Harmony)的超线性加速: Harmony(group-based partitioning)方法始终展现出高于机器数量的加速比,这是由于剪枝设计有效减少了计算开销。
  2. 基于向量的分区(Harmony-vector)线性扩展: Harmony-vector 的性能接近于工作节点数量,因为它没有引入额外开销,并且与工作节点数量呈线性扩展。
  3. 基于维度的分区(Harmony-dimension)的局限性: Harmony-dimension 方法的性能随着工作节点数量的增加先提升后下降。这是因为随着维度数量的增加,通信开销也随之增加,最终抵消了整体性能增益。

6.4.3. 峰值内存使用

本节评估了 Harmony 在查询执行期间的峰值内存消耗,并与基线分区方法在 4 节点上进行比较。

以下是原文 Table 5 的结果:

Dataset Harmony-vector Harmony Harmony-dimension
StarLightCurves 3.94GB 4.01GB 4.07GB
Msong 1.15GB 1.32GB 1.46GB
Sift1M 1.37GB 1.72GB 1.96GB
Deep1M 1.23GB 1.61GB 1.88GB
Word2Vec 658MB 723MB 812MB
HandOutlines 11.06GB 11.19GB 11.33GB
Glove1.2M 814MB 932MB 1.06GB
Glove2.2M 1.64GB 1.98GB 2.23GB

主要发现:

  1. 与数据维度和大小成比例: 三种分区方法的峰值内存使用量通常与数据维度和数据集大小成比例。
  2. Harmony 内存增量随维度增加而减小: HarmonyHarmony-dimension 的峰值内存消耗略高于 Harmony-vector,但这种增加随着数据维度的增长而减小。例如,在 100 维的 Deep1M 数据集中,HarmonyHarmony-vector 多出 30.9%,而在 2709 维的 HandOutlines 数据集中,增幅降至 1.17%。这表明所有涉及维度分区的方案都需要额外的与数据维度无关的中间结果,但随着维度增加,这些结果的影响被稀释,展示了 Harmony 在处理高维数据方面的潜力。
  3. 内存增量与维度切片数相关: 内存使用量的增加与维度切片的数量有关。例如,Harmony 的内存消耗增幅小于 Harmony-dimension,因为它不是完全基于维度进行分区。

6.4.4. 与 Auncel 的比较

Auncel 专注于在特定精度要求下处理低搜索负载的分布式向量查询,其分区策略类似于 Harmony-vector,在负载不平衡时性能不佳。

相比之下,Harmony 通过剪枝技术和细粒度负载均衡来应对偏斜工作负载,更好地处理不均匀的查询分布。虽然两者在分区方法上相似,但在负载不平衡场景下,Harmony 通过利用剪枝机会来保持吞吐量和稳定性,表现优于 Auncel。

7. 总结与思考

7.1. 结论总结

Harmony 提出了一种可扩展的分布式向量数据库,用于高吞吐量近似最近邻搜索(ANNS)。通过引入新颖的多粒度分区策略(结合了基于维度和基于向量的分区)以及利用维度计算单调性的早期停止剪枝机制,Harmony 有效解决了现有分布式 ANNS 系统中负载不平衡和高通信开销的挑战。实验结果表明,Harmony 在各种真实世界数据集上,无论是均匀负载还是偏斜负载,均显著优于最先进的分布式向量数据库。它在四节点配置下实现了平均 4.63 倍的吞吐量提升,并在偏斜工作负载下实现了 58% 的性能提升。其关键创新在于自适应的分区策略、高效的负载均衡、以及在分布式环境中利用维度级剪枝来减少不必要的计算和通信。

7.2. 局限性与未来工作

论文虽然展示了 Harmony 的显著优势,但也隐含了一些潜在的局限性和可以探索的未来方向:

  1. 成本模型的动态适应性: 论文提到成本模型指导动态分区,但其动态性是如何实现的?在查询负载快速变化时,成本模型能否实时、低开销地进行重新评估和调整?这对于高动态环境中的系统稳定性至关重要。
  2. 高维度通信开销: 尽管论文声称通信开销与维度无关,但在实际系统中,维度切片数量的增加仍可能引入更多的网络往返(round trips)和序列化/反序列化开销,尤其是在网络带宽受限或延迟较高的情况下。
  3. 剪枝的普适性: 剪枝效果高度依赖于数据集的分布特性。对于某些难以剪枝的数据集(如 Glove1.2M 所示),Harmony 的优势可能会减弱。未来工作可以探索更通用的剪枝策略,或者结合其他技术来弥补剪枝效果不佳的情况。
  4. 索引更新和维护: 论文主要关注查询性能和索引构建。在大规模分布式系统中,向量数据的动态更新(插入、删除、修改)是一个重要的考虑因素。Harmony 如何高效地处理索引更新,同时保持其性能和负载均衡优势,是一个值得研究的方向。
  5. 与其他 ANN 索引的兼容性: Harmony 目前基于聚类索引进行优化。未来可以探索其多粒度分区和剪枝机制如何与基于图的 ANN 索引(如 HNSW)或更先进的混合索引结构结合,以实现更广泛的适用性。
  6. 错误边界与召回率控制: 论文主要关注高召回率下的性能。虽然提到了 Auncel 的错误边界保证,但 Harmony 自身在提供明确的召回率或错误边界控制方面未详细阐述。未来可以考虑在保持高性能的同时,提供更精细的召回率或精度控制机制。

7.3. 个人启发与批判

个人启发:

  1. 混合式设计思维: Harmony 的成功在于打破了单一分区策略的局限,通过将基于向量和基于维度的分区进行混合,并辅以智能决策,实现了“扬长避短”。这提醒我们在系统设计中,面对复杂问题时,不应拘泥于单一范式,而应思考如何结合多种方法的优势。
  2. 利用数据特性进行优化: 维度级剪枝是利用了距离计算的单调性这一基本数学特性。这种深入挖掘数据和算法固有属性,并将其转化为系统级优化点的思路非常值得借鉴。
  3. 成本模型的重要性: 一个有效的成本模型是自适应系统成功的关键。它将复杂的系统行为量化,为运行时决策提供了依据,使得系统能够智能地响应环境变化。
  4. 流水线与异步的价值: 通过流水线处理和异步通信,Harmony 有效地隐藏了通信延迟,实现了计算和通信的重叠,这是分布式系统性能优化的通用且强大的手段。

批判:

  1. 成本模型的具体实现细节: 论文对成本模型的描述较为抽象,如 ccompdim(b,q)c_{\mathrm{comp}}^{\dim}(b, q)ccommdim(b,q)c_{\mathrm{comm}}^{\dim}(b, q) 等具体如何精确估计,以及 α\alpha 参数的选取策略,缺乏详细说明。这些细节对于理解其在真实世界中的实用性和鲁棒性至关重要。
  2. “维度无关”的通信开销: 论文声称总通信开销与纯向量分区方案相同,因为传输的数据总量不变,只是拆分成了更小的块。然而,实际的分布式系统通信开销不仅仅取决于数据量,还包括连接建立、消息头开销、网络拥塞、以及更多的网络往返造成的延迟。维度切分越多,消息数量越多,这些额外的开销可能会累积,尤其是在高延迟网络或高并发查询场景下,可能成为新的瓶颈。论文的实验似乎在高性能网络环境下进行,这可能掩盖了这方面的潜在问题。
  3. 负载均衡的动态调整开销: 动态调整维度的执行顺序以实现负载均衡虽然有效,但这种调整本身的开销如何?是否会引入额外的协调和调度复杂性,尤其是在大规模集群和高吞吐量下,这种动态调整的频率和粒度如何权衡?
  4. 内存占用与维度: 尽管论文指出随着维度增加,Harmony 相对于 Harmony-vector 的内存增量百分比会减少,但绝对内存占用仍然会增加。对于超高维向量(例如几千甚至上万维),即使是小的百分比增量也可能导致巨大的内存需求,这可能限制其在特定硬件条件下的应用。
  5. 与误差边界的结合: 论文在与 Auncel 比较时指出其在负载不平衡下的优势,但 Auncel 强调了误差边界。如果 Harmony 也能在保持高性能的同时提供严格的误差边界保证,将使其在需要高可靠性 ANNS 的应用中更具竞争力。

相似论文推荐

基于向量语义检索推荐的相关论文。

暂时没有找到相似论文。