Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

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

オープン
  • 何か問題がありますか？
#930 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
68/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
rust
領域
databases, search

調査の方向性

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:

  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.

主要言語
Rust
スター
4.5k
フォーク
603
平均マージ
1日 11時間
マージ済み PR（30日）
56

環境構築

このプロジェクトの環境構築ファイルはまだ確認していません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

ruvnet/RuVector のほかの issue

ruvnet/RuVector の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。