跳到主要内容

核心存储魔法:图 + 选择性重算(省 97% 的原理)

30 秒导读: 传统向量库把每条向量原封不动全存下来,60M 个文本块要 201GB。LEANN 的招数只有一句话:embedding 不存了,只存"谁连谁"的图结构 + 原文,要用的时候现算。同样的 60M 块,它只占 6GB——省了 97%。这一章讲透 build 阶段是怎么把一个普通的 FAISS 索引"掏空"成这种省空间形态的。

这一章只讲存(build 侧)。查询时怎么把 embedding 现场算回来(HNSW 遍历 + ZMQ 按需重算),留给 02-search-recompute.md。

1. 要解决的小问题:embedding 太占地方了​

先看传统向量数据库怎么存东西。

你有 N 条文本块(chunk),每条过一遍 embedding 模型,变成一个 D 维浮点向量(比如 D=768)。传统做法是把这 N × D 的矩阵整个存到磁盘——这样查询时算一次 query 向量,和库里所有向量比距离就行,不用再碰模型。

问题出在这个矩阵会爆炸性地大。算一笔账:

项值
文本块数 N60,000,000
维度 D768(常见句向量维度)
每个数4 字节(float32)
原始 embedding 体积60M × 768 × 4 ≈ 184 GB

README 里给的实测数字更直接:一个 60M 块的 Wiki 语料,传统 FAISS 索引要 201GB(README:65 "Index 60 million text chunks in just 6GB instead of 201GB")。这东西根本塞不进一台笔记本。

关键观察: embedding 是"派生数据"——它是原文过模型算出来的,原文才是"真身"。既然能算出来,为什么非要存?这就是 LEANN 整个设计的出发点。

2. 思路:只存图 + 原文,embedding 现用现算​

LEANN 的取舍可以浓缩成一张对照表:

传统向量库LEANN
存 embedding 向量?存全部 N×D不存(写个空标记占位)
存原文?存存(passages.jsonl)
存图结构(谁连谁)?有的存有的不存存(核心资产)
查询时的 embedding从磁盘读现场重算

README 一句话点破了这个哲学(README:1261):

The magic: Most vector DBs store every single embedding (expensive). LEANN stores a pruned graph structure (cheap) and recomputes embeddings only when needed (fast).

省下来的就是那 184GB 的向量矩阵。代价是查询时要重新过一遍模型——但只算搜索路径上碰到的那几个节点,不是全量,所以还能接受(这就是"selective recomputation,选择性重算"里"选择性"三个字的意思)。

那图为什么要存、又为什么便宜?因为 LEANN 底层用的是 HNSW(Hierarchical Navigable Small World,一种基于图的近似最近邻索引):它本身就是靠"从入口点沿着邻居边一跳跳走向目标"来搜索的。这张邻居图必须留着,否则没法导航。好在图只是一堆整数(节点 ID),比起浮点向量矩阵小得多——这就是"cheap"的来源。

一句话直觉:把 embedding 当缓存,把原文当真身,把图当地图。 地图和真身留着,缓存丢掉、要走到哪儿再算哪儿。

3. build 流水线:从"满索引"到"空壳图"​

理解了思路,来看 build 阶段实际走了哪几步。入口是 HNSWBuilder.build(packages/leann-backend-hnsw/leann_backend_hnsw/hnsw_backend.py:66)。

怎么读这张图: 从上到下是时间顺序。前半段和普通 FAISS 一样先建一个"满"索引(embedding 都在),后半段才是 LEANN 特有的"掏空"动作。

输入: data (N×D embedding 矩阵) + ids (passage ID 列表)
  │
  ▼
① faiss.IndexHNSWFlat(dim, M, metric)      ← 建一个标准 HNSW 索引
  │   index.hnsw.efConstruction = 200        (此刻 embedding 还全在里面)
  ▼
② index.add(data)  →  faiss.write_index()   ← 落盘成 <name>.index
  │                                            (这一步的文件是"满"的,含全部向量)
  ▼
③ 写 <name>.ids.txt                          ← FAISS 整数 label → passage ID 映射
  │
  ▼
④ 分叉:看 is_compact / is_recompute 两个开关
  │
  ├─ is_compact=True ───────► _convert_to_csr(index_file)
  │                              └─ convert_hnsw_graph_to_csr(prune_embeddings=is_recompute)
  │                                   ├─ 图: 原始邻居布局 → CSR(压缩稀疏行)
  │                                   └─ 存储位: 写 NULL_INDEX_FOURCC(丢掉 embedding)
  │
  └─ is_compact=False & is_recompute=True ─► prune_hnsw_embeddings_inplace(index_file)
                                              └─ 保留原始图布局,只把存储位写成 NULL
  │
  ▼
输出: <name>.index(掏空后,只剩图 + 元信息,不含向量)
      + <name>.passages.jsonl(原文) + <name>.meta.json(is_compact/is_pruned 落盘)

注意一个反直觉的点:第 ② 步落盘的 .index 文件其实是"满"的——FAISS 老老实实把所有 embedding 写进去了。LEANN 的省空间不是"从一开始就不写",而是建完之后再回头把 embedding 那一段抠掉、原地替换。这样能复用 FAISS 成熟的 HNSW 建图代码,只在文件格式层做手术。

下面拆开看关键的第 ④ 步。

4. 掏空动作(一):把存储位写成 NULL 标记​

不管走哪条分叉,最终干的事都一样——把文件里那段 embedding 存储数据换成一个"这里是空的"标记。这个标记叫 NULL_INDEX_FOURCC。

FAISS 的索引文件是二进制的,每个组件前面有个 4 字节的 FourCC(四字符码,一个用四个字母当类型标签的整数)。正常的 HNSW 索引在图数据后面会跟一段"storage",FourCC 标着它是个 flat 向量库;LEANN 要做的就是把这个 FourCC 换成 b"null",并且后面不写任何向量字节。

真实定义(convert_to_csr.py:27):

NULL_INDEX_FOURCC = int.from_bytes(b"null", "little")

写文件时的判断非常直白——只要 FourCC 是 NULL,就一个字节的 storage 都不写(convert_to_csr.py:238,write_compact_format):

# 写 storage fourcc(它决定后面怎么读)
f_out.write(struct.pack("<I", storage_fourcc))
# 写压缩后的邻居数据
write_list_vector(f_out, compact_neighbors_data, "i")
# storage 非 NULL 才写向量数据;NULL 就什么都不写
if storage_fourcc != NULL_INDEX_FOURCC and storage_data:
    f_out.write(storage_data)

prune_embeddings=True 时,代码把 output_storage_fourcc 设成 NULL_INDEX_FOURCC、storage_data 设成空 b""(convert_to_csr.py:904):

if prune_embeddings:
    print("   Pruning embeddings: Writing NULL storage marker.")
    output_storage_fourcc = NULL_INDEX_FOURCC
    storage_data = b""

这就是那 184GB 消失的确切位置:原本要写 N×D 个 float32 的地方,现在只留一个 4 字节的 b"null"。

prune_hnsw_embeddings(convert_to_csr.py:408)是这套逻辑的"只裁 embedding、不动图布局"版本:它把索引读进来、原样写回,但两条写路径(compact 走 write_compact_format、非 compact 走 write_original_format)都硬编码传 NULL_INDEX_FOURCC, b""。对外由 prune_hnsw_embeddings_inplace(convert_to_csr.py:987)包一层:写到 .prune.tmp 再 os.replace 原子替换,失败就删临时文件——保证不会留下半截坏文件。

5. 掏空动作(二):把图转成 CSR,顺带裁边​

is_compact=True 时,除了裁 embedding,还多做一件事:把图结构本身也压缩成 CSR(Compressed Sparse Row,压缩稀疏行)格式。这一步在 convert_hnsw_graph_to_csr(convert_to_csr.py:527)里。

5.1 为什么 CSR 省图存储​

先建立直觉。HNSW 是分层图,每个节点在每层有若干条邻居边。FAISS 原始布局给每个节点、每层都预留固定大小的槽位(容量 = 图的 degree,LEANN 默认 M=32),没连满的槽用 -1 占着。稀疏、浪费。

CSR 是稀疏结构的标准省空间表示。核心是只存真实存在的边,用两个指针数组记住"每个节点的边从哪儿到哪儿":

数组存什么类比
compact_neighbors_data把所有节点、所有层的有效邻居首尾拼成一条长数组一本书的正文,连着排
compact_level_ptr每一层的边在上面那条长数组里从哪个下标开始每一层的书签
compact_node_offsets_np每个节点的层指针在 level_ptr 里从哪开始每个节点的目录页码

转换的核心就是把 -1 占位符全丢掉、只保留 >= 0 的真邻居(convert_to_csr.py:818):

level_neighbors_slice = neighbors_np[begin_orig:end_orig]
valid_neighbors_mask = level_neighbors_slice >= 0   # 只要真实邻居
num_valid = np.count_nonzero(valid_neighbors_mask)
if num_valid > 0:
    compact_neighbors_data.extend(level_neighbors_slice[valid_neighbors_mask])

预留但没用的槽位就此消失。图从"固定 M 宽的稀疏矩阵"变成"紧凑变长数组",这是 CSR 省下的部分。

转换后代码还跑一组自检(convert_to_csr.py:838 起):数出来的有效邻居数,要和 compact_neighbors_data 的长度、以及 NumPy 直接 np.sum(neighbors_np >= 0) 的结果三方对上;level_ptr 的末尾指针要等于数据长度。对不上就报错——保证掏空过程没丢边、没错位。

5.2 high-degree preserving pruning 的直觉​

README 把 LEANN 的省空间归给两句话(README:1264):

  • Graph-based selective recomputation: Only compute embeddings for nodes in the search path
  • High-degree preserving pruning: Keep important "hub" nodes while removing redundant connections

第二句是"高度数保留裁剪"。直觉是:图里节点不是平权的——有些节点是"枢纽"(hub),被很多其他节点指着,它们是导航路上的关键中转站;有些边则是冗余的、去掉也不影响能不能走到目标。裁剪时优先保留高度数的枢纽节点及其连接,砍掉冗余边,这样图更小、但可导航性(search 时能走到正确邻居)基本不变。README 强调"No Accuracy Loss"(README:76)正是靠这一点——省的是存储,不是召回。

诚实标注: README 讲清了"保留枢纽、砍冗余边"这个策略意图;但在本章覆盖的 convert_to_csr.py 里,CSR 转换做的是丢弃 -1 空槽这种无损压缩,并没有一段"按度数排序、择优删边"的显式裁剪代码。度数感知的裁边逻辑更可能发生在底层 FAISS/C++ 建图侧(本仓库为二进制后端,Python 侧看不到)。所以这里区分:CSR 掏空 = 无损去空槽(Python 可见);high-degree preserving pruning = 建图策略(README 所述,Python 层不可见,inferred)。

6. 两个开关:is_compact 与 is_recompute​

整条流水线由两个布尔开关控制,语义要分清:

开关管什么True 的效果
is_recompute裁不裁 embedding丢掉向量、查询时重算(省空间的关键)
is_compact图用不用 CSR 紧凑格式图转成 CSR、更省;False 保留原始布局

两者默认都是 True(hnsw_backend.py:52-53,setdefault("is_compact", True) / setdefault("is_recompute", True))——也就是开箱即最省。

6.1 相互约束:非重算必须非紧凑​

两个开关不能随便组合。有一条硬约束:如果不重算(is_recompute=False),就必须用非紧凑存储(is_compact=False)。

道理:CSR 紧凑格式是为"图 + 重算"这套设计的;如果你选择不重算(意味着 embedding 得留着、查询直接读),再套一个丢 embedding 的紧凑格式就自相矛盾。所以代码在两处做自动纠正。

一处在 builder 构造函数(hnsw_backend.py:58):

if not self.is_recompute and self.is_compact:
    # 自动纠正:非重算的 HNSW 必须非紧凑存储
    logger.warning("is_recompute=False requires non-compact HNSW. Forcing is_compact=False.")
    self.is_compact = False
    self.build_params["is_compact"] = False

另一处更早,在 LeannBuilder.__init__(api.py:411),同样把 is_compact 强制成 False 并发 UserWarning。两层都设是为了让 meta 落盘时就一致。

6.2 三种组合的实际形态​

is_recomputeis_compactbuild 走哪条路磁盘上 .index
TrueTrue(默认)_convert_to_csr(prune=True)CSR 图 + NULL storage,最省
TrueFalseprune_hnsw_embeddings_inplace原始图布局 + NULL storage
False(被强制 False)都不走,保留满索引完整图 + 完整 embedding(不省)

对应 build 里的分叉(hnsw_backend.py:102):

if self.is_compact:
    self._convert_to_csr(index_file)          # CSR + 按 is_recompute 决定裁不裁
elif self.is_recompute:
    prune_hnsw_embeddings_inplace(str(index_file))  # 只裁 embedding,不转 CSR

而 _convert_to_csr 把 is_recompute 透传给 prune_embeddings 参数(hnsw_backend.py:114),决定 CSR 转换时要不要顺手把 embedding 也裁掉:

success = convert_hnsw_graph_to_csr(
    str(index_file), str(csr_temp_file), prune_embeddings=self.is_recompute
)

6.3 落盘:meta.json 记住形态​

这两个状态必须写进元数据,否则查询侧不知道该怎么读文件。build 时写进 meta.json(api.py:633):

meta_data["is_compact"] = is_compact
meta_data["is_pruned"] = bool(is_recompute)

注意命名:落盘字段叫 is_pruned(裁没裁 embedding),来源是 is_recompute。查询侧 HNSWSearcher.__init__(hnsw_backend.py:148-150)再把这两个字段读回来配置 C++ 的 HNSWIndexConfig.is_compact / is_recompute——如果一个 pruned 索引却被要求"不重算"搜索,会直接报错(hnsw_backend.py:210,"Recompute is required for pruned/compact HNSW index")。这条搜索侧的链路细节留给 02-search-recompute.md。

7. 巧妙之处(可借鉴)​

  • 建完再掏空,而不是不建。 先让 FAISS 正常建一个满索引落盘,再回头把 embedding 段替换成 NULL 标记。这样完全复用了 FAISS 成熟的 HNSW 建图 + 序列化代码,LEANN 只需在文件格式层做手术,自己不重写建图。见 hnsw_backend.py:89-105。

  • 省空间落在一个 4 字节标记上。 整个"省 97%"的物理实现,最终就是把一段几百 GB 的 storage 换成 b"null" 这 4 个字节 + 后面不写数据(convert_to_csr.py:238)。简单到可以一眼看懂,却是整个项目名字("LEANN")的由来。

  • 原子替换,绝不留坏文件。 掏空写到临时文件(.csr.tmp / .prune.tmp),成功才 shutil.move / os.replace 覆盖原文件,失败就删临时文件并抛错(hnsw_backend.py:118-128、convert_to_csr.py:990-1001)。中途崩溃不会把原索引搞坏。

  • 无损压缩 + 三方自检。 CSR 转换只丢 -1 空槽(无损),转换后用三个独立口径互相印证有效边数(convert_to_csr.py:842-876),错位立即报错。省空间但不敢省正确性。

8. 边界与局限​

  • 省空间的代价是查询算力。 embedding 不存了,每次搜索都要现场过一遍 embedding 模型算路径上节点的向量。没有 GPU / 快速 embedding 时,查询延迟会明显高于"直接读向量"的传统库。这是 selective recomputation 的固有取舍。

  • is_recompute=False 就不省了。 想彻底不重算(查询直接读向量),就退回"完整图 + 完整 embedding"的传统形态,is_compact 被强制 False,失去省空间收益(hnsw_backend.py:58)。省空间和"不重算"二者不可兼得。

  • FourCC 白名单很窄。 转换器只认 INDEX_HNSW_FLAT_FOURCC(b"IHNf",convert_to_csr.py:20/26);遇到 PQ / SQ 等其它 HNSW storage 类型会直接 raise ValueError(convert_to_csr.py:262)。这套掏空逻辑目前只服务 IndexHNSWFlat 一种。

  • 度数感知裁边的真实实现看不到。 如 §5.2 所述,"high-degree preserving pruning"的策略在 README 有明确表述,但 Python 层的 CSR 转换只做无损去空槽;真正按度数择优删边(若有)发生在二进制后端,本仓库源码不可见。

9. 横向对比​

后端存储策略何时用
HNSW(本章)图 + NULL storage,全量重算,省空间最大大多数数据集、极致省空间
DiskANNPQ(乘积量化)压缩向量 + 实时重排,超越内存的数据更大数据、更看重搜索性能
IVF支持原地增删,不重建频繁增量更新

同组各后端的存储/搜索取舍见 03-backends-registry.md;查询侧的 HNSW 遍历 + ZMQ 重算见 02-search-recompute.md;喂进来的 embedding 从哪来见 04-embedding-and-chunking.md。

10. 代码地图(导航索引)​

主题文件路径符号名
build 入口、分叉决策packages/leann-backend-hnsw/leann_backend_hnsw/hnsw_backend.pyHNSWBuilder.build
两开关默认值 + 自动纠正packages/leann-backend-hnsw/leann_backend_hnsw/hnsw_backend.py:58HNSWBuilder.__init__
触发 CSR 转换packages/leann-backend-hnsw/leann_backend_hnsw/hnsw_backend.py:107HNSWBuilder._convert_to_csr
CSR 转换主逻辑packages/leann-backend-hnsw/leann_backend_hnsw/convert_to_csr.py:527convert_hnsw_graph_to_csr
只裁 embedding(不转 CSR)packages/leann-backend-hnsw/leann_backend_hnsw/convert_to_csr.py:408prune_hnsw_embeddings
原子替换封装packages/leann-backend-hnsw/leann_backend_hnsw/convert_to_csr.py:987prune_hnsw_embeddings_inplace
NULL 存储标记常量packages/leann-backend-hnsw/leann_backend_hnsw/convert_to_csr.py:27NULL_INDEX_FOURCC
写 CSR + 判断 NULL storagepackages/leann-backend-hnsw/leann_backend_hnsw/convert_to_csr.py:184write_compact_format
去 -1 空槽的裁边循环packages/leann-backend-hnsw/leann_backend_hnsw/convert_to_csr.py:818convert_hnsw_graph_to_csr(内层)
开关归一化(API 层)packages/leann-core/src/leann/api.py:408LeannBuilder.__init__
is_compact/is_pruned 落盘packages/leann-core/src/leann/api.py:633LeannBuilder(build meta)