SERVER-38259 Don't copy the tree on changes if all cursors are positioned behind it in BiggieSE

author: Gregory Wlodarek <gregory.wlodarek@mongodb.com> 2018-11-26 20:06:26 -0500
committer: Gregory Wlodarek <gregory.wlodarek@mongodb.com> 2018-12-02 17:56:25 -0500
commit: 88bcf424bc9830454847f015757ad710ee30827d (patch)
tree: d801fb326dcd1e63c1d0d03d1fcd7f2bf6cc0692
parent: 9ad645839a0c2aa97b58a327b818aa72962efc31 (diff)
download: mongo-88bcf424bc9830454847f015757ad710ee30827d.tar.gz
2 files changed, 206 insertions, 36 deletions
diff --git a/src/mongo/db/storage/biggie/store.h b/src/mongo/db/storage/biggie/store.h
index 060d8885018..bd838867e53 100644
--- a/src/mongo/db/storage/biggie/store.h
+++ b/src/mongo/db/storage/biggie/store.h
@@ -61,6 +61,8 @@ class RadixStore {
     class Node;
     class Head;
 
+    friend class RadixStoreTest;
+
 public:
     using mapped_type = T;
     using value_type = std::pair<const Key, mapped_type>;
@@ -83,7 +85,9 @@ public:
 
         radix_iterator() : _root(nullptr), _current(nullptr) {}
 
-        ~radix_iterator() = default;
+        ~radix_iterator() {
+            updateTreeView(/*stopIfMultipleCursors=*/true);
+        }
 
         radix_iterator& operator++() {
             repositionIfChanged();
@@ -135,10 +139,7 @@ public:
             // Copy the key from _current before we move our _root reference.
             auto key = _current->_data->first;
 
-            do {
-                _root = _root->_nextVersion;
-            } while (_root->_nextVersion);
-
+            updateTreeView();
             RadixStore store(*_root);
 
             // Find the same or next node in the updated tree.
@@ -228,6 +229,18 @@ public:
             } while (!_current->_data);
         }
 
+        void updateTreeView(bool stopIfMultipleCursors = false) {
+            while (_root && _root->_nextVersion) {
+                if (stopIfMultipleCursors && _root.use_count() > 1)
+                    return;
+
+                bool clearPreviousFlag = _root.use_count() == 1;
+                _root = _root->_nextVersion;
+                if (clearPreviousFlag)
+                    _root->_hasPreviousVersion = false;
+            }
+        }
+
         // "_root" is a pointer to the root of the tree over which this is iterating.
         std::shared_ptr<Head> _root;
 
@@ -279,7 +292,9 @@ public:
             }
         }
 
-        ~reverse_radix_iterator() = default;
+        ~reverse_radix_iterator() {
+            updateTreeView(/*stopIfMultipleCursors=*/true);
+        }
 
         reverse_radix_iterator& operator++() {
             repositionIfChanged();
@@ -331,10 +346,7 @@ public:
             // Copy the key from _current before we move our _root reference.
             auto key = _current->_data->first;
 
-            do {
-                _root = _root->_nextVersion;
-            } while (_root->_nextVersion);
-
+            updateTreeView();
             RadixStore store(*_root);
 
             // Find the same or next node in the updated tree.
@@ -420,6 +432,18 @@ public:
             } while (!_current->isLeaf());
         }
 
+        void updateTreeView(bool stopIfMultipleCursors = false) {
+            while (_root && _root->_nextVersion) {
+                if (stopIfMultipleCursors && _root.use_count() > 1)
+                    return;
+
+                bool clearPreviousFlag = _root.use_count() == 1;
+                _root = _root->_nextVersion;
+                if (clearPreviousFlag)
+                    _root->_hasPreviousVersion = false;
+            }
+        }
+
         // "_root" is a pointer to the root of the tree over which this is iterating.
         std::shared_ptr<Head> _root;
 
@@ -520,7 +544,8 @@ public:
         std::vector<std::pair<Node*, bool>> context;
 
         Node* prev = _root.get();
-        bool isUniquelyOwned = _root.use_count() == 1;
+        int rootUseCount = _root->_hasPreviousVersion ? 2 : 1;
+        bool isUniquelyOwned = _root.use_count() == rootUseCount;
         context.push_back(std::make_pair(prev, isUniquelyOwned));
 
         Node* node = nullptr;
@@ -562,8 +587,10 @@ public:
 
         if (!isUniquelyOwned) {
             invariant(!_root->_nextVersion);
+            invariant(_root.use_count() > rootUseCount);
             _root->_nextVersion = std::make_shared<Head>(*_root);
             _root = _root->_nextVersion;
+            _root->_hasPreviousVersion = true;
             parent = _root.get();
         }
 
@@ -850,26 +877,37 @@ private:
         Head() = default;
         Head(std::vector<uint8_t> key) : Node(key) {}
         Head(const Node& other) : Node(other) {}
-        Head(const Head& other) : Node(other) {
-            _nextVersion = other._nextVersion;
+        Head(const Head& other) : Node(other) {}
+
+        ~Head() {
+            if (_nextVersion)
+                _nextVersion->_hasPreviousVersion = false;
         }
 
         friend void swap(Head& first, Head& second) {
             Node::swap(first, second);
-            std::swap(first._nextVersion, second._nextVersion);
         }
 
-        Head(Head&& other) : Node(std::move(other)) {
-            _nextVersion = std::move(other._nextVersion);
-        }
+        Head(Head&& other) : Node(std::move(other)) {}
 
         Head& operator=(const Head other) {
             swap(*this, other);
             return *this;
         }
 
+        bool hasPreviousVersion() const {
+            return _hasPreviousVersion;
+        }
+
     protected:
+        // Forms a singly linked list of versions that is needed to reposition cursors after
+        // modifications have been made.
         std::shared_ptr<Head> _nextVersion;
+
+        // While we have cursors that haven't been repositioned to the latest tree, this will be
+        // true to help us understand when to copy on modifications due to the extra shared pointer
+        // _nextVersion.
+        bool _hasPreviousVersion = false;
     };
 
     /**
@@ -949,6 +987,31 @@ private:
     }
 
     /**
+     * Makes a copy of the _root node if it isn't uniquely owned during an operation that will
+     * modify the tree.
+     *
+     * The _root node wouldn't be uniquely owned only when there are cursors positioned on the
+     * latest version of the tree. Cursors that are not yet repositioned onto the latest version of
+     * the tree are not considered to be sharing the _root for modifying operations.
+     */
+    void _makeRootUnique() {
+        int rootUseCount = _root->_hasPreviousVersion ? 2 : 1;
+
+        if (_root.use_count() == rootUseCount)
+            return;
+
+        invariant(_root.use_count() > rootUseCount);
+        // Copy the node on a modifying operation when the root isn't unique.
+
+        // There should not be any _nextVersion set in the _root otherwise our tree would have
+        // multiple HEADs.
+        invariant(!_root->_nextVersion);
+        _root->_nextVersion = std::make_shared<Head>(*_root);
+        _root = _root->_nextVersion;
+        _root->_hasPreviousVersion = true;
+    }
+
+    /**
      * _upsertWithCopyOnSharedNodes is a helper function to help manage copy on modification for the
      * tree. This function follows the path for the to-be modified node using the keystring. If at
      * any point, the path is no longer uniquely owned, the following nodes are copied to prevent
@@ -984,16 +1047,7 @@ private:
         int depth = _root->_depth + _root->_trieKey.size();
         uint8_t childFirstChar = static_cast<uint8_t>(charKey[depth]);
 
-        if (_root.use_count() > 1) {
-            // Copy the node on a modifying operation when the root isn't unique.
-
-            // There should not be any _nextVersion set in the _root otherwise our tree would have
-            // multiple HEADs.
-            invariant(!_root->_nextVersion);
-            _root->_nextVersion = std::make_shared<Head>(*_root);
-            _root = _root->_nextVersion;
-        }
-
+        _makeRootUnique();
         _root->_numSubtreeElems += elemNum;
         _root->_sizeSubtreeElems += elemSize;
 
@@ -1217,11 +1271,7 @@ private:
             return nullptr;
 
         // The first node should always be the root node.
-        if (_root.use_count() > 1) {
-            invariant(!_root->_nextVersion);
-            _root->_nextVersion = std::make_shared<Head>(*_root);
-            _root = _root->_nextVersion;
-        }
+        _makeRootUnique();
         context[0] = _root.get();
 
         // If the context only contains the root, and it was copied, return the new root.
diff --git a/src/mongo/db/storage/biggie/store_test.cpp b/src/mongo/db/storage/biggie/store_test.cpp
index c4ff00caf49..f8bb573f320 100644
--- a/src/mongo/db/storage/biggie/store_test.cpp
+++ b/src/mongo/db/storage/biggie/store_test.cpp
@@ -35,12 +35,23 @@
 
 namespace mongo {
 namespace biggie {
-namespace {
 
-using StringStore = RadixStore<std::string, std::string>;
 using value_type = StringStore::value_type;
 
 class RadixStoreTest : public unittest::Test {
+public:
+    StringStore::Head* getRootAddress() const {
+        return thisStore._root.get();
+    }
+
+    int getRootCount() const {
+        return thisStore._root.use_count();
+    }
+
+    bool hasPreviousVersion() const {
+        return thisStore._root->hasPreviousVersion();
+    }
+
 protected:
     StringStore thisStore;
     StringStore parallelStore;
@@ -2311,6 +2322,115 @@ TEST_F(RadixStoreTest, AvoidComparingDifferentTreeVersions) {
     }
 }
 
-}  // namespace
-}  // mongo namespace
+TEST_F(RadixStoreTest, TreeUniqueness) {
+    value_type value1 = std::make_pair("a", "1");
+    value_type value2 = std::make_pair("b", "2");
+    value_type value3 = std::make_pair("c", "3");
+    value_type value4 = std::make_pair("d", "4");
+
+    auto rootAddr = getRootAddress();
+    thisStore.insert(value_type(value1));
+
+    // Neither the address or count should change.
+    ASSERT_EQUALS(rootAddr, getRootAddress());
+    ASSERT_EQUALS(1, getRootCount());
+
+    thisStore.insert(value_type(value2));
+    ASSERT_EQUALS(rootAddr, getRootAddress());
+    ASSERT_EQUALS(1, getRootCount());
+
+    {
+        // Make the tree shared.
+        auto it = thisStore.begin();
+        ASSERT_EQUALS(rootAddr, getRootAddress());
+        ASSERT_EQUALS(2, getRootCount());
+
+        // Inserting should make a copy of the tree.
+        thisStore.insert(value_type(value3));
+
+        // The root's address should change.
+        ASSERT_NOT_EQUALS(rootAddr, getRootAddress());
+        rootAddr = getRootAddress();
+
+        // Count should remain 2 because of _nextVersion
+        ASSERT_EQUALS(2, getRootCount());
+
+        // Inserting again shouldn't make a copy because the cursor hasn't been updated
+        thisStore.insert(value_type(value4));
+        ASSERT_EQUALS(rootAddr, getRootAddress());
+        ASSERT_EQUALS(2, getRootCount());
+
+        // Use the pointer to reposition it on the new tree.
+        *it;
+        ASSERT_EQUALS(rootAddr, getRootAddress());
+        ASSERT_EQUALS(2, getRootCount());
+
+        thisStore.erase("d");
+        ASSERT_NOT_EQUALS(rootAddr, getRootAddress());
+        rootAddr = getRootAddress();
+        ASSERT_EQUALS(2, getRootCount());
+    }
+
+    ASSERT_EQUALS(rootAddr, getRootAddress());
+    ASSERT_EQUALS(1, getRootCount());
+
+    thisStore.erase("c");
+    thisStore.erase("b");
+    thisStore.erase("a");
+
+    ASSERT_EQUALS(rootAddr, getRootAddress());
+    ASSERT_EQUALS(1, getRootCount());
+}
+
+TEST_F(RadixStoreTest, HasPreviousVersionFlagTest) {
+    value_type value1 = std::make_pair("a", "1");
+    value_type value2 = std::make_pair("b", "2");
+    value_type value3 = std::make_pair("c", "3");
+
+    ASSERT_FALSE(hasPreviousVersion());
+    thisStore.insert(value_type(value1));
+
+    {
+        auto it = thisStore.begin();
+        ASSERT_FALSE(hasPreviousVersion());
+    }
+
+    ASSERT_FALSE(hasPreviousVersion());
+
+    {
+        auto it = thisStore.begin();
+        ASSERT_FALSE(hasPreviousVersion());
+
+        thisStore.insert(value_type(value2));
+        ASSERT_TRUE(hasPreviousVersion());
+    }
+
+    ASSERT_FALSE(hasPreviousVersion());
+    thisStore.erase("b");
+
+    // Use multiple cursors
+    {
+        auto it = thisStore.begin();
+        auto it2 = thisStore.begin();
+        ASSERT_FALSE(hasPreviousVersion());
+
+        thisStore.insert(value_type(value2));
+        ASSERT_TRUE(hasPreviousVersion());
+
+        *it;  // Change to repositionIfChanged when merging (SERVER-38262 in master);
+        ASSERT_TRUE(hasPreviousVersion());
+
+        *it2;
+        ASSERT_FALSE(hasPreviousVersion());
+
+        thisStore.insert(value_type(value3));
+        ASSERT_TRUE(hasPreviousVersion());
+
+        *it;
+    }
+
+    ASSERT_FALSE(hasPreviousVersion());
+}
+
 }  // biggie namespace
+}  // mongo namespace
author	Gregory Wlodarek <gregory.wlodarek@mongodb.com>	2018-11-26 20:06:26 -0500
committer	Gregory Wlodarek <gregory.wlodarek@mongodb.com>	2018-12-02 17:56:25 -0500
commit	88bcf424bc9830454847f015757ad710ee30827d (patch)
tree	d801fb326dcd1e63c1d0d03d1fcd7f2bf6cc0692
parent	9ad645839a0c2aa97b58a327b818aa72962efc31 (diff)
download	mongo-88bcf424bc9830454847f015757ad710ee30827d.tar.gz