Add compaction of B-tree nodes in BTreeStore.

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);
+        }
+    }
+}
+
 }