[C API] Reuse slots freed by consolidate in svs_index_dynamic_add_points

未關閉
  • 哪裡不對？
#438 0 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 5 天內回覆

還沒有人認領這個 Issue。

評估

難度
4/5
預估耗時
3-5 天
新手友好度
55/100
Issue 類型
缺陷
描述清晰度
描述清楚
活躍度
活躍
技術堆疊
cpp
領域
backend, performance

研究方向

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.

由索引模型根據 Issue 內容生成。

描述

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.

主要語言
C++
星號
241
分支
48
平均合併
4 天 21 小時
30 天內合併 PR
11

環境準備

  • 沒有 Dockerfile 或 Docker Compose 檔案
  • 沒有 Pull Request 範本
  • 閱讀貢獻指南

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

intel/ScalableVectorSearch 的其他 Issue

查看 intel/ScalableVectorSearch 的全部 Issue

相似的 Issue

更多 C++ Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。