You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Concurrent index: reverse-edge lists grow under update churn until consolidation #469
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.
More data at 50K x 128-d (graph_max_degree 64, FINE_GRAIN at 9330e49), from the benchmark described on #467:
With in-place updates (update_points on live ids) and slot reuse, memory_bytes grew linearly by 51.5 MB (+68%) over 25,000 updates and 25,000 inserts, with no plateau, while data_bytes stayed flat.
On the same pin, add/delete with periodic consolidate + compact stays bounded (62-79 MB over the same churn).
Right after ingest the concurrent index reports 75.2 MB against 51.9 MB for the non-concurrent index at v0.5.0, which is mostly the reverse-edge index.
In the profile of the update path, about 65% of update_entries CPU is GraphConsolidator, whose work set is gathered from these lists, so stale entries may also cost time.
We are prototyping a different approach on the valkey-search side and will report whether it still shows this growth; this is pending that exploration.
Activity
eshenayo commentedon Nov 12, 2026
More data at 50K x 128-d (graph_max_degree 64, FINE_GRAIN at 9330e49), from the benchmark described on #467:
update_pointson live ids) and slot reuse,memory_bytesgrew linearly by 51.5 MB (+68%) over 25,000 updates and 25,000 inserts, with no plateau, whiledata_bytesstayed flat.update_entriesCPU isGraphConsolidator, whose work set is gathered from these lists, so stale entries may also cost time.We are prototyping a different approach on the valkey-search side and will report whether it still shows this growth; this is pending that exploration.