SERVER-59409 part 1, add class ElectionIdSetVersionPair to be used in TopologyStateMachine later

7 files changed, 292 insertions, 1 deletions

diff --git a/src/mongo/client/sdam/SConscript b/src/mongo/client/sdam/SConscript
index b0bfc6108b6..923dfa83fc4 100644
--- a/src/mongo/client/sdam/SConscript
+++ b/src/mongo/client/sdam/SConscript
@@ -138,6 +138,9 @@ env.CppUnitTest(
 
 env.CppUnitTest(
     target='topology_state_machine_test',
-    source=['topology_state_machine_test.cpp'],
+    source=[
+        'election_id_set_version_pair_test.cpp',
+        'topology_state_machine_test.cpp',
+    ],
     LIBDEPS=['sdam', 'sdam_test'],
 )
diff --git a/src/mongo/client/sdam/election_id_set_version_pair.h b/src/mongo/client/sdam/election_id_set_version_pair.h
new file mode 100644
index 00000000000..33e8667c935
--- /dev/null
+++ b/src/mongo/client/sdam/election_id_set_version_pair.h
@@ -0,0 +1,125 @@
+/**
+ *    Copyright (C) 2021-present MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the Server Side Public License, version 1,
+ *    as published by MongoDB, Inc.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    Server Side Public License for more details.
+ *
+ *    You should have received a copy of the Server Side Public License
+ *    along with this program. If not, see
+ *    <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the Server Side Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+#pragma once
+
+#include <boost/optional.hpp>
+
+#include "mongo/bson/oid.h"
+
+namespace mongo::sdam {
+
+// Comparable pair or ElectionId (term) and SetVersion.
+struct ElectionIdSetVersionPair {
+    const boost::optional<mongo::OID> electionId;
+    const boost::optional<int> setVersion;
+
+    bool allDefined() const {
+        return electionId && setVersion;
+    }
+
+    bool allUndefined() const {
+        return !electionId && !setVersion;
+    }
+};
+
+inline bool electionIdEqual(const ElectionIdSetVersionPair& p1,
+                            const ElectionIdSetVersionPair& p2) {
+    return p1.electionId && p2.electionId && (*p1.electionId).compare(*p2.electionId) == 0;
+}
+
+inline bool operator<(const ElectionIdSetVersionPair& p1, const ElectionIdSetVersionPair& p2) {
+    if (electionIdEqual(p1, p2)) {
+        if (p1.setVersion && p2.setVersion) {
+            return *p1.setVersion < *p2.setVersion;
+        }
+        return false;  // Cannot compare Set versions.
+    }
+
+    if (p1.electionId && p2.electionId) {
+        return (*p1.electionId).compare(*p2.electionId) < 0;
+    }
+
+    // We know that election Ids are not comparable.
+    return false;
+}
+
+inline bool operator>(const ElectionIdSetVersionPair& p1, const ElectionIdSetVersionPair& p2) {
+    return p2 < p1;
+}
+
+// Equality operator is not equivalent to "!< && !>" because of grey area of undefined values.
+inline bool operator==(const ElectionIdSetVersionPair& p1, const ElectionIdSetVersionPair& p2) {
+    if (!electionIdEqual(p1, p2)) {
+        return false;
+    }
+
+    if (!p1.setVersion && !p2.setVersion) {
+        return true;
+    }
+
+    return p1.setVersion && p2.setVersion && *p1.setVersion == *p2.setVersion;
+}
+
+inline bool setVersionWentBackwards(const ElectionIdSetVersionPair& current,
+                                    const ElectionIdSetVersionPair& incoming) {
+    return current.setVersion && incoming.setVersion && *current.setVersion > *incoming.setVersion;
+}
+
+/**
+ * @return true if 'incoming' is RS primary and fields have consistent values.
+ */
+inline bool isIncomingPrimaryConsistent(const ElectionIdSetVersionPair& current,
+                                        const ElectionIdSetVersionPair& incoming) {
+    // If coming from primary both election Id and Set version should be always set.
+    // This requirement is true for at least MDB >= 4.0.
+    if (!incoming.electionId || !incoming.setVersion) {
+        return false;
+    }
+
+    if (current.allUndefined()) {
+        return true;  // Further check is not necessary.
+    }
+
+    // Identical term means Set version should be equal or advance because no failover
+    // happened and Set version at the same primary cannot go backwards.
+    if (electionIdEqual(current, incoming)) {
+        return !current.setVersion || *current.setVersion <= *incoming.setVersion;
+    }
+
+    // If Set version goes backwards the term should advance, because it means
+    // failover happened. This is possible if the previous primary failed to replicate
+    // new Set version before failover. When it happens, we will rollback the Set version.
+    if (setVersionWentBackwards(current, incoming)) {
+        return !current.electionId || (*current.electionId).compare(*incoming.electionId) < 0;
+    }
+
+    return true;
+}
+
+}  // namespace mongo::sdam
diff --git a/src/mongo/client/sdam/election_id_set_version_pair_test.cpp b/src/mongo/client/sdam/election_id_set_version_pair_test.cpp
new file mode 100644
index 00000000000..b375a6760fc
--- /dev/null
+++ b/src/mongo/client/sdam/election_id_set_version_pair_test.cpp
@@ -0,0 +1,149 @@
+/**
+ *    Copyright (C) 2021-present MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the Server Side Public License, version 1,
+ *    as published by MongoDB, Inc.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    Server Side Public License for more details.
+ *
+ *    You should have received a copy of the Server Side Public License
+ *    along with this program. If not, see
+ *    <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the Server Side Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/client/sdam/election_id_set_version_pair.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo::sdam {
+namespace {
+
+class ElectionIdSetVersionPairTest : public unittest::Test {
+public:
+    static inline const OID kOidOne{"000000000000000000000001"};
+    static inline const OID kOidTwo{"000000000000000000000002"};
+
+    static inline const boost::optional<OID> kNullOid;
+    static inline const boost::optional<int> kNullSet;
+
+    enum class Compare {
+        kEquals,
+        kLess,
+        kGreater,
+        // When any compare operator returns false.
+        kNotComparable
+    };
+
+    enum class Consistency { kConsistent, kInconsistent };
+
+    struct TestCase {
+        // Curent topology max fields.
+        const boost::optional<OID> kTerm1;
+        const boost::optional<int> kSet1;
+        // Incoming primary fields.
+        const boost::optional<OID> kTerm2;
+        const boost::optional<int> kSet2;
+        const Compare compare;
+        const Consistency consistent;
+    };
+
+    std::string log(const TestCase& t, int testNum) {
+        str::stream s;
+        s << "[" << t.kTerm1 << ", " << t.kSet1 << "][" << t.kTerm2 << ", " << t.kSet2 << "]";
+        s << ", test=" << testNum;
+        return s;
+    }
+
+    void test(const TestCase& t, int testNum) {
+        ElectionIdSetVersionPair p1{t.kTerm1, t.kSet1};
+        ElectionIdSetVersionPair p2{t.kTerm2, t.kSet2};
+
+        switch (t.compare) {
+            case Compare::kEquals:
+                ASSERT_TRUE(p1 == p2) << log(t, testNum);
+                break;
+            case Compare::kLess:
+                ASSERT_TRUE(p1 < p2) << log(t, testNum);
+                break;
+            case Compare::kGreater:
+                ASSERT_TRUE(p1 > p2) << log(t, testNum);
+                break;
+            case Compare::kNotComparable:
+                ASSERT_FALSE(p1 > p2) << log(t, testNum);
+                ASSERT_FALSE(p1 < p2) << log(t, testNum);
+                ASSERT_FALSE(p1 == p2) << log(t, testNum);
+                break;
+        }
+
+        const bool isConsistent = isIncomingPrimaryConsistent(p1, p2);
+        ASSERT_EQ(t.consistent == Consistency::kConsistent, isConsistent) << log(t, testNum);
+    }
+};
+
+TEST_F(ElectionIdSetVersionPairTest, ExpectedOutcome) {
+    std::vector<TestCase> tests = {
+        // At startup, both current fields are not set.
+        {kNullOid, kNullSet, kOidOne, 1, Compare::kNotComparable, Consistency::kConsistent},
+
+        {kOidOne, 1, kOidOne, 1, Compare::kEquals, Consistency::kConsistent},
+
+        // One field is not set. This should never happen however added for better
+        // coverage for malformed protocol.
+        {kNullOid, 1, kOidOne, 1, Compare::kNotComparable, Consistency::kConsistent},
+        {kOidOne, kNullSet, kOidOne, 1, Compare::kNotComparable, Consistency::kConsistent},
+        {kOidOne, 1, kNullOid, 1, Compare::kNotComparable, Consistency::kInconsistent},
+        {kOidOne, 1, kOidOne, kNullSet, Compare::kNotComparable, Consistency::kInconsistent},
+
+        // Primary advanced one way or another. "Less" means current < incoming.
+        {kOidOne, 1, kOidTwo, 1, Compare::kLess, Consistency::kConsistent},
+        {kOidOne, 1, kOidOne, 2, Compare::kLess, Consistency::kConsistent},
+
+        // Primary advanced but current state is incomplete.
+        {kNullOid, 1, kOidTwo, 1, Compare::kNotComparable, Consistency::kConsistent},
+        {kNullOid, 1, kOidOne, 2, Compare::kNotComparable, Consistency::kConsistent},
+        {kOidOne, kNullSet, kOidTwo, 1, Compare::kLess, Consistency::kConsistent},
+        {kOidOne, kNullSet, kOidOne, 2, Compare::kNotComparable, Consistency::kConsistent},
+
+        // Primary went backwards one way or another.
+        // Inconsistent because Set version went backwards without Term being changed (same
+        // primary).
+        {kOidTwo, 2, kOidTwo, 1, Compare::kGreater, Consistency::kInconsistent},
+        {kOidTwo, 2, kOidOne, 2, Compare::kGreater, Consistency::kConsistent},
+
+        // Primary went backwards with current state incomplete.
+        {kNullOid, 2, kOidTwo, 1, Compare::kNotComparable, Consistency::kConsistent},
+        {kOidTwo, kNullSet, kOidOne, 1, Compare::kGreater, Consistency::kConsistent},
+
+        // Stale primary case when Term went backwards but Set version advanced.
+        // This case is 'consistent' because it's normal for stale primary. The
+        // important part is that 'current' > 'incoming', which makes the node 'Unknown'.
+        {kOidTwo, 1, kOidOne, 2, Compare::kGreater, Consistency::kConsistent},
+
+        // Previous primary was unable to replicate the Set version before failover,
+        // new primary forces it to be rolled back.
+        {kOidOne, 2, kOidTwo, 1, Compare::kLess, Consistency::kConsistent},
+    };
+
+    int testNum = 0;
+    for (const auto& t : tests) {
+        test(t, testNum++);
+    }
+}
+
+}  // namespace
+}  // namespace mongo::sdam
diff --git a/src/mongo/client/sdam/server_description.cpp b/src/mongo/client/sdam/server_description.cpp
index 4f16d1c4d8e..143902f021c 100644
--- a/src/mongo/client/sdam/server_description.cpp
+++ b/src/mongo/client/sdam/server_description.cpp
@@ -285,6 +285,10 @@ const boost::optional<mongo::OID>& ServerDescription::getElectionId() const {
     return _electionId;
 }
 
+const ElectionIdSetVersionPair ServerDescription::getElectionIdSetVersionPair() const {
+    return ElectionIdSetVersionPair{getElectionId(), getSetVersion()};
+}
+
 const boost::optional<HostAndPort>& ServerDescription::getPrimary() const {
     return _primary;
 }
diff --git a/src/mongo/client/sdam/server_description.h b/src/mongo/client/sdam/server_description.h
index a8d5f256542..666acd1bc37 100644
--- a/src/mongo/client/sdam/server_description.h
+++ b/src/mongo/client/sdam/server_description.h
@@ -36,6 +36,7 @@
 #include <utility>
 
 #include "mongo/bson/oid.h"
+#include "mongo/client/sdam/election_id_set_version_pair.h"
 #include "mongo/client/sdam/sdam_datatypes.h"
 #include "mongo/db/repl/optime.h"
 #include "mongo/platform/basic.h"
@@ -102,8 +103,10 @@ public:
     const std::set<HostAndPort>& getHosts() const;
     const std::set<HostAndPort>& getPassives() const;
     const std::set<HostAndPort>& getArbiters() const;
+    // TODO(SERVER-59409): remove next 2 methods and keep only pair getter.
     const boost::optional<int>& getSetVersion() const;
     const boost::optional<OID>& getElectionId() const;
+    const ElectionIdSetVersionPair getElectionIdSetVersionPair() const;
     const boost::optional<TopologyVersion>& getTopologyVersion() const;
     const boost::optional<TopologyDescriptionPtr> getTopologyDescription();
 
diff --git a/src/mongo/client/sdam/topology_description.cpp b/src/mongo/client/sdam/topology_description.cpp
index a243eb8075d..63ff6187edf 100644
--- a/src/mongo/client/sdam/topology_description.cpp
+++ b/src/mongo/client/sdam/topology_description.cpp
@@ -93,6 +93,10 @@ const boost::optional<OID>& TopologyDescription::getMaxElectionId() const {
     return _maxElectionId;
 }
 
+const ElectionIdSetVersionPair TopologyDescription::getMaxElectionIdSetVersionPair() const {
+    return ElectionIdSetVersionPair{getMaxElectionId(), getMaxSetVersion()};
+}
+
 const std::vector<ServerDescriptionPtr>& TopologyDescription::getServers() const {
     return _servers;
 }
diff --git a/src/mongo/client/sdam/topology_description.h b/src/mongo/client/sdam/topology_description.h
index dca48d9d852..b7de69401a0 100644
--- a/src/mongo/client/sdam/topology_description.h
+++ b/src/mongo/client/sdam/topology_description.h
@@ -36,6 +36,7 @@
 
 #include "mongo/bson/oid.h"
 #include "mongo/client/read_preference.h"
+#include "mongo/client/sdam/election_id_set_version_pair.h"
 #include "mongo/client/sdam/sdam_configuration.h"
 #include "mongo/client/sdam/sdam_datatypes.h"
 #include "mongo/client/sdam/server_description.h"
@@ -67,8 +68,10 @@ public:
     TopologyType getType() const;
     const boost::optional<std::string>& getSetName() const;
 
+    // TODO(SERVER-59409): remove next 2 methods and keep only pair getter.
     const boost::optional<int>& getMaxSetVersion() const;
     const boost::optional<OID>& getMaxElectionId() const;
+    const ElectionIdSetVersionPair getMaxElectionIdSetVersionPair() const;
 
     const std::vector<ServerDescriptionPtr>& getServers() const;