SERVER-73481 Ensure validate detects out-of-order keys with {full: false}

(cherry picked from commit 288fee69456c966751a49870eefead1b7fa6ae76)

3 files changed, 47 insertions, 9 deletions

diff --git a/jstests/noPassthrough/validate_out_of_order.js b/jstests/noPassthrough/validate_out_of_order.js
new file mode 100644
index 00000000000..27142a71c5f
--- /dev/null
+++ b/jstests/noPassthrough/validate_out_of_order.js
@@ -0,0 +1,37 @@
+/**
+ * Tests that out-of-order keys are detected by validation during both the collection and index scan
+ * phases.
+ */
+(function() {
+"use strict";
+
+const rst = new ReplSetTest({nodes: 1});
+rst.startSet();
+rst.initiate();
+
+let primary = rst.getPrimary();
+let coll = primary.getCollection('test.out_of_order');
+assert.commandWorked(coll.createIndex({x: 1}));
+
+for (let i = 0; i < 5; i++) {
+    assert.commandWorked(coll.insert({x: i}));
+}
+
+// Test record store out-of-order detection.
+assert.commandWorked(
+    primary.adminCommand({configureFailPoint: "WTRecordStoreUassertOutOfOrder", mode: "alwaysOn"}));
+let res = assert.commandWorked(coll.validate());
+assert(!res.valid);
+assert.commandWorked(
+    primary.adminCommand({configureFailPoint: "WTRecordStoreUassertOutOfOrder", mode: "off"}));
+
+// Test index entry out-of-order detection.
+assert.commandWorked(
+    primary.adminCommand({configureFailPoint: "failIndexKeyOrdering", mode: "alwaysOn"}));
+res = assert.commandWorked(coll.validate());
+assert(!res.valid);
+assert.commandWorked(
+    primary.adminCommand({configureFailPoint: "failIndexKeyOrdering", mode: "off"}));
+
+rst.stopSet();
+})();
diff --git a/src/mongo/db/catalog/validate_adaptor.cpp b/src/mongo/db/catalog/validate_adaptor.cpp
index b6cf1a5fa9c..f83aa7512ba 100644
--- a/src/mongo/db/catalog/validate_adaptor.cpp
+++ b/src/mongo/db/catalog/validate_adaptor.cpp
@@ -63,6 +63,7 @@ namespace mongo {
 namespace {
 
 MONGO_FAIL_POINT_DEFINE(crashOnMultikeyValidateFailure);
+MONGO_FAIL_POINT_DEFINE(failIndexKeyOrdering);
 
 // Set limit for size of corrupted records that will be reported.
 const long long kMaxErrorSizeBytes = 1 * 1024 * 1024;
@@ -288,7 +289,7 @@ void _validateKeyOrder(OperationContext* opCtx,
 
     // KeyStrings will be in strictly increasing order because all keys are sorted and they are in
     // the format (Key, RID), and all RecordIDs are unique.
-    if (currKey.compare(prevKey) <= 0) {
+    if (currKey.compare(prevKey) <= 0 || MONGO_unlikely(failIndexKeyOrdering.shouldFail())) {
         if (results && results->valid) {
             results->errors.push_back(str::stream()
                                       << "index '" << descriptor->indexName()
@@ -570,11 +571,6 @@ void ValidateAdaptor::traverseRecordStore(OperationContext* opCtx,
         size_t validatedSize = 0;
         Status status = validateRecord(opCtx, record->id, record->data, &validatedSize, results);
 
-        // RecordStores are required to return records in RecordId order.
-        if (prevRecordId.isValid()) {
-            invariant(prevRecordId < record->id);
-        }
-
         // validatedSize = dataSize is not a general requirement as some storage engines may use
         // padding, but we still require that they return the unpadded record data.
         if (!status.isOK() || validatedSize != static_cast<size_t>(dataSize)) {
diff --git a/src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp b/src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp
index 6c6d7ad19f7..0ce8fa2eb47 100644
--- a/src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp
+++ b/src/mongo/db/storage/wiredtiger/wiredtiger_record_store.cpp
@@ -134,6 +134,7 @@ std::size_t computeRecordIdSize(const RecordId& id) {
 }  // namespace
 
 MONGO_FAIL_POINT_DEFINE(WTCompactRecordStoreEBUSY);
+MONGO_FAIL_POINT_DEFINE(WTRecordStoreUassertOutOfOrder);
 MONGO_FAIL_POINT_DEFINE(WTWriteConflictException);
 MONGO_FAIL_POINT_DEFINE(WTWriteConflictExceptionForReads);
 MONGO_FAIL_POINT_DEFINE(slowOplogSamplingReads);
@@ -2208,9 +2209,13 @@ boost::optional<Record> WiredTigerRecordStoreCursorBase::next() {
         return {};
     }
 
-    if (_forward && _lastReturnedId >= id) {
-        // Crash when testing diagnostics are enabled.
-        invariant(!TestingProctor::instance().isEnabled(), "next was not greater than last");
+    if ((_forward && _lastReturnedId >= id) ||
+        MONGO_unlikely(WTRecordStoreUassertOutOfOrder.shouldFail())) {
+        if (!WTRecordStoreUassertOutOfOrder.shouldFail()) {
+            // Crash when testing diagnostics are enabled and not explicitly uasserting on
+            // out-of-order keys.
+            invariant(!TestingProctor::instance().isEnabled(), "cursor returned out-of-order keys");
+        }
 
         // uassert with 'DataCorruptionDetected' after logging.
         LOGV2_ERROR_OPTIONS(22406,