Hotdry.
归档
ai-systems

PostgreSQL大规模向量索引的内存优化策略与分片算法

分析在12GB内存限制下，如何通过分层K-means、降维技术与树形分片算法，实现100M向量在20分钟内完成索引构建的工程实践。

随着大语言模型和向量嵌入技术的普及，向量相似性搜索已成为现代 AI 应用的基础设施。然而，当数据规模达到亿级时，传统向量索引面临严峻的内存和时间挑战。以 pgvector 为例，索引 100M 个 768 维向量需要约 200GB 内存和 40 小时，这在实际生产环境中几乎不可行。

近期，VectorChord 团队通过一系列创新优化，在 16 vCPU 机器上仅用 12GB 内存，在 20 分钟内完成了同等规模向量的索引构建。这一突破性进展不仅将内存需求降低了 7 倍，还将构建时间缩短了 120 倍。本文将深入分析其背后的内存优化策略与分片算法设计，为工程实践提供可落地的参数指导。

内存优化策略：从 135GB 到 12GB 的突破

分层 K-means 算法：时间复杂度的大幅降低

传统的 K-means 聚类算法在处理大规模向量时面临双重挑战：时间复杂度和内存占用。设 n 为向量数量，c 为质心数量，d 为向量维度，l 为迭代次数，传统 K-means 的时间复杂度为 O (ncdl)，空间复杂度为 O (nd + cd)。

VectorChord 采用的分层 K-means 算法通过巧妙的分治策略解决了这一问题。算法首先将样本向量划分为√c 个不相交子集，在每个子集上独立运行 K-means，最后合并所有子集的质心。这一改变将时间复杂度从 O (fc²dl) 降低到 O (√f c¹・⁵ dl)，其中 f 为采样因子。

当 f=64 且 c=160,000 时，算法速度提升了约 3,200 倍。更重要的是，这种分层处理方式天然适合并行计算，能够在多核 CPU 上高效运行，无需依赖 GPU 加速。

降维技术：Johnson-Lindenstrauss 变换的应用

内存占用的另一个关键因素是向量维度。768 维的浮点向量每个需要 3KB 存储，100M 个向量仅原始数据就需要 300GB 内存。VectorChord 采用 Johnson-Lindenstrauss 变换将维度从 768 降到 100。

Johnson-Lindenstrauss 引理保证，高维空间中的点集可以通过随机正交投影嵌入到低维空间，同时保持点间距离的近似关系。具体实现中，团队构造随机高斯矩阵，通过矩阵乘法将高维向量降维到低维空间进行聚类。

这一优化带来了双重收益：内存占用从 135GB 降至 23GB，同时聚类速度理论上提升了 7 倍。降维后的质心通过二次采样恢复高维表示，精度损失控制在可接受范围内。

采样因子优化：平衡精度与效率

采样因子 f 决定了用于聚类的样本数量与质心数量的比例。通过将 f 从默认值降低到 64，VectorChord 进一步将内存占用从 23GB 降至 6GB，同时使聚类速度提升约 2 倍。

这一优化基于一个重要观察：对于大规模数据集，适度的采样率仍能保持聚类质量。在实际测试中，即使采样因子降低，索引的召回率仅从 95.6% 轻微下降到 94.9%，这一精度损失在大多数应用场景中是可接受的。

树形索引结构与分片算法设计

vchordrq 索引：高度可配置的树形结构

VectorChord 的核心索引类型 vchordrq 是一个高度为 n+1 的树形结构。前 n 层构成不可变的路由结构，专门用于搜索时的快速导航；第 (n+1) 层存储所有数据向量。

这种设计具有灵活的配置性：

  • 当 n=1 时，索引是扁平的、非分区结构
  • 当 n=2 时，索引成为标准的倒排文件索引
  • 当 n=3 时，增加额外的路由层级，适合超大规模数据集

通过增加树的高度 n，索引构建过程被分解为三个清晰阶段：初始化、插入和压缩。每个阶段可以独立优化，特别是插入阶段的计算量随着 n 的增加而显著减少。

分片算法的工程实现

在实际工程中，分片算法的有效性取决于其与 PostgreSQL 存储模型的契合度。VectorChord 的索引构建过程精心设计了以下分片策略：

  1. 智能采样：避免全表扫描，利用 PostgreSQL 的表访问方法采样接口，通过 Feistel 网络实现伪随机排列，仅访问采样块中的向量。

  2. 渐进式构建：索引构建分为三个阶段，允许资源按需分配。初始化阶段构建路由结构，插入阶段填充数据，压缩阶段优化存储布局。

  3. 内存分级管理：树节点仅存储量化后的向量（占用空间小），完整精度向量存储在单独的链表中。这种分离设计使得路由结构能够完全驻留内存，而大数据量存储在磁盘上。

并发优化与争用消除

链表争用的解决方案

在早期版本中，插入阶段存在严重的链表争用问题。所有工作线程共享单个链表来存储完整精度向量，导致随着线程数增加，性能反而下降。

解决方案是采用 1+k 个链表的设计：第一个链表存储前 n 层树的完整精度向量，其余 k 个链表（默认 k=32）存储底层数据。第 i 个工作线程将向量插入到第 (i mod k) 个链表中，彻底消除了争用。

这一改变使 CPU 利用率从 40% 稳定提升到 54%，插入时间从 40-60 分钟降至 30 分钟。

页面扩展锁的优化

性能分析发现，PostgreSQL 的LockRelationForExtension锁成为瓶颈。在 PostgreSQL 16 之前，这个锁的粒度过于粗糙，导致大量线程等待。

VectorChord 利用 PostgreSQL 16 引入的新 API，缩小了关键区段。此外，通过一次性请求 16 页的扩展（而非单页），系统自动切换到fallocate系统调用，显著提升了页面扩展速度。

这些优化使插入时间进一步从 22 分钟降至 9 分钟，CPU 利用率稳定在 90%，写入吞吐量达到 1.8GB/s。

并行化压缩阶段

索引的底层使用两种布局：插入导向的非紧凑布局和搜索导向的紧凑布局。压缩阶段负责将前者转换为后者。

通过并行化这一过程，将工作分配给多个 worker，压缩时间从 8 分钟降至 1 分钟以下。每个 worker 负责处理特定节点的子节点，实现了负载均衡。

可落地参数与配置清单

基于上述分析，以下是一套经过验证的配置参数，适用于在有限内存环境下构建大规模向量索引：

CREATE INDEX ON laion USING vchordrq (embedding vector_ip_ops) WITH (options = $$
build.pin = 2
[build.internal]
lists = [400, 160000]
build_threads = 16
spherical_centroids = true
kmeans_algorithm.hierarchical = {}
kmeans_dimension = 100
sampling_factor = 64
$$);

关键参数说明：

  1. build_threads = 16：匹配 16 vCPU 的硬件配置，充分利用多核并行
  2. kmeans_dimension = 100：将 768 维降至 100 维，平衡内存与精度
  3. sampling_factor = 64：降低采样率，减少内存占用
  4. lists = [400, 160000]：定义倒排列表结构，支持高效检索
  5. kmeans_algorithm.hierarchical = {}：启用分层 K-means 算法

硬件配置建议：

  • 推荐配置：Amazon i7i.4xlarge（16 vCPU，128GB 内存）
  • 内存使用：约 12GB（索引构建期间）
  • 构建时间：18-20 分钟（100M 768 维向量）
  • 查询性能：120 QPS，top-10 召回率 94.9%

监控与调优要点：

  1. 内存监控：关注 RSS（Resident Set Size），确保不超过可用内存的 80%
  2. I/O 吞吐量：目标写入吞吐量 1.5-2.0GB/s，表明系统瓶颈不在 I/O
  3. CPU 利用率：稳定在 85-95% 为理想状态，过低可能表示争用，过高可能表示计算瓶颈
  4. 锁等待时间：使用pg_stat_activity监控锁等待，及时发现争用点

局限性与未来方向

当前方案的主要局限性包括：

  1. 精度轻微损失：召回率从 95.6% 降至 94.9%，对于某些高精度要求的场景可能需要权衡
  2. PostgreSQL 版本依赖：部分优化需要 PostgreSQL 16+，限制了在旧版本上的部署
  3. 真空维护限制：压缩阶段在真空过程中无法并行化，因为 PostgreSQL 不允许嵌套并行

未来可能的改进方向包括：

  • 自适应维度选择：根据数据集特性动态调整降维程度
  • 增量索引构建：支持在不重建整个索引的情况下添加新数据
  • 混合精度存储：对热点数据使用高精度，冷数据使用低精度

结语

PostgreSQL 上的大规模向量索引优化是一个系统工程问题，需要在算法创新、系统理解和工程实践之间找到平衡点。通过分层 K-means、降维技术和智能分片算法的结合，VectorChord 展示了在有限内存环境下处理亿级向量索引的可行性。

这一成果的意义不仅在于性能数字的提升，更在于它降低了向量搜索的门槛，使得更多团队能够在常规硬件上部署大规模 AI 应用。随着向量数据库技术的成熟，我们有理由相信，高效、经济的向量搜索将成为 AI 基础设施的标准组成部分。

资料来源：

  1. VectorChord 博客文章《How We Made 100M Vector Indexing in 20 Minutes Possible on PostgreSQL》
  2. Johnson-Lindenstrauss 引理相关理论研究
  3. PostgreSQL 官方文档关于索引扩展锁的优化讨论
查看归档