SERVER-29944 Implement a basic idempotency checker for testing oplog

idempotency

Signed-off-by: Max Hirschhorn <max.hirschhorn@mongodb.com>

Also includes changes to tie the PseudoRandom instances in
ScalarGenerator and UpdateSequenceGenerator together via a SecureRandom
in runIdempotencyTestCase().

8 files changed, 371 insertions, 99 deletions

diff --git a/src/mongo/db/repl/SConscript b/src/mongo/db/repl/SConscript
index d9300d28962..3cc245b8c56 100644
--- a/src/mongo/db/repl/SConscript
+++ b/src/mongo/db/repl/SConscript
@@ -634,6 +634,17 @@ env.Library(
 )
 
 env.CppUnitTest(
+    target='idempotency_test',
+    source=[
+        'idempotency_test.cpp',
+    ],
+    LIBDEPS=[
+        'idempotency_test_fixture',
+        'idempotency_test_util',
+    ],
+)
+
+env.CppUnitTest(
     target='idempotency_document_structure_test',
     source=[
         'idempotency_document_structure_test.cpp',
diff --git a/src/mongo/db/repl/idempotency_sequence.h b/src/mongo/db/repl/idempotency_sequence.h
deleted file mode 100644
index 012be9754b8..00000000000
--- a/src/mongo/db/repl/idempotency_sequence.h
+++ /dev/null
@@ -1,45 +0,0 @@
-/**
- * Copyright (C) 2017 MongoDB Inc.
- *
- * This program is free software: you can redistribute it and/or  modify
- * it under the terms of the GNU Affero General Public License, version 3,
- * as published by the Free Software Foundation.
- *
- * 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
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- *
- * 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 GNU Affero General 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 <cstddef>
-#include <vector>
-
-#include "mongo/bson/bsonobj.h"
-
-namespace mongo {
-
-class SequenceGenerator {
-public:
-    SequenceGenerator() = default;
-
-    virtual BSONObj generate() const = 0;
-};
-
-}  // namespace mongo
diff --git a/src/mongo/db/repl/idempotency_test.cpp b/src/mongo/db/repl/idempotency_test.cpp
new file mode 100644
index 00000000000..84a03172947
--- /dev/null
+++ b/src/mongo/db/repl/idempotency_test.cpp
@@ -0,0 +1,209 @@
+/**
+ * Copyright (C) 2017 MongoDB Inc.
+ *
+ * This program is free software: you can redistribute it and/or  modify
+ * it under the terms of the GNU Affero General Public License, version 3,
+ * as published by the Free Software Foundation.
+ *
+ * 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
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * 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 GNU Affero General 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/platform/basic.h"
+
+#include "mongo/db/catalog/index_catalog.h"
+#include "mongo/db/db_raii.h"
+#include "mongo/db/dbhelpers.h"
+#include "mongo/db/query/index_bounds.h"
+#include "mongo/db/query/internal_plans.h"
+#include "mongo/db/query/plan_executor.h"
+#include "mongo/db/repl/idempotency_document_structure.h"
+#include "mongo/db/repl/idempotency_test_fixture.h"
+#include "mongo/db/repl/idempotency_update_sequence.h"
+#include "mongo/db/repl/replication_coordinator.h"
+#include "mongo/db/server_options.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace repl {
+namespace {
+
+class RandomizedIdempotencyTest : public IdempotencyTest {
+protected:
+    const int kDocId = 1;
+    const BSONObj kDocIdQuery = BSON("_id" << kDocId);
+
+    std::vector<OplogEntry> createUpdateSequence(const UpdateSequenceGenerator& generator,
+                                                 const size_t length);
+
+    BSONObj canonicalizeDocumentForDataHash(const BSONObj& obj) override;
+
+    BSONObj getDoc();
+
+    std::string getStateString(const CollectionState& state1,
+                               const CollectionState& state2,
+                               const std::vector<OplogEntry>& ops) override;
+
+    Status resetState() override;
+
+    void runIdempotencyTestCase();
+
+    std::vector<OplogEntry> initOps;
+    int64_t seed;
+};
+
+BSONObj RandomizedIdempotencyTest::canonicalizeDocumentForDataHash(const BSONObj& obj) {
+    BSONObjBuilder objBuilder;
+    BSONObjIteratorSorted iter(obj);
+    while (iter.more()) {
+        auto elem = iter.next();
+        if (elem.isABSONObj()) {
+            if (elem.type() == mongo::Array) {
+                objBuilder.append(elem.fieldName(), obj);
+            } else {
+                // If it is a sub object, we'll have to sort it as well before we append it.
+                auto sortedObj = canonicalizeDocumentForDataHash(elem.Obj());
+                objBuilder.append(elem.fieldName(), sortedObj);
+            }
+        } else {
+            // If it is not a sub object, just append it and move on.
+            objBuilder.append(elem);
+        }
+    }
+
+    return objBuilder.obj();
+}
+
+BSONObj RandomizedIdempotencyTest::getDoc() {
+    AutoGetCollectionForReadCommand autoColl(_opCtx.get(), nss);
+    BSONObj doc;
+    Helpers::findById(_opCtx.get(), autoColl.getDb(), nss.ns(), kDocIdQuery, doc);
+    return doc.getOwned();
+}
+
+std::vector<OplogEntry> RandomizedIdempotencyTest::createUpdateSequence(
+    const UpdateSequenceGenerator& generator, const size_t length) {
+    // for each document enumerated & inserted generate a sequence of updates to apply to it.
+    std::vector<OplogEntry> updateSequence;
+    updateSequence.reserve(length);
+    for (size_t i = 0; i < length; i++) {
+        updateSequence.push_back(update(kDocId, generator.generateUpdate()));
+    }
+
+    return updateSequence;
+}
+
+std::string RandomizedIdempotencyTest::getStateString(const CollectionState& state1,
+                                                      const CollectionState& state2,
+                                                      const std::vector<OplogEntry>& ops) {
+    unittest::log() << IdempotencyTest::getStateString(state1, state2, ops);
+    StringBuilder sb;
+    sb << "Ran update ops: ";
+    sb << "[ ";
+    bool firstIter = true;
+    for (auto op : ops) {
+        if (!firstIter) {
+            sb << ", ";
+        } else {
+            firstIter = false;
+        }
+        sb << op.toString();
+    }
+    sb << " ]\n";
+
+    ASSERT_OK(resetState());
+
+    sb << "Start: " << getDoc() << "\n";
+    for (auto op : ops) {
+        ASSERT_OK(runOp(op));
+        sb << "Apply: " << op.getObject() << "\n  ==> " << getDoc() << "\n";
+    }
+
+    sb << "Found from the seed: " << this->seed;
+
+    return sb.str();
+}
+
+Status RandomizedIdempotencyTest::resetState() {
+    Status dropStatus = runOp(dropCollection());
+    if (!dropStatus.isOK()) {
+        return dropStatus;
+    }
+
+    return runOps(initOps);
+}
+
+void RandomizedIdempotencyTest::runIdempotencyTestCase() {
+    ASSERT_OK(
+        ReplicationCoordinator::get(_opCtx.get())->setFollowerMode(MemberState::RS_RECOVERING));
+
+    std::set<StringData> fields{"a", "b"};
+    size_t depth = 1;
+    size_t length = 1;
+
+    // Eliminate the chance of a sub array, because they cause theoretically valid sequences that
+    // cause idempotency issues.
+    const double kScalarProbability = 0.375;
+    const double kDocProbability = 0.375;
+    const double kArrProbability = 0.0;
+
+    this->seed = SecureRandom::create()->nextInt64();
+    PseudoRandom seedGenerator(this->seed);
+    RandomizedScalarGenerator scalarGenerator{PseudoRandom(seedGenerator.nextInt64())};
+    UpdateSequenceGenerator updateGenerator(
+        {fields, depth, length, kScalarProbability, kDocProbability, kArrProbability},
+        PseudoRandom{seedGenerator.nextInt64()},
+        &scalarGenerator);
+
+    const bool kSkipDocs = kDocProbability == 0.0;
+    const bool kSkipArrs = kArrProbability == 0.0;
+    DocumentStructureEnumerator enumerator({fields, depth, length, kSkipDocs, kSkipArrs},
+                                           &scalarGenerator);
+
+    const size_t kUpdateSequenceLength = 5;
+    // For the sake of keeping the speed of iteration sane and feasible.
+    const size_t kNumUpdateSequencesPerDoc = 2;
+
+    for (auto doc : enumerator) {
+        BSONObj docWithId = (BSONObjBuilder(doc) << "_id" << kDocId).obj();
+        this->initOps = std::vector<OplogEntry>{createCollection(), insert(docWithId)};
+        for (size_t i = 0; i < kNumUpdateSequencesPerDoc; i++) {
+            std::vector<OplogEntry> updateSequence =
+                createUpdateSequence(updateGenerator, kUpdateSequenceLength);
+            testOpsAreIdempotent(updateSequence, SequenceType::kAnyPrefixOrSuffix);
+        }
+    }
+}
+
+TEST_F(RandomizedIdempotencyTest, CheckUpdateSequencesAreIdempotentWhenFCV34) {
+    serverGlobalParams.featureCompatibility.version.store(
+        ServerGlobalParams::FeatureCompatibility::Version::k34);
+    runIdempotencyTestCase();
+}
+
+TEST_F(RandomizedIdempotencyTest, CheckUpdateSequencesAreIdempotentWhenFCV36) {
+    serverGlobalParams.featureCompatibility.version.store(
+        ServerGlobalParams::FeatureCompatibility::Version::k36);
+    runIdempotencyTestCase();
+}
+
+}  // namespace
+}  // namespace repl
+}  // namespace mongo
diff --git a/src/mongo/db/repl/idempotency_test_fixture.cpp b/src/mongo/db/repl/idempotency_test_fixture.cpp
index 6c0c38a9147..c98c9651976 100644
--- a/src/mongo/db/repl/idempotency_test_fixture.cpp
+++ b/src/mongo/db/repl/idempotency_test_fixture.cpp
@@ -149,10 +149,19 @@ bool operator==(const CollectionState& lhs, const CollectionState& rhs) {
     return collectionOptionsEqual && indexSpecsEqual && dataHashEqual && existsEqual;
 }
 
+bool operator!=(const CollectionState& lhs, const CollectionState& rhs) {
+    return !(lhs == rhs);
+}
+
 std::ostream& operator<<(std::ostream& stream, const CollectionState& state) {
     return stream << state.toString();
 }
 
+StringBuilderImpl<SharedBufferAllocator>& operator<<(StringBuilderImpl<SharedBufferAllocator>& sb,
+                                                     const CollectionState& state) {
+    return sb << state.toString();
+}
+
 const auto kCollectionDoesNotExist = CollectionState();
 
 /**
@@ -226,7 +235,7 @@ Status IdempotencyTest::runOp(const OplogEntry& op) {
     return runOps({op});
 }
 
-Status IdempotencyTest::runOps(std::initializer_list<OplogEntry> ops) {
+Status IdempotencyTest::runOps(std::vector<OplogEntry> ops) {
     SyncTail syncTail(nullptr, SyncTail::MultiSyncApplyFunc(), nullptr);
     MultiApplier::OperationPtrs opsPtrs;
     for (auto& op : ops) {
@@ -236,17 +245,55 @@ Status IdempotencyTest::runOps(std::initializer_list<OplogEntry> ops) {
     return multiInitialSyncApply_noAbort(_opCtx.get(), &opsPtrs, &syncTail, &fetchCount);
 }
 
-void IdempotencyTest::testOpsAreIdempotent(std::initializer_list<OplogEntry> ops) {
-    ASSERT_OK(runOps(ops));
-    auto state = validate();
+Status IdempotencyTest::resetState() {
+    return Status::OK();
+}
+
+void IdempotencyTest::testOpsAreIdempotent(std::vector<OplogEntry> ops, SequenceType sequenceType) {
+    ASSERT_OK(resetState());
     ASSERT_OK(runOps(ops));
-    ASSERT_EQUALS(state, validate());
+    auto state1 = validate();
+    auto iterations = sequenceType == SequenceType::kEntireSequence ? 1 : ops.size();
+
+    for (std::size_t i = 0; i < iterations; i++) {
+        ASSERT_OK(resetState());
+        std::vector<OplogEntry> fullSequence;
+
+        if (sequenceType == SequenceType::kEntireSequence) {
+            ASSERT_OK(runOps(ops));
+            fullSequence.insert(fullSequence.end(), ops.begin(), ops.end());
+        } else if (sequenceType == SequenceType::kAnyPrefix ||
+                   sequenceType == SequenceType::kAnyPrefixOrSuffix) {
+            std::vector<OplogEntry> prefix(ops.begin(), ops.begin() + i + 1);
+            ASSERT_OK(runOps(prefix));
+            fullSequence.insert(fullSequence.end(), prefix.begin(), prefix.end());
+        }
+
+        ASSERT_OK(runOps(ops));
+        fullSequence.insert(fullSequence.end(), ops.begin(), ops.end());
+
+        if (sequenceType == SequenceType::kAnySuffix ||
+            sequenceType == SequenceType::kAnyPrefixOrSuffix) {
+            std::vector<OplogEntry> suffix(ops.begin() + i, ops.end());
+            ASSERT_OK(runOps(suffix));
+            fullSequence.insert(fullSequence.end(), suffix.begin(), suffix.end());
+        }
+
+        auto state2 = validate();
+        if (state1 != state2) {
+            FAIL(getStateString(state1, state2, fullSequence));
+        }
+    }
 }
 
 OplogEntry IdempotencyTest::createCollection(CollectionUUID uuid) {
     return makeCreateCollectionOplogEntry(nextOpTime(), nss, BSON("uuid" << uuid));
 }
 
+OplogEntry IdempotencyTest::dropCollection() {
+    return makeCommandOplogEntry(nextOpTime(), nss, BSON("drop" << nss.coll()));
+}
+
 OplogEntry IdempotencyTest::insert(const BSONObj& obj) {
     return makeInsertDocumentOplogEntry(nextOpTime(), nss, obj);
 }
@@ -271,24 +318,7 @@ OplogEntry IdempotencyTest::dropIndex(const std::string& indexName) {
     return makeCommandOplogEntry(nextOpTime(), nss, cmd);
 }
 
-CollectionState IdempotencyTest::validate() {
-    AutoGetCollectionForReadCommand autoColl(_opCtx.get(), nss);
-    auto collection = autoColl.getCollection();
-
-    if (!collection) {
-        // Return a mostly default initialized CollectionState struct with exists set to false to
-        // indicate an unfound Collection (or a view).
-        return kCollectionDoesNotExist;
-    }
-    ValidateResults validateResults;
-    BSONObjBuilder bob;
-
-    Lock::DBLock lk(_opCtx.get(), nss.db(), MODE_IX);
-    auto lock = stdx::make_unique<Lock::CollectionLock>(_opCtx->lockState(), nss.ns(), MODE_X);
-    ASSERT_OK(collection->validate(
-        _opCtx.get(), kValidateFull, false, std::move(lock), &validateResults, &bob));
-    ASSERT_TRUE(validateResults.valid);
-
+std::string IdempotencyTest::computeDataHash(Collection* collection) {
     IndexDescriptor* desc = collection->getIndexCatalog()->findIdIndex(_opCtx.get());
     ASSERT_TRUE(desc);
     auto exec = InternalPlanner::indexScan(_opCtx.get(),
@@ -305,14 +335,36 @@ CollectionState IdempotencyTest::validate() {
     md5_init(&st);
 
     PlanExecutor::ExecState state;
-    BSONObj c;
-    while (PlanExecutor::ADVANCED == (state = exec->getNext(&c, NULL))) {
-        md5_append(&st, (const md5_byte_t*)c.objdata(), c.objsize());
+    BSONObj obj;
+    while (PlanExecutor::ADVANCED == (state = exec->getNext(&obj, NULL))) {
+        obj = this->canonicalizeDocumentForDataHash(obj);
+        md5_append(&st, (const md5_byte_t*)obj.objdata(), obj.objsize());
     }
     ASSERT_EQUALS(PlanExecutor::IS_EOF, state);
     md5digest d;
     md5_finish(&st, d);
-    std::string dataHash = digestToString(d);
+    return digestToString(d);
+}
+
+CollectionState IdempotencyTest::validate() {
+    AutoGetCollectionForReadCommand autoColl(_opCtx.get(), nss);
+    auto collection = autoColl.getCollection();
+
+    if (!collection) {
+        // Return a mostly default initialized CollectionState struct with exists set to false to
+        // indicate an unfound Collection (or a view).
+        return kCollectionDoesNotExist;
+    }
+    ValidateResults validateResults;
+    BSONObjBuilder bob;
+
+    Lock::DBLock lk(_opCtx.get(), nss.db(), MODE_IX);
+    auto lock = stdx::make_unique<Lock::CollectionLock>(_opCtx->lockState(), nss.ns(), MODE_X);
+    ASSERT_OK(collection->validate(
+        _opCtx.get(), kValidateFull, false, std::move(lock), &validateResults, &bob));
+    ASSERT_TRUE(validateResults.valid);
+
+    std::string dataHash = computeDataHash(collection);
 
     auto collectionCatalog = collection->getCatalogEntry();
     auto collectionOptions = collectionCatalog->getCollectionOptions(_opCtx.get());
@@ -329,6 +381,15 @@ CollectionState IdempotencyTest::validate() {
     return collectionState;
 }
 
+std::string IdempotencyTest::getStateString(const CollectionState& state1,
+                                            const CollectionState& state2,
+                                            const std::vector<OplogEntry>& ops) {
+    StringBuilder sb;
+    sb << "The state: " << state1 << " does not match with the state: " << state2
+       << " found after applying the operations a second time, therefore breaking idempotency.";
+    return sb.str();
+}
+
 template OplogEntry IdempotencyTest::update<int>(int _id, const BSONObj& obj);
 template OplogEntry IdempotencyTest::update<const char*>(char const* _id, const BSONObj& obj);
 
diff --git a/src/mongo/db/repl/idempotency_test_fixture.h b/src/mongo/db/repl/idempotency_test_fixture.h
index c3c3ff1275f..95059ad7315 100644
--- a/src/mongo/db/repl/idempotency_test_fixture.h
+++ b/src/mongo/db/repl/idempotency_test_fixture.h
@@ -46,6 +46,9 @@
 #include "mongo/util/uuid.h"
 
 namespace mongo {
+
+class Collection;
+
 namespace repl {
 
 struct CollectionState {
@@ -78,11 +81,16 @@ struct CollectionState {
 };
 
 bool operator==(const CollectionState& lhs, const CollectionState& rhs);
+bool operator!=(const CollectionState& lhs, const CollectionState& rhs);
 std::ostream& operator<<(std::ostream& stream, const CollectionState& state);
+StringBuilderImpl<SharedBufferAllocator>& operator<<(StringBuilderImpl<SharedBufferAllocator>& sb,
+                                                     const CollectionState& state);
 
 class IdempotencyTest : public SyncTailTest {
 protected:
+    enum class SequenceType : int { kEntireSequence, kAnyPrefix, kAnySuffix, kAnyPrefixOrSuffix };
     OplogEntry createCollection(CollectionUUID uuid = UUID::gen());
+    OplogEntry dropCollection();
     OplogEntry insert(const BSONObj& obj);
     template <class IdType>
     OplogEntry update(IdType _id, const BSONObj& obj);
@@ -93,14 +101,31 @@ protected:
         return OpTime(Timestamp(Seconds(lastSecond++), 0), 1LL);
     }
     Status runOp(const OplogEntry& entry);
-    Status runOps(std::initializer_list<OplogEntry> ops);
+    Status runOps(std::vector<OplogEntry> ops);
+    virtual Status resetState();
+
     /**
      * This method returns true if running the list of operations a single time is equivalent to
      * running them two times. It returns false otherwise.
      */
-    void testOpsAreIdempotent(std::initializer_list<OplogEntry> ops);
+    void testOpsAreIdempotent(std::vector<OplogEntry> ops,
+                              SequenceType sequenceType = SequenceType::kEntireSequence);
 
     /**
+     * This function exists to work around the issue described in SERVER-30470 by providing a
+     * mechanism for the RandomizedIdempotencyTest class to avoid triggering failures caused by
+     * differences in the ordering of fields within a document. By default it returns the document
+     * unchanged.
+     */
+    virtual BSONObj canonicalizeDocumentForDataHash(const BSONObj& obj) {
+        return obj;
+    };
+
+    std::string computeDataHash(Collection* collection);
+    virtual std::string getStateString(const CollectionState& state1,
+                                       const CollectionState& state2,
+                                       const std::vector<OplogEntry>& ops);
+    /**
      * Validate data and indexes. Return the MD5 hash of the documents ordered by _id.
      */
     CollectionState validate();
@@ -116,7 +141,6 @@ OplogEntry makeCreateCollectionOplogEntry(OpTime opTime,
 OplogEntry makeInsertDocumentOplogEntry(OpTime opTime,
                                         const NamespaceString& nss,
                                         const BSONObj& documentToInsert);
-
 OplogEntry makeUpdateDocumentOplogEntry(OpTime opTime,
                                         const NamespaceString& nss,
                                         const BSONObj& documentToUpdate,
diff --git a/src/mongo/db/repl/idempotency_update_sequence.cpp b/src/mongo/db/repl/idempotency_update_sequence.cpp
index b902316ec76..24335b5b5f9 100644
--- a/src/mongo/db/repl/idempotency_update_sequence.cpp
+++ b/src/mongo/db/repl/idempotency_update_sequence.cpp
@@ -265,19 +265,14 @@ DocumentStructureEnumerator UpdateSequenceGenerator::_getValidEnumeratorForPath(
     return enumerator;
 }
 
-BSONObj UpdateSequenceGenerator::generate() const {
-    return generateUpdate();
-}
-
 std::vector<std::string> UpdateSequenceGenerator::getPaths() const {
     return this->_paths;
 }
 
 UpdateSequenceGenerator::UpdateSequenceGenerator(UpdateSequenceGeneratorConfig config,
+                                                 PseudoRandom random,
                                                  ScalarGenerator* scalarGenerator)
-    : _config(std::move(config)),
-      _random(std::unique_ptr<SecureRandom>(SecureRandom::create())->nextInt64()),
-      _scalarGenerator(scalarGenerator) {
+    : _config(std::move(config)), _random(random), _scalarGenerator(scalarGenerator) {
     auto path = "";
     _generatePaths(config, path);
     // Creates the same shuffle each time, but we don't care. We want to mess up the DFS ordering.
diff --git a/src/mongo/db/repl/idempotency_update_sequence.h b/src/mongo/db/repl/idempotency_update_sequence.h
index c4b1d9cefdd..60f56d2879c 100644
--- a/src/mongo/db/repl/idempotency_update_sequence.h
+++ b/src/mongo/db/repl/idempotency_update_sequence.h
@@ -35,7 +35,6 @@
 
 #include "mongo/base/string_data.h"
 #include "mongo/db/repl/idempotency_scalar_generator.h"
-#include "mongo/db/repl/idempotency_sequence.h"
 #include "mongo/platform/random.h"
 
 namespace mongo {
@@ -61,15 +60,15 @@ struct UpdateSequenceGeneratorConfig {
     const double arrProbability = 0.250;
 };
 
-class UpdateSequenceGenerator : public SequenceGenerator {
+class UpdateSequenceGenerator {
 
 public:
-    UpdateSequenceGenerator(UpdateSequenceGeneratorConfig config, ScalarGenerator* scalarGenerator);
+    UpdateSequenceGenerator(UpdateSequenceGeneratorConfig config,
+                            PseudoRandom random,
+                            ScalarGenerator* scalarGenerator);
 
     BSONObj generateUpdate() const;
 
-    BSONObj generate() const override;
-
     std::vector<std::string> getPaths() const;
 
     friend std::vector<std::string> eliminatePrefixPaths_forTest(
diff --git a/src/mongo/db/repl/idempotency_update_sequence_test.cpp b/src/mongo/db/repl/idempotency_update_sequence_test.cpp
index 1905015c896..b9a251dabbb 100644
--- a/src/mongo/db/repl/idempotency_update_sequence_test.cpp
+++ b/src/mongo/db/repl/idempotency_update_sequence_test.cpp
@@ -55,8 +55,10 @@ TEST(UpdateGenTest, FindsAllPaths) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 1;
     size_t length = 1;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generator({fields, depth, length}, &trivialScalarGenerator);
+    UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator);
 
     ASSERT_EQ(generator.getPaths().size(), 5U);
 
@@ -85,8 +87,10 @@ TEST(UpdateGenTest, NoDuplicatePaths) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 2;
     size_t length = 2;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generator({fields, depth, length}, &trivialScalarGenerator);
+    UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator);
 
     auto paths = generator.getPaths();
     for (size_t i = 0; i < paths.size(); i++) {
@@ -105,8 +109,10 @@ TEST(UpdateGenTest, UpdatesHaveValidPaths) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 1;
     size_t length = 1;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generator({fields, depth, length}, &trivialScalarGenerator);
+    UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator);
     auto update = generator.generateUpdate();
 
     BSONObj updateArg;
@@ -143,8 +149,10 @@ TEST(UpdateGenTest, UpdatesAreNotAmbiguous) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 1;
     size_t length = 1;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generator({fields, depth, length}, &trivialScalarGenerator);
+    UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator);
     auto update = generator.generateUpdate();
 
     BSONObj updateArg;
@@ -190,9 +198,11 @@ TEST(UpdateGenTest, UpdatesPreserveDepthConstraint) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 2;
     size_t length = 1;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generator({fields, depth, length, 0.333, 0.333, 0.334},
-                                      &trivialScalarGenerator);
+    UpdateSequenceGenerator generator(
+        {fields, depth, length, 0.333, 0.333, 0.334}, random, &trivialScalarGenerator);
 
     BSONElement setElem;
     BSONObj update;
@@ -227,9 +237,11 @@ TEST(UpdateGenTest, OnlyGenerateUnset) {
     size_t depth = 1;
     size_t length = 1;
 
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generatorNoSet({fields, depth, length, 0.0, 0.0, 0.0},
-                                           &trivialScalarGenerator);
+    UpdateSequenceGenerator generatorNoSet(
+        {fields, depth, length, 0.0, 0.0, 0.0}, random, &trivialScalarGenerator);
+
     for (size_t i = 0; i < 100; i++) {
         auto update = generatorNoSet.generateUpdate();
         if (!update["$unset"]) {
@@ -246,9 +258,12 @@ TEST(UpdateGenTest, OnlySetUpdatesWithScalarValue) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 1;
     size_t length = 1;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generatorNoUnsetAndOnlyScalar({fields, depth, length, 1.0, 0.0, 0.0},
-                                                          &trivialScalarGenerator);
+    UpdateSequenceGenerator generatorNoUnsetAndOnlyScalar(
+        {fields, depth, length, 1.0, 0.0, 0.0}, random, &trivialScalarGenerator);
+
     for (size_t i = 0; i < 100; i++) {
         auto update = generatorNoUnsetAndOnlyScalar.generateUpdate();
         if (!update["$set"]) {
@@ -271,9 +286,12 @@ TEST(UpdateGenTest, OnlySetUpdatesWithScalarsAtMaxDepth) {
     std::set<StringData> fields{"a", "b"};
     size_t depth = 2;
     size_t length = 1;
+
+    PseudoRandom random(SecureRandom::create()->nextInt64());
     TrivialScalarGenerator trivialScalarGenerator;
-    UpdateSequenceGenerator generatorNeverScalar({fields, depth, length, 0.0, 0.5, 0.5},
-                                                 &trivialScalarGenerator);
+    UpdateSequenceGenerator generatorNeverScalar(
+        {fields, depth, length, 0.0, 0.5, 0.5}, random, &trivialScalarGenerator);
+
     for (size_t i = 0; i < 100; i++) {
         auto update = generatorNeverScalar.generateUpdate();
         for (auto elem : update["$set"].Obj()) {