SERVER-56127 Retryable update may execute more than once if chunk is migrated and shard key pattern uses nested fields

9 files changed, 313 insertions, 6 deletions

diff --git a/etc/backports_required_for_multiversion_tests.yml b/etc/backports_required_for_multiversion_tests.yml
index 7a74aa7479c..06e463e78b8 100644
--- a/etc/backports_required_for_multiversion_tests.yml
+++ b/etc/backports_required_for_multiversion_tests.yml
@@ -116,6 +116,8 @@ all:
     test_file: jstests/replsets/step_down_chaining_disabled.js
   - ticket: SERVER-50486
     test_file: jstests/replsets/dont_refresh_session_prepare_secondary.js
+  - ticket: SERVER-56127
+    test_file: jstests/sharding/retryable_writes_nested_shard_key.js
   - ticket: SERVER-59197
     test_file: jstests/replsets/sessions_collection_reaping.js
   - ticket: SERVER-37904
@@ -175,8 +177,6 @@ suites:
   - ticket: SERVER-47568
     test_file: jstests/replsets/disable_cluster_time_gossiping_in_unreadable_state.js
 
-  sharding_multiversion:
-
   sharding_jscore_multiversion_passthrough:
   - ticket: SERVER-47469
     test_file: jstests/core/apply_ops_system_dot_views.js
@@ -184,3 +184,7 @@ suites:
   sharded_collections_jscore_multiversion_passthrough:
   - ticket: SERVER-47469
     test_file: jstests/core/apply_ops_system_dot_views.js
+
+  sharding_multiversion:
+  - ticket: SERVER-56127
+    test_file: jstests/sharding/retryable_writes_nested_shard_key.js
diff --git a/jstests/sharding/retryable_writes_nested_shard_key.js b/jstests/sharding/retryable_writes_nested_shard_key.js
new file mode 100644
index 00000000000..38ff71dc2d0
--- /dev/null
+++ b/jstests/sharding/retryable_writes_nested_shard_key.js
@@ -0,0 +1,83 @@
+/**
+ * Tests retryable insert, update and delete operations on a sharded collection with a nested shard
+ * key to ensure that each operation is not re-executed when run after chunk migration.
+ */
+
+(function() {
+"use strict";
+
+load("jstests/sharding/libs/create_sharded_collection_util.js");
+
+const st = new ShardingTest({mongos: 1, config: 1, shards: 2, rs: {nodes: 1}});
+
+const db = st.s.getDB("test");
+const collection = db.getCollection("mycoll");
+CreateShardedCollectionUtil.shardCollectionWithChunks(collection, {"x.y": 1}, [
+    {min: {"x.y": MinKey}, max: {"x.y": 0}, shard: st.shard0.shardName},
+    {min: {"x.y": 0}, max: {"x.y": 10}, shard: st.shard0.shardName},
+    {min: {"x.y": 10}, max: {"x.y": 20}, shard: st.shard1.shardName},
+    {min: {"x.y": 20}, max: {"x.y": MaxKey}, shard: st.shard1.shardName},
+]);
+
+assert.commandWorked(collection.insert({_id: 0, x: {y: 5}, counter: 0}));
+assert.commandWorked(collection.insert({_id: 1, x: {y: 15}}));
+
+const session = st.s.startSession({causalConsistency: false, retryWrites: false});
+const sessionCollection = session.getDatabase(db.getName()).getCollection(collection.getName());
+
+const updateCmd = {
+    updates: [{q: {"x.y": 5, _id: 0}, u: {$inc: {counter: 1}}}],
+    txnNumber: NumberLong(0),
+};
+
+const deleteCmd = {
+    deletes: [{q: {"x.y": 15, _id: 1}, limit: 1}],
+    txnNumber: NumberLong(1),
+};
+
+const insertCmd = {
+    documents: [{_id: 2, x: {y: 25}}],
+    txnNumber: NumberLong(2),
+};
+
+// Test that updateCmd is only executed a single time by verifying that counter has only been
+// incremented once.
+const firstRes = assert.commandWorked(sessionCollection.runCommand("update", updateCmd));
+assert.eq({n: firstRes.n, nModified: firstRes.nModified}, {n: 1, nModified: 1});
+
+assert.commandWorked(db.adminCommand(
+    {moveChunk: collection.getFullName(), find: {"x.y": 5}, to: st.shard1.shardName}));
+
+const secondRes = assert.commandWorked(sessionCollection.runCommand("update", updateCmd));
+print(`secondRes: ${tojsononeline(secondRes)}`);
+assert.eq(collection.findOne({_id: 0}), {_id: 0, x: {y: 5}, counter: 1});
+
+// Tests deleteCmd is only executed a single time by verifying that the command is able to
+// run a second time and that the response to the second command is equivalent to the first
+const firstResDelete = assert.commandWorked(sessionCollection.runCommand("delete", deleteCmd));
+assert.eq({n: firstResDelete.n}, {n: 1});
+assert.eq(collection.findOne({_id: 1}), null);
+
+assert.commandWorked(db.adminCommand(
+    {moveChunk: collection.getFullName(), find: {"x.y": 15}, to: st.shard0.shardName}));
+
+const secondResDelete = assert.commandWorked(sessionCollection.runCommand("delete", deleteCmd));
+print(`secondResDelete: ${tojsononeline(secondResDelete)}`);
+assert.eq(secondResDelete.n, firstResDelete.n);
+
+// Tests insertCmd is only executed a single time by verifying that the command is able to
+// run a second time and that the response to the second command is equivalent to the first.
+//   - If command were to execute a second time, we would receieve a duplicate key error
+const firstResInsert = assert.commandWorked(sessionCollection.runCommand("insert", insertCmd));
+assert.eq({n: firstResInsert.n}, {n: 1});
+
+assert.commandWorked(db.adminCommand(
+    {moveChunk: collection.getFullName(), find: {"x.y": 25}, to: st.shard0.shardName}));
+
+const secondResInsert = assert.commandWorked(sessionCollection.runCommand("insert", insertCmd));
+print(`secondResInsert: ${tojsononeline(secondResInsert)}`);
+assert.eq(secondResInsert.n, firstResInsert.n);
+assert.eq(collection.findOne({_id: 2}), {_id: 2, x: {y: 25}});
+
+st.stop();
+})();
diff --git a/src/mongo/db/repl/oplog_entry.cpp b/src/mongo/db/repl/oplog_entry.cpp
index 0ee07fb03ee..3c6b0568413 100644
--- a/src/mongo/db/repl/oplog_entry.cpp
+++ b/src/mongo/db/repl/oplog_entry.cpp
@@ -277,6 +277,20 @@ bool OplogEntry::isCrudOpType() const {
     return isCrudOpType(getOpType());
 }
 
+bool OplogEntry::isUpdateOrDelete() const {
+    auto opType = getOpType();
+    switch (opType) {
+        case OpTypeEnum::kDelete:
+        case OpTypeEnum::kUpdate:
+            return true;
+        case OpTypeEnum::kInsert:
+        case OpTypeEnum::kCommand:
+        case OpTypeEnum::kNoop:
+            return false;
+    }
+    MONGO_UNREACHABLE;
+}
+
 bool OplogEntry::shouldPrepare() const {
     return getCommandType() == CommandType::kApplyOps &&
         getObject()[ApplyOpsCommandInfoBase::kPrepareFieldName].booleanSafe();
diff --git a/src/mongo/db/repl/oplog_entry.h b/src/mongo/db/repl/oplog_entry.h
index 7462d70694e..a557b25ee35 100644
--- a/src/mongo/db/repl/oplog_entry.h
+++ b/src/mongo/db/repl/oplog_entry.h
@@ -231,6 +231,11 @@ public:
     bool isCrudOpType() const;
 
     /**
+     * Returns true if the oplog entry is for an Update or Delete operation.
+     */
+    bool isUpdateOrDelete() const;
+
+    /**
      * Returns if the operation should be prepared. Must be called on an 'applyOps' entry.
      */
     bool shouldPrepare() const;
diff --git a/src/mongo/db/s/session_catalog_migration_source.cpp b/src/mongo/db/s/session_catalog_migration_source.cpp
index 7c3ac3b2fd3..ba7c3338719 100644
--- a/src/mongo/db/s/session_catalog_migration_source.cpp
+++ b/src/mongo/db/s/session_catalog_migration_source.cpp
@@ -314,8 +314,7 @@ bool SessionCatalogMigrationSource::_handleWriteHistory(WithLock, OperationConte
             }
 
             if (nextOplog->isCrudOpType()) {
-                auto shardKey =
-                    _keyPattern.extractShardKeyFromDoc(nextOplog->getObjectContainingDocumentKey());
+                auto shardKey = _keyPattern.extractShardKeyFromOplogEntry(*nextOplog);
                 if (!_chunkRange.containsKey(shardKey)) {
                     continue;
                 }
diff --git a/src/mongo/s/SConscript b/src/mongo/s/SConscript
index 3ba193d8a1f..e1be6ac9065 100644
--- a/src/mongo/s/SConscript
+++ b/src/mongo/s/SConscript
@@ -90,6 +90,7 @@ env.Library(
     LIBDEPS=[
         '$BUILD_DIR/mongo/db/matcher/expressions',
         '$BUILD_DIR/mongo/db/query/query_planner',
+        '$BUILD_DIR/mongo/db/repl/oplog_entry',
         '$BUILD_DIR/mongo/db/storage/key_string',
         '$BUILD_DIR/mongo/db/update/update_common',
         '$BUILD_DIR/mongo/util/concurrency/ticketholder',
diff --git a/src/mongo/s/shard_key_pattern.cpp b/src/mongo/s/shard_key_pattern.cpp
index 5d59c25653c..8b56f945fe3 100644
--- a/src/mongo/s/shard_key_pattern.cpp
+++ b/src/mongo/s/shard_key_pattern.cpp
@@ -54,6 +54,8 @@ constexpr size_t kMaxFlattenedInCombinations = 4000000;
 
 constexpr auto kIdField = "_id"_sd;
 
+const BSONObj kNullObj = BSON("" << BSONNULL);
+
 /**
  * Currently the allowable shard keys are either:
  * i) a hashed single field, e.g. { a : "hashed" }, or
@@ -102,6 +104,10 @@ std::vector<std::unique_ptr<FieldRef>> parseShardKeyPattern(const BSONObj& keyPa
     return parsedPaths;
 }
 
+bool isValidShardKeyElementForExtractionFromDocument(const BSONElement& element) {
+    return element.type() != Array;
+}
+
 bool isValidShardKeyElement(const BSONElement& element) {
     return !element.eoo() && element.type() != Array;
 }
@@ -152,6 +158,15 @@ BSONElement findEqualityElement(const EqualityMatches& equalities, const FieldRe
     return extractKeyElementFromMatchable(matchable, suffixStr);
 }
 
+BSONElement extractFieldFromDocumentKey(const BSONObj& documentKey, StringData fieldName) {
+    BSONElement output;
+    for (auto&& documentKeyElt : documentKey) {
+        if (fieldName == documentKeyElt.fieldNameStringData()) {
+            return documentKeyElt;
+        }
+    }
+    return output;
+}
 }  // namespace
 
 constexpr int ShardKeyPattern::kMaxShardKeySizeBytes;
@@ -271,11 +286,53 @@ BSONObj ShardKeyPattern::extractShardKeyFromMatchable(const MatchableDocument& m
     return keyBuilder.obj();
 }
 
+BSONObj ShardKeyPattern::extractShardKeyFromDocumentKey(const BSONObj& documentKey) const {
+    BSONObjBuilder keyBuilder;
+    for (auto&& shardKeyField : _keyPattern.toBSON()) {
+        auto matchEl =
+            extractFieldFromDocumentKey(documentKey, shardKeyField.fieldNameStringData());
+
+        if (matchEl.eoo()) {
+            matchEl = kNullObj.firstElement();
+        }
+
+        // A shard key field cannot have array values. If we encounter array values return
+        // immediately.
+        if (!isValidShardKeyElementForExtractionFromDocument(matchEl)) {
+            return BSONObj();
+        }
+
+        if (isHashedPatternEl(shardKeyField)) {
+            keyBuilder.append(
+                shardKeyField.fieldNameStringData(),
+                BSONElementHasher::hash64(matchEl, BSONElementHasher::DEFAULT_HASH_SEED));
+        } else {
+            keyBuilder.appendAs(matchEl, shardKeyField.fieldNameStringData());
+        }
+    }
+    dassert(isShardKey(keyBuilder.asTempObj()));
+    return keyBuilder.obj();
+}
+
 BSONObj ShardKeyPattern::extractShardKeyFromDoc(const BSONObj& doc) const {
     BSONMatchableDocument matchable(doc);
     return extractShardKeyFromMatchable(matchable);
 }
 
+BSONObj ShardKeyPattern::extractShardKeyFromOplogEntry(const repl::OplogEntry& entry) const {
+    if (!entry.isCrudOpType()) {
+        return BSONObj();
+    }
+
+    auto objWithDocumentKey = entry.getObjectContainingDocumentKey();
+
+    if (!entry.isUpdateOrDelete()) {
+        return extractShardKeyFromDoc(objWithDocumentKey);
+    }
+
+    return extractShardKeyFromDocumentKey(objWithDocumentKey);
+}
+
 std::vector<StringData> ShardKeyPattern::findMissingShardKeyFieldsFromDoc(const BSONObj doc) const {
     std::vector<StringData> missingFields;
     BSONMatchableDocument matchable(doc);
diff --git a/src/mongo/s/shard_key_pattern.h b/src/mongo/s/shard_key_pattern.h
index 42557730e0c..ccc570fe4d7 100644
--- a/src/mongo/s/shard_key_pattern.h
+++ b/src/mongo/s/shard_key_pattern.h
@@ -38,6 +38,7 @@
 #include "mongo/db/keypattern.h"
 #include "mongo/db/matcher/matchable.h"
 #include "mongo/db/query/index_bounds.h"
+#include "mongo/db/repl/oplog_entry.h"
 
 namespace mongo {
 
@@ -121,6 +122,30 @@ public:
     BSONObj normalizeShardKey(const BSONObj& shardKey) const;
 
     /**
+     * Given a document key expressed in dotted notation, extracts its shard key, applying hashing
+     * if necessary.
+     * Note: For a shardKeyPattern {a.b: 1, c: 1}
+     *  The documentKey for the document {a: {b: 10}, c: 20} is {a.b: 10, c: 20}
+     *  The documentKey for the document {a: {b: 10, d: 20}, c: 30} is {a.b: 10, c: 30}
+     *  The documentKey for the document {a: {b: {d: 10}}, c: 30} is {a.b: {d: 10}, c: 30}
+     *
+     * Examples:
+     *  If 'this' KeyPattern is {a: 1}
+     *   {a: 10, b: 20} --> returns {a: 10}
+     *   {b: 20} --> returns {a: null}
+     *   {a: {b: 10}} --> returns {a: {b: 10}}
+     *   {a: [1,2]} --> returns {}
+     *  If 'this' KeyPattern is {a.b: 1, c: 1}
+     *   {a.b: 10, c: 20} --> returns {a.b: 10, c: 20}
+     *   {a.b: 10} --> returns {a.b: 10, c: null}
+     *   {a.b: {z: 10}, c: 20} --> returns {a.b: {z: 10}, c: 20}
+     *  If 'this' KeyPattern is {a : "hashed"}
+     *   {a: 10, b: 20} --> returns {a: NumberLong("7766103514953448109")}
+     *   {b: 20} --> returns {a: NumberLong("2338878944348059895")}
+     */
+    BSONObj extractShardKeyFromDocumentKey(const BSONObj& documentKey) const;
+
+    /**
      * Given a MatchableDocument, extracts the shard key corresponding to the key pattern.
      * For each path in the shard key pattern, extracts a value from the matchable document.
      *
@@ -151,6 +176,26 @@ public:
     BSONObj extractShardKeyFromDoc(const BSONObj& doc) const;
 
     /**
+     * Given an Oplog entry, extracts the shard key corresponding to the key pattern for insert,
+     * update, and delete op types. If the op type is not a CRUD operation, an empty BSONObj()
+     * will be returned.
+     *
+     * For update and delete operations, the Oplog entry will contain an object with the document
+     * key.
+     *
+     * For insert operations, the Oplog entry will contain the original document from which the
+     * document key must be extracted
+     *
+     * Examples:
+     *  For KeyPattern {'a.b': 1}
+     *   If the oplog entries contains field op='i'
+     *     oplog contains: { a : { b : "1" } }
+     *   If the oplog entries contains field op='u' or op='d'
+     *     oplog contains: { 'a.b': "1" }
+     */
+    BSONObj extractShardKeyFromOplogEntry(const repl::OplogEntry& entry) const;
+
+    /**
      * Returns the set of shard key fields which are absent from the given document. Note that the
      * vector returned by this method contains StringData elements pointing into ShardKeyPattern's
      * underlying BSONObj. If the fieldnames are required to survive beyond the lifetime of this
diff --git a/src/mongo/s/shard_key_pattern_test.cpp b/src/mongo/s/shard_key_pattern_test.cpp
index ecde034896b..15e1edf03fe 100644
--- a/src/mongo/s/shard_key_pattern_test.cpp
+++ b/src/mongo/s/shard_key_pattern_test.cpp
@@ -29,11 +29,10 @@
 
 #include "mongo/platform/basic.h"
 
-#include "mongo/s/shard_key_pattern.h"
-
 #include "mongo/db/hasher.h"
 #include "mongo/db/json.h"
 #include "mongo/db/query/query_test_service_context.h"
+#include "mongo/s/shard_key_pattern.h"
 #include "mongo/unittest/unittest.h"
 
 namespace mongo {
@@ -41,6 +40,32 @@ namespace {
 
 using std::string;
 
+/**
+ * Creates OplogEntry with given field values.
+ */
+repl::OplogEntry makeOplogEntry(repl::OpTime opTime,
+                                repl::OpTypeEnum opType,
+                                NamespaceString nss,
+                                BSONObj oField,
+                                boost::optional<BSONObj> o2Field = boost::none) {
+    return {repl::OplogEntry(opTime,                           // optime
+                             boost::none,                      // hash
+                             opType,                           // opType
+                             nss,                              // namespace
+                             boost::none,                      // uuid
+                             boost::none,                      // fromMigrate
+                             repl::OplogEntry::kOplogVersion,  // version
+                             oField,                           // o
+                             o2Field,                          // o2
+                             {},                               // sessionInfo
+                             boost::none,                      // upsert
+                             Date_t(),                         // wall clock time
+                             {},                               // statement ids
+                             boost::none,    // optime of previous write within same transaction
+                             boost::none,    // pre-image optime
+                             boost::none)};  // post-image optime
+}
+
 TEST(ShardKeyPattern, SingleFieldShardKeyPatternsValidityCheck) {
     ShardKeyPattern(BSON("a" << 1));
     ShardKeyPattern(BSON("a" << 1.0f));
@@ -124,6 +149,10 @@ static BSONObj docKey(const ShardKeyPattern& pattern, const BSONObj& doc) {
     return pattern.extractShardKeyFromDoc(doc);
 }
 
+static BSONObj docKeyFromOplog(const ShardKeyPattern& pattern, const repl::OplogEntry& entry) {
+    return pattern.extractShardKeyFromOplogEntry(entry);
+}
+
 TEST(ShardKeyPattern, ExtractDocShardKeySingle) {
     //
     // Single field ShardKeyPatterns
@@ -207,6 +236,76 @@ TEST(ShardKeyPattern, ExtractDocShardKeyNested) {
     ASSERT_BSONOBJ_EQ(docKey(pattern, fromjson("{a:{b:[10, 20]}, c:30}")), BSONObj());
 }
 
+TEST(ShardKeyPattern, ExtractShardKeyFromOplogUnnested) {
+    //
+    // Unnested ShardKeyPatterns from oplog entries with CRUD operation
+    //
+
+    ShardKeyPattern pattern(BSON("a" << 1));
+    auto deleteOplog = makeOplogEntry(repl::OpTime(Timestamp(50, 10), 1),  // optime
+                                      repl::OpTypeEnum::kDelete,           // op type
+                                      NamespaceString("a"),                // namespace
+                                      BSON("_id" << 1 << "a" << 5));       // o
+    auto insertOplog = makeOplogEntry(repl::OpTime(Timestamp(60, 10), 1),  // optime
+                                      repl::OpTypeEnum::kInsert,           // op type
+                                      NamespaceString("a"),                // namespace
+                                      BSON("_id" << 2 << "a" << 6));       // o
+    auto updateOplog = makeOplogEntry(repl::OpTime(Timestamp(70, 10), 1),  // optime
+                                      repl::OpTypeEnum::kUpdate,           // op type
+                                      NamespaceString("a"),                // namespace
+                                      BSON("_id" << 3),                    // o
+                                      BSON("_id" << 3 << "a" << 7));       // o2
+
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, deleteOplog), fromjson("{a: 5}"));
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, insertOplog), fromjson("{a: 6}"));
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, updateOplog), fromjson("{a: 7}"));
+}
+
+TEST(ShardKeyPattern, ExtractShardKeyFromOplogNested) {
+    //
+    // Nested ShardKeyPatterns from oplog entries with CRUD operation
+    //
+
+    ShardKeyPattern pattern(BSON("a.b" << 1));
+    auto deleteOplog = makeOplogEntry(repl::OpTime(Timestamp(50, 10), 1),          // optime
+                                      repl::OpTypeEnum::kDelete,                   // op type
+                                      NamespaceString("a.b"),                      // namespace
+                                      BSON("_id" << 1 << "a.b" << 5));             // o
+    auto insertOplog = makeOplogEntry(repl::OpTime(Timestamp(60, 10), 1),          // optime
+                                      repl::OpTypeEnum::kInsert,                   // op type
+                                      NamespaceString("a.b"),                      // namespace
+                                      BSON("_id" << 2 << "a" << BSON("b" << 6)));  // o
+    auto updateOplog = makeOplogEntry(repl::OpTime(Timestamp(70, 10), 1),          // optime
+                                      repl::OpTypeEnum::kUpdate,                   // op type
+                                      NamespaceString("a.b"),                      // namespace
+                                      BSON("_id" << 3),                            // o
+                                      BSON("_id" << 3 << "a.b" << 7));             // o2
+
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, deleteOplog), fromjson("{'a.b': 5}"));
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, insertOplog), fromjson("{'a.b': 6}"));
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, updateOplog), fromjson("{'a.b': 7}"));
+}
+
+TEST(ShardKeyPattern, ExtractShardKeyFromOplogNonCRUD) {
+    //
+    // Oplogs with non-CRUD op types
+    //
+
+    ShardKeyPattern pattern(BSON("a.b" << 1));
+    auto noopOplog = makeOplogEntry(repl::OpTime(Timestamp(50, 10), 1),     // optime
+                                    repl::OpTypeEnum::kNoop,                // op type
+                                    NamespaceString("a.b"),                 // namespace
+                                    BSON("_id" << 1 << "a.b" << 5));        // o
+    auto commandOplog = makeOplogEntry(repl::OpTime(Timestamp(60, 10), 1),  // optime
+                                       repl::OpTypeEnum::kCommand,          // op type
+                                       NamespaceString("a.b"),              // namespace
+                                       BSON("create"
+                                            << "c"));  // o
+
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, noopOplog), BSONObj());
+    ASSERT_BSONOBJ_EQ(docKeyFromOplog(pattern, commandOplog), BSONObj());
+}
+
 TEST(ShardKeyPattern, ExtractDocShardKeyDeepNested) {
     //
     // Deeply nested ShardKeyPatterns