Skip to content
BranchesTags

Repository files navigation

QuantifyWebANN Benchmark

量化已足够：端侧向量搜索的简洁高效方案

基于 Int8 量化实现 4x 内存压缩，使大规模向量索引完全可以放入浏览器内存。实验表明，简单全内存量化方案已能满足端侧性能需求，复杂的磁盘 IO 调度策略带来的收益有限，而工程复杂度成本过高。

🎯 核心洞察

简洁高效的 DiskANN 模式：量化 + HNSW + Reranking

在内存受限的端侧场景下，仿照 DiskANN 思路的量化索引 + 图搜索 + 精确重排序是一种简洁而有效的架构模式：

方案 内存占用 延迟 (p99) Recall@10 工程复杂度
✅ 量化 + HNSW + Reranking ~25% (Int8 4x压缩) ~10ms 97-99% 低
⚠️ WebANNS (20% 内存占用) 20% ~400ms ~95% 高

核心观点:

  • 高维向量的 ANNS 任务中，量化 + Reranking 对 Recall 影响很小（实测保持 97-99%）
  • Int8 量化将内存压缩 4x，配合 WASM SIMD128 加速，延迟稳定在 10ms 级别
  • 相比需要复杂缓存调度的磁盘懒加载方案，这种模式工程简单、性能足够好

🏗️ 技术架构

┌─────────────────────────────────────────────────────────────────────┐
│                        Search Pipeline                              │
├─────────────────────────────────────────────────────────────────────┤
│                                                                     │
│  ┌──────────────────┐    ┌──────────────┐    ┌──────────────┐      │
│  │ Stage 1          │    │ Stage 2      │    │ Stage 3      │      │
│  │ WASM Search      │ -> │ IO Fetch     │ -> │ Reranking    │      │
│  │ (Int8 HNSW)      │    │ (IndexedDB)  │    │ (Float32)    │      │
│  │ C++ + SIMD128    │    │ 批量读取     │    │ 精确距离     │      │
│  │ ~1.5ms (100K)    │    │ ~0.4ms (20个)│    │ ~0.02ms      │      │
│  └──────────────────┘    └──────────────┘    └──────────────┘      │
│                                                                     │
│  Key: • WASM 引擎使用 SIMD128 向量化指令，实现极速距离计算          │
│       • Disk IO 仅发生在 Stage 2，且仅批量读取候选向量             │
│       • IndexedDB 使用单事务并行 get()，优化 I/O 性能               │
│                                                                     │
└─────────────────────────────────────────────────────────────────────┘

📊 内存效率

数据集 原始 (Float32) 量化 (Int8) 压缩比
50K × 128d 24.4 MB 6.1 MB 4x
480K × 768d 1.4 GB 350 MB 4x
Wiki-480K (7.5GB) 7.5 GB 1.8 GB 4x

关键洞察： Int8 量化后，Wiki-480K 数据集完全可以放入 WASM 的 4GB 线性内存！ 而如果使用 RabitQ 一类的算法/32 甚至更高的量化 + reranking 的做法可以实现更夸张的压缩比， 由于瓶颈在外部的访存， 看起来大量的 reranking 是完全可以接受并且很不错的做法。

🚀 快速开始

1. 下载原始数据集

📦 下载链接: Google Drive - PQWebANN Datasets

从 Google Drive 下载 .jsonl 格式的原始数据文件，例如：

  • arxiv_1k.jsonl
  • arxiv_100k.jsonl
  • finance_13k.jsonl
  • wiki_60k.jsonl
  • wiki_480k.jsonl

注意: .jsonl 文件包含原始向量数据和元数据。索引文件 (.index, .vectors, .queries, .gt, .meta) 需要通过步骤 4 的构建器生成。

2. 安装与运行

# 安装依赖
npm install

# 启动开发服务器
npm run dev

# 构建生产版本
npm run build
npm run preview

3. 编译 WASM 模块 (可选)

如果您修改了 C++ 代码或想重新编译 WASM：

cd src/wasm
./build.sh

要求: 需要安装 Emscripten

4. 生成预构建索引

使用 C++ 离线索引构建器从 .jsonl 文件生成预构建索引：

cd offline_builder
mkdir build && cd build

# 编译构建器
cmake ..
make

# 从 .jsonl 生成索引
./build_index \
  --input /path/to/arxiv_100k.jsonl \
  --output ../../public/prebuilt/arxiv_100k \
  --quantization int8 \
  --M 16 \
  --ef-construction 200

参数说明:

  • --input: 输入的 .jsonl 文件路径
  • --output: 输出文件前缀（会在 public/prebuilt/ 生成多个文件）
  • --quantization: 量化类型
    • int8: Int8 量化 (推荐，4x 压缩)
    • int4: Int4 量化 (8x 压缩，精度略降)
    • float32: 无量化 (基准对比)
  • --M: HNSW 连接度 (默认 16，越大召回率越高但内存占用越大)
  • --ef-construction: 构建时的 ef 参数 (默认 200，越大构建越慢但质量越高)

生成的文件:

public/prebuilt/
├── arxiv_100k_int8.index     # HNSW 图结构 + 量化向量
├── arxiv_100k_int8.vectors   # 原始 Float32 向量 (用于 reranking)
├── arxiv_100k_int8.queries   # 查询向量
├── arxiv_100k_int8.gt        # Ground truth (正确答案)
└── arxiv_100k_int8.meta      # 元数据 (维度、向量数等)

批量生成示例:

使用提供的批量构建脚本可一次性生成所有数据集的多种量化版本:

# 使用自动化批量构建脚本 (推荐)
bash scripts/build_all_indices.sh

该脚本会自动:

  • 检查并构建 offline_builder
  • 为每个数据集生成 Int8、Int4、Float32 三种量化版本
  • 清理旧索引
  • 显示详细的构建进度和文件大小

手动生成单个索引:

# 如需手动控制参数
./build_index \
  --input /path/to/arxiv_100k.jsonl \
  --output ../../public/prebuilt/arxiv_100k \
  --quantization int8 \
  --M 16 \
  --ef-construction 200

5. 运行自动化基准测试

# 完整测试 (所有预构建索引)
npm run benchmark -- --port 4173

# 快速测试 (仅 3 个小数据集)
npm run benchmark -- --quick --port 4173

# 测试特定索引
npm run benchmark -- --index arxiv_100k_int8 --port 4173

注意: 基准测试前请先运行 npm run build && npm run preview

📁 项目结构

├── src/
│   ├── wasm/
│   │   ├── hnsw.cpp              # C++ HNSW 实现 (SIMD128 优化)
│   │   └── build.sh              # Emscripten 编译脚本
│   ├── lib/
│   │   ├── IndexManager.js       # JS HNSW 索引管理（备用）
│   │   ├── USearchAdapter.js     # WASM 桥接层
│   │   ├── StorageManager.js     # IndexedDB 存储管理
│   │   ├── PrebuiltIndexLoader.js # 预构建索引加载器
│   │   └── BenchmarkPipeline.js  # 三阶段搜索流水线
│   ├── main.js                   # 应用入口
│   └── style.css                 # 样式
├── public/
│   ├── hnsw.wasm                 # 编译后的 WASM 模块
│   ├── hnsw.js                   # WASM 胶水代码
│   └── prebuilt/                 # 预构建索引数据集
├── scripts/
│   └── auto_benchmark.js         # Puppeteer 自动化测试
└── offline_builder/              # C++ 离线索引构建器

🔬 三阶段搜索流水线

Stage 1: WASM Search (Int8 量化 HNSW)

  • 引擎: C++ 编译的 WASM 模块，启用 SIMD128 指令集
  • 操作: 在内存中进行全量图遍历，查询向量量化为 Int8
  • 输出: Top-K × 2 候选 ID (例如 Top-10 需要检索 20 个候选)
  • 典型延迟: ~1.5ms (100K 向量), ~0.5ms (1K 向量)

Stage 2: IndexedDB Batch Fetch

  • 策略: 单事务 + 并行 get() 请求
  • 操作: 仅读取候选向量的原始 Float32 数据
  • 优化:
    • ✅ 直接存储 Float32Array（避免 Array.from() 转换）
    • ✅ 禁用内存缓存（测试真实磁盘 I/O）
    • ✅ 批量读取，零拷贝
  • 典型延迟: ~0.4ms (20 个向量)

Stage 3: Exact Reranking

  • 算法: 精确 L2 距离计算 (Float32)
  • 操作: 对候选向量重排序，返回最终 Top-K
  • 典型延迟: ~0.02ms (重排 20 个向量)

📈 两种架构对比

指标 全内存量化方案 磁盘懒加载方案
索引存储 内存 (Int8) 磁盘 (Float32)
图遍历 IO 0 次 每次 hop 都读取
距离计算 IO 0 次 每次计算都读取
重排序 IO ~200 次 N/A
总 IO 次数 ~200 数千次
工程复杂度 简单 复杂（需要缓存策略）

🛠️ 技术栈

  • C++ / Emscripten - WASM 编译工具链
  • WASM SIMD128 - 向量化指令集 (4x Float32 并行, 16x Int8 并行)
  • Vite - 现代前端构建工具
  • Vanilla JS - 无框架依赖，轻量高效
  • IndexedDB - 浏览器持久化存储
  • HNSW - Hierarchical Navigable Small World 图索引算法
  • Int8/Int4 量化 - 4x-8x 内存压缩
  • Puppeteer - 自动化浏览器测试

📝 关键代码设计

WASM SIMD 距离计算 (C++)

#ifdef __wasm_simd128__
// Int8 向量化距离计算 - 一次处理 16 个元素
v128_t sum = wasm_i32x4_const_splat(0);
for (int i = 0; i <= dim - 16; i += 16) {
    v128_t a = wasm_v128_load(vec_a + i);
    v128_t b = wasm_v128_load(vec_b + i);
    
    // 扩展为 16-bit，避免溢出
    v128_t a_lo = wasm_u16x8_extend_low_u8x16(a);
    v128_t diff_lo = wasm_i16x8_sub(a_lo, b_lo);
    
    // 平方并累加到 32-bit
    v128_t sq = wasm_i32x4_dot_i16x8(diff_lo, diff_lo);
    sum = wasm_i32x4_add(sum, sq);
}
#endif

StorageManager 优化 (JavaScript)

// 批量读取优化 - 单事务并发请求
async batchFetch(ids) {
  const transaction = this.db.transaction([STORE_NAME], 'readonly');
  const store = transaction.objectStore(STORE_NAME);
  
  // 并发发起所有请求，不要循环 await！
  for (const id of ids) {
    store.get(id).onsuccess = (e) => {
      // 直接使用 Float32Array，零拷贝
      const vec = e.target.result.vector; // 已经是 Float32Array
      results.set(id, vec);
    };
  }
}

预构建索引加载 (零拷贝)

// 直接将二进制数据传递给 WASM，避免 JS 解析开销
const graphBuffer = new Uint8Array(buffer, offset, graphSize);
await wasmAdapter.loadIndex({
  quantizedVectors,  // Int8Array
  graphBuffer,       // 原始二进制图结构
  scales,            // Float32Array
  offsets            // Float32Array
});

🎓 学术贡献与实验结论

本项目通过实现和基准测试证明：

核心发现

  1. Int8 量化 + SIMD 足够高效

    • 不需要复杂的 PQ (Product Quantization) 训练
    • SIMD128 指令集实现向量化距离计算
    • 召回率保持在 97-99% (Recall@10)

  2. WASM 性能突破内存墙

    • 现代浏览器 WASM 线性内存可达 4GB
    • Int8 量化使 480K×768d 数据集从 1.4GB 压缩至 350MB
    • 完全消除图遍历阶段的磁盘 I/O

  3. IndexedDB 批量优化有效

    • 单事务 + 并行 get() 策略
    • 直接存储 TypedArray，避免序列化开销
    • 20 个向量的批量读取仅需 ~0.4ms

  4. 简洁架构足以满足需求

    • 三阶段流水线清晰易懂
    • 无需缓存策略、页面调度等复杂机制
    • 工程简单、易于维护和扩展

基准测试数据 (预览)

数据集 向量数 维度 WASM (ms) IO (ms) 总延迟 (ms) Recall@10
ArXiv-1K 1,000 768 0.5 0.3 0.8 99.2%
ArXiv-100K 100,000 768 1.5 0.4 1.9 97.9%
Wiki-60K 60,000 768 1.2 0.4 1.6 98.5%

配置: Search K=20, Rerank K=10, SIMD128 启用, Cache 禁用

架构方案对比总结

指标 量化全内存方案 磁盘懒加载方案
索引存储 内存 (Int8 WASM) 磁盘 (IndexedDB)
图遍历 I/O 0 次 每次 hop 都需要
距离计算加速 SIMD128 JavaScript 标量
重排序 I/O 20-200 次批量读取 N/A
平均延迟 ~2ms ~200-500ms
工程复杂度 简单 复杂 (需缓存/调度)

📄 License

MIT

核心结论：量化已足够！使用 WASM + SIMD + Int8 量化，简单架构即可实现高效端侧向量搜索。

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

1 star

Watchers

0 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages