@harperfast/hnsw
持续、渐进、可同时搜索的Node.jsHNSW矢量指数—— 一个本地( Rust) traversal 引擎通过一个内存映射的固定相片图文件.
大多数用于节点的 HNSW 库要么在 JS 对象中保存图表(每次访问费用较低,GC) 或包裹一个没有可持久递增持久性的内膜C++指数。 这个是 围绕不同的合同:
- 文件是索引 . 每个索引一个内存映射的文件:固定大小的节点槽 (量化矢量 + 相邻 id , 页面分组, 这样插槽从不交叉页面 边框),一个内文件上层区域,一个id自由列表,和一个可持久水印. 重新开放是即时的——没有重建,没有侧车.
- 搜索从不触及JS事件循环. 查询在 libuv 线条池上运行 N- API 逐一通过; 反向为零复制, 与 SIMD (AVX2) int8 映射相对 不对称-相距.
- 阅读和写作是真正并行的. 每秒后锁, 没有全局锁 搜索路径。 在1M×768-d(ef 512)的一个Linux盒上测量: 6 300+ 质保单合计 横跨 8 个搜索线索, 而一个写手维持~ 1 100 个插入/s,p50 ≈ 1 ms.
- 索引以核心构建天平.
insertBatch一个N -API用一整块 横跨和扇子 插入在工人线上 在本地模块,关闭 事件回路 – 每秒下方的下方锁是使同时插入安全的地方。 缩放曲线 DESIGN.md 第11节。 。 。 . - 按设计递增. 插入、 更新到原地, 随邻居修复而删除; 删除 iD通过自由列表被再用,所以churn从来没有夸大图表. 逆向溢出 使用覆盖- 意识穿透( 以 Robust- Prune 为界) —— 1M 时的0. 999回放@ 10 (768-d int8,ef 512) 在被校正的高斯-混合体上.
- 内置过滤器 . 允许位集过滤(零回调),或 JS 上游 在输油管批量中通过线程安全功能评估,而转盘则不断扩展 一个忙碌的事件循环 需要投机性的过度拍摄, 从来没有搜索的线条摊位.
- 两种融合模式. 独立( 库会分配 ID并维护图 :
insert编号 :remove编号 :search),或反射(writeNodeRaw编号 :clearNode: 主机应用程序 已经维持了 HNSW 图形镜像并获得本地搜索路径 就是这样 哈波尔 综合起来).
杜可被故意放轻松:文件是msync'd在一个有交易的cadence上 水印,预期的恢复模式是"从水印上重放索引",与 (原始内容存档于2017-10-21). the host's 权威唱片店. 近似指数不需要每个承诺的发音; 他们需要廉价的,有限度的追赶。 见 设计 格式、格式和格式 货币模型、计量基线和每项贸易背后的理由.
安装
npm install @harperfast/hnsw
作为平台专用的预建装订船 optionalDependencies
(单位:千美元)@harperfast/hnsw-<platform>-<arch>[-glibc])为linux-x64,linux-arm64,darwin-arm64,并
(原始内容存档于2019-09-31). win32-x64. 没有发布装订的平台(musl、darwin-x64、win32-arm64)
安装时的源 Rust工具链 确是存在的,确是明显的
否则就出错。 Linux x86 64 是性能目标(AVX2 + 内核锁崩溃恢复);
macOS和Windows是功能性的(没有锁接取——取而代之是受约束的降解).
使用量
const { Plane } = require('@harperfast/hnsw');
// keyCap 40 (min 8): each slot carries up to 40 bytes of the host's key inline (longer keys overflow)
// layer-0 cap: 64 (= 4M for M 16) in general — for these 768-d vectors it stays within 0.35 pt of
// cap 128's recall@10 with a 19% smaller slot; 32 for narrow vectors on a plane that outgrows RAM,
// the smallest slot, but 1.3–2.2 pts below cap 128 under ef 1024 at 4M × 128-d (DESIGN.md §10)
const plane = Plane.create('/data/vectors.hnsw', 768, 64, 10_000_000, 40);
// ... or with the finer storage precision (see below):
// const plane = Plane.create('/data/vectors.hnsw', 128, 32, 10_000_000, 40, undefined, 'int16');
const id = plane.insert(myFloat32Vector, Buffer.from(myRecordKey));
// bulk load: one crossing per chunk, inserted in parallel off the event loop; `ids` is in input
// order, keys are concatenated with SearchHits-style ends. Records the plane cannot hold come
// back in `rejected` (index + code) with 0xFFFFFFFF in their slot; a full plane rejects the
// promise with an error that still carries `ids`.
const { ids, rejected } = await plane.insertBatch(chunkVectors /* count × dims */, chunkKeys, chunkKeyEnds, 8 /* threads */);
// parallel typed arrays, ascending by distance; hit i's key is keys.subarray(keyEnds[i-1] ?? 0, keyEnds[i])
const { ids, distances, keys, keyEnds } = await plane.search(queryVector, 10, 512);
// filtered: allow-bitset over node ids
const allowed = new Uint8Array(Math.ceil(plane.idHighWater() / 8));
// ... set bits ...
const filtered = await plane.search(queryVector, 10, 512, allowed);
// or a JS predicate, batched off the event loop
const predicated = await plane.searchWithPredicate(queryVector, 10, 512, (ids) =>
Uint8Array.from(ids, (id) => (isVisible(id) ? 1 : 0))
);
储存精度
向量被以每个向量对称的尺度来进行定量储存. 默认, 'int8',地图
每个组件改为 max|c|/127 ——每个元素的矢量最大成分的0.8%左右,
它通常足够接近 军衔 候选人但不参加 分数 他们,故叫
通常将返回的命中数与精确的矢量重排. 'int16' 地图到 max|c|/32767
取而代之:~256x更细,每元素约0.03%. 这是否足够接近 以放弃
重新排位是一个关于你的人身和准确预算的问题, 这个包不能
回答这个问题——先用你自己的数据来验证它,然后才停止调整。 费钱
每个插槽再增加一字节——32个顶点+40%,128个暗点(320个~448个B),+89%
1536(1728 ~ 3264 B)——因此适合小到中维度,而int8则保持正确的选择
宽的嵌入,将每个横向扫描的字节翻倍将搜索推入
具有记忆力的制度。 选择被固定在创建中,没有重建就无法改变.
Int16平面搭载了更新的格式版本,因此这个软件包的更古老的构件拒绝打开
a. 而不是误读其槽布局; plane.precision 报告飞机的解码器.
平面是衍生状态; 当主机必须停止维护一个且不能删除文件时
(窗口分享违规情况,而另一个进程则绘制地图), invalidatePlane(path) -或者说
plane.invalidateFile() 通过一个手柄,宿主已经持有——持久地标记它
不可取用:单向带内接合(水印为:0, Plane.open 拒绝)+ fsync'd
<path>.stale 侧车(stalePathFor(path),哪个 open 也拒绝)。 只有当
也没有标记土地。 主机同时删除文件并重建.
完整 API 输入 指数.d.ts。 。 。 .
基准
cargo run --release --bin bench -- 1000000 768 100 512 /tmp/bench.hnsw 64 8 构建 1M ×
768-d 图上的校正高斯混合体, 报告p50/p95/p99, 每期访问费用,
蛮力召回@10,并同时通货通过. 第九个参数选择
储存精度(int8, (中文(简体) ), int16,或 both 建造和测量每平方平面的一平
每个运行先打印出一个内核微基准. 设计工作的数字
(Linux,单框):p50 0.75 ms,0.33 μs/visit, recept@10 0.999 —~9× 墙钟和
~13× 优化纯JS执行同一图的每个访问费用
同样的召回.
状态
取自哈珀向量-索引引擎;格式 (v8 for int8平面,v9 for int16) 和API年轻,可能 用一个版本凸起+再索引来更改(旧格式版本无法打开;重建). 路线图:预建, 二进制量化槽格式 (~4×更小的曲面平面), Matryoshka 维度截取, 角增生, 指数 用本地的顶- k 合并来切片 .
许可证
阿帕奇 - 2.0