[CASSANDRA-16435] Reverse iteration with paging may throw if the page boundary coincides with open tombstone boundary

• Type: Bug
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 4.0-rc1, 4.0
• Component/s: Consistency/Coordination
• Bug Category: Availability - Response Crash
• Severity: Critical
• Complexity: Normal
• Discovered By: Fuzz Test
• Platform: All
• Since Version: 4.0-alpha1

Source Control Link

https://github.com/apache/cassandra/commit/6f13c864a02b32daa7696eca27431f5385a306df

Test and Documentation Plan

Tests included; extensive testing with Harry has been completed

• Assignee: Alex Petrov
• Reporter: Alex Petrov

Authors

Alex Petrov

Reviewers

Aleksey Yeschenko, Marcus Eriksson

• Created: 09/Feb/21 16:36
• Updated: 16/Mar/22 15:26
• Resolved: 09/Mar/21 13:55

Description

If sstable contains a tombstone that has an open bound which coincides with current page bound, we’ll generate an impossible empty slice range. 
 
Minimal repro:
 

        try (Cluster cluster = init(builder().withNodes(3).start()))
        {
            cluster.schemaChange("CREATE TABLE " + KEYSPACE + ".tbl (pk int, ck int, regular int, PRIMARY KEY (pk, ck))");
            cluster.coordinator(1).execute("DELETE FROM " + KEYSPACE + ".tbl WHERE pk = 1 AND ck > 1 AND ck < 10", ConsistencyLevel.ALL);
            cluster.coordinator(1).execute("insert into " + KEYSPACE + ".tbl (pk, ck, regular) values (1,1,1)", ConsistencyLevel.ALL);
            cluster.coordinator(1).execute("insert into " + KEYSPACE + ".tbl (pk, ck, regular) values (1,2,2)", ConsistencyLevel.ALL);
            cluster.coordinator(1).execute("insert into " + KEYSPACE + ".tbl (pk, ck, regular) values (1,3,3)", ConsistencyLevel.ALL);
            cluster.stream().forEach(n -> {
                n.nodetool("flush");
            });
            Iterator<Object[]> iter = cluster.coordinator(1).executeWithPaging("SELECT pk,ck,regular FROM " + KEYSPACE + ".tbl " +
                                                                               "WHERE pk=? AND ck>=? ORDER BY ck DESC;",
                                                                               ConsistencyLevel.QUORUM, 1,
                                                                               1,1);
            while (iter.hasNext())
            {
                System.out.println(Arrays.toString(iter.next()));
            }
        }
 

Stack trace: 
 

Caused by: java.lang.IllegalArgumentException: [1, 1)
at com.google.common.base.Preconditions.checkArgument(Preconditions.java:141)
at org.apache.cassandra.db.Slices.with(Slices.java:66)
at org.apache.cassandra.db.columniterator.SSTableReversedIterator$ReverseReader.setIterator(SSTableReversedIterator.java:140)
at org.apache.cassandra.db.columniterator.SSTableReversedIterator$ReverseReader.setForSlice(SSTableReversedIterator.java:134)
at org.apache.cassandra.db.columniterator.AbstractSSTableIterator.<init>(AbstractSSTableIterator.java:118)
at org.apache.cassandra.db.columniterator.SSTableReversedIterator.<init>(SSTableReversedIterator.java:52)
at org.apache.cassandra.io.sstable.format.big.BigTableReader.iterator(BigTableReader.java:75)
at org.apache.cassandra.io.sstable.format.big.BigTableReader.iterator(BigTableReader.java:67)
at org.apache.cassandra.db.rows.UnfilteredRowIteratorWithLowerBound.initializeIterator(UnfilteredRowIteratorWithLowerBound.java:100)
at org.apache.cassandra.db.rows.LazilyInitializedUnfilteredRowIterator.maybeInit(LazilyInitializedUnfilteredRowIterator.java:48)
at org.apache.cassandra.db.rows.LazilyInitializedUnfilteredRowIterator.partitionLevelDeletion(LazilyInitializedUnfilteredRowIterator.java:81)
at org.apache.cassandra.db.rows.UnfilteredRowIteratorWithLowerBound.partitionLevelDeletion(UnfilteredRowIteratorWithLowerBound.java:161)
at org.apache.cassandra.db.SinglePartitionReadCommand.queryMemtableAndDiskInternal(SinglePartitionReadCommand.java:672)
at org.apache.cassandra.db.SinglePartitionReadCommand.queryMemtableAndDisk(SinglePartitionReadCommand.java:566)
at org.apache.cassandra.db.SinglePartitionReadCommand.queryStorage(SinglePartitionReadCommand.java:400)
at org.apache.cassandra.db.ReadCommand.executeLocally(ReadCommand.java:460)
at org.apache.cassandra.service.StorageProxy$LocalReadRunnable.runMayThrow(StorageProxy.java:2011)
at org.apache.cassandra.service.StorageProxy$DroppableRunnable.run(StorageProxy.java:2725)
... 5 common frames omitted