gistfile1.txt

diff --git a/src/kudu/consensus/consensus.proto b/src/kudu/consensus/consensus.proto
index 5eeecdd..69b5377 100644
--- a/src/kudu/consensus/consensus.proto
+++ b/src/kudu/consensus/consensus.proto
@@ -227,8 +227,10 @@ message CommitMsg {
 
 // NO_OP requests are replicated by a peer after being elected leader.
 message NoOpRequestPB {
- // Allows to set a dummy payload, for tests.
- optional bytes payload_for_tests = 1;
+  // Allows to set a dummy payload, for tests.
+  optional bytes payload_for_tests = 1;
+
+  optional bool timestamp_in_opid_order = 2;
 }
 
 // Status message received in the peer responses.
diff --git a/src/kudu/tablet/tablet_bootstrap.cc b/src/kudu/tablet/tablet_bootstrap.cc
index 58f9f54..4e5730d 100644
--- a/src/kudu/tablet/tablet_bootstrap.cc
+++ b/src/kudu/tablet/tablet_bootstrap.cc
@@ -1068,10 +1068,29 @@ Status TabletBootstrap::HandleEntryPair(LogEntryPB* replicate_entry, LogEntryPB*
 
 #undef RETURN_NOT_OK_REPLAY
 
-  // Non-tablet operations should not advance the safe time, because they are
-  // not started serially and so may have timestamps that are out of order.
-  if (op_type == NO_OP || op_type == CHANGE_CONFIG_OP) {
-    return Status::OK();
+  bool timestamp_assignment_order;
+  switch (op_type) {
+    case CHANGE_CONFIG_OP:
+      timestamp_assignment_in_order = false;
+      break;
+    case NO_OP: {
+      const auto& req = replicate.noop_request();
+      if (!req.has_timestamp_in_opid_order()) {
+        // In prior versions, not set, but only NO_OPs were generated on leadership
+        // changes, so they were in-order.
+        timestamp_assignment_in_order = true;
+      } else {
+        timestamp_assignment_in_order = req.timestamp_in_opid_order();
+      break;
+    }
+    default:
+      // All other op types are assigned in opid order.
+      timestamp_assignment_in_order = true;
+      break;
+  }
+  if (!timestamp_assignment_in_order) {
+    // Don't advance the safe time.
+    return;
   }
 
   // Handle safe time advancement: