Concurrent index: reverse-edge lists grow under update churn until consolidation

Đang mở
  • Có gì không ổn?
#469 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 5 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
42/100
Loại issue
Lỗi
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
cpp
Lĩnh vực
databases

Hướng nghiên cứu

Read include/svs/concurrent/reverse_edges.h and include/svs/concurrent/graph.h, especially replace_node_locked and the update_entries path, then inspect the C API memory accounting in bindings/c/src/svs_c.cpp. Reproduce the reported single-threaded update churn and track reverse-edge memory; done means reverse-edge storage stays bounded under repeated slot reuse without breaking concurrent writers or edge repair.

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

Mô tả

Summary

With SVS_SYNC_KIND_FINE_GRAIN, the concurrent index's reverse-edge index
(ReverseEdges, include/svs/concurrent/reverse_edges.h) only ever gains
entries during inserts and updates. Stale entries are pruned only by
consolidation. A caller that reuses deleted slots with
svs_index_dynamic_update_points + svs_index_dynamic_replace_id (#467, #468)
rarely needs to consolidate, so these lists keep growing. The growth shows in
svs_index_get_memory_usage and in graph_bytes of
svs_index_get_memory_breakdown, because the C API adds reverse_edges_bytes
to graph_bytes (bindings/c/src/svs_c.cpp:678).

Where it comes from

The code below is on main (added in #369) and unchanged by #467 or #468;
line numbers are at 9330e49, the head of #468.

  • replace_node_locked (include/svs/concurrent/graph.h, around line 503)
    records every new out-edge and, for every dropped out-edge, records the
    reverse pairing. It never removes an entry. The exact variant is commented
    out ("[Exact list] ... reverse_edges list would be exact for single
    thread. Need investigation for concurent case.").
  • ReverseEdges stores each list as a std::vector, so capacity is never
    returned even when consolidation removes entries.

Measurement

Single-threaded, through the C API. L2, FLOAT32, dimension 8,
graph_max_degree 64, construction window 128, 500 live vectors. Each round
deletes 100 vectors, then inserts 100 new ones into the deleted slots
(update_points on the deleted id, then replace_id to the new id). No
consolidation runs.

Inserts Memory growth since the initial fill
0 0 (the index uses 226,598 bytes)
5,000 252,580
20,000 260,004
40,000 265,124

data_bytes stays flat, so every slot is reused. All of the growth is in
graph_bytes, about 130 extra entries per node, roughly twice
graph_max_degree. After that it keeps rising slowly, by about 1.6 KB per
5,000 inserts.

Request

Could the reverse-edge index stay bounded without a full consolidation?
For example:

  • remove the reverse entry when an edge is dropped (the commented-out exact
    variant), if it can be made safe for concurrent writers; or
  • prune and shrink_to_fit a node's list when update_entries rewrites that
    node, since it already holds the node's lock and repairs its edges.

Without one of these, an index whose inserts reuse deleted slots grows to
about twice its graph size under steady churn, even though it never adds a
slot.

Ngôn ngữ chính
C++
Star
241
Fork
48
Merge trung bình
4 ngày 21 giờ
Pull request đã merge (30 ngày)
11

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

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 intel/ScalableVectorSearch

Tất cả issue của intel/ScalableVectorSearch

Issue tương tự

Thêm issue về C++

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.