diff options
author | Henrik Edin <henrik.edin@mongodb.com> | 2020-06-16 14:57:46 -0400 |
---|---|---|
committer | Evergreen Agent <no-reply@evergreen.mongodb.com> | 2020-06-18 13:27:09 +0000 |
commit | b33246adf882e0cda564384e6574d684e6cf7c6e (patch) | |
tree | 13d8b8363f665fd5cc0f07a05497cbbcebc007fc /src/mongo/db/storage | |
parent | 89f797fe34c6dda8fa571f7d161d9871eba151a5 (diff) | |
download | mongo-b33246adf882e0cda564384e6574d684e6cf7c6e.tar.gz |
SERVER-48746 Radix tree merge compresses nodes if needed and does not leave leaf nodes without data
Diffstat (limited to 'src/mongo/db/storage')
-rw-r--r-- | src/mongo/db/storage/biggie/store.h | 24 | ||||
-rw-r--r-- | src/mongo/db/storage/biggie/store_test.cpp | 67 |
2 files changed, 85 insertions, 6 deletions
diff --git a/src/mongo/db/storage/biggie/store.h b/src/mongo/db/storage/biggie/store.h index a2f74a29945..3ef7fab3e0d 100644 --- a/src/mongo/db/storage/biggie/store.h +++ b/src/mongo/db/storage/biggie/store.h @@ -1351,11 +1351,11 @@ private: * Merges changes from base to other into current. Throws merge_conflict_exception if there are * merge conflicts. */ - void _merge3Helper(Node* current, - const Node* base, - const Node* other, - std::vector<Node*>& context, - std::vector<uint8_t>& trieKeyIndex) { + Node* _merge3Helper(Node* current, + const Node* base, + const Node* other, + std::vector<Node*>& context, + std::vector<uint8_t>& trieKeyIndex) { context.push_back(current); // Root doesn't have a trie key. @@ -1423,7 +1423,17 @@ private: if (node->_trieKey == baseNode->_trieKey && baseNode->_trieKey == otherNode->_trieKey && node->_data == baseNode->_data && baseNode->_data == otherNode->_data) { - _merge3Helper(node, baseNode, otherNode, context, trieKeyIndex); + Node* updatedNode = + _merge3Helper(node, baseNode, otherNode, context, trieKeyIndex); + if (!updatedNode->_data) { + // Drop if leaf node without data, that is not valid. Otherwise we might + // need to compress if we have only one child. + if (updatedNode->isLeaf()) { + current->_children[key] = nullptr; + } else { + _compressOnlyChild(updatedNode); + } + } } else { _mergeResolveConflict(node, baseNode, otherNode); _rebuildContext(context, trieKeyIndex); @@ -1444,6 +1454,8 @@ private: context.pop_back(); if (!trieKeyIndex.empty()) trieKeyIndex.pop_back(); + + return current; } Node* _begin(Node* root) const noexcept { diff --git a/src/mongo/db/storage/biggie/store_test.cpp b/src/mongo/db/storage/biggie/store_test.cpp index a61c1fe978f..5dc07e35df3 100644 --- a/src/mongo/db/storage/biggie/store_test.cpp +++ b/src/mongo/db/storage/biggie/store_test.cpp @@ -1649,6 +1649,73 @@ TEST_F(RadixStoreTest, MergeBaseKeyNegativeCharTest) { ASSERT_EQ(thisStore.find("aac")->second, "c"); } +TEST_F(RadixStoreTest, MergeWillRemoveEmptyInternalLeaf) { + baseStore.insert({"aa", "a"}); + baseStore.insert({"ab", "b"}); + baseStore.insert({"ac", "c"}); + baseStore.insert({"ad", "d"}); + + otherStore = baseStore; + otherStore.erase("ac"); + otherStore.erase("ad"); + + thisStore = baseStore; + thisStore.erase("aa"); + thisStore.erase("ab"); + + thisStore.merge3(baseStore, otherStore); + + // The store is in a valid state that is traversable and we should find no nodes + ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0); +} + +TEST_F(RadixStoreTest, MergeWillRemoveEmptyInternalLeafWithUnrelatedBranch) { + baseStore.insert({"aa", "a"}); + baseStore.insert({"ab", "b"}); + baseStore.insert({"ac", "c"}); + baseStore.insert({"ad", "d"}); + baseStore.insert({"b", "b"}); + + otherStore = baseStore; + otherStore.erase("ac"); + otherStore.erase("ad"); + otherStore.erase("b"); + + thisStore = baseStore; + thisStore.erase("aa"); + thisStore.erase("ab"); + + thisStore.merge3(baseStore, otherStore); + + // The store is in a valid state that is traversable and we should find no nodes + ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0); +} + +TEST_F(RadixStoreTest, MergeWillCompressNodes) { + baseStore.insert({"aa", "a"}); + baseStore.insert({"ab", "b"}); + baseStore.insert({"ac", "c"}); + baseStore.insert({"ad", "d"}); + + otherStore = baseStore; + otherStore.erase("ab"); + otherStore.erase("ac"); + + thisStore = baseStore; + thisStore.erase("aa"); + + thisStore.merge3(baseStore, otherStore); + + // The store is in a valid state that is traversable and we should find a single node + ASSERT_EQ(thisStore.find("ad")->second, "d"); + ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 1); + + // Removing this node should not result in an internal leaf node without data + thisStore.erase("ad"); + + ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0); +} + TEST_F(RadixStoreTest, MergeConflictingModifications) { value_type value1 = std::make_pair("foo", "1"); value_type value2 = std::make_pair("foo", "2"); |