[C API] Reuse slots freed by consolidate in svs_index_dynamic_add_points

Aperta
  • Qualcosa non va?
#438 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 5 giorni

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
55/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
cpp
Ambito
backend, performance

Direzione di ricerca

Read include/svs/index/vamana/dynamic_index.h around add_points, consolidate, and the first_empty_ TODO, then trace the C API add path in bindings/c/src/index_vamana.cpp. Compare the proposed reuse approaches and check how they avoid an O(N) scan per add. Done means consolidated slots are reused through the C API without that per-add scan; review existing dynamic-index tests for coverage.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

Summary

Through the C API, slots freed by svs_index_dynamic_consolidate are never reused by svs_index_dynamic_add_points, so a dynamic index that sees deletes or updates keeps growing until it is compacted. Please make consolidated slots reusable by the C API's add path.

Details (at cde3771)

  • delete_entries marks slots Deleted; consolidate() repairs the graph and turns them Empty (include/svs/index/vamana/dynamic_index.h:1105-1108).
  • add_points looks for Empty slots starting at reuse_empty ? 0 : first_empty_ (dynamic_index.h:772). first_empty_ only moves up (:843) and is reset only by compact() (:992). The constructor carries a TODO about this logic (:369-372).
  • The C++ orchestrator exposes reuse_empty (include/svs/orchestrators/dynamic_vamana.h:80), but the C API's DynamicIndexVamana::add_points calls index.add_points(new_points, ids) without it (bindings/c/src/index_vamana.cpp:187), and svs_index_dynamic_add_points has no way to request it.

So through the C API, consolidation repairs search but doesn't stop growth: every add after a delete appends a new slot.

Measured (valkey-search, ALGORITHM SVS_VAMANA)

2,000 vectors, DIM 128, then 100k updates (each a delete plus an add):

Memory after churn Search latency after churn
No consolidation 104 MiB (from 26 MiB) 3.87 ms
Consolidate only 104 MiB 0.75 ms
Consolidate + compact 26 MiB 0.92 ms

To bound memory we currently run svs_index_dynamic_compact after every consolidation. That copies every live vector and rewrites the graph, under an exclusive lock.

Ask

Let the C API's add path reuse slots that consolidation freed, without an O(N) scan per add. For example:

  1. Have consolidate() lower first_empty_ to the first slot it freed, so the default add_points path reuses them (this looks like what the TODO at :369-372 is about); or
  2. Expose reuse_empty in the C API (a parameter on svs_index_dynamic_add_points, or a dynamic-index option). As implemented it rescans from slot 0 on every add, though, which would cost append-heavy workloads.

With either, valkey-search would consolidate only, and compact only when it wants memory back.

Consumer context

valkey-search builds SVS from the C API submodule, pinned at cde3771. The consolidate + compact workaround is eshenayo/valkey-search#24.

Lingua principale
C++
Stelle
241
Fork
48
Merge medio
4g 21h
PR unite (30g)
11

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di intel/ScalableVectorSearch

Tutte le issue di intel/ScalableVectorSearch

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.