[CASSANDRA-14894] RangeTombstoneList doesn't properly clean up mergeable or superseded rts in some cases

• Type: Bug
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 3.0.18, 3.11.4, 4.0-alpha1, 4.0
• Component/s: Local/SSTable
• Bug Category: Degradation - Performance Bug/Regression
• Severity: Normal
• Complexity: Challenging
• Discovered By: Fuzz Test
• Since Version: 3.0.0
• Assignee: Blake Eggleston
• Reporter: Blake Eggleston

Authors

Blake Eggleston

Reviewers

Sam Tunnicliffe

• Created: 15/Nov/18 20:09
• Updated: 15/May/20 08:03
• Resolved: 28/Nov/18 17:33

Description

There are a few scenarios RangeTombstoneList doesn't handle correctly.

If there are 2 overlapping range tombstones with identical timestamps, they should be merged. Instead, they're stored as 2 rts with congruent bounds and identical timestamps.

If a range tombstone supersedes multiple sequential range tombstones, instead of removing them, they cause the superseding rt to be split into multiple rts with congruent bounds and identical timestamps.

When converted to an UnfilteredRowIterator, these become extra boundary markers with the same timestamp on each side. Logically these are noops, but they do cause digest mismatches which will cause unneeded read repairs, and repair overstreaming (since they're also included in flushed sstables).

Also, not sure if this is reachable in practice, but querying RTL with an empty slice that covers a range tombstone causes an rt to be returned with an empty slice. If reachable this might cause extra read repairs as well.