From 2e89964a6f4fa7a978290fd3babbec572b59fe65 Mon Sep 17 00:00:00 2001 From: Henrik Edin Date: Wed, 3 Jun 2020 08:14:38 -0400 Subject: SERVER-48561 Merging unique leaf nodes in the radix tree with the same data should not be a merge conflict --- src/mongo/db/storage/biggie/store.h | 10 +++++++--- src/mongo/db/storage/biggie/store_test.cpp | 19 +++++++++++++++++++ 2 files changed, 26 insertions(+), 3 deletions(-) (limited to 'src/mongo') diff --git a/src/mongo/db/storage/biggie/store.h b/src/mongo/db/storage/biggie/store.h index 80da6009cf9..a2f74a29945 100644 --- a/src/mongo/db/storage/biggie/store.h +++ b/src/mongo/db/storage/biggie/store.h @@ -1407,9 +1407,13 @@ private: current->_children[key] = other->_children[key]; } } else if (baseNode && otherNode && baseNode != otherNode) { - // If all three are unique and leaf nodes, then it is a merge conflict. - if (node->isLeaf() && baseNode->isLeaf() && otherNode->isLeaf()) - throw merge_conflict_exception(); + // If all three are unique and leaf nodes with different data, then it is a merge + // conflict. + if (node->isLeaf() && baseNode->isLeaf() && otherNode->isLeaf()) { + if (node->_data != baseNode->_data || baseNode->_data != otherNode->_data) + throw merge_conflict_exception(); + continue; + } // If the keys and data are all the exact same, then we can keep recursing. // Otherwise, we manually resolve the differences element by element. The diff --git a/src/mongo/db/storage/biggie/store_test.cpp b/src/mongo/db/storage/biggie/store_test.cpp index c49b8411e52..a61c1fe978f 100644 --- a/src/mongo/db/storage/biggie/store_test.cpp +++ b/src/mongo/db/storage/biggie/store_test.cpp @@ -1709,6 +1709,25 @@ TEST_F(RadixStoreTest, MergeConflictingInsertions) { ASSERT_THROWS(thisStore.merge3(baseStore, otherStore), merge_conflict_exception); } +TEST_F(RadixStoreTest, MergeDifferentLeafNodesSameDataTest) { + baseStore.insert({"a", "a"}); + baseStore.insert({"aa", "a"}); + + otherStore = baseStore; + otherStore.insert({"aaa", "a"}); + otherStore.erase("aaa"); + + thisStore = baseStore; + thisStore.insert({"aab", "b"}); + thisStore.erase("aab"); + + thisStore.merge3(baseStore, otherStore); + + expected.insert({"a", "a"}); + expected.insert({"aa", "a"}); + ASSERT_TRUE(thisStore == expected); +} + TEST_F(RadixStoreTest, UpperBoundTest) { value_type value1 = std::make_pair("foo", "1"); value_type value2 = std::make_pair("bar", "2"); -- cgit v1.2.1