4、基础策略二：标记删除+异步合并（Mark & Sweep）——LSM-Tree思想在向量索引中的应用
上一章我们聊了全量重建，简单粗暴但代价高。这一章我们来看一种更优雅的思路——标记删除+异步合并。说白了，就是借鉴LSM-Tree的思想，把删除和更新操作先“记下来”，等时机成熟了再统一处理。
我个人习惯把这种策略叫做“懒人模式”。你想想看，每次删除都要立刻从索引里把向量抠掉，代价太大了。不如先打个标记，等积累到一定程度，再一次性清理。这不就是LSM-Tree的经典套路吗？
4.1 核心思想：写操作先记账，读操作要擦眼
这个策略的核心就两句话：
- 写操作（删除/更新）：不直接修改主索引，而是写入一个增量日志或标记位。
- 读操作（查询）：先查主索引，再查增量日志，合并结果后过滤掉已删除的向量。
我在项目中遇到过这样一个场景：用户频繁删除和重新插入向量，如果每次删除都触发索引重建，系统根本扛不住。用了标记删除后，写入吞吐直接提升了10倍。
关键洞察：标记删除的本质是将随机写转化为顺序写，同时将清理操作延迟到系统空闲时执行。
4.2 架构设计：双索引 + 合并器
这套架构通常包含三个核心组件：
- 主索引（Base Index）：存储所有“有效”的向量，定期重建。
- 增量日志（Delta Log）：记录所有删除/更新操作的标记，通常是位图或布隆过滤器。
- 合并器（Merger）：后台线程，定期将增量日志合并到主索引中。
我画了一张图，帮你理解这个流程：
4.3 具体实现：位图标记 + 定期合并
在实际工程中，我最常用的实现方式是位图标记法。每个向量分配一个唯一的ID，删除时在位图中将对应位置置为1。查询时，先查主索引拿到候选结果，再根据位图过滤掉已删除的ID。
来看一段伪代码：
class MarkSweepIndex:
def __init__(self):
self.base_index = VectorIndex() # 主索引
self.deleted_bitmap = BitArray() # 删除位图
self.delete_count = 0
self.merge_threshold = 10000 # 合并阈值
def delete(self, vector_id):
# 标记删除，不修改主索引
self.deleted_bitmap.set(vector_id, 1)
self.delete_count += 1
# 达到阈值，触发异步合并
if self.delete_count >= self.merge_threshold:
self.trigger_merge()
def search(self, query, top_k):
# 1. 在主索引中搜索
candidates = self.base_index.search(query, top_k * 2)
# 2. 过滤已删除的向量
results = []
for id, distance in candidates:
if not self.deleted_bitmap.get(id):
results.append((id, distance))
return results[:top_k]
def merge(self):
# 后台线程执行
# 1. 从主索引中移除已删除的向量
# 2. 重建主索引
# 3. 清空删除位图
self.base_index.remove_deleted(self.deleted_bitmap)
self.deleted_bitmap.clear()
self.delete_count = 0避坑指南：我曾经在merge时直接在主索引上做原地删除，结果导致查询线程读到脏数据。后来改成写时复制（Copy-on-Write），先构建新索引，再原子切换引用，才彻底解决这个问题。
4.4 性能对比：标记删除 vs 全量重建
我整理了一张对比表，帮你直观感受两者的差异：
| 维度 | 全量重建 | 标记删除+异步合并 |
|---|---|---|
| 写入延迟 | 高（每次删除都重建） | 低（仅标记，O(1)） |
| 查询延迟 | 稳定（索引始终最新） | 略高（需额外过滤） |
| 内存开销 | 低（无额外结构） | 中（位图/日志） |
| CPU开销 | 高（频繁重建） | 低（后台合并） |
| 适用场景 | 低频写入，高频查询 | 高频写入，查询可容忍少量延迟 |
4.5 合并策略：什么时候该动手？
合并时机很关键。我总结了几种常见策略：
- 阈值触发：删除数量达到N时触发。简单粗暴，但可能在高负载时雪上加霜。
- 定时触发：每隔T分钟触发一次。适合流量平稳的场景。
- 空闲触发：监控系统负载，在CPU/IO空闲时触发。最优雅，但实现复杂。
我个人习惯用阈值+空闲的组合策略。举个例子：当删除量达到5000条时，检查当前CPU利用率是否低于30%，如果是则立即合并，否则等待下一个检查周期。
警告：合并操作会占用大量IO和CPU。如果合并期间写入量仍然很大，可能导致合并速度跟不上删除速度，最终增量日志无限膨胀，查询性能急剧下降。这就是所谓的“合并风暴”。
4.6 实战经验：我在项目中踩过的坑
嗯，这里要分享几个真实教训：
- 位图溢出：向量ID范围很大时，位图会占用大量内存。我后来改用布隆过滤器，虽然有小概率误判，但内存节省了90%。
- 合并期间查询超时：合并时主索引被锁住，查询只能等。解决方案是双缓冲——合并期间用旧索引服务查询，合并完成后再切换。
- 删除标记残留：有一次合并线程崩溃，导致部分删除标记没被清理。后来加了WAL（Write-Ahead Log），确保合并操作的原子性。
4.7 适用场景与局限性
这个策略最适合以下场景：
- 写入量远大于删除量
- 查询可以容忍毫秒级的额外延迟
- 系统有明确的低峰期可以执行合并
但如果你遇到这些情况，可能要考虑其他方案：
- 删除操作占比超过30%——增量日志会膨胀得很快
- 查询要求P99延迟低于10ms——额外的过滤开销可能超标
- 向量ID空间极大（如百亿级）——位图内存扛不住