diff options
author | Geir Storli <geirst@verizonmedia.com> | 2021-08-20 15:19:32 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-08-20 15:19:32 +0200 |
commit | 30c8dac6c619d6fe2d5858e5def4f64c64a11029 (patch) | |
tree | 5f548058fb1915892153030fe2bc0fd9f95bd820 /searchlib | |
parent | 50ddf43caca8a1ad859dab77df94b8934a42f7ed (diff) | |
parent | cce05ad694031a4379fbeeda4c576f933104108f (diff) |
Merge pull request #18783 from vespa-engine/toregge/compact-hnsw-index
Compact HNSW index when ratio of dead bytes / address space is too high
Diffstat (limited to 'searchlib')
10 files changed, 300 insertions, 6 deletions
diff --git a/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp b/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp index a49816f1a52..084bdf90a14 100644 --- a/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp +++ b/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp @@ -36,6 +36,7 @@ LOG_SETUP("tensorattribute_test"); using document::WrongTensorTypeException; using search::AttributeGuard; using search::AttributeVector; +using search::CompactionStrategy; using search::attribute::DistanceMetric; using search::attribute::HnswIndexParams; using search::queryeval::GlobalFilter; @@ -199,11 +200,18 @@ public: void trim_hold_lists(generation_t first_used_gen) override { _trim_gen = first_used_gen; } + bool consider_compact(const CompactionStrategy&) override { + return false; + } + vespalib::MemoryUsage update_stat() override { + return vespalib::MemoryUsage(); + } vespalib::MemoryUsage memory_usage() const override { ++_memory_usage_cnt; return vespalib::MemoryUsage(); } void get_state(const vespalib::slime::Inserter&) const override {} + void shrink_lid_space(uint32_t) override { } std::unique_ptr<NearestNeighborIndexSaver> make_saver() const override { if (_index_value != 0) { return std::make_unique<MockIndexSaver>(_index_value); diff --git a/searchlib/src/tests/tensor/hnsw_index/hnsw_index_test.cpp b/searchlib/src/tests/tensor/hnsw_index/hnsw_index_test.cpp index 3f7ec140781..9e7f082e237 100644 --- a/searchlib/src/tests/tensor/hnsw_index/hnsw_index_test.cpp +++ b/searchlib/src/tests/tensor/hnsw_index/hnsw_index_test.cpp @@ -1,5 +1,6 @@ // Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#include <vespa/searchcommon/common/compaction_strategy.h> #include <vespa/searchlib/common/bitvector.h> #include <vespa/searchlib/tensor/distance_functions.h> #include <vespa/searchlib/tensor/doc_vector_access.h> @@ -20,7 +21,7 @@ using namespace search::tensor; using namespace vespalib::slime; using vespalib::Slime; using search::BitVector; - +using search::CompactionStrategy; template <typename FloatType> class MyDocVectorAccess : public DocVectorAccess { @@ -42,6 +43,8 @@ public: ArrayRef ref(_vectors[docid]); return vespalib::eval::TypedCells(ref); } + + void clear() { _vectors.clear(); } }; struct LevelGenerator : public RandomLevelGenerator { @@ -111,6 +114,10 @@ public: MemoryUsage memory_usage() const { return index->memory_usage(); } + MemoryUsage commit_and_update_stat() { + commit(); + return index->update_stat(); + } void expect_entry_point(uint32_t exp_docid, uint32_t exp_level) { EXPECT_EQ(exp_docid, index->get_entry_docid()); EXPECT_EQ(exp_level, index->get_entry_level()); @@ -166,6 +173,8 @@ public: docid, hit.docid, hit.distance, thr); } } + + FloatVectors& get_vectors() { return vectors; } }; @@ -533,6 +542,113 @@ TEST_F(HnswIndexTest, shrink_called_heuristic) EXPECT_TRUE(index->check_link_symmetry()); } +namespace { + +template <class ResultGraph> +ResultGraph +make_graph_helper(HnswIndex& index) +{ + using LevelArrayRef = HnswGraph::LevelArrayRef; + using LinkArrayRef = HnswGraph::LinkArrayRef; + auto& graph = index.get_graph(); + ResultGraph result(graph.size()); + assert(!graph.get_node_ref(0).valid()); + for (uint32_t doc_id = 1; doc_id < graph.size(); ++doc_id) { + auto& node = result[doc_id]; + auto node_ref = graph.get_node_ref(doc_id); + if constexpr (std::is_same_v<std::remove_reference_t<decltype(node)>, uint32_t>) { + node = node_ref.ref(); + } else { + LevelArrayRef level_array(graph.get_level_array(node_ref)); + for (uint32_t level = 0; level < level_array.size(); ++level) { + if constexpr (std::is_same_v<std::remove_reference_t<decltype(node)>, std::vector<uint32_t>>) { + node.emplace_back(level_array[level].load_relaxed().ref()); + } else { + LinkArrayRef link_array(graph.get_link_array(level_array, level)); + node.emplace_back(std::vector<uint32_t>(link_array.begin(), link_array.end())); + } + } + } + } + return result; +} + +using LinkGraph = std::vector<std::vector<std::vector<uint32_t>>>; + +LinkGraph +make_link_graph(HnswIndex& index) +{ + return make_graph_helper<LinkGraph>(index); +} + +using LinkArrayRefGraph = std::vector<std::vector<uint32_t>>; + +LinkArrayRefGraph +make_link_array_refs(HnswIndex& index) +{ + return make_graph_helper<LinkArrayRefGraph>(index); +} + +using LevelArrayRefGraph = std::vector<uint32_t>; + +LevelArrayRefGraph +make_level_array_refs(HnswIndex& index) +{ + return make_graph_helper<LevelArrayRefGraph>(index); +} + +} + +TEST_F(HnswIndexTest, hnsw_graph_is_compacted) +{ + init(true); + get_vectors().clear(); + uint32_t doc_id = 1; + for (uint32_t x = 0; x < 100; ++x) { + for (uint32_t y = 0; y < 50; ++y) { + get_vectors().set(doc_id, { float(x), float(y) }); + ++doc_id; + } + } + uint32_t doc_id_end = doc_id; + for (doc_id = 1; doc_id < doc_id_end; ++doc_id) { + add_document(doc_id); + } + for (doc_id = 10; doc_id < doc_id_end; ++doc_id) { + remove_document(doc_id); + } + auto mem_1 = commit_and_update_stat(); + auto link_graph_1 = make_link_graph(*index); + auto link_array_refs_1 = make_link_array_refs(*index); + auto level_array_refs_1 = make_level_array_refs(*index); + // Normal compaction + EXPECT_TRUE(index->consider_compact(CompactionStrategy())); + auto mem_2 = commit_and_update_stat(); + EXPECT_LT(mem_2.usedBytes(), mem_1.usedBytes()); + for (uint32_t i = 0; i < 10; ++i) { + mem_1 = mem_2; + // Forced compaction to move things around + index->compact_link_arrays(true, false); + index->compact_level_arrays(true, false); + commit(); + index->update_stat(); + mem_2 = commit_and_update_stat(); + EXPECT_LE(mem_2.usedBytes(), mem_1.usedBytes()); + if (mem_2.usedBytes() == mem_1.usedBytes()) { + break; + } + } + auto link_graph_2 = make_link_graph(*index); + auto link_array_refs_2 = make_link_array_refs(*index); + auto level_array_refs_2 = make_level_array_refs(*index); + EXPECT_EQ(link_graph_1, link_graph_2); + EXPECT_NE(link_array_refs_1, link_array_refs_2); + EXPECT_NE(level_array_refs_1, level_array_refs_2); + index->shrink_lid_space(10); + auto mem_3 = commit_and_update_stat(); + EXPECT_LT(mem_3.usedBytes(), mem_2.usedBytes()); +} + TEST(LevelGeneratorTest, gives_various_levels) { InvLogLevelGenerator generator(4); diff --git a/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.cpp b/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.cpp index 62a1072de48..1639f5f8113 100644 --- a/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.cpp +++ b/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.cpp @@ -400,6 +400,18 @@ DenseTensorAttribute::getVersion() const } void +DenseTensorAttribute::onCommit() +{ + TensorAttribute::onCommit(); + if (_index) { + if (_index->consider_compact(getConfig().getCompactionStrategy())) { + incGeneration(); + updateStat(true); + } + } +} + +void DenseTensorAttribute::onGenerationChange(generation_t next_gen) { // TODO: Change onGenerationChange() to send current generation instead of next generation. @@ -430,6 +442,15 @@ DenseTensorAttribute::get_state(const vespalib::slime::Inserter& inserter) const } } +void +DenseTensorAttribute::onShrinkLidSpace() +{ + TensorAttribute::onShrinkLidSpace(); + if (_index) { + _index->shrink_lid_space(getCommittedDocIdLimit()); + } +} + vespalib::eval::TypedCells DenseTensorAttribute::get_vector(uint32_t docid) const { diff --git a/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.h b/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.h index 752db849b68..8899b1e4bd1 100644 --- a/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.h +++ b/searchlib/src/vespa/searchlib/tensor/dense_tensor_attribute.h @@ -43,9 +43,11 @@ public: std::unique_ptr<AttributeSaver> onInitSave(vespalib::stringref fileName) override; void compactWorst() override; uint32_t getVersion() const override; + void onCommit() override; void onGenerationChange(generation_t next_gen) override; void removeOldGenerations(generation_t first_used_gen) override; void get_state(const vespalib::slime::Inserter& inserter) const override; + void onShrinkLidSpace() override; // Implements DocVectorAccess vespalib::eval::TypedCells get_vector(uint32_t docid) const override; diff --git a/searchlib/src/vespa/searchlib/tensor/hnsw_graph.cpp b/searchlib/src/vespa/searchlib/tensor/hnsw_graph.cpp index b1545d587b8..f58dbcafbec 100644 --- a/searchlib/src/vespa/searchlib/tensor/hnsw_graph.cpp +++ b/searchlib/src/vespa/searchlib/tensor/hnsw_graph.cpp @@ -9,6 +9,7 @@ namespace search::tensor { HnswGraph::HnswGraph() : node_refs(), + node_refs_size(1u), nodes(HnswIndex::make_default_node_store_config()), links(HnswIndex::make_default_link_store_config()), entry_docid_and_level() @@ -30,6 +31,9 @@ HnswGraph::make_node_for_document(uint32_t docid, uint32_t num_levels) vespalib::Array<AtomicEntryRef> levels(num_levels, AtomicEntryRef()); auto node_ref = nodes.add(levels); node_refs[docid].store_release(node_ref); + if (docid >= node_refs_size.load(std::memory_order_relaxed)) { + node_refs_size.store(docid + 1, std::memory_order_release); + } return node_ref; } @@ -47,6 +51,19 @@ HnswGraph::remove_node_for_document(uint32_t docid) auto old_links_ref = levels[i].load_acquire(); links.remove(old_links_ref); } + if (docid + 1 == node_refs_size.load(std::memory_order_relaxed)) { + trim_node_refs_size(); + } +} + +void +HnswGraph::trim_node_refs_size() +{ + uint32_t check_doc_id = node_refs_size.load(std::memory_order_relaxed) - 1; + while (check_doc_id > 0u && !node_refs[check_doc_id].load_relaxed().valid()) { + --check_doc_id; + } + node_refs_size.store(check_doc_id + 1, std::memory_order_release); } void diff --git a/searchlib/src/vespa/searchlib/tensor/hnsw_graph.h b/searchlib/src/vespa/searchlib/tensor/hnsw_graph.h index 4d07f74f8e3..57826088ca5 100644 --- a/searchlib/src/vespa/searchlib/tensor/hnsw_graph.h +++ b/searchlib/src/vespa/searchlib/tensor/hnsw_graph.h @@ -40,6 +40,7 @@ struct HnswGraph { using LinkArrayRef = LinkStore::ConstArrayRef; NodeRefVector node_refs; + std::atomic<uint32_t> node_refs_size; NodeStore nodes; LinkStore links; @@ -52,6 +53,8 @@ struct HnswGraph { void remove_node_for_document(uint32_t docid); + void trim_node_refs_size(); + NodeRef get_node_ref(uint32_t docid) const { return node_refs[docid].load_acquire(); } diff --git a/searchlib/src/vespa/searchlib/tensor/hnsw_index.cpp b/searchlib/src/vespa/searchlib/tensor/hnsw_index.cpp index 8183a7caf3d..ca5f522457a 100644 --- a/searchlib/src/vespa/searchlib/tensor/hnsw_index.cpp +++ b/searchlib/src/vespa/searchlib/tensor/hnsw_index.cpp @@ -5,6 +5,7 @@ #include "hnsw_index_loader.h" #include "hnsw_index_saver.h" #include "random_level_generator.h" +#include <vespa/searchcommon/common/compaction_strategy.h> #include <vespa/searchlib/util/state_explorer_utils.h> #include <vespa/vespalib/data/slime/cursor.h> #include <vespa/vespalib/data/slime/inserter.h> @@ -228,7 +229,7 @@ HnswIndex::search_layer(const TypedCells& input, uint32_t neighbors_to_find, FurthestPriQ& best_neighbors, uint32_t level, const search::BitVector *filter) const { NearestPriQ candidates; - uint32_t doc_id_limit = _graph.node_refs.size(); + uint32_t doc_id_limit = _graph.node_refs_size.load(std::memory_order_acquire); if (filter) { doc_id_limit = std::min(filter->size(), doc_id_limit); } @@ -253,9 +254,11 @@ HnswIndex::search_layer(const TypedCells& input, uint32_t neighbors_to_find, } candidates.pop(); for (uint32_t neighbor_docid : _graph.get_link_array(cand.node_ref, level)) { + if (neighbor_docid >= doc_id_limit) { + continue; + } auto neighbor_ref = _graph.get_node_ref(neighbor_docid); if ((! neighbor_ref.valid()) - || (neighbor_docid >= doc_id_limit) || visited.is_marked(neighbor_docid)) { continue; @@ -282,7 +285,12 @@ HnswIndex::HnswIndex(const DocVectorAccess& vectors, DistanceFunction::UP distan _vectors(vectors), _distance_func(std::move(distance_func)), _level_generator(std::move(level_generator)), - _cfg(cfg) + _cfg(cfg), + _visited_set_pool(), + _cached_level_arrays_memory_usage(), + _cached_level_arrays_address_space_usage(0, 0, (1ull << 32)), + _cached_link_arrays_memory_usage(), + _cached_link_arrays_address_space_usage(0, 0, (1ull << 32)) { assert(_distance_func); } @@ -472,6 +480,93 @@ HnswIndex::trim_hold_lists(generation_t first_used_gen) _graph.links.trimHoldLists(first_used_gen); } +void +HnswIndex::compact_level_arrays(bool compact_memory, bool compact_address_space) +{ + auto context = _graph.nodes.compactWorst(compact_memory, compact_address_space); + uint32_t doc_id_limit = _graph.node_refs.size(); + vespalib::ArrayRef<AtomicEntryRef> refs(&_graph.node_refs[0], doc_id_limit); + context->compact(refs); +} + +void +HnswIndex::compact_link_arrays(bool compact_memory, bool compact_address_space) +{ + auto context = _graph.links.compactWorst(compact_memory, compact_address_space); + uint32_t doc_id_limit = _graph.node_refs.size(); + for (uint32_t doc_id = 1; doc_id < doc_id_limit; ++doc_id) { + EntryRef level_ref = _graph.node_refs[doc_id].load_relaxed(); + if (level_ref.valid()) { + vespalib::ArrayRef<AtomicEntryRef> refs(_graph.nodes.get_writable(level_ref)); + context->compact(refs); + } + } +} + +namespace { + +bool +consider_compact_arrays(const CompactionStrategy& compaction_strategy, vespalib::MemoryUsage& memory_usage, vespalib::AddressSpace& address_space_usage, std::function<void(bool,bool)> compact_arrays) +{ + size_t used_bytes = memory_usage.usedBytes(); + size_t dead_bytes = memory_usage.deadBytes(); + bool compact_memory = compaction_strategy.should_compact_memory(used_bytes, dead_bytes); + size_t used_address_space = address_space_usage.used(); + size_t dead_address_space = address_space_usage.dead(); + bool compact_address_space = compaction_strategy.should_compact_address_space(used_address_space, dead_address_space); + if (compact_memory || compact_address_space) { + compact_arrays(compact_memory, compact_address_space); + return true; + } + return false; +} + +} + +bool +HnswIndex::consider_compact_level_arrays(const CompactionStrategy& compaction_strategy) +{ + return consider_compact_arrays(compaction_strategy, _cached_level_arrays_memory_usage, _cached_level_arrays_address_space_usage, + [this](bool compact_memory, bool compact_address_space) + { compact_level_arrays(compact_memory, compact_address_space); }); +} + +bool +HnswIndex::consider_compact_link_arrays(const CompactionStrategy& compaction_strategy) +{ + return consider_compact_arrays(compaction_strategy, _cached_link_arrays_memory_usage, _cached_link_arrays_address_space_usage, + [this](bool compact_memory, bool compact_address_space) + { compact_link_arrays(compact_memory, compact_address_space); }); +} + +bool +HnswIndex::consider_compact(const CompactionStrategy& compaction_strategy) +{ + bool result = false; + if (consider_compact_level_arrays(compaction_strategy)) { + result = true; + } + if (consider_compact_link_arrays(compaction_strategy)) { + result = true; + } + return result; +} + +vespalib::MemoryUsage +HnswIndex::update_stat() +{ + vespalib::MemoryUsage result; + result.merge(_graph.node_refs.getMemoryUsage()); + _cached_level_arrays_memory_usage = _graph.nodes.getMemoryUsage(); + _cached_level_arrays_address_space_usage = _graph.nodes.addressSpaceUsage(); + result.merge(_cached_level_arrays_memory_usage); + _cached_link_arrays_memory_usage = _graph.links.getMemoryUsage(); + _cached_link_arrays_address_space_usage = _graph.links.addressSpaceUsage(); + result.merge(_cached_link_arrays_memory_usage); + result.merge(_visited_set_pool.memory_usage()); + return result; +} + vespalib::MemoryUsage HnswIndex::memory_usage() const { @@ -526,6 +621,18 @@ HnswIndex::get_state(const vespalib::slime::Inserter& inserter) const _cfg.neighbors_to_explore_at_construction()); } +void +HnswIndex::shrink_lid_space(uint32_t doc_id_limit) +{ + assert(doc_id_limit >= 1u); + assert(doc_id_limit >= _graph.node_refs_size.load(std::memory_order_relaxed)); + uint32_t old_doc_id_limit = _graph.node_refs.size(); + if (doc_id_limit >= old_doc_id_limit) { + return; + } + _graph.node_refs.shrink(doc_id_limit); +} + std::unique_ptr<NearestNeighborIndexSaver> HnswIndex::make_saver() const { diff --git a/searchlib/src/vespa/searchlib/tensor/hnsw_index.h b/searchlib/src/vespa/searchlib/tensor/hnsw_index.h index ef0f38c2263..6f6d213d6cc 100644 --- a/searchlib/src/vespa/searchlib/tensor/hnsw_index.h +++ b/searchlib/src/vespa/searchlib/tensor/hnsw_index.h @@ -80,6 +80,10 @@ protected: RandomLevelGenerator::UP _level_generator; Config _cfg; mutable vespalib::ReusableSetPool _visited_set_pool; + vespalib::MemoryUsage _cached_level_arrays_memory_usage; + vespalib::AddressSpace _cached_level_arrays_address_space_usage; + vespalib::MemoryUsage _cached_link_arrays_memory_usage; + vespalib::AddressSpace _cached_link_arrays_address_space_usage; uint32_t max_links_for_level(uint32_t level) const; void add_link_to(uint32_t docid, uint32_t level, const LinkArrayRef& old_links, uint32_t new_link) { @@ -161,8 +165,15 @@ public: void remove_document(uint32_t docid) override; void transfer_hold_lists(generation_t current_gen) override; void trim_hold_lists(generation_t first_used_gen) override; + void compact_level_arrays(bool compact_memory, bool compact_addreess_space); + void compact_link_arrays(bool compact_memory, bool compact_address_space); + bool consider_compact_level_arrays(const CompactionStrategy& compaction_strategy); + bool consider_compact_link_arrays(const CompactionStrategy& compaction_strategy); + bool consider_compact(const CompactionStrategy& compaction_strategy) override; + vespalib::MemoryUsage update_stat() override; vespalib::MemoryUsage memory_usage() const override; void get_state(const vespalib::slime::Inserter& inserter) const override; + void shrink_lid_space(uint32_t doc_id_limit) override; std::unique_ptr<NearestNeighborIndexSaver> make_saver() const override; bool load(const fileutil::LoadedBuffer& buf) override; @@ -184,6 +195,7 @@ public: void set_node(uint32_t docid, const HnswNode &node); bool check_link_symmetry() const; std::pair<uint32_t, bool> count_reachable_nodes() const; + HnswGraph& get_graph() { return _graph; } static vespalib::datastore::ArrayStoreConfig make_default_node_store_config(); static vespalib::datastore::ArrayStoreConfig make_default_link_store_config(); diff --git a/searchlib/src/vespa/searchlib/tensor/hnsw_index_loader.cpp b/searchlib/src/vespa/searchlib/tensor/hnsw_index_loader.cpp index ac98b28d105..c0aec9ff91a 100644 --- a/searchlib/src/vespa/searchlib/tensor/hnsw_index_loader.cpp +++ b/searchlib/src/vespa/searchlib/tensor/hnsw_index_loader.cpp @@ -38,7 +38,9 @@ HnswIndexLoader::load(const fileutil::LoadedBuffer& buf) } } if (_failed) return false; - _graph.node_refs.ensure_size(num_nodes); + _graph.node_refs.ensure_size(std::max(num_nodes, 1u)); + _graph.node_refs_size.store(std::max(num_nodes, 1u), std::memory_order_release); + _graph.trim_node_refs_size(); auto entry_node_ref = _graph.get_node_ref(entry_docid); _graph.set_entry_node({entry_docid, entry_node_ref, entry_level}); return true; diff --git a/searchlib/src/vespa/searchlib/tensor/nearest_neighbor_index.h b/searchlib/src/vespa/searchlib/tensor/nearest_neighbor_index.h index fd37cf80720..0122738e173 100644 --- a/searchlib/src/vespa/searchlib/tensor/nearest_neighbor_index.h +++ b/searchlib/src/vespa/searchlib/tensor/nearest_neighbor_index.h @@ -14,7 +14,10 @@ namespace vespalib::slime { struct Inserter; } namespace search::fileutil { class LoadedBuffer; } -namespace search { class BitVector; } +namespace search { +class BitVector; +class CompactionStrategy; +} namespace search::tensor { @@ -59,8 +62,11 @@ public: virtual void remove_document(uint32_t docid) = 0; virtual void transfer_hold_lists(generation_t current_gen) = 0; virtual void trim_hold_lists(generation_t first_used_gen) = 0; + virtual bool consider_compact(const CompactionStrategy& compaction_strategy) = 0; + virtual vespalib::MemoryUsage update_stat() = 0; virtual vespalib::MemoryUsage memory_usage() const = 0; virtual void get_state(const vespalib::slime::Inserter& inserter) const = 0; + virtual void shrink_lid_space(uint32_t doc_id_limit) = 0; /** * Creates a saver that is used to save the index to binary form. |