Add compaction of BTreeStore.

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<TreeStore::KeyDataType> additions;
         std::vector<TreeStore::KeyType> 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<EntryRef> 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<uint32_t>& to_hold);
     void move_btree_nodes(EntryRef ref);
 
+    std::vector<uint32_t> start_compact_worst_buffers();
+    EntryRef move(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 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<uint32_t>
 BTreeStore<KeyT, DataT, AggrT, CompareT, TraitsT, AggrCalcT>::
 start_compact_worst_btree_nodes()
 {
+    _builder.clear();
     return _allocator.start_compact_worst();
 }
 
@@ -1002,4 +1003,35 @@ move_btree_nodes(EntryRef ref)
     }
 }
 
+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_buffers()
+{
+    freeze();
+    return _store.startCompactWorstBuffers(true, false);
+}
+
+template <typename KeyT, typename DataT, typename AggrT, typename CompareT,
+          typename TraitsT, typename AggrCalcT>
+typename BTreeStore<KeyT, DataT, AggrT, CompareT, TraitsT, AggrCalcT>::EntryRef
+BTreeStore<KeyT, DataT, AggrT, CompareT, TraitsT, AggrCalcT>::
+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;
+}
+
 }