SERVER-34293 Add test for atomicity and isolation of transactions.

Also adds a helper function for running a function inside of a
transaction and automatically retrying until it either succeeds or the
server returns a non-WriteConflict error response.

6 files changed, 361 insertions, 92 deletions

diff --git a/jstests/concurrency/fsm_libs/assert.js b/jstests/concurrency/fsm_libs/assert.js
index 1c3dfa55408..437742ac396 100644
--- a/jstests/concurrency/fsm_libs/assert.js
+++ b/jstests/concurrency/fsm_libs/assert.js
@@ -44,13 +44,20 @@ if (typeof globalAssertLevel === 'undefined') {
 var assertWithLevel = function(level) {
     assert(AssertLevel.isAssertLevel(level), 'expected AssertLevel as first argument');
 
-    function quietlyDoAssert(msg) {
+    function quietlyDoAssert(msg, obj) {
         // eval if msg is a function
         if (typeof msg === 'function') {
             msg = msg();
         }
 
-        throw new Error(msg);
+        var ex;
+        if (obj) {
+            ex = _getErrorWithCode(obj, msg);
+        } else {
+            ex = new Error(msg);
+        }
+
+        throw ex;
     }
 
     function wrapAssertFn(fn, args) {
diff --git a/jstests/concurrency/fsm_workload_helpers/auto_retry_transaction.js b/jstests/concurrency/fsm_workload_helpers/auto_retry_transaction.js
new file mode 100644
index 00000000000..f98e7d796e9
--- /dev/null
+++ b/jstests/concurrency/fsm_workload_helpers/auto_retry_transaction.js
@@ -0,0 +1,68 @@
+'use strict';
+
+var {withTxnAndAutoRetryOnWriteConflict} = (function() {
+
+    /**
+     * Calls 'func' with the print() function overridden to be a no-op.
+     *
+     * This function is useful for silencing JavaScript backtraces that would otherwise be logged
+     * from doassert() being called, even when the JavaScript exception is ultimately caught and
+     * handled.
+     */
+    function quietly(func) {
+        const printOriginal = print;
+        try {
+            print = Function.prototype;
+            func();
+        } finally {
+            print = printOriginal;
+        }
+    }
+
+    /**
+     * Runs 'func' inside of a transaction started with 'txnOptions', and automatically retries
+     * until it either succeeds or the server returns a non-WriteConflict error response.
+     *
+     * The caller should take care to ensure 'func' doesn't modify any captured variables in a
+     * speculative fashion where calling it multiple times would lead to unintended behavior. The
+     * transaction started by the withTxnAndAutoRetryOnWriteConflict() function is only known to
+     * have committed after the withTxnAndAutoRetryOnWriteConflict() function returns.
+     */
+    function withTxnAndAutoRetryOnWriteConflict(
+        session, func, {txnOptions: txnOptions = {readConcern: {level: 'snapshot'}}} = {}) {
+        let hasWriteConflict;
+
+        do {
+            session.startTransaction(txnOptions);
+            hasWriteConflict = false;
+
+            try {
+                func();
+
+                // commitTransaction() calls assert.commandWorked(), which may fail with a
+                // WriteConflict error response. We therefore suppress its doassert() output.
+                quietly(() => session.commitTransaction());
+            } catch (e) {
+                try {
+                    // abortTransaction() calls assert.commandWorked(), which may fail with a
+                    // WriteConflict error response. We therefore suppress its doassert() output.
+                    quietly(() => session.abortTransaction());
+                } catch (e) {
+                    // We ignore the error from abortTransaction() because the transaction may have
+                    // implicitly been aborted by the server already and will therefore return a
+                    // NoSuchTransaction error response. We need to call abortTransaction() in order
+                    // to update the mongo shell's state such that it agrees no transaction is
+                    // currently in progress on this session.
+                }
+
+                if (e.code !== ErrorCodes.WriteConflict) {
+                    throw e;
+                }
+
+                hasWriteConflict = true;
+            }
+        } while (hasWriteConflict);
+    }
+
+    return {withTxnAndAutoRetryOnWriteConflict};
+})();
diff --git a/jstests/concurrency/fsm_workloads/multi_statement_transaction_atomicity_isolation.js b/jstests/concurrency/fsm_workloads/multi_statement_transaction_atomicity_isolation.js
new file mode 100644
index 00000000000..a6a2f41f5ac
--- /dev/null
+++ b/jstests/concurrency/fsm_workloads/multi_statement_transaction_atomicity_isolation.js
@@ -0,0 +1,216 @@
+'use strict';
+
+/**
+ * multi_statement_transaction_atomicity_isolation.js
+ *
+ * Inserts a handful of documents into a collection. Each thread then updates multiple documents
+ * inside of a multi-statement transaction. The resulting documents are of the form
+ *
+ *   {_id: 0, order: [{tid: 0, iteration: 0, numUpdated: 3},
+ *                    {tid: 1, iteration: 0, numUpdated: 2},
+ *                    ...]}
+ *
+ *   {_id: 1, order: [{tid: 0, iteration: 0, numUpdated: 3},
+ *                    {tid: 1, iteration: 0, numUpdated: 2},
+ *                    ...]}
+ *
+ *   {_id: 2, order: [{tid: 0, iteration: 0, numUpdated: 3}, ...]}
+ *
+ * where the {tid: 0, iteration: 0, numUpdated: 3} element should occur 3 times and should always
+ * come before the {tid: 1, iteration: 0, numUpdated: 2} element's 2 occurrences. In other words, we
+ * track
+ *
+ *   (1) the relative order in which each of the transactions commit based on their position within
+ *       the array, and
+ *
+ *   (2) the expected number of occurrences for each element in the array.
+ *
+ * An anomaly is detected if either
+ *
+ *   (a) transaction A's (tid, txnNumber, numToUpdate) element precedes transaction B's
+ *       (tid, txnNumber, numToUpdate) element in one document and follows it in another. This would
+ *       suggest that the database failed to detect a write-write conflict despite both transactions
+ *       modifying the same document and is therefore not providing snapshot isolation.
+ *
+ *   (b) transaction C's (tid, txnNumber, numToUpdate) element doesn't appear numToUpdate times
+ *       across a consistent snapshot of all of the documents. This would suggest that the database
+ *       failed to atomically update all documents modified in a concurrent transaction.
+ *
+ * @tags: [uses_transactions]
+ */
+
+load('jstests/libs/cycle_detection.js');  // for Graph
+
+// For withTxnAndAutoRetryOnWriteConflict.
+load('jstests/concurrency/fsm_workload_helpers/auto_retry_transaction.js');
+
+var $config = (function() {
+
+    function checkTransactionCommitOrder(documents) {
+        const graph = new Graph();
+
+        for (let doc of documents) {
+            const commitOrder = doc.order;
+            for (let i = 1; i < commitOrder.length; ++i) {
+                // We add an edge from commitOrder[i - 1] to commitOrder[i] because it being earlier
+                // in the array that was $push'd to indicates that the commitOrder[i - 1]
+                // transaction happened before the commit[i] transaction order.
+                graph.addEdge(commitOrder[i - 1], commitOrder[i]);
+            }
+        }
+
+        const result = graph.findCycle();
+
+        if (result.length > 0) {
+            const isOpPartOfCycle = (op) =>
+                result.some(cyclicOp => bsonBinaryEqual({_: op}, {_: cyclicOp}));
+
+            const filteredDocuments = documents.map(doc => {
+                const filteredCommitOrder = doc.order.filter(isOpPartOfCycle);
+                return Object.assign({}, doc, {order: filteredCommitOrder});
+            });
+
+            assertWhenOwnColl.eq([], result, tojson(filteredDocuments));
+        }
+    }
+
+    function checkNumUpdatedByEachTransaction(documents) {
+        const updateCounts = new Map();
+
+        for (let doc of documents) {
+            for (let op of doc.order) {
+                // We store 'op' both as the key and as part of the value because the mongo shell's
+                // Map type mangles the key and doesn't provide an API to retrieve the original
+                // key-value pairs.
+                const value = updateCounts.get(op) || {op, actual: 0};
+                updateCounts.put(op, {op, actual: value.actual + 1});
+            }
+        }
+
+        for (let {
+                 op, actual
+             } of updateCounts.values()) {
+            assert.eq(op.numUpdated, actual, () => {
+                return 'transaction ' + tojson(op) + ' should have updated ' + op.numUpdated +
+                    ' documents, but ' + actual + ' were updated: ' + tojson(updateCounts.values());
+            });
+        }
+    }
+
+    const states = (function() {
+
+        function getAllDocuments(collection, numDocs) {
+            // We intentionally use a smaller batch size when fetching all of the documents in the
+            // collection in order to stress the behavior of reading from the same snapshot over the
+            // course of multiple network roundtrips.
+            const batchSize = Math.max(2, Math.floor(numDocs / 5));
+
+            collection.getDB().getSession().startTransaction();
+            const documents =
+                collection.find().batchSize(batchSize).readConcern('snapshot').toArray();
+            collection.getDB().getSession().commitTransaction();
+
+            assertWhenOwnColl.eq(numDocs, documents.length, () => tojson(documents));
+            return documents;
+        }
+
+        function getDocIdsToUpdate(numDocs) {
+            // Generate between [2, numDocs / 2] operations.
+            const numOps = 2 + Random.randInt(Math.ceil(numDocs / 2) - 1);
+
+            // Select 'numOps' document (without replacement) to update.
+            let docIds = Array.from({length: numDocs}, (value, index) => index);
+            return Array.shuffle(docIds).slice(0, numOps);
+        }
+
+        return {
+            init: function init(db, collName) {
+                this.iteration = 0;
+                this.session = db.getMongo().startSession({causalConsistency: false});
+            },
+
+            update: function update(db, collName) {
+                const collection = this.session.getDatabase(db.getName()).getCollection(collName);
+                const docIds = getDocIdsToUpdate(this.numDocs);
+
+                // We apply the following update to each of the 'docIds' documents to record the
+                // number of times we expect to see the transaction being run in this execution of
+                // the update() state function by this worker thread present across all documents.
+                // Using the $push operator causes a transaction which commits after another
+                // transaction to appear later in the array.
+                const updateMods = {
+                    $push: {
+                        order: {
+                            tid: this.tid,
+                            iteration: this.iteration,
+                            numUpdated: docIds.length,
+                        }
+                    }
+                };
+
+                withTxnAndAutoRetryOnWriteConflict(this.session, () => {
+                    for (let [i, docId] of docIds.entries()) {
+                        const res = collection.runCommand('update', {
+                            updates: [{q: {_id: docId}, u: updateMods}],
+                        });
+                        assertAlways.commandWorked(res);
+                        assertWhenOwnColl.eq(res.n, 1, () => tojson(res));
+                        assertWhenOwnColl.eq(res.nModified, 1, () => tojson(res));
+                    }
+                });
+
+                ++this.iteration;
+            },
+
+            checkConsistency: function checkConsistency(db, collName) {
+                const collection = this.session.getDatabase(db.getName()).getCollection(collName);
+                const documents = getAllDocuments(collection, this.numDocs);
+                checkTransactionCommitOrder(documents);
+                checkNumUpdatedByEachTransaction(documents);
+            }
+        };
+    })();
+
+    const transitions = {
+        init: {update: 0.9, checkConsistency: 0.1},
+        update: {update: 0.9, checkConsistency: 0.1},
+        checkConsistency: {update: 1}
+    };
+
+    function setup(db, collName, cluster) {
+        const bulk = db[collName].initializeUnorderedBulkOp();
+
+        for (let i = 0; i < this.numDocs; ++i) {
+            bulk.insert({_id: i, order: []});
+        }
+
+        const res = bulk.execute({w: 'majority'});
+        assertWhenOwnColl.commandWorked(res);
+        assertWhenOwnColl.eq(this.numDocs, res.nInserted);
+    }
+
+    function teardown(db, collName, cluster) {
+        const documents = db[collName].find().toArray();
+        checkTransactionCommitOrder(documents);
+        checkNumUpdatedByEachTransaction(documents);
+    }
+
+    function skip(cluster) {
+        if (cluster.isSharded() || cluster.isStandalone()) {
+            return {skip: true, msg: 'only runs in a replica set.'};
+        }
+        return {skip: false};
+    }
+
+    return {
+        threadCount: 10,
+        iterations: 50,
+        states: states,
+        transitions: transitions,
+        data: {numDocs: 10},
+        setup: setup,
+        teardown: teardown,
+        skip: skip
+    };
+
+})();
diff --git a/jstests/concurrency/fsm_workloads/multi_statement_transaction_simple.js b/jstests/concurrency/fsm_workloads/multi_statement_transaction_simple.js
index 5364d1509ab..ba018cd2768 100644
--- a/jstests/concurrency/fsm_workloads/multi_statement_transaction_simple.js
+++ b/jstests/concurrency/fsm_workloads/multi_statement_transaction_simple.js
@@ -4,55 +4,40 @@
  * Creates several bank accounts. On each iteration, each thread:
  *  - chooses two accounts and amount of money being transfer
  *  - or checks the balance of each account
+ *
  * @tags: [uses_transactions]
  */
+
+// For withTxnAndAutoRetryOnWriteConflict.
+load('jstests/concurrency/fsm_workload_helpers/auto_retry_transaction.js');
+
 var $config = (function() {
 
-    function _calcTotalMoneyBalances(sessionDb, txnNumber, collName) {
-        let res = sessionDb.runCommand({
-            find: collName,
-            batchSize: 0,
-            filter: {},
-            readConcern: {level: "snapshot"},
-            txnNumber: NumberLong(txnNumber),
-            startTransaction: true,
-            autocommit: false
-        });
-        assertWhenOwnColl.commandWorked(res);
-        let cursorId = res.cursor.id;
-
-        let total = 0;
-        while (bsonWoCompare({_: cursorId}, {_: 0}) !== 0) {
-            res = sessionDb.runCommand({
-                getMore: cursorId,
-                collection: collName,
-                txnNumber: NumberLong(txnNumber),
-                autocommit: false
-            });
-            assertWhenOwnColl.commandWorked(res);
-            res.cursor.nextBatch.forEach(function(account) {
-                total += account.balance;
-            });
-            cursorId = res.cursor.id;
-        }
-        // commitTransaction can only be called on the admin database.
-        assertWhenOwnColl.commandWorked(sessionDb.adminCommand(
-            {commitTransaction: 1, txnNumber: NumberLong(txnNumber), autocommit: false}));
-        return total;
+    function computeTotalOfAllBalances(documents) {
+        return documents.reduce((total, account) => total + account.balance, 0);
     }
 
     var states = (function() {
 
+        function getAllDocuments(collection, numDocs) {
+            collection.getDB().getSession().startTransaction();
+            const documents = collection.find().readConcern('snapshot').toArray();
+            collection.getDB().getSession().commitTransaction();
+
+            assertWhenOwnColl.eq(numDocs, documents.length, () => tojson(documents));
+            return documents;
+        }
+
         function init(db, collName) {
-            const session = db.getMongo().startSession({causalConsistency: false});
-            this.sessionDb = session.getDatabase(db.getName());
-            this.txnNumber = 0;
+            this.session = db.getMongo().startSession({causalConsistency: false});
         }
 
         function checkMoneyBalance(db, collName) {
-            this.txnNumber++;
-            assertWhenOwnColl.eq(_calcTotalMoneyBalances(this.sessionDb, this.txnNumber, collName),
-                                 this.numAccounts * this.initialValue);
+            const collection = this.session.getDatabase(db.getName()).getCollection(collName);
+            const documents = getAllDocuments(collection, this.numAccounts);
+            assertWhenOwnColl.eq(this.numAccounts * this.initialValue,
+                                 computeTotalOfAllBalances(documents),
+                                 () => tojson(documents));
         }
 
         function transferMoney(db, collName) {
@@ -61,51 +46,29 @@ var $config = (function() {
             while (transferFrom === transferTo) {
                 transferTo = Random.randInt(this.numAccounts);
             }
-            // Make transferAmount nonzero so that each update will be executed
+
+            // We make 'transferAmount' non-zero in order to guarantee that the documents matched by
+            // the update operations are modified.
             const transferAmount = Random.randInt(this.initialValue / 10) + 1;
-            const commands = [
-                {
-                  update: collName,
-                  updates: [{q: {_id: transferFrom}, u: {$inc: {balance: -transferAmount}}}],
-                  readConcern: {level: "snapshot"},
-                  startTransaction: true,
-                  autocommit: false
-                },
-                {
-                  update: collName,
-                  updates: [{q: {_id: transferTo}, u: {$inc: {balance: transferAmount}}}],
-                  autocommit: false
-                },
-                {commitTransaction: 1, autocommit: false}
-            ];
-
-            let hasWriteConflict;
-            do {
-                this.txnNumber++;
-                hasWriteConflict = false;
-                for (let cmd of commands) {
-                    cmd["txnNumber"] = NumberLong(this.txnNumber);
-                    let res;
-                    if (cmd.hasOwnProperty("commitTransaction")) {
-                        res = this.sessionDb.adminCommand(cmd);
-                    } else {
-                        res = this.sessionDb.runCommand(cmd);
-                    }
-                    if (res.ok === 0) {
-                        if (res.code === ErrorCodes.WriteConflict) {
-                            hasWriteConflict = true;
-                            break;
-                        } else {
-                            assertWhenOwnColl.commandWorked(res, () => tojson(cmd));
-                        }
-                    }
-
-                    // For the updates, ensure that exactly one document was updated.
-                    if (res.hasOwnProperty("nModified")) {
-                        assertWhenOwnColl.eq(res.nModified, 1, tojson(res));
-                    }
-                }
-            } while (hasWriteConflict);
+
+            const collection = this.session.getDatabase(db.getName()).getCollection(collName);
+            withTxnAndAutoRetryOnWriteConflict(this.session, () => {
+                let res = collection.runCommand('update', {
+                    updates: [{q: {_id: transferFrom}, u: {$inc: {balance: -transferAmount}}}],
+                });
+
+                assertAlways.commandWorked(res);
+                assertWhenOwnColl.eq(res.n, 1, () => tojson(res));
+                assertWhenOwnColl.eq(res.nModified, 1, () => tojson(res));
+
+                res = collection.runCommand('update', {
+                    updates: [{q: {_id: transferTo}, u: {$inc: {balance: transferAmount}}}],
+                });
+
+                assertAlways.commandWorked(res);
+                assertWhenOwnColl.eq(res.n, 1, () => tojson(res));
+                assertWhenOwnColl.eq(res.nModified, 1, () => tojson(res));
+            });
         }
 
         return {init: init, transferMoney: transferMoney, checkMoneyBalance: checkMoneyBalance};
@@ -118,14 +81,17 @@ var $config = (function() {
         for (let i = 0; i < this.numAccounts; ++i) {
             bulk.insert({_id: i, balance: this.initialValue});
         }
-        assertWhenOwnColl.commandWorked(bulk.execute({w: "majority"}));
+
+        const res = bulk.execute({w: 'majority'});
+        assertWhenOwnColl.commandWorked(res);
+        assertWhenOwnColl.eq(this.numAccounts, res.nInserted);
     }
 
     function teardown(db, collName, cluster) {
-        const session = db.getMongo().startSession({causalConsistency: false});
-        assertWhenOwnColl.eq(
-            _calcTotalMoneyBalances(session.getDatabase(db.getName()), NumberLong(0), collName),
-            this.numAccounts * this.initialValue);
+        const documents = db[collName].find().toArray();
+        assertWhenOwnColl.eq(this.numAccounts * this.initialValue,
+                             computeTotalOfAllBalances(documents),
+                             () => tojson(documents));
     }
 
     var transitions = {
@@ -142,8 +108,8 @@ var $config = (function() {
     };
 
     return {
-        threadCount: 4,
-        iterations: 20,
+        threadCount: 10,
+        iterations: 100,
         startState: 'init',
         states: states,
         transitions: transitions,
diff --git a/jstests/libs/cycle_detection.js b/jstests/libs/cycle_detection.js
index 326dd54129e..fc2965e3e2b 100644
--- a/jstests/libs/cycle_detection.js
+++ b/jstests/libs/cycle_detection.js
@@ -85,8 +85,9 @@ function Graph() {
                 if (result.length > 1) {
                     // A cycle has been detected during the recursive call to doDepthFirstSearch().
                     // Unless we've already closed the loop, the (node, otherNode) edge must be part
-                    // of it.
-                    if (result[0] !== result[result.length - 1]) {
+                    // of it. Note that we use friendlyEqual() to match the definition of sameness
+                    // as the mongo shell's Map type.
+                    if (!friendlyEqual(result[0], result[result.length - 1])) {
                         result.unshift(node);
                     }
                     return result;
diff --git a/jstests/noPassthrough/cycle_detection_test.js b/jstests/noPassthrough/cycle_detection_test.js
index 516dcb00a0f..f708decae79 100644
--- a/jstests/noPassthrough/cycle_detection_test.js
+++ b/jstests/noPassthrough/cycle_detection_test.js
@@ -76,4 +76,15 @@
         graph.addEdge(w, z);
         assert.eq([w, z], graph.findCycle());
     })();
+
+    (function testGraphMinimizesCycleUsingNonReferentialEquality() {
+        const graph = new Graph();
+        graph.addEdge({a: 1}, {a: 2});
+        graph.addEdge({a: 2}, {a: 3});
+        graph.addEdge({a: 3}, {a: 4});
+        graph.addEdge({a: 4}, {a: 5});
+        graph.addEdge({a: 5}, {a: 3});
+
+        assert.eq([{a: 3}, {a: 4}, {a: 5}, {a: 3}], graph.findCycle());
+    })();
 })();