diff options
author | Tor Egge <Tor.Egge@online.no> | 2021-04-15 15:44:12 +0200 |
---|---|---|
committer | Tor Egge <Tor.Egge@online.no> | 2021-04-15 16:07:29 +0200 |
commit | 169dfe734ab11cb5d54b7445650614ce541b6ebc (patch) | |
tree | c70fc9f468c880cfa3b6fe4346327cec36a6ad03 | |
parent | 7dd25b911e859fe609928bb9794444d2749ce0ba (diff) |
Add compaction of B-tree nodes in BTreeStore.
-rw-r--r-- | vespalib/CMakeLists.txt | 1 | ||||
-rw-r--r-- | vespalib/src/tests/btree/btree_store/CMakeLists.txt | 9 | ||||
-rw-r--r-- | vespalib/src/tests/btree/btree_store/btree_store_test.cpp | 94 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btreestore.h | 4 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btreestore.hpp | 34 |
5 files changed, 142 insertions, 0 deletions
diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt index 3bdd477fcb6..5cf06093977 100644 --- a/vespalib/CMakeLists.txt +++ b/vespalib/CMakeLists.txt @@ -26,6 +26,7 @@ vespa_define_module( src/tests/benchmark_timer src/tests/box src/tests/btree + src/tests/btree/btree_store src/tests/child_process src/tests/component src/tests/compress diff --git a/vespalib/src/tests/btree/btree_store/CMakeLists.txt b/vespalib/src/tests/btree/btree_store/CMakeLists.txt new file mode 100644 index 00000000000..2913267bea2 --- /dev/null +++ b/vespalib/src/tests/btree/btree_store/CMakeLists.txt @@ -0,0 +1,9 @@ +# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +vespa_add_executable(vespalib_btree_store_test_app TEST + SOURCES + btree_store_test.cpp + DEPENDS + vespalib + GTest::GTest +) +vespa_add_test(NAME vespalib_btree_store_test_app COMMAND vespalib_btree_store_test_app COST 30) diff --git a/vespalib/src/tests/btree/btree_store/btree_store_test.cpp b/vespalib/src/tests/btree/btree_store/btree_store_test.cpp new file mode 100644 index 00000000000..b75c2722d80 --- /dev/null +++ b/vespalib/src/tests/btree/btree_store/btree_store_test.cpp @@ -0,0 +1,94 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include <vespa/vespalib/btree/btreestore.h> +#include <vespa/vespalib/btree/btreenodeallocator.hpp> +#include <vespa/vespalib/btree/btreeroot.hpp> +#include <vespa/vespalib/btree/btreestore.hpp> +#include <vespa/vespalib/datastore/buffer_type.hpp> +#include <vespa/vespalib/gtest/gtest.h> + +using vespalib::GenerationHandler; +using vespalib::datastore::EntryRef; + +namespace vespalib::btree { + +using MyTraits = BTreeTraits<4, 4, 31, false>; +using TreeStore = BTreeStore<int, int, btree::NoAggregated, std::less<int>, MyTraits>; + +class BTreeStoreTest : public ::testing::Test { +protected: + GenerationHandler _gen_handler; + TreeStore _store; + + BTreeStoreTest(); + ~BTreeStoreTest(); + + void inc_generation() + { + _store.freeze(); + _store.transferHoldLists(_gen_handler.getCurrentGeneration()); + _gen_handler.incGeneration(); + _store.trimHoldLists(_gen_handler.getFirstUsedGeneration()); + } + + EntryRef make_tree(int start_key, int end_key) + { + std::vector<TreeStore::KeyDataType> additions; + std::vector<TreeStore::KeyType> removals; + EntryRef root; + for (int i = start_key; i < end_key; ++i) { + additions.emplace_back(i, 0); + } + _store.apply(root, + &additions[0], &additions[0] + additions.size(), + &removals[0], &removals[0] + removals.size()); + return root; + } + static std::vector<int> make_exp_sequence(int start_key, int end_key) + { + std::vector<int> sequence; + for (int i = start_key; i < end_key; ++i) { + sequence.emplace_back(i); + } + return sequence; + } + std::vector<int> get_sequence(EntryRef root) const { + std::vector<int> sequence; + _store.foreach_frozen_key(root, [&sequence](int key) { sequence.emplace_back(key); }); + return sequence; + } +}; + +BTreeStoreTest::BTreeStoreTest() + : _gen_handler(), + _store() +{ +} + +BTreeStoreTest::~BTreeStoreTest() = default; + +TEST_F(BTreeStoreTest, require_that_nodes_for_multiple_btrees_are_compacted) +{ + auto &store = this->_store; + EntryRef root1 = make_tree(4, 40); + EntryRef root2 = make_tree(100, 130); + store.clear(make_tree(1000, 20000)); + inc_generation(); + auto usage_before = store.getMemoryUsage(); + auto to_hold = store.start_compact_worst_btree_nodes(); + store.move_btree_nodes(root1); + store.move_btree_nodes(root2); + store.finish_compact_worst_btree_nodes(to_hold); + inc_generation(); + EXPECT_EQ(make_exp_sequence(4, 40), get_sequence(root1)); + EXPECT_EQ(make_exp_sequence(100, 130), get_sequence(root2)); + auto usage_after = store.getMemoryUsage(); + EXPECT_GT(usage_before.deadBytes(), usage_after.deadBytes()); + store.clear(root1); + store.clear(root2); + inc_generation(); +} + +} + +GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/btree/btreestore.h b/vespalib/src/vespa/vespalib/btree/btreestore.h index d822c72de60..14d3922c182 100644 --- a/vespalib/src/vespa/vespalib/btree/btreestore.h +++ b/vespalib/src/vespa/vespalib/btree/btreestore.h @@ -389,6 +389,10 @@ public: void foreach_frozen(EntryRef ref, FunctionType func) const; + std::vector<uint32_t> start_compact_worst_btree_nodes(); + void finish_compact_worst_btree_nodes(const std::vector<uint32_t>& to_hold); + void move_btree_nodes(EntryRef ref); + private: static constexpr size_t MIN_BUFFER_ARRAYS = 128u; template <typename FunctionType, bool Frozen> diff --git a/vespalib/src/vespa/vespalib/btree/btreestore.hpp b/vespalib/src/vespa/vespalib/btree/btreestore.hpp index bd7331bc996..12f91999a77 100644 --- a/vespalib/src/vespa/vespalib/btree/btreestore.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreestore.hpp @@ -968,4 +968,38 @@ getAggregated(const EntryRef ref) const return a; } +template <typename KeyT, typename DataT, typename AggrT, typename CompareT, + typename TraitsT, typename AggrCalcT> +std::vector<uint32_t> +BTreeStore<KeyT, DataT, AggrT, CompareT, TraitsT, AggrCalcT>:: +start_compact_worst_btree_nodes() +{ + return _allocator.start_compact_worst(); +} + +template <typename KeyT, typename DataT, typename AggrT, typename CompareT, + typename TraitsT, typename AggrCalcT> +void +BTreeStore<KeyT, DataT, AggrT, CompareT, TraitsT, AggrCalcT>:: +finish_compact_worst_btree_nodes(const std::vector<uint32_t>& to_hold) +{ + _allocator.finishCompact(to_hold); +} + +template <typename KeyT, typename DataT, typename AggrT, typename CompareT, + typename TraitsT, typename AggrCalcT> +void +BTreeStore<KeyT, DataT, AggrT, CompareT, TraitsT, AggrCalcT>:: +move_btree_nodes(EntryRef ref) +{ + if (ref.valid()) { + RefType iRef(ref); + uint32_t clusterSize = getClusterSize(iRef); + if (clusterSize == 0) { + BTreeType *tree = getWTreeEntry(iRef); + tree->move_nodes(_allocator); + } + } +} + } |