Major - P3 Let's consider a shard with three (3) range deletion tasks still pending: [0, 10), [10, 20), [30, 40). And let's consider an inbound chunk migration for the range [25, 35) which partially overlaps with the pending range deletion task [30, 40).
RangeDeleterService::getOverlappingRangeDeletionsFuture() uses std::set::lower_bound() to position an iterator at the smallest range deletion task with a ChunkRange::_minKey greater than or equal to the inbound chunk migration _minKey. In the context of the example, the iterator is initially positioned at the [30, 40) range deletion task. The function then shifts the iterator to the preceding smaller range deletion task. This is because while the preceding range deletion task has a ChunkRange::_minKey strictly less than the inbound chunk migration _minKey, the preceding range deletion task may have a ChunkRange::_maxKey greater than or equal to the inbound chunk migration _minKey and is therefore overlapping. Continuing the example, the iterator is re-positioned at the [10, 20) range deletion task.
The problem is RangeDeleterService::getOverlappingRangeDeletionsFuture() incorrectly assumes when the preceding smaller range deletion task isn't overlapping with the inbound chunk migration that no subsequent larger range deletion tasks can overlap with the inbound chunk migration either. However, despite the [10, 20) range deletion task not overlapping with the [25, 35) chunk migration range, the [30, 40) range deletion task does overlap with it. The following C++ test case demonstrates this bug.
TEST_F(RangeDeleterServiceTest, GetOverlappingRangeDeletionsWithNonContiguousTasks) {
auto rds = RangeDeleterService::get(opCtx);
// Register range deletion tasks [0, 10) - [10, 20) - [30, 40).
auto taskWithOngoingQueries0 = createRangeDeletionTaskWithOngoingQueries(
uuidCollA, BSON(kShardKey << 0), BSON(kShardKey << 10));
auto completionFuture0 =
registerAndCreatePersistentTask(opCtx,
taskWithOngoingQueries0->getTask(),
taskWithOngoingQueries0->getOngoingQueriesFuture());
auto taskWithOngoingQueries10 = createRangeDeletionTaskWithOngoingQueries(
uuidCollA, BSON(kShardKey << 10), BSON(kShardKey << 20));
auto completionFuture10 =
registerAndCreatePersistentTask(opCtx,
taskWithOngoingQueries10->getTask(),
taskWithOngoingQueries10->getOngoingQueriesFuture());
auto taskWithOngoingQueries30 = createRangeDeletionTaskWithOngoingQueries(
uuidCollA, BSON(kShardKey << 30), BSON(kShardKey << 40));
auto completionFuture30 =
registerAndCreatePersistentTask(opCtx,
taskWithOngoingQueries30->getTask(),
taskWithOngoingQueries30->getOngoingQueriesFuture());
// Range overlapping with [30, 40).
auto inputRange = ChunkRange(BSON(kShardKey << 25), BSON(kShardKey << 35));
auto futureReadyWhenTask30Ready =
rds->getOverlappingRangeDeletionsFuture(uuidCollA, inputRange);
ASSERT(!futureReadyWhenTask30Ready.isReady());
// Drain ongoing queries one task per time and check only expected futures get marked as ready.
taskWithOngoingQueries0->drainOngoingQueries();
ASSERT(!futureReadyWhenTask30Ready.isReady());
taskWithOngoingQueries10->drainOngoingQueries();
ASSERT(!futureReadyWhenTask30Ready.isReady());
taskWithOngoingQueries30->drainOngoingQueries();
ASSERT_OK(futureReadyWhenTask30Ready.getNoThrow(opCtx));
}