Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

ruvector-delta-index: delete() of the entry point leaves search anchored to a phantom node — the rest of the graph becomes unreachable

Đang mở
  • Có gì không ổn?
#930 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
68/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
rust
Lĩnh vực
databases, search

Hướng nghiên cứu

Bắt đầu trong crates/ruvector-delta-index/src/lib.rs bằng cách lần theo DeltaHnsw::delete(), search_layer, connect_node và random_level(). Thêm coverage hồi quy với seed cố định cho việc xóa entry point trước khi tìm kiếm, và xóa rồi chèn; hoàn tất khi không có kết quả nào có ID rỗng hoặc khoảng cách vô hạn, các node còn hoạt động vẫn có thể truy cập được và các node mới có thể được tìm thấy. Đồng thời xác minh edge case của random-level được mô tả trong issue.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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:

  1. Phantom results. The deleted node is returned as a SearchResult with an empty id and f32::MAX distance — search_layer unconditionally seeds its result heap with the start node.
  2. Total recall loss. Because delete() cleared the deleted node's own neighbor lists, the entry point now has no outgoing edges. greedy_search/search_layer cannot 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 None if the index is now empty;
  • have search_layer skip 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.

Ngôn ngữ chính
Rust
Star
4.5k
Fork
603
Merge trung bình
2 ngày 9 giờ
Pull request đã merge (30 ngày)
34

Chuẩn bị môi trường

Chúng tôi chưa kiểm tra các tệp thiết lập môi trường của dự án này. Hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của ruvnet/RuVector

Tất cả issue của ruvnet/RuVector

Issue tương tự

Thêm issue về Rust

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.