From 461c9bb041bc0cf9537ba118811a921db716adf6 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Fri, 16 Apr 2021 12:28:57 +0200 Subject: Add compaction of BTreeStore. --- .../tests/btree/btree_store/btree_store_test.cpp | 81 ++++++++++++++++++---- vespalib/src/vespa/vespalib/btree/btreerootbase.h | 5 ++ vespalib/src/vespa/vespalib/btree/btreestore.h | 3 + vespalib/src/vespa/vespalib/btree/btreestore.hpp | 32 +++++++++ 4 files changed, 106 insertions(+), 15 deletions(-) diff --git a/vespalib/src/tests/btree/btree_store/btree_store_test.cpp b/vespalib/src/tests/btree/btree_store/btree_store_test.cpp index b75c2722d80..7eaf298ab40 100644 --- a/vespalib/src/tests/btree/btree_store/btree_store_test.cpp +++ b/vespalib/src/tests/btree/btree_store/btree_store_test.cpp @@ -31,7 +31,7 @@ protected: _store.trimHoldLists(_gen_handler.getFirstUsedGeneration()); } - EntryRef make_tree(int start_key, int end_key) + EntryRef add_sequence(int start_key, int end_key) { std::vector additions; std::vector removals; @@ -57,6 +57,8 @@ protected: _store.foreach_frozen_key(root, [&sequence](int key) { sequence.emplace_back(key); }); return sequence; } + + void test_compact_sequence(uint32_t sequence_length); }; BTreeStoreTest::BTreeStoreTest() @@ -65,28 +67,77 @@ BTreeStoreTest::BTreeStoreTest() { } -BTreeStoreTest::~BTreeStoreTest() = default; +BTreeStoreTest::~BTreeStoreTest() +{ + _store.clearBuilder(); + inc_generation(); +} + +void +BTreeStoreTest::test_compact_sequence(uint32_t sequence_length) +{ + auto &store = _store; + EntryRef ref1 = add_sequence(4, 4 + sequence_length); + EntryRef ref2 = add_sequence(5, 5 + sequence_length); + EntryRef old_ref1 = ref1; + EntryRef old_ref2 = ref2; + std::vector refs; + for (int i = 0; i < 1000; ++i) { + refs.emplace_back(add_sequence(i + 6, i + 6 + sequence_length)); + } + for (auto& ref : refs) { + store.clear(ref); + } + inc_generation(); + auto usage_before = store.getMemoryUsage(); + for (uint32_t pass = 0; pass < 15; ++pass) { + auto to_hold = store.start_compact_worst_buffers(); + ref1 = store.move(ref1); + ref2 = store.move(ref2); + store.finishCompact(to_hold); + inc_generation(); + } + EXPECT_NE(old_ref1, ref1); + EXPECT_NE(old_ref2, ref2); + EXPECT_EQ(make_exp_sequence(4, 4 + sequence_length), get_sequence(ref1)); + EXPECT_EQ(make_exp_sequence(5, 5 + sequence_length), get_sequence(ref2)); + auto usage_after = store.getMemoryUsage(); + EXPECT_GT(usage_before.deadBytes(), usage_after.deadBytes()); + store.clear(ref1); + store.clear(ref2); +} 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)); + EntryRef ref1 = add_sequence(4, 40); + EntryRef ref2 = add_sequence(100, 130); + store.clear(add_sequence(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)); + for (uint32_t pass = 0; pass < 15; ++pass) { + auto to_hold = store.start_compact_worst_btree_nodes(); + store.move_btree_nodes(ref1); + store.move_btree_nodes(ref2); + store.finish_compact_worst_btree_nodes(to_hold); + inc_generation(); + } + EXPECT_EQ(make_exp_sequence(4, 40), get_sequence(ref1)); + EXPECT_EQ(make_exp_sequence(100, 130), get_sequence(ref2)); auto usage_after = store.getMemoryUsage(); EXPECT_GT(usage_before.deadBytes(), usage_after.deadBytes()); - store.clear(root1); - store.clear(root2); - inc_generation(); + store.clear(ref1); + store.clear(ref2); +} + +TEST_F(BTreeStoreTest, require_that_short_arrays_are_compacted) +{ + test_compact_sequence(4); +} + +TEST_F(BTreeStoreTest, require_that_btree_roots_are_compacted) +{ + test_compact_sequence(10); } } diff --git a/vespalib/src/vespa/vespalib/btree/btreerootbase.h b/vespalib/src/vespa/vespalib/btree/btreerootbase.h index 1813e6de3d9..f1f44b6aae6 100644 --- a/vespalib/src/vespa/vespalib/btree/btreerootbase.h +++ b/vespalib/src/vespa/vespalib/btree/btreerootbase.h @@ -52,6 +52,11 @@ public: allocator.needFreeze(this); } + void prepare_hold() { + // entry for _root is owned by new copy of BTreeRootBase. + _root = BTreeNode::Ref(); + } + void setRoots(BTreeNode::Ref newRoot) { _root = newRoot; _frozenRoot = newRoot.ref(); diff --git a/vespalib/src/vespa/vespalib/btree/btreestore.h b/vespalib/src/vespa/vespalib/btree/btreestore.h index 14d3922c182..0125d74cfc8 100644 --- a/vespalib/src/vespa/vespalib/btree/btreestore.h +++ b/vespalib/src/vespa/vespalib/btree/btreestore.h @@ -393,6 +393,9 @@ public: void finish_compact_worst_btree_nodes(const std::vector& to_hold); void move_btree_nodes(EntryRef ref); + std::vector start_compact_worst_buffers(); + EntryRef move(EntryRef ref); + private: static constexpr size_t MIN_BUFFER_ARRAYS = 128u; template diff --git a/vespalib/src/vespa/vespalib/btree/btreestore.hpp b/vespalib/src/vespa/vespalib/btree/btreestore.hpp index 12f91999a77..9cde2979f68 100644 --- a/vespalib/src/vespa/vespalib/btree/btreestore.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreestore.hpp @@ -974,6 +974,7 @@ std::vector BTreeStore:: start_compact_worst_btree_nodes() { + _builder.clear(); return _allocator.start_compact_worst(); } @@ -1002,4 +1003,35 @@ move_btree_nodes(EntryRef ref) } } +template +std::vector +BTreeStore:: +start_compact_worst_buffers() +{ + freeze(); + return _store.startCompactWorstBuffers(true, false); +} + +template +typename BTreeStore::EntryRef +BTreeStore:: +move(EntryRef ref) +{ + if (!ref.valid() || !_store.getCompacting(ref)) { + return ref; + } + RefType iRef(ref); + uint32_t clusterSize = getClusterSize(iRef); + if (clusterSize == 0) { + BTreeType *tree = getWTreeEntry(iRef); + auto ref_and_ptr = allocBTreeCopy(*tree); + tree->prepare_hold(); + return ref_and_ptr.ref; + } + const KeyDataType *shortArray = getKeyDataEntry(iRef, clusterSize); + return allocKeyDataCopy(shortArray, clusterSize).ref; +} + } -- cgit v1.2.3