用 Rust 从零搭一个向量检索服务:标量过滤该放在图搜索的哪一步
讲 HNSW 的那篇只讲了"怎么用图做近似最近邻"。但真实请求从来不是这样:
SELECT * FROM docs
WHERE category = 'tech' AND tenant_id = 42
ORDER BY embedding <-> $query
LIMIT 10;ORDER BY 之前还有一堆 WHERE。 而 HNSW 的图是按全量数据建的,它根本不知道 WHERE 是什么。
这篇不讲 HNSW 怎么建图(前面的轮子已经讲过),只讲一件事:怎么把一个算法装成一个服务。
第一步:先定接口,因为它决定了后面所有取舍
pub struct Hit {
pub id: DocId,
pub distance: f32,
/// 命中的那条向量来自哪个段(段是这篇的核心单位)
pub segment: SegmentId,
}
pub enum Filter {
/// 没有过滤条件
None,
/// 等值 / 集合成员
In { field: String, values: Vec<String> },
/// 范围
Range { field: String, lo: i64, hi: i64 },
/// 组合
And(Vec<Filter>),
Or(Vec<Filter>),
}
pub trait VectorIndex: Send + Sync {
fn search(
&self,
query: &[f32],
k: usize,
filter: Option<&Filter>,
) -> Result<Vec<Hit>>;
fn insert(&mut self, id: DocId, vector: &[f32], meta: &Meta) -> Result<()>;
fn delete(&mut self, id: DocId) -> Result<()>;
/// 告诉调用方"这次搜索到底扫了多少" —— 排查召回率问题的唯一线索
fn stats(&self) -> IndexStats;
}Filter 不是 HashMap<String, String>,而是一个枚举表达式树,理由在第二步会显出来。
stats() 这个方法看起来多余,但它是必需的。 因为这个系统是近似的——同一个查询,参数不同,返回的结果可能完全不同。没有"这次扫了多少节点"这类内部计数器,你连"召回率为什么掉了"都无从查起。
第二步:全文的核心——过滤放在图搜索的哪一步
这是向量检索服务里唯一真正难的设计决策。有四种放法,每一种都会在特定场景下崩掉。
放法一:后置过滤(post-filter)
// 先用 HNSW 搜出一批,再过滤
let candidates = hnsw.search(query, k * 10)?; // 多搜 10 倍
let hits: Vec<_> = candidates.into_iter()
.filter(|h| matches_filter(&h.meta, &filter))
.take(k)
.collect();问题在哪? 如果过滤条件的选择率是 1%,那么搜出来的 10K 个候选里只有 10K × 1% = K/10 个能过。要么返回不足 K 条,要么把 K 放大到 100 倍——而放大 100 倍意味着搜索成本也涨 100 倍。
这里有个反直觉的事实:HNSW 的单次搜索不是常数时间。 ef 参数越大,访问的节点越多。所以"多搜一点再过滤"在低选择率下会直接退化成暴力搜索。
放法二:前置过滤(pre-filter)
反过来,先用标量索引算出"满足条件的所有 id",再在集合内做搜索:
let allowed: RoaringBitmap = scalar_index.query(filter)?; // 精确的行号集合
// 在图上搜索,但只走 allowed 里的节点
let hits = hnsw.search_within(query, k, &allowed)?;问题在哪?HNSW 的图是全量数据建的,而"过滤后的子集"在图上通常是不连通的。
全量图(连通) 过滤后子集(不连通)
A ── B ── C A C
│ │ │
D ── E ── F (过滤掉了 B、D、E、F 之后,A 和 C 之间没有边)于是搜索会提前终止:贪心走到 A 之后,发现所有邻居都被过滤掉了,就以为"到了局部最优",返回 A。 而真正最近的 C 从来没被访问过。
这就是前置过滤的致命伤:它把"图的连通性"这个前提给破坏了,而 HNSW 的正确性完全建立在连通性上。 子集越小,崩塌越彻底——恰好选择率越低的时候,前置过滤越像"随机返回结果"。
放法三:内联过滤(filter-aware traversal)
ACORN 这类做法给了一个折中:
impl Hnsw {
fn search_filtered(
&self,
query: &[f32],
k: usize,
allowed: &RoaringBitmap,
ef: usize,
) -> Vec<Hit> {
let mut visited = VisitedSet::new(self.len());
let mut candidates = BinaryHeap::new(); // 候选:按距离取最近
let mut results = BinaryHeap::new(); // 结果:按距离取最远
let entry = self.entry_point();
visited.mark(entry);
candidates.push(Reverse(Neighbor { id: entry, dist: self.dist(query, entry) }));
while let Some(Reverse(current)) = candidates.pop() {
// ★ 关键:走不动就提前停
if results.len() >= ef
&& current.dist > results.peek().map(|r| r.id.dist).unwrap_or(f32::MAX)
{
break;
}
for &nb in self.neighbors(current.id) {
if visited.is_marked(nb) {
continue;
}
visited.mark(nb);
let d = self.dist(query, nb);
// ★★ 这一步是内联过滤和前置过滤的唯一区别:
// 不满足条件的节点"不作为结果",但仍然"作为跳板"继续扩展
if allowed.contains(nb) {
results.push(Neighbor { id: nb, dist: d });
if results.len() > ef {
results.pop();
}
}
candidates.push(Reverse(Neighbor { id: nb, dist: d }));
}
}
results.into_sorted_vec().into_iter().take(k).collect()
}
}注意 allowed.contains(nb) 那个判断的位置:它只决定"这个节点要不要进结果集",不决定"要不要从它继续走"。
这就是全部的精髓。 被过滤掉的节点变成了纯跳板——它们让图保持连通,却不污染结果。 代价是这些被跳过的节点照样要计算距离、照样要访问邻居,所以"扫的节点数"比无过滤时更多,ef 需要调高。
前置过滤和后置过滤都是"在没有过滤的世界里找一个不符合过滤的答案";内联过滤是"承认过滤存在,但让图仍然连通"。 这句话的解释力很强——它同时也是"为什么标注了过滤条件的 ANN 问题比纯 ANN 难"的答案。
放法四:干脆用暴力扫描
这条路经常被忽略,但它有明确的适用区间:
fn brute_force(&self, query: &[f32], k: usize, allowed: &RoaringBitmap) -> Vec<Hit> {
// 只对候选集做距离计算:顺序读、无分支、可向量化
let mut heap = BinaryHeap::with_capacity(k + 1);
for id in allowed.iter() {
let d = self.dist(query, id);
heap.push(Neighbor { id, dist: d });
if heap.len() > k {
heap.pop();
}
}
heap.into_sorted_vec()
}为什么它可以赢?
因为候选集足够小的时候,"扫过所有候选"比"在图上游走"更快——图遍历是随机内存访问(cache miss 一生之敌),暴力扫描是连续内存访问(硬件预取器最喜欢的形状)。在候选集小于几千条的时候,暴力扫经常比 HNSW 还快。
那到底选哪个?看选择率
| 过滤后剩余比例 | 推荐策略 | 理由 |
|---|---|---|
| > 50% | 后置过滤(K 放大 2~3 倍) | 过滤几乎不减候选,图搜索的成本优势保留 |
| 5% ~ 50% | 内联过滤(ef 调高) | 连通性不能丢,但要避免搜进无关区域 |
| < 5% | 暴力扫描 | 候选集本身已经很小,随机访问的图反而更慢 |
| 无法估算 | 内联过滤 + 自适应 ef | 最稳,最慢 |
这张表是这篇最实用的东西,但更重要的是它的前提:你得先能算出选择率。
/// 估算过滤条件的选择率——搜索策略的开关依赖它
fn estimate_selectivity(&self, filter: &Filter) -> f64 {
let allowed = self.scalar_index.count(filter);
allowed as f64 / self.total_docs as f64
}位图让这个估算变得廉价(一次 popcount),这是"标量索引用位图而不是用 B 树"的一个隐藏收益。
这也是"索引不是越多越好"的一个实例:选择率低的时候,索引反而是负担。 而系统必须知道这一点,才有资格做自适应——"总是用 HNSW"和"总是用暴力扫描"一样,都是没做完的设计。
第三步:标量索引——位图 + 布隆,方向不能搞反
标量索引要支撑两件事:(1)算出精确的候选行集合;(2)在更大的范围(段)上做粗粒度排除。
pub struct ScalarIndex {
/// 段内:字段值 → 行号位图(精确)
postings: HashMap<(Field, Value), RoaringBitmap>,
/// 段级:字段值 → 布隆过滤器(粗粒度)
bloom: HashMap<Field, BloomFilter>,
total_rows: u32,
}布隆过滤器的语义方向必须记牢:
impl BloomFilter {
/// false 是确定的:这个段里绝对没有这个值
/// true 是不确定的:这个段里"可能"有
pub fn may_contain(&self, value: &[u8]) -> bool { /* ... */ }
}所以它只能用来"排除段",不能用来"确认行"。
pub fn candidate_segments(&self, filter: &Filter, segments: &[Segment]) -> Vec<SegmentId> {
segments.iter()
.filter(|seg| {
// 布隆说不可能有 → 整个段跳过,省掉一次位图运算 + 一次段打开
match filter {
Filter::In { field, values } => {
!values.iter().all(|v| !seg.bloom[field].may_contain(v.as_bytes()))
}
_ => true,
}
})
.map(|s| s.id)
.collect()
}这个方向一搞反,整个系统就会静默地返回错误结果——比如拿布隆去确认行的存在,那么"误判为存在"的行会被算进候选集,然后因为向量里没有这条记录而…直接被忽略掉(因为它在向量索引里不存在),表面上没问题,实际上召回率已经被悄悄削掉一块。
布隆过滤器是"排除器"不是"确认器"。 讲 S3 客户端的那篇、讲一致性哈希的那篇里都出现过它,方向永远是同一个:误判只允许误报存在,不允许误报不存在。 这条性质一旦反着用,错误不会崩,只会变慢和变差——而这恰恰是最难发现的那种错。
第四步:删除——为什么不能真的删
删除是向量索引里最容易被低估的操作。HNSW 里删一个节点,要把它所有邻居互相连起来修复图,还要重算它们的邻居列表——成本比插入高一个数量级,而且反复删插会让图退化成一团乱麻。
所以主流做法是把 LSM 那套搬过来:
pub struct Segment {
/// 原始向量:连续存储,一条紧挨一条(不是 Vec<Vec<f32>>)
vectors: Vec<f32>,
dim: usize,
/// 图结构:每个节点的邻居列表,用偏移量索引到 adjacency 里
graph: HnswGraph,
/// 行号 → 全局 doc id
doc_ids: Vec<DocId>,
/// 被删除的行号(软删除)
tombstones: RoaringBitmap,
/// 段是不是只读的
immutable: bool,
}impl Segment {
/// 删除 = 标一个位,O(1)
pub fn delete(&mut self, id: DocId) -> bool {
if let Some(row) = self.row_of(id) {
self.tombstones.insert(row);
true
} else {
false
}
}
}搜索时在出口处过滤掉墓碑:
fn finalize(&self, mut hits: Vec<Hit>, k: usize) -> Vec<Hit> {
hits.retain(|h| !self.tombstones.contains(h.row));
hits.truncate(k);
hits
}但这带来一个连锁问题:墓碑比例高了之后,搜索"名义上取 K 条,实际只剩几条"。 所以必须监控:
pub struct IndexStats {
pub segments: usize,
pub live_docs: u64,
pub tombstoned_docs: u64,
/// 这个比值超过阈值就该触发合并
pub tombstone_ratio: f64,
pub last_search_nodes_visited: usize,
}当 tombstone_ratio > 0.2(行业常见阈值)时触发段合并,合并时顺带把墓碑物理清除——注意这时必须重建图,因为图结构是绑在行号上的,删掉行之后邻居列表全部错位。
这个设计能成立的关键是"段不可变"。 段一旦落盘就不再修改,所以墓碑是唯一需要写的东西,而且写入永远不碰图结构。代价是空间放大(墓碑占着位置)和查询时的额外过滤,收益是删除变成 O(1)、以及"读操作完全不需要锁"。 后者才是真正的收益——读路径无锁,是这个服务能扛住高并发的根本原因。
段合并本身也要讲清代价:
| 动作 | 是否需要重建图 | 代价 |
|---|---|---|
| 加墓碑 | 不需要 | O(1) |
| 段合并(重排行号) | 需要 | O(n log n) + 全量重连边 |
| 段合并(只做删除,不重排) | 需要 | 同上 |
| 加新段 | 不需要 | 增量建图 |
所以合并是批量的、离线做的,绝不能放在请求路径上。 这也是为什么真实系统都提供 "optimize / force merge" 这类手动触发接口——把"什么时候付这笔钱"交给运维,而不是自动付。
第五步:量化——瓶颈是内存带宽,不是算力
先算一笔账,这决定了后面全部优化的方向:
768 维 f32 向量 = 768 × 4 = 3,072 字节
100 万条 = 3.07 GB (只算向量本身)
HNSW 图结构 = 每个节点 M=16 个邻居 × 4 字节 × 100 万 ≈ 64 MB图结构只有 64 MB,向量本体却有 3 GB。 这个比例说明了一切:
图遍历(HNSW 的核心动作)在做什么?
1. 读一个节点的邻居列表(64 MB 里的 64 字节) ← L2 可能命中
2. 对每个邻居:从 3 GB 里读出它的 3 KB 向量 ← 必然 cache miss
3. 算一次距离:768 次乘加 = 约 100 纳秒第 2 步的代价远大于第 3 步。 从主存读 3 KB 大约要几百纳秒到 1 微秒,而计算只要 100 纳秒。所以这个系统是内存带宽受限(memory-bound)的,不是计算受限的。
这就是量化的全部意义所在——不是为了算得快,是为了搬得少。
pub enum VectorStorage {
/// 原始精度
F32(Vec<f32>),
/// 标量量化:每个 f32 压成 i8(1/4 空间)
Int8 { data: Vec<i8>, scale: Vec<f32>, offset: Vec<f32> },
/// 乘积量化:切 m 段,每段查一个 256 项的码本
PQ { codes: Vec<u8>, codebooks: Vec<Vec<f32>> },
}| 方式 | 每条向量占用 | 相对查询质量 |
|---|---|---|
| f32 | 3,072 B | 1.0(基准) |
| int8(标量量化) | 768 B | 召回损失通常 < 2% |
| PQ,m=96 子空间 | 96 B | 召回损失 5% ~ 15%(取决于训练数据) |
| PQ + rerank | 96 B + 原始(仅候选) | 接近 f32 |
标量量化的性价比高得离谱:空间降到 1/4,召回损失通常很小,而且int8 的距离计算可以用 SIMD 一次算 16 个(AVX2)或 32 个(AVX-512)维度,比 f32 的通道数翻倍。
代价是"必须存 scale 和 offset"——量化的边界是数据相关的,所以要么在写入时按段统计 min/max,要么用固定的理论范围([-1, 1] 之类,前提是向量已归一化)。前者更准,后者更省元数据。
两阶段检索:先粗排再精排
大压缩比必然损失精度,所以标准结构是用压缩数据找候选,用原始数据定结果:
pub fn search_two_stage(
&self,
query: &[f32],
k: usize,
candidates: usize, // 粗排候选数,通常 4~10 倍 k
) -> Vec<Hit> {
// ① 粗排:在压缩空间里搜,便宜但略糙
let rough = self.search_compressed(query, candidates)?;
// ② 精排:取回原始向量,重算距离
let mut refined: Vec<Hit> = rough.into_iter()
.map(|mut h| {
h.distance = self.dist_exact(query, h.row); // 只有 candidates 次
h
})
.collect();
refined.sort_by(|a, b| a.distance.partial_cmp(&b.distance).unwrap());
refined.truncate(k);
refined
}这里有一个隐藏的取舍:candidates 越大,召回率越高,但精排要读的原始向量也越多。 因为原始向量是全量存的,读 1000 条原始向量 = 3 MB 的内存随机读——这一步很容易吃掉粗排省下的全部收益。
标准答案是"原始向量只在段内按行号密集存",这样精排是"随机访问 1000 个位置",而不是"随机访问 1000 个散落的指针"。一条 Vec<f32> 连续存储 vs Vec<Vec<f32>>,在精排这一步能差出一个数量级——这是纯粹的内存布局问题,和算法毫无关系。
向量检索的优化顺序应该是:先看内存布局,再看量化,最后才看距离计算函数。 调换顺序的话,你会在第三项上花很多时间,然后发现瓶颈一直在第一项。讲性能测量那篇说过"别靠猜,先量出来",这里的具体形态就是:如果 perf 显示大量 cache-miss,那问题一定在布局,不在算术。
第六步:并发——读多写少的形状
这个服务的读写比通常是 1000:1 以上,所以整个并发设计都围绕"让读无锁":
pub struct VectorService {
/// 完整索引快照:读的时候 clone 一次 Arc,之后完全无锁
snapshot: ArcSwap<IndexSnapshot>,
/// 写入缓冲:单写者
writer: Mutex<WriteBuffer>,
/// 每线程复用的搜索缓冲(对象池思路)
pools: SearchPool,
}
pub struct IndexSnapshot {
segments: Vec<Arc<Segment>>,
scalar: ScalarIndex,
/// 快照版本号,方便排查"为什么两个请求结果不一致"
generation: u64,
}读路径:
pub fn search(&self, query: &[f32], k: usize, filter: Option<&Filter>) -> Result<Vec<Hit>> {
// 一次原子读,拿到一个不可变的快照
let snap = self.snapshot.load();
// 每线程一个 buffer,避免反复分配 visited 集合
let mut ctx = self.pools.acquire();
let mut all = Vec::new();
for seg in &snap.segments {
if !seg.may_match(filter) { continue; } // 布隆粗筛
let allowed = snap.scalar.query(filter, seg); // 位图精筛
all.extend(seg.search_within(query, k, &allowed, &mut ctx));
}
Ok(merge_topk(all, k))
}这里有三层无锁:
ArcSwap让"读快照"是一次原子读,不阻塞写入构建新快照(写入是构造一个全新的IndexSnapshot再原子交换)- 段本身不可变,所以多个线程共享
Arc<Segment>完全不需要锁 - 搜索缓冲按线程复用(
ctx),不跨线程共享
为什么缓冲要复用? 因为 HNSW 每次搜索都要一个"访问过"集合:
pub struct SearchContext {
/// 用版本号数组代替 HashSet:避免每次搜索清空
visited_epoch: Vec<u32>,
current_epoch: u32,
}
impl SearchContext {
#[inline]
fn is_visited(&mut self, row: usize) -> bool {
self.visited_epoch[row] == self.current_epoch
}
#[inline]
fn mark_visited(&mut self, row: usize) {
self.visited_epoch[row] = self.current_epoch;
}
fn next_query(&mut self) {
// 不清空数组!只把版本号 +1,一次 O(1) 的"逻辑清空"
self.current_epoch += 1;
if self.current_epoch == u32::MAX {
self.visited_epoch.fill(0);
self.current_epoch = 1;
}
}
}这是一个小技巧但收益巨大。 100 万行的索引,每次搜索要标记几千个节点。用 HashSet 的话每次搜索要分配、插入、扩容、释放;用 Vec<u32> 版本号,每次搜索只有一次 +1。
代价是内存固定为 4 字节/行,而且必须能接受"每 40 亿次搜索才真正清空一次"。 这是典型的"用空间和巧妙换掉分配器压力"——讲 TinyLFU 的那篇、讲布隆过滤器的那篇,本质都是同一类交换。
分配器是高并发服务的隐形瓶颈。 每次请求分配一个几千项的集合,分配器就要加锁、找块、记录——这些开销和真正的计算毫无关系,却常常占掉一半的时间。 所以高并发服务的第一条设计规则是:请求路径上不分配,或者只从每线程的池里拿。
第七步:距离计算的布局问题
#[inline]
pub fn l2_sqr(a: &[f32], b: &[f32]) -> f32 {
debug_assert_eq!(a.len(), b.len());
let mut sum = 0.0f32;
for i in 0..a.len() {
let d = a[i] - b[i];
sum += d * d;
}
sum
}这段代码能比"同样语义的 Vec<Vec
| 布局 | 一次距离计算的访存 | 效果 |
|---|---|---|
Vec<Vec<f32>> |
先读指针,再读数据(两次间接) | 每次都是 cache miss |
Vec<f32> + 偏移 |
直接读 data[row*dim .. (row+1)*dim] |
连续,硬件预取生效 |
这是"用顺序换随机"在微观层面的又一次出现(列存那篇讲的是宏观版本)。 而且它比宏观测的版本更值得在意——因为向量检索的主循环就是在做这件事几百万次。
再往上一层才是 SIMD。 关键判断是:编译器自动向量化这段简单循环的条件是"没有别名、没有分支、长度可知"。 a 和 b 都是 &[f32] 时可能别名,所以显式用切片分块 + assert_eq! 长度有时反而能让 LLVM 更放心地向量化。先把布局和边界弄干净,SIMD 才有东西可以优化——这一点向量化执行那篇里已经吃过一次同样的教训。
第八步:召回率怎么测——近似系统必须有刻度
这是"算法"和"服务"的分界线。 HNSW 是近似的,所以"返回了 10 条"不等于"返回了最近 10 条"。一个没有召回率刻度的向量检索服务,等于一个不能调参的黑盒。
/// 在测试集上计算 recall@k
pub fn recall_at_k(index: &dyn VectorIndex, queries: &[Query], k: usize) -> f64 {
let mut total = 0.0;
for q in queries {
// ground truth 用暴力搜索算出来(只在小数据集上做)
let truth: HashSet<DocId> = brute_force(&q.vector, k, q.filter.as_ref())
.into_iter().map(|h| h.id).collect();
let got: HashSet<DocId> = index.search(&q.vector, k, q.filter.as_ref())
.unwrap().into_iter().map(|h| h.id).collect();
total += truth.intersection(&got).count() as f64 / k as f64;
}
total / queries.len() as f64
}这个函数必须在 CI 里跑,而且必须带过滤条件跑。 因为最容易被静默破坏的正是"带过滤时的召回率"——前置过滤的连通性崩塌、后置过滤的候选不足、布隆方向搞反,全都只会让这个数字往下掉,而不产生任何错误。
实践中要建立一条基线曲线:
| 配置 | ef | 召回@10 | 平均延迟 | 每次搜索访问节点数 |
|---|---|---|---|---|
| 无过滤 | 50 | 0.98 | 0.4 ms | 1,200 |
| 无过滤 | 200 | 0.998 | 1.3 ms | 4,800 |
| 过滤(选择率 30%) | 200 | 0.95 | 2.1 ms | 7,900 |
| 过滤(选择率 1%) | 200 | 0.72 | 9.8 ms | 36,000 |
| 过滤(选择率 1%) | 暴力扫描 | 1.00 | 0.6 ms | 10,000(全部候选) |
最后一行是最有教育意义的一行:选择率 1% 的时候,暴力扫描不但更准,还快 16 倍。 这正是第二步那张决策表的经验依据——而这张表只能靠测出来,不能靠推理。
近似检索系统的"正确性"是一个连续量,不是一个布尔值。 所以它必须自带刻度,而且刻度要跟着过滤条件变化。任何"返回了结果就算成功"的验收方式,都是在掩盖系统性召回损失。
结论
把 HNSW 装成服务之后,多出来的四件事,恰好就是前面四篇轮子的交接点:
HNSW → 给了一个能贪心搜索的图
这篇新增:
过滤语义 → 内联过滤:被过滤的节点不能当结果,但必须当跳板
删除 → 墓碑 + 不可变段(借 LSM 的结构)
内存 → 量化 + 段内稠密布局(借列存的布局思路)
并发 → ArcSwap 快照 + 每线程缓冲(借对象池的思想)四件事里有三件和"算法"无关,全是接口和布局问题。 这也是这一整个系列想反复说明的:轮子是算法,系统是接口。
最后把这篇的四条判断留成一张清单:
- 过滤策略必须由选择率决定,而选择率必须能便宜地算出来(位图 popcount)
- 布隆只能排除段,不能确认行——方向反了不会报错,只会掉召回
- 量化是为了少搬内存,不是为了算得快——先修布局,再量化,最后才碰 SIMD
- 召回率必须有刻度,而且必须带上过滤条件一起测
第 3 条和第 4 条合起来解释了向量检索为什么"看起来简单、上线很难":它的错误形式是"结果差一点",不是"结果不对"。 而一个不报错的降级,永远是最贵的那个 bug。
下一篇换到网络协议那边,看一个完全不同的形状:整个系统的难点不在计算,而在"缓存到底该信谁"。