「腾讯云 NoSQL」技术之向量数据库篇: 索引六边形战士 IVF-RabitQ 如何实现集性能、成本、召回于一身

腾讯云NoSQL技术

发布于 2025-12-24 15:44:56

1750

导语：向量数据库，堪称支撑推荐系统、图像识别及大模型检索增强生成（RAG）等 AI应用的核心基石。然而，当业务数据规模从百万级跃升至百亿甚至千亿时，如何在海量数据下平衡检索性能、召回精度与硬件成本，直接决定了 AI应用的商业价值与可行性。传统的 HNSW 索引虽性能优越但内存成本高昂，限制了其在超大规模场景的应用；而 IVF系列索引在降低成本时，又常以牺牲性能和召回率为代价。RabitQ 的出现，正是为了解决这一业界难题。本文将深入剖析 RabitQ 算法从单 bit 到多 bit 版本的演进脉络与数学理论，并结合腾讯云 NoSQL团队向量数据库（VDB）的工程实践，揭示其在并发读写、内存管理等方面的优化方案，为读者完整展示下一代向量索引技术如何兼得性能、成本与召回率。本文作者：腾讯云NoSQL团队：何华均、霄文韬、章俊&PCG大数据部：周建国、白嗣东

RabitQ之前向量索引面临的现实问题

自从2017年Faiss库和HNSWlib开源后，向量索引近些年经过演进后，主要以HNSW图搜、IVF聚簇索引两大方向为主要演进路线。在RabitQ算法出来之前，在索引面临实际业务场景落地的时候，始终会面临一些客观问题：

HNSW图搜-性能好但成本高

HNSW索引以Search性能佳的特点在很多业务场景中作为向量索引盲选目标，但随着数据规模的增加，HNSW图搜默认放在机器中有限的内存资源上运行，所以硬件成本会随着数据规模的增加而线性增加。

例如在100万1024d的向量，在不量化的前提下数据本身会占用4GB内存空间，而HNSW的边也会占用内存空间，所以实际会占用5-6GB，这个成本并不昂贵，但当数据规模达到100亿其内存资源将是现在的1万倍，值得注意的是这些资源并非用于计算，而是用于存储数据。而相对来讲，传统数据库的100亿数据属于家常便饭，成本相对来讲要低数百倍。

HNSW量化在一定程度上可节约成本，通常可以使用FP16、BF16、int8三种方式，其中FP16、BF16的方式在Tencent VDB上已工程落地，int8量化虽然可以进一步降低内存使用，但我们在多组数据集验证后，其召回率会有明显下降，因此VDB暂时未考虑基于int8量化进行工程落地。

即使不考虑召回率，通过int8量化后的图索引，也只会减少4倍的空间，对于10亿、100亿乃至更大数据规模时，资源的成本依然是一个非常头痛的问题，我们需要更大的量化比，同时又希望召回率达到很高的标准。

IVF-SQ/PQ量化-数倍降低成本但性能差且召回不可控

IVF-SQ/PQ的量化等级可以做到更高，例如IVF-PQ的量化可以达到无限大，另外IVF索引在内存中并没有存放边，其额外内存较少且可控。同时IVF索引相对于FLAT暴搜，会提前将范围缩小到nprobe个聚簇中，这样相对于FLAT来讲性能通常有10倍以上的提升，所以在RabitQ正式推出前，其作为诸多业务选择百亿级规模向量存储方案之一，但是IVF同样会面临2大问题：

性能差： 相对于HNSW图搜索引的新能要低1个数量级（虽然相对FLAT会更好）。 召回率不可控： SQ和PQ的量化方式，无法从数学上证明其精度损失的范围，更多需要基于数据特征做特定的选择和细节优化来提升召回率。

关于HNSW和IVF系列的索引问题不局限于上述提到的点（例如IVF的预训练和聚簇倾斜问题），但由于本文主要聚焦召回/成本/性能，在此不再继续展开。

RabitQ改变现状的方式

随着AI应用的爆发，业界对向量数据库的应用场景、规模上提出越来越高的要求，各向量服务厂商、开源组织一直通过各种方式在召回、性能、成本上下功夫，一直很难找到完美的解法，例如：DiskANN是一种磁盘方案来降低成本，但其性能表现欠佳。大家一直期待有一种相对完美的索引来解决这样的问题，RabitQ的诞生让我们对这块找到了希望。

很感谢南洋理工大学提供了一种RabitQ算法，其在性能（时间）、空间（成本）、召回上把向量索引带入一个新的理论阶段。在整个向量领域，作者第一个通过数学理论证明了经过RabitQ量化后的索引，其召回误差可以控制在一个公式内“距离无偏估计器”（与原始数据的特点关系不大），而经过实际的工程实践也符合作者推导的数学公式，RabitQ最高可以做到32倍的量化，同时其性能也超越HNSW。那么接下来就RabitQ理论和实践细节将展开介绍。

RabitQ的数学理论

Rabit在2024年作者推出了单bit版本，其量化等级固定32倍，虽然可通过“距离无偏估计器”进行误差估算，但单bit的量化依然会有明显的召回率下降，所以需要通过原始数据二次精排来提升召回，但这就导致了其性能的下降。而在今年（2025年）作者推出了多bit版本，可以通过调整bit数来提升召回，实践证明通常5-7bit的量化就可以达到99的召回率，同时作者对查询性能上进行了大量的优化。

目前外部同行所推出的RabitQ版本是基于单bit版本，我们会先介绍单bit理论基础。TencentVDB很有幸第一个在多bit版本上进行工程落地和实践，并已正式在V2.7版正式对外服务，所以我们会进一步介绍多bit的理论，以及在TencentVDB上的工程实践。

1-bit RaBitQ

公式衍变

以欧式距离为基础，RaBitQ衍生出了仅依赖内积计算的理论。首先归一化原始向量

oro_r

和原始查询向量

qrq_r

，即

o=or−c∣∣or−c∣∣o = \frac{o_r -c }{||o_r -c||}

q=qr−c∣∣qr−c∣∣q = \frac{q_r -c }{||q_r -c||}

，其中

为簇心向量.

维向量的欧式距离公式计算衍生如下（三角函数）：

\end{aligned}

其中，

∣∣(or−c)∣∣||(o_r -c)||

表示簇中原始向量到簇心的距离，可通过预计算提前保存下来；

∣∣(qr−c)∣∣||(q_r - c)||

为查询向量到簇心的距离，仅需计算一次。因此，公式中仅内积

⟨q,o⟩\langle q,o \rangle

不可提前计算。

码表构建

码本空间：假设归一化后的D维向量数据均匀地分布在单位超球面上，通过直觉，码本也应该均匀地分布在单位超球面上。为此，码本的天然构造如下：

C:={+1D,−1D}D.C:= {\{+\frac{1}{\sqrt{D}},-\frac{1}{\sqrt{D}}\}}^D.

即当

x∈Cx \in C

, 则

是由

{+1D,−1D}{{\{+\frac{1}{\sqrt{D}},-\frac{1}{\sqrt{D}}\}}}

组成的

维向量。为了使得向量分布更加均匀，使得量化结果更好。RaBitQ通过Johnson-Lindenstrauss转换，利用随机正交矩阵

使得码本更加分散和随机，定义如下：

Crand:={Px∣x∈C}.C_{rand}:=\{Px|x \in C\}.

计算量化码：量化的目标是从码本空间中找到一条与数据向量距离最小的向量

PxPx

作为其量化向量，即,给定一条归一化后的数据向量

，量化目标为：

\end{aligned}.

因此,

的量化向量为

o‾=Px‾\overline{o} = P\overline{x}

。令

x‾=2x‾b−1DD.\overline{x} = \frac{2\overline{x}_b - \bold{1}_D}{\sqrt{D}}.

其中

x‾[i]∈{0,1}\overline{x}[i] \in \{0, 1\}

，当

x‾b[i]=1\overline{x}_b[i]=1

时，

x‾[i]=1D\overline{x}[i] = \frac{1}{ \sqrt{D}}

；当

x‾b[i]=0\overline{x}_b[i]=0

时，

x‾[i]=−1D\overline{x}[i] = \frac{-1 }{\sqrt{D}}

。因此，

的量化码为

x‾b\overline{x}_b

，其中每一维的量化码都可仅用1bit表示。

误差分析

RaBitQ的无偏差估计是其核心贡献之一。通过理论分析，内积

⟨o,q⟩\langle o, q \rangle

可近似表示为，如下形式：

⟨o,q⟩≈⟨o‾,q⟩⟨o‾,o⟩.\langle o, q \rangle \approx \frac{\langle \overline{o}, q \rangle}{\langle \overline{o}, o \rangle}.

因此

E(⟨o‾,q⟩⟨o‾,o⟩)=⟨o,q⟩\mathbb{E}(\frac{\langle \overline{o}, q \rangle}{\langle \overline{o}, o \rangle}) = \langle o, q \rangle

。进而，通过下面的公式来评估误差:

P{∣⟨o‾,q⟩⟨o‾,o⟩∣−⟨o,q⟩>1−⟨o‾,o⟩⟨o‾,o⟩2⋅ϵ0D−1}≤2e−c0ϵ02.\mathbb{P}{\{|\frac{\langle \overline{o}, q \rangle}{\langle \overline{o}, o \rangle}| - \langle o, q \rangle > \sqrt{\frac{1- \langle \overline{o}, o \rangle}{\langle \overline{o}, o \rangle ^2}} \cdot \frac{\epsilon_0}{\sqrt{D-1}}\} \le 2e^{-c_0\epsilon_0^2}}.

其中，

ϵ0\epsilon_0

是可变参数，控制误差范围；

c0c_0

是常数项。因此，在置信度为

1−2e−c0ϵ021-2e^{-c_0\epsilon_0^2}

时，区间为

⟨o‾,q⟩⟨o‾,o⟩+−1−⟨o‾,o⟩⟨o‾,o⟩2⋅ϵ0D−1.\frac{\langle \overline{o}, q \rangle}{\langle \overline{o}, o \rangle} \substack{+ \\ -}\sqrt{\frac{1- \langle \overline{o}, o \rangle}{\langle \overline{o}, o \rangle ^2}} \cdot \frac{\epsilon_0}{\sqrt{D-1}}.

误差有很大的概率在

1D\frac{1}{\sqrt{D}}

附近。该理论推导涉及较多的数学证明，感兴趣的同学可以查看论文原文。

内积计算

回到

⟨o‾,q⟩⟨o‾,o⟩\frac{\langle \overline{o}, q \rangle}{\langle \overline{o}, o \rangle}

的计算上。其中

⟨o‾,o⟩\langle \overline{o}, o \rangle

可预计算。因此，仅需要计算归一化后的查询向量

与量化向量

o‾\overline{o}

的内积

⟨o‾,q⟩\langle \overline{o}, q \rangle

即可。

⟨o‾,q⟩=⟨Px‾,q⟩=⟨P−1Px‾,P−1q⟩=⟨x‾,q′⟩.\langle \overline{o}, q \rangle = \langle P\overline{x}, q \rangle = \langle P^{-1}P\overline{x}, P^{-1}q \rangle = \langle \overline{x}, q'\rangle.

其中，

q′=P−1qq' = P^{-1}q

查询向量

q′q'

的量化过程：基于前面的介绍,可知

x‾\overline{x}

每个维度的值都为

+−1D\substack{+ \\ -} \frac{1}{\sqrt{D}}

，其符号由量化码

x‾b\overline{x}_b

决定。进一步地，采用标量量化SQ的思想，将查询向量

q′q'

的每个维度值量化为

BqBq

个比特表示的整数，令

vl:=min1≤iD q′[i]v_l:=\underset{1 \le i \\ D}{\text{min}}~ q'[i]

，

vr:=max1≤iD q′[i]v_r:=\underset{1 \le i \\ D}{\text{max}}~ q'[i]

Δ:=(vr−vl)/(2Bq−1)\Delta:= (v_r- v_l) / (2^{Bq} -1)

，则标量量化为:

q‾u[i]=⌊q′[i]−vlΔ+ui⌋.\overline{q}_{u}[i] = \lfloor \frac{q'[i] - v_l}{\Delta} + u_i\rfloor.

其中

uiu_i

是从均分分布的

[0,1][0,1]

区间中采样得到，

q‾u[i]∈{0,1,...,2Bq−1}\overline{q}_{u}[i] \in\{ 0, 1, ..., 2^{Bq} - 1\}

。因此，

q′q'

的量化向量

q‾\overline{q}

为

q‾=Δq‾u+vl⋅1D.\overline{q} = \Delta \overline{q}_u + v_l\cdot \bold{1}_D.

计算量化向量内积: 将内积计算转

x‾b\overline{x}_b

和

q‾u\overline{q}_u

的内积

\end{aligned}

其中，

∑i=1Dx‾b[i]\sum\limits_{i=1}^D \overline{x}_b[i]

和

D⋅vl\sqrt{D}\cdot v_l

可预计算保存下来，

∑i=1Dq‾u[i]\sum\limits_{i=1}^D \overline{q}_u[i]

查询全流程中仅需计算一次。因此，剩下的任务仅为计算

⟨x‾b,q‾u⟩\langle \overline{x}_b, \overline{q}_u \rangle

，其中，

x‾b\overline{x}_b

由0和1组成，

q‾u\overline{q}_u

由

BqBq

-bits的整数组成。

快速计算

⟨x‾b,q‾u⟩\langle \overline{x}_b, \overline{q}_u \rangle

基于PQ的思路，可通过两种方案快速计算量化码的内积。 1. 单向量计算方案： 基于二进制“与”运算（bitwise-AND）和popcount（数1）运算。此方案适用于单个数据向量的距离估计，核心思想是将整数内积分解为二进制位操作，利用现代CPU的位指令（如AND和popcount）实现高效计算。原理

位分解：将查询向量的量化代码

q‾u\overline{q}_u

的每个维度，分解为

BqBq

个二进制位，即:

q‾u[i]=∑j=0Bq−12j⋅q‾u(j)[i].\overline{q}_u[i] = \sum_{j=0}^{Bq-1} 2^j\cdot \overline{q}^{(j)}_u[i].

其中，

q‾u(j)[i]∈{0,1}\overline{q}^{(j)}_u[i]\in \{0, 1\}

表示

q‾u[i]\overline{q}_u[i]

的第

位，如

Bq=4,q‾u[i]=5(0101)Bq =4, \overline{q}_u[i] = 5 (0101)

,则

q‾u(0)[i]=1,q‾u(1)[i]=0,q‾u(2)[i]=1,q‾u(3)[i]=0\overline{q}^{(0)}_u[i]=1,\overline{q}^{(1)}_u[i]=0,\overline{q}^{(2)}_u[i]=1,\overline{q}^{(3)}_u[i]=0

。

内积分解：将内积分解为二进制运算

\end{aligned}

其中，

⟨x‾b,q‾u(j)⟩\langle \overline{x}_b, \overline{q}^{(j)}_u\rangle

是两个二进制的内积，可通过位运算操作快速计算，即“与”运算后进行popcount运算，下图展示了分解过程。

硬件加速与优势： 指令支持：现代CPU（如x86）提供单周期位操作（AND）和popcount指令，延迟极低。效率：仅需进行

BqBq

次二进操作和在D-bit上做popcount操作，位操作效率远高于整数乘加。

2. 批量计算方案-基于SIMD和LUTs的FastScan：其设计灵感来自PQ的FastScan实现，通过子段分割、查找表（LUTs）和SIMD指令实现高吞吐量。原理

子段分割：将数据向量的量化码

x‾b\overline{x}_b

(D维)分解为M个子段，每个字段包含4位，即

M=D/4M = D/4

。

预计算LUTs：为每个子段

i(1≤i≤M)i (1 \le i \le M)

生成一张查找表(LUT)，其包含16个条目（4位bits对应的值0-15），用

表示。每个条目存储预计算的内积值

⟨s,q‾u[i]⟩\langle s,\overline{q}_u[i] \rangle

。

是子段值（0-15）；

q‾u[i]\overline{q}_u[i]

是查询向量在第

个子段对应的4个维度的量化值(Bq-bits整数)；

实际计算的内积为：

⟨s,q‾u[i]⟩=∑k=14sk⋅q‾u[i][k]\langle s,\overline{q}_u[i] \rangle = \sum\limits_{k=1}^{4}s_k\cdot\overline{q}_u[i][k]

。其中

sks_k

是

的第

位，

q‾u[i][k]\overline{q}_u[i][k]

是子段

中的第

个维度。

SIMD并行查表: 使用SIMD指令（如AVX2，AVX512）批量处理数据向量，以子段值为索引并行检索LUTs，累加最终的内积。
数据打包：将数据向量的量化代码分组为批量（如32个向量一组），并且对齐每个向量的子段值，打包到SIMD寄存器（如AVX2的256位寄存器可存32个8位值）。

两种方案共同支撑了RaBitQ在ANN搜索中的高效性，平衡了灵活性与吞吐量。实际系统中，可根据查询模式动态选择方案（如IVF索引中，批量处理候选向量）。此设计体现了RaBitQ在理论严谨性（无偏估计）与工程优化（硬件加速）间的平衡。

多bits版RaBitQ

回顾1-bitRaBitQ，其通过正交旋转矩阵

，将归一化后的数据向量

，映射到码表空间

CrC_r

中：

Cr:={Px∣x∈C}，其中C:={+1D,−1D}D.C_r:= \{Px| x \in C\}，其中 C:= \{+\frac{1}{\sqrt{D}}, -\frac{1}{\sqrt{D}}\}^D.

然而，其量化得到的量化码

x‾b\overline{x}_b

的值仅为0或1，导致最终得到的误差仍然较大。因此，作者2025年提出了Extending RaBitQ，即多比特版RaBitQ。主要的扩展在于提供了更精细的码本空间（B比特）。

码表构建

码本空间：

G:={−2B−12+u∣u=0,1,2,...,2B−1}D.\mathcal{G}:= \{-\frac{2^B-1}{2} + u| u = 0, 1, 2,..., 2^B-1\}^D.

Gr:={Py∣∣y∣∣∣y∈G}.\mathcal{G}_r:= \{P\frac{y}{||y||}|y \in \mathcal{G}\}.

如下图所示，左图为集合

G\mathcal{G}

，右图中红色实心点为归一化后的向量

y/∣∣y∣∣y/||y||

。

计算量化码：目标为找到o‾∈Gr\overline{o} \in \mathcal{G_r}o∈Gr，使得距离∣∣o‾−o∣∣2||\overline{o} - o||^2∣∣o−o∣∣2最小。令∣∣o‾−o∣∣||\overline{o}-o||∣∣o−o∣∣最小时，y‾\overline{y}y是G\mathcal{G}G中对应的向量，即o‾=Py‾∣∣y‾∣∣\overline{o} = P\frac{\overline{y}}{||\overline{y}||}o=P∣∣y∣∣y。 y‾=arg miny∈G∣∣Py∣∣y∣∣−o∣∣=arg maxy∈G⟨y∣∣y∣∣,P−1o⟩. \begin{aligned} \overline{y} = \underset{y\in \mathcal{G}}{\text{arg min}} ||P\frac{y}{||y||} - o|| = \underset{y\in \mathcal{G}}{\text{arg max}} \langle\frac{y}{||y||}, P^{-1}o \rangle. \end{aligned}y=y∈Garg min∣∣P∣∣y∣∣y−o∣∣=y∈Garg max⟨∣∣y∣∣y,P−1o⟩. 论文中提供了快速寻找y‾\overline{y}y的方法，感兴趣的同学可以查看原论文。由码本空间G\mathcal{G}G的定义，可将y‾\overline{y}y表示为如下形式： y‾=y‾u−(2B−1)2⋅1D。\overline{y} = \overline{y}_u - \frac{(2^B-1)}{2}\cdot \bold{1}_D。y=yu−2(2B−1)⋅1D。其中, 任意1 \le i \le D ,有, 有,有\overline{y}_u[i] \in {0, 1, …, 2^{B}-1}，即，即，即\overline{y}_u为为为o的量化码向量。

内积计算

⟨o,q⟩\langle o ,q \rangle

的估计与1-bit版RaBitQ一样，为

⟨o,q⟩=⟨o‾,q⟩⟨o‾,o⟩\langle o ,q \rangle = \frac{\langle \overline{o} ,q \rangle}{\langle \overline{o} ,o \rangle}

。因此，多比特版本需要实时评估

⟨o‾,q⟩\langle \overline{o} ,q \rangle

的大小。

\end{aligned}

由此可见，上述公式中，仅

⟨y‾u,q′⟩\langle \overline{y}_u, q' \rangle

需实时计算，其中

q′=P−1qq' = P^{-1}q

，同样可采用SQ对其进行量化。

y‾u\overline{y}_u

由

-bits的整数组成，当

等于1时，上述计算可退变成1-bit版RaBitQ。由于1-bit的计算速度很快，所以作者进一步地将

y‾u\overline{y}_u

拆解成了两部分

y‾u=2B−1⋅y‾0+y‾last.\overline{y}_u = 2^{B-1}\cdot \overline{y}_0 + \overline{y}_{last}.

可知

y‾0=x‾b\overline{y}_0 = \overline{x}_b

(1-bit), 如下图所示：

基于此分解后，可基于1-bit版RaBitQ提供FastScan方案快速计算

⟨y‾0,q′⟩\langle \overline{y}_0 , q'\rangle

，进而提供的误差估计快速剔除不可能ANN候选集的向量。进一步地，再计算候选向量的余下部分

⟨y‾last,q′⟩\langle \overline{y}_{last} , q'\rangle

。最终的内积为：

⟨y‾u,q′⟩=⟨2B−1⋅y‾0,q′⟩+⟨y‾last,q′⟩。\langle \overline{y}_{u} , q'\rangle = \langle 2^{B-1}\cdot\overline{y}_{0}, q'\rangle + \langle \overline{y}_{last}, q'\rangle。

其中，当B=5或B=9时，

y‾last\overline{y}_{last}

为4-bits和8-bits，可根据现存的多种量化技术快速计算。同时，当B=3,4,7,8时，效率仍然十分可观。

实验

1-bit版Rabit实验

在1-bit版RaBitQ实验中，作者对比了普通PQ，4bitPQ（ScaNN），优化版本的PQ（OPQ/LSQ），以及HNSW。实验结果表明，1-bit版RaBitQ在精度和召回上均远好于IVF-PQ，并且提供了更极致的压缩比例。

多bit版Rabit实验

在多bits版RaBitQ的实验中，可直观地看到bit设置的越大，RaBitQ能获得的最大召回率越高，同时QPS会有所下降，但仍然比LVQ性能高。

实验结论

10倍+性能： 在同等召回率下，其性能大约是HNSW的1.5倍，是IVF-PQ的15-20倍。 1/10成本： 满足同等召回率下，其成本只有HNSW的1/10左右 召回随着维度和bit数增加而增加： 作者提出的“距离无偏估计器”公式上与之对应，实验也证明同等bit数下随着维度增加召回率会随之上升。

TencentVDB在RabitQ上的工程落地

作者开源了RabitQ-lib库，其代码已接近工程实践水准，并进行了AVX-512的指令集优化。不过在与VDB的框架结合过程中，依然避免不了诸多改造。框架与接口本身的适配，以及部分bug修复这里不一一说明，本文主要聚焦于内存存储结构和指令集的改造，主要包括以下几点： ● 开源版RabitQ不具备流式写入（增、删、改）能力，VDB需要提供这样的能力，才可以满足最终用户对数据的CRUD操作。 ● 开源版RabitQ在聚簇内部实现时，直接采用一大块连续内存存储向量数据，这种实现针对静态数据是高效的，但如果数据是持续写入和更新的，则不够高效：如果采取预分配策略，则前期可能导致大量内存空间浪费；预分配空间写满后，后续新增导致扩容时，会导致数据拷贝和内存临时翻倍的问题，影响在线读写延迟。 ● 开源多bit版RabitQ默认不支持avx-2指令集，导致在相对低端的机型上无法运行。

内存体系结构Segment化

内存布局&运行访问 TencentVDB基于IVF-RabitQ代码，对其内存管理部分进行了重构，将聚簇内的内存存储结构从整块连续内存，优化为多Segment的分段连续存储的方式。

● 无大内存分配：此时一个聚簇内部不在是一块大的数组，而是有1-N个Segment组成，每个Segment的内存size是可控的，且按照cache line对齐，避免False Sharing。因此后续新增数据时，只需要追加新的Segment数据块，从而避免数据拷贝。在代码层面VDB使用SegmentCluster来实现每个聚簇数据的存储：

○ num_表示该聚簇的条目总量 ○ batch_data_表示1bit量化数据，分段存储。vector的每个元素是一个char指针，指向Segment大小的连续存储空间，表示为： ■ 其中BatchSize为32，即32个向量数据为1个基本单元。 ■ padded_dim是按照64位对齐之后的向量维度，用于加速SIMD指令集的处理速度。 ■ f_add，f_rescale以及f_error是预计算的3个相关因子，每个向量1组，用于加速距离无偏估计。 ■ Factor是可调的放大系数，用于控制单个Segment的实际向量个数。一定取值范围内，Factor越大，则检索效率越高（连续内存寻址，可加速向量距离计算），但空间浪费可能越大，新增Segment的分配时间可能越长。实测发现，Factor取值为8，能较好的平衡空间占用和检索性能。 ○ ex_data_表示额外bit量化数据，同样分段存储，和batch_data_结构相似。vector的每个元素是一个char*指针，同样指向Segment大小的连续存储空间，表示为：

● 多Segment快速寻址：经过多Segment调整后，通过统一的外部业务id到内部id映射，可快速定位到对应的聚簇Cluster、Segment、Segment内的offset偏移量。

● 读写加锁范围：Segment化后，当数据要进行读写并发操作时，会针对局部Segment进行加锁（分段锁），例如聚簇内有100个Segment，此时读写并发过程中“锁冲突概率”降低到：1/100，可以有效地提升系统的吞吐能力。

插入数据到Segment ● 首先，计算出距离新数据距离最近的聚簇，该聚簇即为新数据插入的目标聚簇。 ● 接着，尝试追加新数据到该聚簇的最后一个Segment的空闲区域，确保整体数据的紧密排布，从而充分利用空间。 ● 如果Segment不存在空闲区域，则会创建新的Segment写入数据，这使得后续一段时间内持续写入“无需频繁分配”内存。

从Segment上删除和修改数据● 尝试将Segment的尾部数据填充到删除数据的位置，确保删除后数据依然密集分布。通常的数组元素删除操作，需要将“数组元素大量向前移动的方式”来完成删除空间的填充，其时间复杂度是O(n)，而改进后的方式时间复杂度是O(1）

● 跨Segment移动的处理2种方式： ○ 方案1：始终只保持最后1个Segment尾部存在空闲空间，其余的Segment删除数据时，都从最后一个Segment的尾部数据移动填补，所有插入数据也从最后一个Segment尾部追加。该方式简单直接，无需维护Free-list和空间碎片整理，如果最后一个Segment无数据时，可以整块内存直接释放，不会破坏整体结构。不过删除和修改数据时会出现跨Segment加锁，以及并发写入时，锁冲突概率相对较高。 ○ 方案2：每个Segment删除数据时，从当前删除数据所在Segment上移动其尾部数据到被删除的位置，确保Segment空间前缀部分是紧凑的，该方式在追加数据时，锁冲突会更小，删除阶段不会出现跨Segment加锁。但该方法需要维护Free-list，期间内存空间会出现碎片，如果集中整理空间碎片可能会导致业务出现抖动。

● 当发生修改时，VDB是通过先删除、再插入的方式进行封装，也就是复用上述删除和新增的两个步骤来完成。

AVX2指令集适配改造

RabitQ算法相比其他量化算法，存储空间小的一大关键在于量化后的向量各个元素通过高位打包，低位拼接的形式存储量化后的向量；召回率高的另一关键在于量化向量解压缩后，配合预先计算好的误差参数得到相对无损的距离；计算速度快在于硬件加速，引入更多向量寄存器的avx2/avx512指令集的SIMD计算架构比较适合当前的任务。需要硬件加速的地方主要是涉及到到量化码的压缩/解压缩部分、以及部分计算结果累加的代码。

量化向量解压缩

压缩和解压缩是适配的。压缩阶段将量化后的向量的高位元素打包进一个为一个最近整型，低位不断拼接到多个8位整型数组中。最终合并到一起。期间大部分为移位操作，且性能约束低，直接使用SSE指令比较通用；解压缩阶段avx指令贯穿其中。解压缩阶段目的是将向量恢复压缩前的状态，此时主要涉及到查询场景，性能要求更高。我们以3bit版本的压缩和解压缩为例, 了解压缩原理并为其适配解压的代码，剩余的其他1~8bit的解压缩程序虽然都不一样，但原理近似。 ● 压缩3bit：以长度为64的向量，3bit压缩，向量元素取值为unit8：0~2^3-1 = 0~7。我们以下述向量为例

● 解压3bit：以avx 512为例，解压缩时主要是将低位和高位还原，其还原原理图示如下。对于avx2而言，即是将一次性处理512bit转换为分两次各处理256 bit即可。

● 3bit 示例code：

其基本逻辑遵循解包的流程，主要包括以下几步： ● 从内存中一次性加载此前被压缩的64个向量元素的：低位的128位数据到128个XMM寄存器（占16byte）、以及高64位到一个64bit的整型中（占8byte） ● 解出64个向量元素压缩前的低2位：利用整数左移函数，分批将128位共计64个向量元素拆解为4组，每组16个向量元素，与低位mask 按位& ● 解包64个向量元素压缩前的高1位：移位解，2个64位整型组合成一个128位向量，与高位mask求与，得到64个元素的高1位 ● 合并高低位，加载解包向量到256个YMM寄存器，执行内积计算

avx2/avx512 性能对比

使用ann-benchmark评测，avx2 性能微弱于avx512，整体强于Faiss标准库；以SIFT-1M数据集为例，在topk=10、100下，avx2/avx512优于Faiss，且索引文件size大幅降低4倍于Faiss IVF 机器环境： ● CPU: AMD EPYC 9754 128-Core Processor ● 内存：64GB

向量索引的进一步探索

RabitQ是一种量化方式，目前VDB已提供多bit版IVF-RabitQ，后续还会进一步提供HNSW-RabitQ索引服务，其综合HNSW的图搜与RabitQ的空间量化和计算代价低的优势。 RabitQ的思路将向量索引算法带入一个新的阶段，不过向量索引本身还依然存在其它的工程问题是RabitQ也无法解决的。例如: IVF索引的聚簇倾斜问题依然会发生，RabitQ通过算法虽可以极大减少input query向量与聚簇内每个向量的计算代价，但其并不能解决input query命中数据倾斜的聚簇时，其匹配的向量数量会突然变多，我们需要通过其它的手段来处理以下几个重点： ● 发现聚簇倾斜（可观测） ● 不断优化“采样算法”让数据尽可能不倾斜，简单的思路是让倾斜的聚簇按照比例采集更多的样本，调整步长让采集的数据可分布在更大的写入时间序中 ● 有效减少扫描行数，即使命中倾斜的聚簇，也依然可以保证稳定的性能和高召回 ● 控制相对稳定的扫描行数，随着聚簇内数据规模增加，不会导致检索性能线性增加 VDB团队也在上述方向上持续探索算法有一段时间，并已在理论和实验上取得一定的突破，将在此基础上构建自研索引（IVF-ABQ），其核心理论基础是基于三角函数中的距离和夹角来划分Blocking的思路。目前VDB已在1million~1billion多组数据集下（开源/业务）实验验证结论，通过IVF-ABQ算法在几乎不降低召回的前提下，可减少10倍以上的“扫描行数”以降低整体向量计算次数，简单归纳： ● IVF-ABQ：减少扫描行数，相对稳定的扫描行数 ● IVF-RabitQ：相同扫描行数下，降低计算代价可见IVF-ABQ、IVF-RabitQ分别解决不同的问题，两者可以有效结合，发挥出更大的价值，这是我们VDB团队接下来落地自动弹性索引的坚实基础。

参考文献： [1] Gao, J., & Long, C. (2024). Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 2(3), 1-27. [2] Gao, J., Gou, Y., Xu, Y., Yang, Y., Long, C., & Wong, R. C. W. (2025). Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 3(3), 1-26.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-28，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯云