Skip to content

Commit 3325068

Browse files
alonre24alonre24
authored
Avoid adding connection to marked deleted elements upon delete in-place in tiered index [MOD-7732] (#543)
* test buggy scenario - WIP * Fix logic for inplace, add test * make test stricter + format * avoid collecting marked deleted elements in the candidates selection phase. * Meirav's CR
1 parent a4015a5 commit 3325068

5 files changed

Lines changed: 181 additions & 26 deletions

File tree

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

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,17 @@ struct ElementLevelData {
5858
void setNumLinks(linkListSize num) { this->numLinks = num; }
5959
void setLinkAtPos(size_t pos, idType node_id) { this->links[pos] = node_id; }
6060
void appendLink(idType node_id) { this->links[this->numLinks++] = node_id; }
61+
void removeLink(idType node_id) {
62+
size_t i = 0;
63+
for (; i < numLinks; i++) {
64+
if (links[i] == node_id) {
65+
links[i] = links[numLinks - 1];
66+
break;
67+
}
68+
}
69+
assert(i < numLinks && "Corruption in HNSW index"); // node_id not found - error
70+
numLinks--;
71+
}
6172
void newIncomingUnidirectionalEdge(idType node_id) {
6273
this->incomingUnidirectionalEdges->push_back(node_id);
6374
}

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

Lines changed: 45 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -951,24 +951,34 @@ void HNSWIndex<DataType, DistType>::repairConnectionsForDeletion(
951951
idType element_internal_id, idType neighbour_id, ElementLevelData &node_level,
952952
ElementLevelData &neighbor_level, size_t level, vecsim_stl::vector<bool> &neighbours_bitmap) {
953953

954-
// put the deleted element's neighbours in the candidates.
954+
if (isMarkedDeleted(neighbour_id)) {
955+
// Just remove the deleted element from the neighbor's neighbors list. No need to repair as
956+
// this change is temporary, this neighbor is about to be removed from the graph as well.
957+
neighbor_level.removeLink(element_internal_id);
958+
return;
959+
}
960+
961+
// Add the deleted element's neighbour's original neighbors in the candidates.
955962
vecsim_stl::vector<idType> candidate_ids(this->allocator);
956963
candidate_ids.reserve(node_level.getNumLinks() + neighbor_level.getNumLinks());
957-
for (size_t j = 0; j < node_level.getNumLinks(); j++) {
958-
// Don't put the neighbor itself in his own candidates
959-
if (node_level.getLinkAtPos(j) != neighbour_id) {
960-
candidate_ids.push_back(node_level.getLinkAtPos(j));
961-
}
962-
}
963-
// add the deleted element's neighbour's original neighbors in the candidates.
964964
vecsim_stl::vector<bool> neighbour_orig_neighbours_set(curElementCount, false, this->allocator);
965965
for (size_t j = 0; j < neighbor_level.getNumLinks(); j++) {
966-
neighbour_orig_neighbours_set[neighbor_level.getLinkAtPos(j)] = true;
967-
// Don't add the removed element to the candidates, nor nodes that are already in the
968-
// candidates set.
969-
if (neighbor_level.getLinkAtPos(j) != element_internal_id &&
970-
!neighbours_bitmap[neighbor_level.getLinkAtPos(j)]) {
971-
candidate_ids.push_back(neighbor_level.getLinkAtPos(j));
966+
idType cand = neighbor_level.getLinkAtPos(j);
967+
neighbour_orig_neighbours_set[cand] = true;
968+
// Don't add the removed element to the candidates, nor nodes that are neighbors of the
969+
// original deleted element and will also be added to the candidates set.
970+
if (cand != element_internal_id && !neighbours_bitmap[cand]) {
971+
candidate_ids.push_back(cand);
972+
}
973+
}
974+
// Put the deleted element's neighbours in the candidates.
975+
for (size_t j = 0; j < node_level.getNumLinks(); j++) {
976+
// Don't put the neighbor itself in his own candidates and nor marked deleted elements that
977+
// were not neighbors before.
978+
idType cand = node_level.getLinkAtPos(j);
979+
if (cand != neighbour_id &&
980+
(!isMarkedDeleted(cand) || neighbour_orig_neighbours_set[cand])) {
981+
candidate_ids.push_back(cand);
972982
}
973983
}
974984

@@ -990,8 +1000,7 @@ void HNSWIndex<DataType, DistType>::repairConnectionsForDeletion(
9901000

9911001
neighbor_level.setLinks(candidates);
9921002

993-
// remove neighbour id from the incoming list of nodes for his
994-
// neighbours that were chosen to remove
1003+
// Update unidirectional incoming edges w.r.t. the edges that were removed.
9951004
for (auto node_id : not_chosen_candidates) {
9961005
if (neighbour_orig_neighbours_set[node_id]) {
9971006
// if the node id (the neighbour's neighbour to be removed)
@@ -1010,21 +1019,21 @@ void HNSWIndex<DataType, DistType>::repairConnectionsForDeletion(
10101019
neighbor_level.setLinks(candidate_ids);
10111020
}
10121021

1013-
// updates for the new edges created
1022+
// Updates for the new edges created
10141023
for (size_t i = 0; i < neighbor_level.getNumLinks(); i++) {
10151024
idType node_id = neighbor_level.getLinkAtPos(i);
10161025
if (!neighbour_orig_neighbours_set[node_id]) {
10171026
ElementLevelData &node_level = getElementLevelData(node_id, level);
1018-
// if the node has an edge to the neighbour as well, remove it
1019-
// from the incoming nodes of the neighbour
1020-
// otherwise, need to update the edge as incoming.
1021-
1027+
// If the node has an edge to the neighbour as well, remove it from the incoming nodes
1028+
// of the neighbour. Otherwise, we need to update the edge as unidirectional incoming.
10221029
bool bidirectional_edge = false;
10231030
for (size_t j = 0; j < node_level.getNumLinks(); j++) {
10241031
if (node_level.getLinkAtPos(j) == neighbour_id) {
10251032
// Swap the last element with the current one (equivalent to removing the
10261033
// neighbor from the list) - this should always succeed and return true.
1027-
neighbor_level.removeIncomingUnidirectionalEdgeIfExists(node_id);
1034+
bool res = neighbor_level.removeIncomingUnidirectionalEdgeIfExists(node_id);
1035+
(void)res;
1036+
assert(res && "The edge should be in the incoming unidirectional edges");
10281037
bidirectional_edge = true;
10291038
break;
10301039
}
@@ -1642,9 +1651,16 @@ void HNSWIndex<DataType, DistType>::removeAndSwap(idType internalId) {
16421651
ElementLevelData &cur_level = getElementLevelData(element, level);
16431652
for (size_t i = 0; i < cur_level.getNumLinks(); i++) {
16441653
ElementLevelData &neighbour = getElementLevelData(cur_level.getLinkAtPos(i), level);
1645-
// This should always succeed, since every outgoing edge should be unidirectional at
1646-
// this point (after all the repair jobs are done).
1647-
neighbour.removeIncomingUnidirectionalEdgeIfExists(internalId);
1654+
// Note that in case of in-place delete, we might have not accounted for this edge in
1655+
// in the unidirectional edges, since there is no point in keeping it there temporarily
1656+
// (we know we will get here and remove this deleted id permanently).
1657+
// However, upon asynchronous delete, this should always succeed since we do update
1658+
// the incoming edges in the mutual update even for deleted elements.
1659+
bool res = neighbour.removeIncomingUnidirectionalEdgeIfExists(internalId);
1660+
// Assert the logical condition of: is_marked_deleted(id) => res==True.
1661+
(void)res;
1662+
assert((!isMarkedDeleted(internalId) || res) && "The edge should be in the incoming "
1663+
"unidirectional edges");
16481664
}
16491665
}
16501666

@@ -1716,7 +1732,10 @@ void HNSWIndex<DataType, DistType>::removeVectorInPlace(const idType element_int
17161732
// incoming edges.
17171733
if (!bidirectional_edge) {
17181734
// This should always return true (remove should succeed).
1719-
neighbor_level.removeIncomingUnidirectionalEdgeIfExists(element_internal_id);
1735+
bool res =
1736+
neighbor_level.removeIncomingUnidirectionalEdgeIfExists(element_internal_id);
1737+
(void)res;
1738+
assert(res && "The edge should be in the incoming unidirectional edges");
17201739
}
17211740
}
17221741

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,3 +21,4 @@ INDEX_TEST_FRIEND_CLASS(HNSWTestParallel_parallelSearchCombined_Test)
2121
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_deleteFromHNSWMultiLevels_Test)
2222
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTest_deleteFromHNSWWithRepairJobExec_Test)
2323
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTest_swapJobBasic_Test)
24+
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_deleteInplaceAvoidUpdatedMarkedDeleted_Test)

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,8 @@ INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_FitMemoryTest_Test)
5252
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_deleteBothAsyncAndInplace_Test)
5353
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_deleteBothAsyncAndInplaceMulti_Test)
5454
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_deleteInplaceMultiSwapId_Test)
55+
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_deleteInplaceAvoidUpdatedMarkedDeleted_Test)
56+
INDEX_TEST_FRIEND_CLASS(HNSWTieredIndexTestBasic_switchDeleteModes_Test)
5557

5658
friend class BF16TieredTest;
5759
friend class FP16TieredTest;

‎tests/unit/test_hnsw_tiered.cpp‎

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3678,3 +3678,125 @@ TYPED_TEST(HNSWTieredIndexTestBasic, deleteInplaceMultiSwapId) {
36783678
ASSERT_EQ(tiered_index->deleteVector(0), 2);
36793679
ASSERT_EQ(tiered_index->getHNSWIndex()->safeGetEntryPointState().first, 0);
36803680
}
3681+
3682+
TYPED_TEST(HNSWTieredIndexTestBasic, deleteInplaceAvoidUpdatedMarkedDeleted) {
3683+
// Create TieredHNSW index instance with a mock queue.
3684+
size_t dim = 4;
3685+
HNSWParams params = {
3686+
.type = TypeParam::get_index_type(), .dim = dim, .metric = VecSimMetric_L2};
3687+
VecSimParams hnsw_params = CreateParams(params);
3688+
3689+
auto mock_thread_pool = tieredIndexMock();
3690+
3691+
auto *tiered_index = this->CreateTieredHNSWIndex(hnsw_params, mock_thread_pool);
3692+
auto allocator = tiered_index->getAllocator();
3693+
3694+
// Insert three vector to HNSW, expect a full graph to be created
3695+
GenerateAndAddVector<TEST_DATA_T>(tiered_index->backendIndex, dim, 0, 0);
3696+
GenerateAndAddVector<TEST_DATA_T>(tiered_index->backendIndex, dim, 1, 1);
3697+
GenerateAndAddVector<TEST_DATA_T>(tiered_index->backendIndex, dim, 2, 2);
3698+
3699+
// Delete vector with id=0 asynchronously, expect to have a repair job for the other vectors.
3700+
ASSERT_EQ(tiered_index->deleteVector(0), 1);
3701+
ASSERT_EQ(tiered_index->idToRepairJobs.size(), 2);
3702+
ASSERT_EQ(tiered_index->idToRepairJobs.at(1)[0]->associatedSwapJobs.size(), 1);
3703+
ASSERT_EQ(tiered_index->idToRepairJobs.at(2)[0]->associatedSwapJobs.size(), 1);
3704+
3705+
// Execute the repair job for 1->0. Now, 0->1 is unidirectional edge
3706+
ASSERT_TRUE(mock_thread_pool.jobQ.front().job->isValid);
3707+
mock_thread_pool.thread_iteration();
3708+
ASSERT_EQ(tiered_index->idToRepairJobs.size(), 1);
3709+
ASSERT_EQ(tiered_index->idToRepairJobs.at(2)[0]->associatedSwapJobs.size(), 1);
3710+
3711+
// Insert another vector with id=3, that should be connected to both 1 and 2.
3712+
GenerateAndAddVector<TEST_DATA_T>(tiered_index->backendIndex, dim, 3, -1);
3713+
3714+
// Delete in-place id=2, expect that upon repairing inplace 1 due to 1->2, there will *not* be
3715+
// a new edge 1->0 since 0 is deleted. Also the other repair job 2->0 should be invalidated.
3716+
// Also, expect that repairing 3 in-place will not create a new edge to marked deleted 0 and
3717+
// vice versa.
3718+
tiered_index->setWriteMode(VecSim_WriteInPlace);
3719+
ASSERT_EQ(tiered_index->deleteVector(2), 1);
3720+
ASSERT_FALSE(mock_thread_pool.jobQ.front().job->isValid);
3721+
int **neighbours;
3722+
ASSERT_EQ(tiered_index->getHNSWIndex()->getHNSWElementNeighbors(1, &neighbours),
3723+
VecSimDebugCommandCode_OK);
3724+
// Expect 1 neighbors at level 0 (id=3) and that 0 is NOT a new neighbor for 1.
3725+
ASSERT_EQ(neighbours[0][0], 1);
3726+
ASSERT_EQ(neighbours[0][1], 3);
3727+
VecSimDebug_ReleaseElementNeighborsInHNSWGraph(neighbours);
3728+
3729+
ASSERT_EQ(tiered_index->getHNSWIndex()->getHNSWElementNeighbors(3, &neighbours),
3730+
VecSimDebugCommandCode_OK);
3731+
ASSERT_EQ(neighbours[0][0], 1);
3732+
// Expect 1 neighbors at level 0 (id=1) and that 0 is NOT a new neighbor for 3.
3733+
ASSERT_EQ(neighbours[0][1], 1);
3734+
VecSimDebug_ReleaseElementNeighborsInHNSWGraph(neighbours);
3735+
3736+
auto &level_data = tiered_index->getHNSWIndex()->getElementLevelData((idType)0, 0);
3737+
// Expect 1 neighbors at level 0 (id=1) and that 3 is NOT a new neighbor for 0.
3738+
ASSERT_EQ(level_data.getNumLinks(), 1);
3739+
ASSERT_EQ(level_data.getLinkAtPos(0), 1);
3740+
3741+
// Expect that id=0 is a ready swap job and execute it.
3742+
ASSERT_EQ(tiered_index->readySwapJobs, 1);
3743+
ASSERT_TRUE(tiered_index->idToSwapJob.contains(0));
3744+
tiered_index->runGC();
3745+
}
3746+
3747+
TYPED_TEST(HNSWTieredIndexTestBasic, switchDeleteModes) {
3748+
// Create TieredHNSW index instance with a mock queue.
3749+
size_t dim = 16;
3750+
size_t n = 1000;
3751+
size_t swap_job_threshold = 10;
3752+
HNSWParams params = {
3753+
.type = TypeParam::get_index_type(),
3754+
.dim = dim,
3755+
.metric = VecSimMetric_L2,
3756+
.blockSize = 100,
3757+
};
3758+
VecSimParams hnsw_params = CreateParams(params);
3759+
auto mock_thread_pool = tieredIndexMock();
3760+
3761+
auto *tiered_index =
3762+
this->CreateTieredHNSWIndex(hnsw_params, mock_thread_pool, swap_job_threshold);
3763+
auto allocator = tiered_index->getAllocator();
3764+
3765+
// Launch the BG threads loop that takes jobs from the queue and executes them.
3766+
mock_thread_pool.init_threads();
3767+
3768+
// Create and insert vectors one by one inplace.
3769+
VecSim_SetWriteMode(VecSim_WriteInPlace);
3770+
std::srand(10); // create pseudo random generator with any arbitrary seed.
3771+
for (size_t i = 0; i < n; i++) {
3772+
TEST_DATA_T vector[dim];
3773+
for (size_t j = 0; j < dim; j++) {
3774+
vector[j] = std::rand() / (TEST_DATA_T)RAND_MAX;
3775+
}
3776+
VecSimIndex_AddVector(tiered_index, vector, i);
3777+
}
3778+
EXPECT_EQ(tiered_index->backendIndex->indexSize(), n);
3779+
3780+
// Update vectors while changing the write mode.
3781+
for (size_t i = 0; i < n; i++) {
3782+
TEST_DATA_T vector[dim];
3783+
for (size_t j = 0; j < dim; j++) {
3784+
vector[j] = std::rand() / (TEST_DATA_T)RAND_MAX;
3785+
}
3786+
EXPECT_EQ(tiered_index->addVector(vector, i), 0);
3787+
if (i % 10 == 0) {
3788+
// Change mode every 10 vectors.
3789+
auto next_mode = tiered_index->getWriteMode() == VecSim_WriteInPlace
3790+
? VecSim_WriteAsync
3791+
: VecSim_WriteInPlace;
3792+
VecSim_SetWriteMode(next_mode);
3793+
}
3794+
}
3795+
3796+
mock_thread_pool.thread_pool_join();
3797+
ASSERT_EQ(tiered_index->frontendIndex->indexSize(), 0);
3798+
ASSERT_EQ(tiered_index->backendIndex->indexLabelCount(), n);
3799+
auto state = tiered_index->getHNSWIndex()->checkIntegrity();
3800+
ASSERT_EQ(state.valid_state, 1);
3801+
ASSERT_EQ(state.connections_to_repair, 0);
3802+
}

0 commit comments

Comments
 (0)