YT-23172: Fix max progress calculation in case of non-overlapping progresses

commit_hash:4700e0a0d3dcac740c21a2d3303b6568d4c680a9

2 files changed, 37 insertions, 13 deletions

diff --git a/yt/yt/client/chaos_client/replication_card.cpp b/yt/yt/client/chaos_client/replication_card.cpp
index 78b2be376ca..9aa1561afe9 100644
--- a/yt/yt/client/chaos_client/replication_card.cpp
+++ b/yt/yt/client/chaos_client/replication_card.cpp
@@ -743,19 +743,31 @@ TReplicationProgress BuildMaxProgress(
 
         if (otherIt == otherEnd) {
             cmpResult = -1;
-            if (!upperKeySelected && CompareRows(progressIt->LowerKey, other.UpperKey) >= 0) {
-                upperKeySelected = true;
-                otherTimestamp = NullTimestamp;
-                tryAppendSegment(other.UpperKey, progressTimestamp);
-                continue;
+            if (!upperKeySelected) {
+                int upperKeyCmpResult = CompareRows(progressIt->LowerKey, other.UpperKey);
+                if (upperKeyCmpResult >= 0) {
+                    upperKeySelected = true;
+                    otherTimestamp = NullTimestamp;
+                    if (upperKeyCmpResult > 0) {
+                        // UpperKey is smaller than progressIt->LowerKey so there's a gap to fill with progressTimestamp.
+                        tryAppendSegment(other.UpperKey, progressTimestamp);
+                        continue;
+                    }
+                }
             }
         } else if (progressIt == progressEnd) {
             cmpResult = 1;
-            if (!upperKeySelected && CompareRows(otherIt->LowerKey, progress.UpperKey) >= 0) {
-                upperKeySelected = true;
-                progressTimestamp = NullTimestamp;
-                tryAppendSegment(progress.UpperKey, otherTimestamp);
-                continue;
+            if (!upperKeySelected) {
+                int upperKeyCmpResult = CompareRows(otherIt->LowerKey, progress.UpperKey);
+                if (upperKeyCmpResult >= 0) {
+                    upperKeySelected = true;
+                    progressTimestamp = NullTimestamp;
+                    if (upperKeyCmpResult > 0) {
+                        // UpperKey is smaller than otherIt->LowerKey so there's a gap to fill with otherTimestamp.
+                        tryAppendSegment(progress.UpperKey, otherTimestamp);
+                        continue;
+                    }
+                }
             }
         } else {
             cmpResult = CompareRows(progressIt->LowerKey, otherIt->LowerKey);
@@ -902,4 +914,3 @@ THashMap<TReplicaId, TDuration> ComputeReplicasLag(const THashMap<TReplicaId, TR
 ////////////////////////////////////////////////////////////////////////////////
 
 } // namespace NYT::NChaosClient
-
diff --git a/yt/yt/client/unittests/replication_progress_ut.cpp b/yt/yt/client/unittests/replication_progress_ut.cpp
index 5ef0cf52652..41746f544ce 100644
--- a/yt/yt/client/unittests/replication_progress_ut.cpp
+++ b/yt/yt/client/unittests/replication_progress_ut.cpp
@@ -735,8 +735,21 @@ INSTANTIATE_TEST_SUITE_P(
             "{segments=[{lower_key=[1];timestamp=1073741824};{lower_key=[2];timestamp=3221225472}];"
                 "upper_key=[<type=max>#]}",
             "{segments=[{lower_key=[];timestamp=1073741824};{lower_key=[2];timestamp=3221225472}];"
-                "upper_key=[<type=max>#]}")
-
+                "upper_key=[<type=max>#]}"),
+        std::tuple(
+            "{segments=[{lower_key=[2];timestamp=1}];upper_key=[<type=max>#]}",
+            "{segments=[{lower_key=[1];timestamp=1}];upper_key=[2]}",
+            "{segments=[{lower_key=[1];timestamp=1}];upper_key=[<type=max>#]}"),
+        std::tuple(
+            "{segments=[{lower_key=[3];timestamp=1}];upper_key=[<type=max>#]}",
+            "{segments=[{lower_key=[1];timestamp=1}];upper_key=[2]}",
+            "{segments=[{lower_key=[1];timestamp=1};{lower_key=[2];timestamp=0};{lower_key=[3];timestamp=1}];"
+                "upper_key=[<type=max>#]}"),
+        std::tuple(
+            "{segments=[{lower_key=[1];timestamp=1};{lower_key=[2];timestamp=0};{lower_key=[3];timestamp=1}];"
+                "upper_key=[<type=max>#]}",
+            "{segments=[{lower_key=[2];timestamp=1}];upper_key=[3]}",
+            "{segments=[{lower_key=[1];timestamp=1}];upper_key=[<type=max>#]}")
 ));
 
 ////////////////////////////////////////////////////////////////////////////////