Skip to content

Commit 1c0ec77

Browse files
meiravgrimeiravgri
authored
[MOD-10926] Expose SVS Marked Deleted Vector Count via Statistics API (#796)
SVSIndex rename chnages_num -> num_marked_deleted to emphasize it onluy counts deletions SVSIndexBase: move num_marked_deleted to SVSIndexBase so it can be simply fetched without complex cast add getNumMarkedDeleted to API add virtual getNumMarkedDeleted to tiered index to be called by VecSimTieredIndex::statisticInfo hnsw tiered implmnetaion: call hnsw->VecSimIndexTombstone::getNumMarkedDeleted, (hnsw inhrits VecSimIndexTombstone) svs imp: returns SVSIndexBase::getNumMarkedDeleted
1 parent 9fb223a commit 1c0ec77

6 files changed

Lines changed: 116 additions & 22 deletions

File tree

‎src/VecSim/algorithms/hnsw/hnsw_tiered.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -201,6 +201,9 @@ class TieredHNSWIndex : public VecSimTieredIndex<DataType, DistType> {
201201

202202
int addVector(const void *blob, labelType label) override;
203203
int deleteVector(labelType label) override;
204+
size_t getNumMarkedDeleted() const override {
205+
return this->getHNSWIndex()->getNumMarkedDeleted();
206+
}
204207
size_t indexSize() const override;
205208
size_t indexCapacity() const override;
206209
double getDistanceFrom_Unsafe(labelType label, const void *blob) const override;

‎src/VecSim/algorithms/svs/svs.h‎

Lines changed: 15 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ struct SVSIndexBase
3535
: public SVSSerializer
3636
#endif
3737
{
38-
38+
SVSIndexBase() : num_marked_deleted{0} {};
3939
virtual ~SVSIndexBase() = default;
4040
virtual int addVectors(const void *vectors_data, const labelType *labels, size_t n) = 0;
4141
virtual int deleteVectors(const labelType *labels, size_t n) = 0;
@@ -44,9 +44,14 @@ struct SVSIndexBase
4444
virtual void setNumThreads(size_t numThreads) = 0;
4545
virtual size_t getThreadPoolCapacity() const = 0;
4646
virtual bool isCompressed() const = 0;
47+
size_t getNumMarkedDeleted() const { return num_marked_deleted; }
4748
#ifdef BUILD_TESTS
4849
virtual svs::logging::logger_ptr getLogger() const = 0;
4950
#endif
51+
protected:
52+
// Index marked deleted vectors counter to initiate reindexing if it exceeds threshold
53+
// markIndexUpdate() manages this counter
54+
size_t num_marked_deleted;
5055
};
5156

5257
template <typename MetricType, typename DataType, bool isMulti, size_t QuantBits,
@@ -72,10 +77,6 @@ class SVSIndex : public VecSimIndexAbstract<svs_details::vecsim_dt<DataType>, fl
7277

7378
bool forcePreprocessing;
7479

75-
// Index severe changes counter to initiate reindexing if number of changes exceed threshold
76-
// markIndexUpdated() manages this counter
77-
size_t changes_num;
78-
7980
// Index build parameters
8081
svs::index::vamana::VamanaBuildParameters buildParams;
8182

@@ -273,26 +274,27 @@ class SVSIndex : public VecSimIndexAbstract<svs_details::vecsim_dt<DataType>, fl
273274
return deleted_num;
274275
}
275276

276-
// Count severe index changes (currently deletions only) and consolidate index if needed
277+
// Count deletions and consolidate index if needed
277278
void markIndexUpdate(size_t n = 1) {
278279
if (!impl_)
279280
return;
280281

281282
// SVS index instance should not be empty
282283
if (indexSize() == 0) {
283284
this->impl_.reset();
284-
changes_num = 0;
285+
num_marked_deleted = 0;
285286
return;
286287
}
287288

288-
changes_num += n;
289+
num_marked_deleted += n;
289290
// consolidate index if number of changes bigger than 50% of index size
290291
const float consolidation_threshold = .5f;
291292
// indexSize() should not be 0 see above lines
292293
assert(indexSize() > 0);
293-
if (static_cast<float>(changes_num) / indexSize() > consolidation_threshold) {
294+
// Note: if this function is called after deleteVectorsImpl, indexSize is already updated
295+
if (static_cast<float>(num_marked_deleted) / indexSize() > consolidation_threshold) {
294296
impl_->consolidate();
295-
changes_num = 0;
297+
num_marked_deleted = 0;
296298
}
297299
}
298300

@@ -312,7 +314,7 @@ class SVSIndex : public VecSimIndexAbstract<svs_details::vecsim_dt<DataType>, fl
312314
SVSIndex(const SVSParams &params, const AbstractIndexInitParams &abstractInitParams,
313315
const index_component_t &components, bool force_preprocessing)
314316
: Base{abstractInitParams, components}, forcePreprocessing{force_preprocessing},
315-
changes_num{0}, buildParams{svs_details::makeVamanaBuildParameters(params)},
317+
buildParams{svs_details::makeVamanaBuildParameters(params)},
316318
search_window_size{svs_details::getOrDefault(params.search_window_size,
317319
SVS_VAMANA_DEFAULT_SEARCH_WINDOW_SIZE)},
318320
search_buffer_capacity{
@@ -373,7 +375,7 @@ class SVSIndex : public VecSimIndexAbstract<svs_details::vecsim_dt<DataType>, fl
373375
.pruneTo = this->buildParams.prune_to,
374376
.useSearchHistory = this->buildParams.use_full_search_history,
375377
.numThreads = this->getNumThreads(),
376-
.numberOfMarkedDeletedNodes = this->changes_num,
378+
.numberOfMarkedDeletedNodes = this->num_marked_deleted,
377379
.searchWindowSize = this->search_window_size,
378380
.searchBufferCapacity = this->search_buffer_capacity,
379381
.leanvecDim = this->leanvec_dim,
@@ -673,7 +675,7 @@ class SVSIndex : public VecSimIndexAbstract<svs_details::vecsim_dt<DataType>, fl
673675
// https://intel.github.io/ScalableVectorSearch/python/dynamic.html#svs.DynamicVamana.compact
674676
impl_->compact();
675677
}
676-
changes_num = 0;
678+
num_marked_deleted = 0;
677679
}
678680

679681
#ifdef BUILD_TESTS

‎src/VecSim/algorithms/svs/svs_tiered.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -826,6 +826,9 @@ class TieredSVSIndex : public VecSimTieredIndex<DataType, float> {
826826
}
827827
return ret;
828828
}
829+
size_t getNumMarkedDeleted() const override {
830+
return this->GetSVSIndex()->getNumMarkedDeleted();
831+
}
829832

830833
size_t indexSize() const override {
831834
std::shared_lock<std::shared_mutex> flat_lock(this->flatIndexGuard);

‎src/VecSim/vec_sim_tiered_index.h‎

Lines changed: 2 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -139,7 +139,7 @@ class VecSimTieredIndex : public VecSimIndexInterface {
139139
return this->allocator->getAllocationSize() + this->backendIndex->getAllocationSize() +
140140
this->frontendIndex->getAllocationSize();
141141
}
142-
142+
virtual size_t getNumMarkedDeleted() const = 0;
143143
size_t indexLabelCount() const override;
144144
VecSimIndexStatsInfo statisticInfo() const override;
145145
virtual VecSimIndexDebugInfo debugInfo() const override;
@@ -319,14 +319,9 @@ template <typename DataType, typename DistType>
319319
VecSimIndexStatsInfo VecSimTieredIndex<DataType, DistType>::statisticInfo() const {
320320
auto stats = VecSimIndexStatsInfo{
321321
.memory = this->getAllocationSize(),
322-
.numberOfMarkedDeleted = 0, // Default value if cast fails
322+
.numberOfMarkedDeleted = this->getNumMarkedDeleted(),
323323
};
324324

325-
// If backend implements VecSimIndexTombstone, get number of marked deleted
326-
if (auto tombstone = dynamic_cast<VecSimIndexTombstone *>(this->backendIndex)) {
327-
stats.numberOfMarkedDeleted = tombstone->getNumMarkedDeleted();
328-
}
329-
330325
return stats;
331326
}
332327

‎tests/unit/test_svs.cpp‎

Lines changed: 13 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -182,6 +182,7 @@ TYPED_TEST(SVSTest, svs_vector_update_test) {
182182
// Delete the last vector.
183183
VecSimIndex_DeleteVector(index, 1);
184184
EXPECT_EQ(VecSimIndex_IndexSize(index), 0);
185+
ASSERT_EQ(svs_index->getNumMarkedDeleted(), 0);
185186

186187
VecSimIndex_Free(index);
187188
}
@@ -261,9 +262,19 @@ TYPED_TEST(SVSTest, svs_bulk_vectors_add_delete_test) {
261262
runTopKSearchTest(index, query, k, verify_res, nullptr, BY_ID);
262263

263264
// Delete almost all vectors
265+
// First delete small amount of vector to prevent consolidation.
266+
const size_t first_batch_deletion = 10;
267+
ASSERT_EQ(svs_index->deleteVectors(ids.data(), first_batch_deletion), first_batch_deletion);
268+
ASSERT_EQ(VecSimIndex_IndexSize(index), n - first_batch_deletion);
269+
ASSERT_EQ(svs_index->getNumMarkedDeleted(), first_batch_deletion);
270+
271+
// Now delete enough vectors to trigger consolidation.
264272
const size_t keep_num = 1;
265-
ASSERT_EQ(svs_index->deleteVectors(ids.data(), n - keep_num), n - keep_num);
273+
ASSERT_EQ(svs_index->deleteVectors(ids.data() + first_batch_deletion,
274+
n - keep_num - first_batch_deletion),
275+
n - keep_num - first_batch_deletion);
266276
ASSERT_EQ(VecSimIndex_IndexSize(index), keep_num);
277+
ASSERT_EQ(svs_index->getNumMarkedDeleted(), 0);
267278

268279
VecSimIndex_Free(index);
269280
}
@@ -3012,7 +3023,7 @@ TYPED_TEST(SVSTest, logging_runtime_params) {
30123023
for (size_t i = 0; i < 10; i++) {
30133024
index->addVector(v[i].data(), ids[i]);
30143025
}
3015-
3026+
ASSERT_EQ(svs_index->getNumMarkedDeleted(), 10);
30163027
ASSERT_EQ(VecSimIndex_IndexSize(index), n);
30173028

30183029
float query[] = {50, 50, 50, 50};

‎tests/unit/test_svs_tiered.cpp‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -824,6 +824,79 @@ TYPED_TEST(SVSTieredIndexTest, deleteVector) {
824824
}
825825
}
826826

827+
TYPED_TEST(SVSTieredIndexTestBasic, markedDeleted) {
828+
// Create TieredSVS index instance with a mock queue.
829+
size_t dim = 4;
830+
constexpr size_t n = 10;
831+
constexpr size_t transfer_trigger = n;
832+
SVSParams params = {.type = TypeParam::get_index_type(),
833+
.dim = dim,
834+
.metric = VecSimMetric_L2,
835+
.num_threads = 1};
836+
VecSimParams svs_params = CreateParams(params);
837+
auto mock_thread_pool = tieredIndexMock();
838+
839+
auto *tiered_index = this->CreateTieredSVSIndex(svs_params, mock_thread_pool, transfer_trigger,
840+
transfer_trigger);
841+
ASSERT_INDEX(tiered_index);
842+
843+
for (size_t i = 0; i < n; i++) {
844+
GenerateAndAddVector<TEST_DATA_T>(tiered_index, dim, i);
845+
}
846+
// Vectors are still in the flat buffer.
847+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), n);
848+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 0);
849+
// Override a vector while in the flat buffer
850+
851+
GenerateAndAddVector<TEST_DATA_T>(tiered_index, dim, 0);
852+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), n);
853+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 0);
854+
855+
// Move vectors to the backend
856+
mock_thread_pool.thread_iteration();
857+
ASSERT_EQ(tiered_index->GetBackendIndex()->indexSize(), n);
858+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), 0);
859+
ASSERT_EQ(tiered_index->indexSize(), n);
860+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 0);
861+
862+
// Override a vector while in the backend
863+
GenerateAndAddVector<TEST_DATA_T>(tiered_index, dim, 1);
864+
ASSERT_EQ(tiered_index->indexSize(), n);
865+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 1);
866+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), 1);
867+
868+
ASSERT_EQ(tiered_index->GetBackendIndex()->indexSize(), n - 1);
869+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), 1);
870+
871+
// Delete the overriden vector
872+
VecSimIndex_DeleteVector(tiered_index, 1);
873+
ASSERT_EQ(tiered_index->indexSize(), n - 1);
874+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 1);
875+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), 1);
876+
ASSERT_EQ(tiered_index->GetBackendIndex()->indexSize(), n - 1);
877+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), 0);
878+
879+
// Delete another arbirtrary vector
880+
VecSimIndex_DeleteVector(tiered_index, 0);
881+
ASSERT_EQ(tiered_index->indexSize(), n - 2);
882+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 2);
883+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), 2);
884+
ASSERT_EQ(tiered_index->GetBackendIndex()->indexSize(), n - 2);
885+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), 0);
886+
887+
// Empty Index
888+
for (size_t i = 2; i < n; i++) {
889+
VecSimIndex_DeleteVector(tiered_index, i);
890+
}
891+
892+
// Consolidate should be triggered and mark deleted count should be zeroed.
893+
ASSERT_EQ(tiered_index->indexSize(), 0);
894+
ASSERT_EQ(tiered_index->getNumMarkedDeleted(), 0);
895+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), 0);
896+
ASSERT_EQ(tiered_index->GetBackendIndex()->indexSize(), 0);
897+
ASSERT_EQ(tiered_index->GetFlatIndex()->indexSize(), 0);
898+
}
899+
827900
TYPED_TEST(SVSTieredIndexTestBasic, deleteVectorMulti) {
828901
// Create TieredSVS index instance with a mock queue.
829902
size_t dim = 4;
@@ -2556,6 +2629,8 @@ TYPED_TEST(SVSTieredIndexTest, writeInPlaceMode) {
25562629
// Validate that the vector is removed in place.
25572630
tiered_index->deleteVector(vec_label);
25582631
ASSERT_EQ(tiered_index->GetBackendIndex()->indexSize(), 1);
2632+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), 0);
2633+
EXPECT_EQ(tiered_index->statisticInfo().numberOfMarkedDeleted, 0);
25592634
}
25602635

25612636
TYPED_TEST(SVSTieredIndexTest, switchWriteModes) {
@@ -2728,6 +2803,9 @@ TYPED_TEST(SVSTieredIndexTestBasic, runGCAPI) {
27282803
for (size_t i = 0; i < threshold; i++) {
27292804
tiered_index->deleteVector(i);
27302805
}
2806+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), threshold);
2807+
EXPECT_EQ(tiered_index->statisticInfo().numberOfMarkedDeleted, threshold);
2808+
27312809
// Launch the BG threads loop that takes jobs from the queue and executes them.
27322810
mock_thread_pool.init_threads();
27332811
mock_thread_pool.thread_pool_join();
@@ -2744,6 +2822,8 @@ TYPED_TEST(SVSTieredIndexTestBasic, runGCAPI) {
27442822
auto size_after_gc = tiered_index->getAllocationSize();
27452823
// Expect that the size of the index was reduced.
27462824
ASSERT_LT(size_after_gc, size_before_gc);
2825+
ASSERT_EQ(tiered_index->GetSVSIndex()->getNumMarkedDeleted(), 0);
2826+
EXPECT_EQ(tiered_index->statisticInfo().numberOfMarkedDeleted, 0);
27472827
}
27482828

27492829
TYPED_TEST(SVSTieredIndexTestBasic, switchDeleteModes) {

0 commit comments

Comments
 (0)