ruvector-delta-index: delete() of the entry point leaves search anchored to a phantom node — the rest of the graph becomes unreachable
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
调研方向
从 crates/ruvector-delta-index/src/lib.rs 开始，跟踪 DeltaHnsw::delete()、search_layer、connect_node 和 random_level()。为搜索前删除入口点，以及删除后再插入这两种情况添加使用固定 seed 的回归测试覆盖；完成标准是不存在空 ID 或无限距离的结果，存活节点仍然可达，并且能够找到新节点。另外，验证 issue 中描述的 random-level 边界情况。
由索引模型根据 Issue 内容生成。
描述
Defect
DeltaHnsw::delete() (crates/ruvector-delta-index/src/lib.rs) blanks the node (id = String::new(), clears vector and neighbors) and removes it from every other node's neighbor list — but never touches entry_point. If the deleted node is the entry point, every subsequent search starts from a node whose id is empty, whose distance is defined as f32::MAX, and whose neighbor lists are empty.
Verified failure (probe run on the post-#825 code)
let mut index = DeltaHnsw::new(4, DeltaHnswConfig::default());
index.insert("a", vec[1.0, 0.0, 0.0, 0.0]).unwrap();
index.insert("b", vec[0.0, 1.0, 0.0, 0.0]).unwrap();
index.delete("a").unwrap(); // "a" is the entry point
let results = index.search(&[1.0, 0.0, 0.0, 0.0], 2).unwrap();
Observed output:
result: id="" dist=340282350000000000000000000000000000000
Two distinct consequences, both worse than a stale row:
- Phantom results. The deleted node is returned as a
SearchResultwith an empty id andf32::MAXdistance —search_layerunconditionally seeds its result heap with the start node. - Total recall loss. Because
delete()cleared the deleted node's own neighbor lists, the entry point now has no outgoing edges.greedy_search/search_layercannot leave it, so every live vector in the index becomes unreachable. In the probe, "b" is simply gone: the search returns only the phantom.
The same dangling reference corrupts inserts: connect_node navigates from entry_point, so new nodes connect to nothing until one of them happens to be assigned a level higher than the dead entry point's.
Suggested fix
In delete(), after blanking the node, check entry_point:
- if the deleted index is the entry point, re-seat it on any live node (e.g. scan for the highest-level node with a non-empty vector), or
Noneif the index is now empty; - have
search_layerskip nodes with empty vectors when seeding/collecting results (defense-in-depth — tombstones should never be returnable); - regression tests: delete-the-entry-point then search (must return only live ids, and must reach all live nodes), and delete-then-insert (new node must be reachable).
Related, same file
random_level() computes (-r.ln() * level_mult).floor() as usize with r: f64 = rng.gen() in [0, 1). At r == 0.0 (probability ~2⁻⁵³ per insert) -ln(0) = +inf, the cast saturates to usize::MAX, and HnswNode::new's vec[SmallVec::new(); level + 1] overflows/aborts. A r.max(f64::MIN_POSITIVE) clamp (or capping the level at e.g. 64) closes it. Worth folding into the same fix PR.
Found during the ADR-340 hardening pass (the #825 fix touched the adjacent code). Per ADR-340 invariant 6, the regression tests should use a seeded RNG.
- 主要语言
- Rust
- 星标
- 4.5k
- 派生
- 603
- 平均合并
- 1 天 11 小时
- 30 天内合并 PR
- 56
环境准备
我们还没有检查这个项目的环境配置文件。先看它的 README，通用步骤见我们的新手贡献指南。
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
ruvnet/RuVector 的其他 Issue
-
难度 2/5 1-3 小时 新手友好度 76/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 76/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 83/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 74/100
维护者通常 1 天内回复
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 78/100
software-challenge/player_rust#22 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 68/100
foundry-rs/foundry#17175 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 88/100
维护者通常 1 天内回复
-
state:triage-needed
难度 2/5 1-3 小时 新手友好度 72/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 76/100
github/copilot-sdk#2793 ·
维护者通常 1 天内回复