跳到主要内容

底层引擎:C++ ANN 索引 + KV 存储(及 Rust 绑定)

30 秒导读: 前面几章讲的 viking:// 范式、分层建树、目录检索、RAGFS,最终"算距离、存字段、落磁盘"这些脏活,都交给一个用 C++ 写、编成 Python 扩展的原生引擎。本章钻到全篇最深一层:这块引擎里到底装了什么(一个 flat 暴力近邻索引 + 两种 KV 存储 + 一套行编码),以及它怎么经 abi3 稳定 ABI 被 Python 调用。

本章是 存储层:VikingFS 门面、RAGFS 与向量库 的"地板下面"。第 04 章讲的 Python 向量库 openviking/storage/vectordb/ 是门面;这里讲它调用的 src/ C++ 原生代码是引擎。两者之间隔着一层 abi3 胶囊边界,本章会把这层边界讲透。

1. 这是什么(零基础也能懂)​

一句话定义: 这是 OpenViking 的"原生底座"——一个 C++ 写的向量检索 + 键值存储引擎,编译成 .so 后当作普通 Python 模块被上层导入。

它解决什么问题。 向量检索的内层循环是"拿一个 query 向量,和库里成千上万个向量逐一算距离,取最近的 K 个"。这种密集浮点计算如果用 Python 跑,会慢到不可用。于是 OpenViking 把这一层用 C++ 实现,并针对 CPU 的 SIMD 指令(一条指令同时算 8/16 个浮点)做了优化。

它包含哪几块。

子系统干什么目录
ANN 索引引擎存向量、算距离、取 top-ksrc/index/
KV 存储层存元数据行,内存态或落 leveldbsrc/store/
公共设施二进制 I/O、JSON、排序、日志src/common/
abi3 绑定把上面三块暴露成 Python 函数src/abi3_engine_backend.cpp

用起来什么样。 上层 Python 完全感知不到这是 C++。它只是 import 一个模块,new 一个引擎对象,喂请求、拿结果:

# 示意,非源码 —— 上层 IndexEngineProxy 内部就是这么用引擎的
import openviking.storage.vectordb.engine as engine

eng = engine.IndexEngine('{"vector_index_type":"flat","dimension":768,...}')  # 建一个 flat 索引
req = engine.AddDataRequest()
req.label, req.vector = 42, [0.1, 0.2, ...]     # 一条数据 = 一个 id + 一个向量
eng.add_data([req])                              # 落进 C++ buffer

真实入口在 openviking/storage/vectordb/index/local_index.py:72,那里 IndexEngineProxy 就是 self.index_engine = engine.IndexEngine(index_path_or_json)。

一句话直觉。 把这层想成数据库的"存储引擎"(像 MySQL 之于 InnoDB):上层管语义、管协议、管虚拟文件系统;这层只管"向量摆哪、字节怎么排、距离怎么算最快"。

2. 顶层全景(这层大概怎么转)​

怎么读下面这张图: 从上到下是调用深度。虚线是那条最关键的"语言边界"——上面是 Python,下面是 C++,中间靠 PyCapsule(把 C++ 裸指针包成 Python 能拿的不透明句柄)缝合。

上层门面(第 04 章)  openviking/storage/vectordb/index/local_index.py
        │  engine.IndexEngine(...) / add_data / search / dump
        ▼
Python 薄封装      storage/vectordb/engine/__init__.py     ← 按 CPU 选 SIMD 变体
                  storage/vectordb/engine/_python_api.py  ← 把胶囊包成 IndexEngine 类
· · · · · · · · · · · · · · abi3 语言边界 · · · · · · · · · · · · · ·   ← GIL 在此释放
C 扩展入口         src/abi3_engine_backend.cpp   (_native / _x86_avx2 …)
        │
        ├─► IndexEngine ─► IndexManagerImpl ─┬─► VectorIndexAdapter ─► BruteforceSearch
        │   (index/)                          │        (flat 暴力近邻 + 量化 + SIMD 距离)
        │                                     ├─► ScalarIndex        (字段位图,做过滤)
        │                                     └─► ManagerMeta        (维度/距离/时间戳)
        │
        └─► KVStore ─┬─► VolatileStore   (std::map,纯内存)
            (store/) └─► PersistStore    (leveldb,落盘)
                     └─► BytesRow/Schema (定长+变长行编码)

部件一句话职责:

部件职责真实符号 · 位置
IndexEngine对外门面,转发到 implindex/index_engine.h:14
IndexManagerImpl编排:锁、解析 DSL、拼装过滤+召回index/detail/index_manager_impl.cpp:21
BruteforceSearch真正存向量、算距离、取 top-kindex/detail/vector/common/bruteforce.h:30
ScalarIndex按字段建位图,过滤出候选偏移index/detail/scalar/scalar_index.h:14
VolatileStore / PersistStore两种 KV 后端(内存 / leveldb)store/volatile_store.h:13 · store/persist_store.h:12
BytesRow把一行字段序列化成紧凑字节串store/bytes_row.h:66
abi3 backendPython↔C++ 的胶水与类型转换abi3_engine_backend.cpp:1514

主线走一遍(高层,不进代码): 上层调 search(query, topk, dsl) → abi3 把 Python dict 翻成 C++ SearchRequest、释放 GIL → IndexManagerImpl::search 先解析 DSL 过滤条件、用 ScalarIndex 算出一个"允许命中"的位图 → 把位图交给 BruteforceSearch::search_knn,只对位图内的向量算距离、维护一个大小为 K 的堆 → 结果 labels/scores 回传,abi3 再翻成 Python dict。

注意:索引引擎(index/)和 KV 存储(store/)是两套彼此独立的子系统,只是恰好由同一个 abi3 模块导出。前者服务"向量检索",被上层的 index/ 层用;后者服务"键值元数据",被上层的 store/ 层用。下面分别讲。

3. 核心原理(逐个机制,由浅入深)​

3.1 ANN 索引:一块连续 buffer 上的暴力检索​

要解决的小问题: 怎么在"能增删、能过滤、还要快"的前提下,存一堆向量并找最近邻。

思路。 OpenViking 这一版只实现了一种索引类型:flat(暴力全量扫描,不建图/不分簇)。它不追求"近似",而是把每个向量都比一遍——胜在实现简单、结果精确、增删便宜,适合单机、量级不特别巨大的记忆库场景。IndexManagerImpl 里明确写死:除了 "flat" 一律抛异常(index_manager_impl.cpp:50)。

核心数据结构:一块手工排布的字节数组。 BruteforceSearch 不用 std::vector<Struct>,而是自己 malloc 一整块 data_buffer_,每个元素等宽,内部三段拼接:

一个元素(element_byte_size_ 字节)= 三段紧挨着:
┌────────────────────────┬──────────────┬───────────────────┐
│  编码后的向量           │  label (u64) │  logical_offset(u32)│
│  vector_byte_size_ 字节 │   8 字节      │      4 字节          │
└────────────────────────┴──────────────┴───────────────────┘

布局计算在构造函数里:element_byte_size_ = vector_byte_size_ + sizeof(uint64_t) + sizeof(uint32_t)(bruteforce.h:41)。向量段的宽度由"量化器"决定(见 3.2)。

三套 id 空间——这是最容易绕晕、也最关键的设计。 同一条数据有三个身份,各管一件事:

id谁用它特性由谁维护
label (u64)用户 / 上层业务主键,稳定label_map_: label→物理槽
logical_offset (u32)标量索引 / 位图单调递增、永不复用offset_map_: offset→物理槽
物理下标 indexbuffer 本身删除时会被搬动就是 buffer 里的第几格

为什么要分三层?因为删除用"和最后一格交换再弹出"(swap-remove,bruteforce.h:132 remove_point),物理下标会变,不能拿它当稳定 id;而标量索引的位图必须用一个稳定 id 当行号,于是引入永不复用的 logical_offset。IndexManagerImpl::register_label_offset_converter_(index_manager_impl.cpp:110)就是给标量索引注册一个"label→offset"的回调,把两套 id 桥起来。

增: add_point(bruteforce.h:66)。已存在的 label 就地覆盖;新 label 则在 buffer 尾部追加,分配一个新的 logical_offset,登记进两张 map。容量不够就 resize_buffer(current_count_*2+1)(倍增 realloc)。

删: remove_point(bruteforce.h:132)。把要删的槽用最后一个槽的数据覆盖,再修正被搬来的那条的两张 map,current_count_--。O(1) 删除,代价是物理顺序被打乱(所以才需要 logical_offset)。

查: search_knn(bruteforce.h:184)。核心是一个大小为 K 的最小堆(std::priority_queue + std::greater),堆顶是"当前 top-k 里最差的那个";每算完一个距离,若堆没满就塞,满了且比堆顶好就替换堆顶:

// bruteforce.h:222 —— 维护 top-k 的经典手法
if (pq.size() < k) {
  pq.emplace(dist, label);
} else if (dist > pq.top().first) {   // 注意:统一成"越大越好"
  pq.pop();
  pq.emplace(dist, label);
}

有过滤位图时走 else 分支:不再遍历全量,而是 filter_bitmap->get_set_list(offsets) 拿到允许的 logical_offset 列表,经 offset_map_ 找到物理槽再算(bruteforce.h:235)。

一个统一化的巧思:分数方向。 内积(IP)天然"越大越相似",L2 距离却"越小越近"。为了让上面那个堆逻辑对两种度量都成立,L2 情况下把原始距离翻成 1 - dist(compute_score,bruteforce.h:423,由 reverse_query_score_ 控制),于是全程"分数越大越好",召回排序和堆比较不用为度量分叉。

3.2 距离核与量化:SIMD 在哪、int8 怎么压​

距离核。 距离函数不是普通 for 循环,而是按 CPU 能力选 SIMD 实现。以 L2 为例,space_l2.h 里对同一个 l2_sqr 写了五个版本——x86 三路 SIMD(AVX512/AVX/SSE)+ ARM NEON + 标量兜底,构造 L2Space 时按编译宏挑一个(space_l2.h:143 起的 #if defined(OV_SIMD_NEON) … 一串 #elif,NEON 优先、层层回退到标量):

宏实现一次处理
OV_SIMD_NEONl2_sqr_neon(:128,ARM,转调 KRL 库)一批(KRL 向量化)
OV_SIMD_AVX512l2_sqr_avx512(:25)16 个 float
OV_SIMD_AVXl2_sqr_avx(:54)8 个 float
OV_SIMD_SSEl2_sqr_sse(:92)4 个 float
(都没有)l2_sqr_ref(:11)标量,1 个

表按源码 dispatch 的判定顺序排:NEON 走 #if、x86 三路和标量走后续 #elif(space_l2.h:143-152)。x86 机器上 OV_SIMD_NEON 不定义,自然落到 AVX512→AVX→SSE→ref。

这里埋着一个关键工程决策:同一份 C++ 源码被编成多个 SIMD 变体(见 3.3 和第 4 节)。宏的判定在 vector_base.h:9-32(x86 检测 :10-23、ARM NEON 检测 :24-32)。

量化器。 向量段可以存原始 float32,也可以存压缩后的 int8。createQuantizer(quantizer.h:65)按配置二选一:

  • Float32Quantizer:直接 memcpy,每维 4 字节。
  • Int8Quantizer:调 quantize_vector_int8(quantization_int8.h:11)。做法是找该向量绝对值最大值当 scale = max_abs/127,逐维量化到 [-127,127] 的 int8,末尾附上 scale(4 字节),L2 度量下再多存一个 norm_sq(4 字节)。每维压到 1 字节,内存和带宽降到约 1/4,代价是精度损失。

3.3 abi3 边界:C++ 怎么变成 Python 模块​

要解决的小问题: 把 C++ 对象安全地交给 Python 拿着,还要跨 Python 小版本复用同一个 .so,并且不因为持有 GIL 而卡住其它线程。

稳定 ABI(abi3)。 文件开头 #define Py_LIMITED_API 0x030A0000(abi3_engine_backend.cpp:3)把自己限定在 Python 3.10 的"有限 API"里。好处:一个 .so 能被 3.10 及以后的多个 Python 版本加载,不必为每个小版本各编一份。

PyCapsule 当句柄。 C++ 对象(IndexEngine、KVStore、Schema、BytesRow)不暴露内部结构,而是 new 出来后装进一个带名字的胶囊交给 Python,并挂一个析构器负责 delete。例如建引擎:

// abi3_engine_backend.cpp:1164 —— 裸指针进胶囊,Python 只拿到一个不透明句柄
return PyCapsule_New(new vdb::IndexEngine(path_or_json),
                     kIndexCapsuleName, index_capsule_destructor);

胶囊名(如 "openviking.vectordb.IndexEngine",abi3_engine_backend.cpp:24)兼作类型标签:capsule_to_ptr 取指针时会校验名字,防止把 Store 句柄误当 Index 用。

每次真干活都释放 GIL。 所有会阻塞的 C++ 调用都包在 call_without_gil 里(abi3_engine_backend.cpp:50),它 PyEval_SaveThread() 放锁、跑 C++、再 PyEval_RestoreThread()。这样一个线程在算距离时,别的 Python 线程还能跑:

// abi3_engine_backend.cpp:1245 —— search 期间不占着 GIL
const vdb::SearchResult result =
    call_without_gil([&]() { return engine->search(request); });

导出面。 底部 kModuleMethods(abi3_engine_backend.cpp:1514)登记了全部 _index_engine_*、_store_*、_bytes_row_* 函数;模块初始化时挂一个常量 _ENGINE_BACKEND_API = "abi3-v1"(abi3_engine_backend.cpp:1585),Python 侧靠它识别"这是新式 abi3 后端"。

Python 侧的两段封装。

  1. engine/__init__.py 是运行时选择器:探测 CPU,在 _x86_avx512 / _x86_avx2 / _x86_sse3 / _native 里挑一个能用的 .so 加载(_select_variant),挑不到就返回一个"缺失符号"占位对象而非直接崩。
  2. engine/_python_api.py::build_abi3_exports(第 414 行)把胶囊函数包装成友好的类:IndexEngine.search(req) 内部就是 backend._index_engine_search(self._handle, req) 再 SearchResult.from_backend(...)。上层拿到的就是普通 Python 类。

一个容易忽略的细节:同名的纯 Python 兜底。 _python_api.py 里还有一份纯 Python 实现的 Schema/BytesRow(第 72、139 行),字节布局和 C++ 版逐字节对齐(同样的 1 字节头 + 定长区 + 变长区)。当原生后端缺失时用它兜底,保证行为一致、只是慢。

4. 深入实现:KV 存储层​

存储层和索引引擎并列,是另一套独立子系统。它就是一个抽象 KV 接口加两种实现,再加一套行编码。

抽象接口 KVStore。 六个纯虚方法(store/kv_store.h:10):exec_op(批量增删)、get_data、put_data、delete_data、clear_data、seek_range(前缀区间扫描)。

两种实现,取舍如下:

VolatileStorePersistStore
底座std::map<string,string>leveldb
落盘不落,进程退出即失落磁盘,WriteOptions.sync=true 强同步
并发shared_mutex,读并发写独占交给 leveldb 自身
区间扫描lower_bound 遍历leveldb Iterator::Seek
位置store/volatile_store.cppstore/persist_store.cpp

PersistStore 值得看的两点:读用快照(GetSnapshot,persist_store.cpp:35)保证一次批量 get 看到一致视图;所有写走 WriteBatch 且 sync=true(persist_store.cpp:59),牺牲吞吐换持久性——记忆库不能因宕机丢数据。

行编码 BytesRow。 把一行"字段名→值"压成一个紧凑字节串。规则:

一行序列化后 = 头(1B) + 定长区 + 变长区
┌──────┬───────────────────────────┬──────────────────────────┐
│字段数 │ 定长区:每个字段按 id 顺序   │ 变长区:string/list 的实际  │
│ 1B   │  · 定长类型直接放值          │  内容,定长区里存一个 u32    │
│      │  · 变长类型放一个 u32 偏移   │  偏移指过来                 │
└──────┴───────────────────────────┴──────────────────────────┘

Schema 构造时要求字段 id 从 0 连续到 N-1(bytes_row.cpp:33),并按 id 顺序算好每个字段在定长区的 offset。serialize 分两趟:第一趟量出变长区总长、定好每个变长字段的偏移;第二趟把定长值和变长内容写进 buffer(bytes_row.cpp:100)。deserialize_field 反过来读,且每一步都带边界检查,越界就退回默认值而不是崩(bytes_row.cpp:322),因为字节串可能来自旧 schema 或损坏数据。支持九种类型(FieldType,bytes_row.h:16),含三种 list。

这套编码为什么不用 protobuf/json?因为它是"schema 已知、海量小行、要快"的场景:定长字段零解析开销、变长字段一次偏移跳转,比通用序列化省得多。

5. 巧妙之处(可借鉴的技术)​

  • 三套 id 空间解耦"稳定引用"与"物理搬动"。 用户拿 label、位图用永不复用的 logical_offset、buffer 内部用会被 swap 的物理下标,让 O(1) 删除和稳定过滤位图共存。bruteforce.h:110-122。
  • 分数方向统一。 L2 用 1-dist 翻向,让"越大越好"的堆逻辑对 IP/L2 通吃,消掉度量分支。bruteforce.h:423。
  • 一份源码、多份 SIMD 二进制、运行时选择。 编译期按 -msse3/-mavx2/-mavx512 各出一个 abi3 .so(src/CMakeLists.txt:263-285),运行时 engine/__init__.py 按 CPU 能力挑最优、挑不到降级——兼容老 CPU 又不牺牲新 CPU 的速度。
  • 胶囊名当类型标签 + 每调用释放 GIL。 既防止句柄张冠李戴,又让原生计算不阻塞其它 Python 线程。abi3_engine_backend.cpp:442、:50。
  • C++ 与纯 Python 行编码逐字节对齐。 原生不可用时无缝降级,格式不变。_python_api.py:139 vs store/bytes_row.cpp。

6. 边界与局限(诚实)​

  • 只有 flat 暴力索引。 没有 HNSW/IVF 等近似索引;非 "flat" 直接抛异常(index_manager_impl.cpp:50)。查询是 O(N·dim),数据量很大时线性变慢——这是精确与简单的取舍,不是 bug。
  • 索引整库常驻内存。 data_buffer_ 是一整块 malloc,容量倍增增长;超大库会受单机内存约束。持久化靠 dump/load 全量读写目录(index_manager_impl.cpp:372)。
  • 写路径全局独占锁。 add_data/delete_data 用 unique_lock(index_manager_impl.cpp:297),写期间读也被挡;为强一致牺牲写并发。
  • string 字段上限 65535 字节。 超了抛 invalid_argument(bytes_row.cpp:127),因为变长字段长度用 u16 存。
  • 代码里看不出:分布式/多副本一致性——这层就是单机引擎,复制与分片(若有)在更上层或另有组件,本仓 src/ 内无实现。

7. 代码地图里的顶端:Rust CLI 的位置​

代码地图另有一个最上层入口——Rust 写的 ov 命令行,在 crates/ov_cli/。它和本章的 C++ 引擎不在一条调用链上:CLI 通过 HTTP/客户端与上层服务交互(crates/ov_cli/src/client.rs、base_client.rs),把子命令分发给 commands/(chat.rs、search.rs、filesystem.rs…,见 commands/mod.rs),并带一套 TUI(tui/)。

也就是说全局有两条原生代码路径,互不穿透:

用户 CLI  →  crates/ov_cli (Rust)  →  HTTP  →  上层 Python 服务 ─┐
                                                                ├─► C++ 引擎(本章)
上层 Python 直接 import  ──────────────────────────────────────┘   经 abi3

CLI 的具体交互不在本章范围,这里只在代码地图上给它定个位:它是"顶端入口",引擎是"底层地板"。

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

用符号名 grep 定位比行号更抗漂移。

主题文件关键符号
索引对外门面src/index/index_engine.h · .cppIndexEngine
索引编排(锁/DSL/召回)src/index/detail/index_manager_impl.cppIndexManagerImpl::search · add_data · register_label_offset_converter_
flat 暴力检索核心src/index/detail/vector/common/bruteforce.hBruteforceSearch::search_knn · add_point · remove_point
索引适配器src/index/detail/vector/vector_index_adapter.hVectorIndexAdapter · BruteForceIndex
请求/结果结构体src/index/common_structs.hAddDataRequest · SearchRequest · SearchResult
SIMD 距离核src/index/detail/vector/common/space_l2.h · vector_base.hL2Space · l2_sqr_neon · l2_sqr_avx512 · MetricFunc
量化器src/index/detail/vector/common/quantizer.h · quantization_int8.hcreateQuantizer · quantize_vector_int8
索引元数据src/index/detail/meta/vector_index_meta.hVectorIndexMeta · BruteForceMeta
标量过滤索引src/index/detail/scalar/scalar_index.hScalarIndex::add_row_data · get_field_sets
KV 抽象接口src/store/kv_store.hKVStore
内存 / 持久 KVsrc/store/volatile_store.cpp · persist_store.cppVolatileStore · PersistStore
行编码src/store/bytes_row.h · .cppSchema · BytesRow::serialize · deserialize_field
abi3 绑定入口src/abi3_engine_backend.cppcall_without_gil · py_new_index_engine · kModuleMethods
构建多 SIMD 变体src/CMakeLists.txtov_add_python_backend · ov_get_x86_variant_flags
Python 变体选择器openviking/storage/vectordb/engine/__init__.py_select_variant · _load_backend
Python 类封装 + 纯 Py 兜底openviking/storage/vectordb/engine/_python_api.pybuild_abi3_exports · BytesRow(纯 Python)
上层调用点(承接 04)openviking/storage/vectordb/index/local_index.pyIndexEngineProxy
顶端 Rust CLIcrates/ov_cli/src/main.rs · commands/mod.rsmain · commands