SERVER-47694: fix multikey. again

Split the single _isMultikey variable on an IndexCatalogEntry(Impl) into two
separate variables: _isMultikeyForReader and _isMultikeyForWriter.

_isMultikeyForReader is flipped as early as possible. Readers concurrent
with multikey flipping may forgo a possible optimization when their snapshot
sees no multikey data.

_isMultikeyForWriter is flipped after the storage engine commits a multikey
change to the on-disk catalog. At this point, writers may, under some
circumstances, optimize away some catalog writes.

Move logic for optimizing readers (multikey paths, clearing query cache) outside
of the onCommit.

Adds a failpoint widenWUOWChangesWindow which sleeps transaction commit and
onCommit/onRollback handlers.

Have validate assert multikey paths are set correctly for the documents observed
during its collection scan.

8 files changed, 89 insertions, 35 deletions

diff --git a/src/mongo/db/catalog/SConscript b/src/mongo/db/catalog/SConscript
index a3fb3fde6e6..298478faa9b 100644
--- a/src/mongo/db/catalog/SConscript
+++ b/src/mongo/db/catalog/SConscript
@@ -389,6 +389,7 @@ env.Library(
         'catalog_impl',
     ],
     LIBDEPS_PRIVATE=[
+        '$BUILD_DIR/mongo/db/multi_key_path_tracker',
         'throttle_cursor',
         'validate_state',
     ]
diff --git a/src/mongo/db/catalog/index_catalog_entry_impl.cpp b/src/mongo/db/catalog/index_catalog_entry_impl.cpp
index 832d3d2767d..cca329b0007 100644
--- a/src/mongo/db/catalog/index_catalog_entry_impl.cpp
+++ b/src/mongo/db/catalog/index_catalog_entry_impl.cpp
@@ -80,7 +80,9 @@ IndexCatalogEntryImpl::IndexCatalogEntryImpl(OperationContext* const opCtx,
 
     {
         stdx::lock_guard<Latch> lk(_indexMultikeyPathsMutex);
-        _isMultikey.store(_catalogIsMultikey(opCtx, &_indexMultikeyPaths));
+        const bool isMultikey = _catalogIsMultikey(opCtx, &_indexMultikeyPaths);
+        _isMultikeyForRead.store(isMultikey);
+        _isMultikeyForWrite.store(isMultikey);
         _indexTracksPathLevelMultikeyInfo = !_indexMultikeyPaths.empty();
     }
 
@@ -158,7 +160,7 @@ bool IndexCatalogEntryImpl::isFrozen() const {
 }
 
 bool IndexCatalogEntryImpl::isMultikey() const {
-    return _isMultikey.load();
+    return _isMultikeyForRead.load();
 }
 
 MultikeyPaths IndexCatalogEntryImpl::getMultikeyPaths(OperationContext* opCtx) const {
@@ -180,7 +182,7 @@ void IndexCatalogEntryImpl::setIsReady(bool newIsReady) {
 
 void IndexCatalogEntryImpl::setMultikey(OperationContext* opCtx,
                                         const MultikeyPaths& multikeyPaths) {
-    if (!_indexTracksPathLevelMultikeyInfo && isMultikey()) {
+    if (!_indexTracksPathLevelMultikeyInfo && _isMultikeyForWrite.load()) {
         // If the index is already set as multikey and we don't have any path-level information to
         // update, then there's nothing more for us to do.
         return;
@@ -335,30 +337,35 @@ void IndexCatalogEntryImpl::_catalogSetMultikey(OperationContext* opCtx,
                                                        _descriptor->indexName(),
                                                        multikeyPaths);
 
-    // The commit handler for a transaction that sets the multikey flag. When the recovery unit
-    // commits, update the multikey paths if needed and clear the plan cache if the index metadata
-    // has changed.
-    opCtx->recoveryUnit()->onCommit(
-        [this, multikeyPaths, indexMetadataHasChanged](boost::optional<Timestamp>) {
-            _isMultikey.store(true);
-
-            if (_indexTracksPathLevelMultikeyInfo) {
-                stdx::lock_guard<Latch> lk(_indexMultikeyPathsMutex);
-                for (size_t i = 0; i < multikeyPaths.size(); ++i) {
-                    _indexMultikeyPaths[i].insert(multikeyPaths[i].begin(), multikeyPaths[i].end());
-                }
-            }
-
-            if (indexMetadataHasChanged && _queryInfo) {
-                LOGV2_DEBUG(
-                    20351,
+    // In the absense of using the storage engine to read from the catalog, we must set multikey
+    // prior to the storage engine transaction committing.
+    //
+    // Moreover, there must not be an `onRollback` handler to reset this back to false. Given a long
+    // enough pause in processing `onRollback` handlers, a later writer that successfully flipped
+    // multikey can be undone. Alternatively, one could use a counter instead of a boolean to avoid
+    // that problem.
+    _isMultikeyForRead.store(true);
+    if (_indexTracksPathLevelMultikeyInfo) {
+        stdx::lock_guard<Latch> lk(_indexMultikeyPathsMutex);
+        for (size_t i = 0; i < multikeyPaths.size(); ++i) {
+            _indexMultikeyPaths[i].insert(multikeyPaths[i].begin(), multikeyPaths[i].end());
+        }
+    }
+    if (indexMetadataHasChanged && _queryInfo) {
+        LOGV2_DEBUG(47187005,
                     1,
-                    "{ns}: clearing plan cache - index {descriptor_keyPattern} set to multi key.",
-                    "ns"_attr = ns(),
-                    "descriptor_keyPattern"_attr = _descriptor->keyPattern());
-                _queryInfo->clearQueryCache();
-            }
-        });
+                    "Index set to multi key, clearing query plan cache",
+                    "namespace"_attr = ns(),
+                    "keyPattern"_attr = _descriptor->keyPattern());
+        _queryInfo->clearQueryCache();
+    }
+
+    opCtx->recoveryUnit()->onCommit([this](boost::optional<Timestamp>) {
+        // Writers must attempt to flip multikey until it's confirmed a storage engine
+        // transaction successfully commits. Only after this point may a writer optimize out
+        // flipping multikey.
+        _isMultikeyForWrite.store(true);
+    });
 }
 
 KVPrefix IndexCatalogEntryImpl::_catalogGetPrefix(OperationContext* opCtx) const {
diff --git a/src/mongo/db/catalog/index_catalog_entry_impl.h b/src/mongo/db/catalog/index_catalog_entry_impl.h
index 4f4691359aa..91d4762b826 100644
--- a/src/mongo/db/catalog/index_catalog_entry_impl.h
+++ b/src/mongo/db/catalog/index_catalog_entry_impl.h
@@ -240,9 +240,12 @@ private:
     // called.
     bool _indexTracksPathLevelMultikeyInfo = false;
 
-    // Set to true if this index is multikey. '_isMultikey' serves as a cache of the information
-    // stored in the NamespaceDetails or DurableCatalog.
-    AtomicWord<bool> _isMultikey;
+    // Set to true if this index may contain multikey data.
+    AtomicWord<bool> _isMultikeyForRead;
+
+    // Set to true after a transaction commit successfully updates multikey on the catalog data. At
+    // this point, future writers do not need to update the catalog.
+    AtomicWord<bool> _isMultikeyForWrite;
 
     // Controls concurrent access to '_indexMultikeyPaths'. We acquire this mutex rather than the
     // RESOURCE_METADATA lock as a performance optimization so that it is cheaper to detect whether
diff --git a/src/mongo/db/catalog/validate_adaptor.cpp b/src/mongo/db/catalog/validate_adaptor.cpp
index 4e0219d1fcb..1d51dc41770 100644
--- a/src/mongo/db/catalog/validate_adaptor.cpp
+++ b/src/mongo/db/catalog/validate_adaptor.cpp
@@ -43,6 +43,7 @@
 #include "mongo/db/index/index_descriptor.h"
 #include "mongo/db/index/wildcard_access_method.h"
 #include "mongo/db/matcher/expression.h"
+#include "mongo/db/multi_key_path_tracker.h"
 #include "mongo/db/operation_context.h"
 #include "mongo/db/storage/execution_context.h"
 #include "mongo/db/storage/key_string.h"
@@ -102,7 +103,7 @@ Status ValidateAdaptor::validateRecord(OperationContext* opCtx,
 
         auto documentKeySet = executionCtx.keys();
         auto multikeyMetadataKeys = executionCtx.multikeyMetadataKeys();
-        auto multikeyPaths = executionCtx.multikeyPaths();
+        auto documentMultikeyPaths = executionCtx.multikeyPaths();
 
         iam->getKeys(executionCtx.pooledBufferBuilder(),
                      recordBson,
@@ -110,7 +111,7 @@ Status ValidateAdaptor::validateRecord(OperationContext* opCtx,
                      IndexAccessMethod::GetKeysContext::kAddingKeys,
                      documentKeySet.get(),
                      multikeyMetadataKeys.get(),
-                     multikeyPaths.get(),
+                     documentMultikeyPaths.get(),
                      recordId,
                      IndexAccessMethod::kNoopOnSuppressedErrorFn);
 
@@ -118,7 +119,7 @@ Status ValidateAdaptor::validateRecord(OperationContext* opCtx,
             iam->shouldMarkIndexAsMultikey(
                 documentKeySet->size(),
                 {multikeyMetadataKeys->begin(), multikeyMetadataKeys->end()},
-                *multikeyPaths)) {
+                *documentMultikeyPaths)) {
             std::string msg = str::stream()
                 << "Index " << descriptor->indexName() << " is not multi-key but has more than one"
                 << " key in document " << recordId;
@@ -127,6 +128,18 @@ Status ValidateAdaptor::validateRecord(OperationContext* opCtx,
             curRecordResults.valid = false;
         }
 
+        if (descriptor->isMultikey()) {
+            const MultikeyPaths& indexPaths = descriptor->getMultikeyPaths(opCtx);
+            if (!MultikeyPathTracker::covers(indexPaths, *documentMultikeyPaths.get())) {
+                std::string msg = str::stream()
+                    << "Index " << descriptor->indexName()
+                    << " multi-key paths do not cover a document. RecordId: " << recordId;
+                ValidateResults& curRecordResults = (*_indexNsResultsMap)[descriptor->indexName()];
+                curRecordResults.errors.push_back(msg);
+                curRecordResults.valid = false;
+            }
+        }
+
         IndexInfo& indexInfo = _indexConsistency->getIndexInfo(descriptor->indexName());
         for (const auto& keyString : *multikeyMetadataKeys) {
             try {
diff --git a/src/mongo/db/multi_key_path_tracker.cpp b/src/mongo/db/multi_key_path_tracker.cpp
index 003a600e6bf..342e571ea0f 100644
--- a/src/mongo/db/multi_key_path_tracker.cpp
+++ b/src/mongo/db/multi_key_path_tracker.cpp
@@ -77,6 +77,19 @@ bool MultikeyPathTracker::isMultikeyPathsTrivial(const MultikeyPaths& paths) {
     return true;
 }
 
+bool MultikeyPathTracker::covers(const MultikeyPaths& parent, const MultikeyPaths& child) {
+    for (size_t idx = 0; idx < parent.size(); ++idx) {
+        auto& parentPath = parent[idx];
+        auto& childPath = child[idx];
+        for (auto&& item : childPath) {
+            if (parentPath.find(item) == parentPath.end()) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
 void MultikeyPathTracker::addMultikeyPathInfo(MultikeyPathInfo info) {
     invariant(_trackMultikeyPathInfo);
     // Merge the `MultikeyPathInfo` input into the accumulated value being tracked for the
diff --git a/src/mongo/db/multi_key_path_tracker.h b/src/mongo/db/multi_key_path_tracker.h
index b155bc1fe58..d6efe1e71db 100644
--- a/src/mongo/db/multi_key_path_tracker.h
+++ b/src/mongo/db/multi_key_path_tracker.h
@@ -69,6 +69,11 @@ public:
      */
     static bool isMultikeyPathsTrivial(const MultikeyPaths& paths);
 
+    /**
+     * Return true iff the child's paths are a subset of the parent.
+     */
+    static bool covers(const MultikeyPaths& parent, const MultikeyPaths& child);
+
     // Decoration requires a default constructor.
     MultikeyPathTracker() = default;
 
diff --git a/src/mongo/db/storage/SConscript b/src/mongo/db/storage/SConscript
index d7bc2666a27..b22c098c1dd 100644
--- a/src/mongo/db/storage/SConscript
+++ b/src/mongo/db/storage/SConscript
@@ -43,11 +43,14 @@ env.Library(
     target='recovery_unit_base',
     source=[
         'recovery_unit.cpp',
-        ],
+    ],
     LIBDEPS=[
         '$BUILD_DIR/mongo/base',
-        ],
-    )
+    ],
+    LIBDEPS_PRIVATE=[
+        '$BUILD_DIR/mongo/util/fail_point',
+    ],
+)
 
 env.Library(
     target='key_string',
diff --git a/src/mongo/db/storage/recovery_unit.cpp b/src/mongo/db/storage/recovery_unit.cpp
index 963efa781a6..38b3bcff8d4 100644
--- a/src/mongo/db/storage/recovery_unit.cpp
+++ b/src/mongo/db/storage/recovery_unit.cpp
@@ -33,7 +33,9 @@
 
 #include "mongo/db/storage/recovery_unit.h"
 #include "mongo/logv2/log.h"
+#include "mongo/util/fail_point.h"
 #include "mongo/util/scopeguard.h"
+#include "mongo/util/time_support.h"
 
 namespace mongo {
 namespace {
@@ -41,6 +43,7 @@ namespace {
 // determine if documents changed, but a different recovery unit may be used across a getMore,
 // so there is a chance the snapshot ID will be reused.
 AtomicWord<unsigned long long> nextSnapshotId{1};
+MONGO_FAIL_POINT_DEFINE(widenWUOWChangesWindow);
 }  // namespace
 
 RecoveryUnit::RecoveryUnit() {
@@ -71,6 +74,9 @@ void RecoveryUnit::commitRegisteredChanges(boost::optional<Timestamp> commitTime
     // Getting to this method implies `runPreCommitHooks` completed successfully, resulting in
     // having its contents cleared.
     invariant(_preCommitHooks.empty());
+    if (MONGO_unlikely(widenWUOWChangesWindow.shouldFail())) {
+        sleepmillis(1000);
+    }
     for (auto& change : _changes) {
         try {
             // Log at higher level because commits occur far more frequently than rollbacks.
@@ -88,6 +94,9 @@ void RecoveryUnit::commitRegisteredChanges(boost::optional<Timestamp> commitTime
 
 void RecoveryUnit::abortRegisteredChanges() {
     _preCommitHooks.clear();
+    if (MONGO_unlikely(widenWUOWChangesWindow.shouldFail())) {
+        sleepmillis(1000);
+    }
     try {
         for (Changes::const_reverse_iterator it = _changes.rbegin(), end = _changes.rend();
              it != end;