Reads of recent writes coming from memtable may temporarily miss some of the deletions under rare usage patterns #10913

tgrabiec · 2022-06-28T10:23:42Z

There is a bug introduced in e74c3c8 (4.6.0) which makes memtable reader skip one a range tombstone for a certain pattern of deletions and under certain sequence of events.

For the problem to trigger, there have to be multiple MVCC versions (at least 2) which contain deletions of the following form:

[a, c] @ t0
[a, b) @ t1, [b, d] @ t2

c > b

The proper sequence for such versions is (assuming d > c):

[a, b) @ t1,
[b, d] @ t2

Due to the bug, the reader will produce:

[a, b) @ t1,
[b, c] @ t0

The reader also needs to be preempted right before processing [b, d] @ t2 and iterators need to get invalidated so that lsa_partition_reader::do_refresh_state() is called and it skips over [b, d] @ t2. Otherwise, the reader will emit [b, d] @ t2 later. If it emits the proper range tombstone, it's possible that it will violate fragment order in the stream if _rt_stream accumulated remainders (possible with 3 MVCC versions).

The problem goes away once MVCC versions merge.

The text was updated successfully, but these errors were encountered:

…e conditions There is a bug introduced in e74c3c8 (4.6.0) which makes memtable reader skip one a range tombstone for a certain pattern of deletions and under certain sequence of events. For the problem to trigger, there have to be multiple MVCC versions (at least 2) which contain deletions of the following form: [a, c] @ t0 [a, b) @ t1, [b, d] @ t2 c > b The proper sequence for such versions is (assuming d > c): [a, b) @ t1, [b, d] @ t2 Due to the bug, the reader will produce: [a, b) @ t1, [b, c] @ t0 The reader also needs to be preempted right before processing [b, d] @ t2 and iterators need to get invalidated so that lsa_partition_reader::do_refresh_state() is called and it skips over [b, d] @ t2. Otherwise, the reader will emit [b, d] @ t2 later. If it does emit the proper range tombstone, it's possible that it will violate fragment order in the stream if _rt_stream accumulated remainders (possible with 3 MVCC versions). The problem goes away once MVCC versions merge. Fixes scylladb#10913

bhalevy · 2022-06-28T11:15:31Z

@tgrabiec how does this issue relate to #10830?

…e conditions There is a bug introduced in e74c3c8 (4.6.0) which makes memtable reader skip one a range tombstone for a certain pattern of deletions and under certain sequence of events. _rt_stream contains the result of deoverlapping range tombstones which had the same position, which were sipped from all the versions. The result of deoverlapping may produce a range tombstone which starts later, at the same position as a more recent tombstone which has not been sipped from the partition version yet. If we consume the old range tombstone from _rt_stream and then refresh the iterators, the refresh will skip over the newer tombstone. The fix is to drop the logic which drains _rt_stream so that _rt_stream is always merged with partition versions. For the problem to trigger, there have to be multiple MVCC versions (at least 2) which contain deletions of the following form: [a, c] @ t0 [a, b) @ t1, [b, d] @ t2 c > b The proper sequence for such versions is (assuming d > c): [a, b) @ t1, [b, d] @ t2 Due to the bug, the reader will produce: [a, b) @ t1, [b, c] @ t0 The reader also needs to be preempted right before processing [b, d] @ t2 and iterators need to get invalidated so that lsa_partition_reader::do_refresh_state() is called and it skips over [b, d] @ t2. Otherwise, the reader will emit [b, d] @ t2 later. If it does emit the proper range tombstone, it's possible that it will violate fragment order in the stream if _rt_stream accumulated remainders (possible with 3 MVCC versions). The problem goes away once MVCC versions merge. Fixes scylladb#10913 Fixes scylladb#10830

tgrabiec · 2022-06-28T16:58:11Z

In #10830 we observe a failure in test_reverse_reader_reads_in_native_reverse_order, which is about discrepancy between data returned by reversed reader and forward reader with reversed result (which should be the same). The reversed reader hits this bug, whereas the forward reader doesn't, and that's because in reverse the positions of range tombstones are aligned differently. The reverse reader is missing a range tombstone and the row has more live cells than it should.

…e conditions There is a bug introduced in e74c3c8 (4.6.0) which makes memtable reader skip one a range tombstone for a certain pattern of deletions and under certain sequence of events. _rt_stream contains the result of deoverlapping range tombstones which had the same position, which were sipped from all the versions. The result of deoverlapping may produce a range tombstone which starts later, at the same position as a more recent tombstone which has not been sipped from the partition version yet. If we consume the old range tombstone from _rt_stream and then refresh the iterators, the refresh will skip over the newer tombstone. The fix is to drop the logic which drains _rt_stream so that _rt_stream is always merged with partition versions. For the problem to trigger, there have to be multiple MVCC versions (at least 2) which contain deletions of the following form: [a, c] @ t0 [a, b) @ t1, [b, d] @ t2 c > b The proper sequence for such versions is (assuming d > c): [a, b) @ t1, [b, d] @ t2 Due to the bug, the reader will produce: [a, b) @ t1, [b, c] @ t0 The reader also needs to be preempted right before processing [b, d] @ t2 and iterators need to get invalidated so that lsa_partition_reader::do_refresh_state() is called and it skips over [b, d] @ t2. Otherwise, the reader will emit [b, d] @ t2 later. If it does emit the proper range tombstone, it's possible that it will violate fragment order in the stream if _rt_stream accumulated remainders (possible with 3 MVCC versions). The problem goes away once MVCC versions merge. Fixes #10913 Fixes #10830 Closes #10914 (cherry picked from commit a6aef60)

avikivity · 2022-07-19T16:17:16Z

Backported to 4.6, 5.0.

…e conditions There is a bug introduced in e74c3c8 (4.6.0) which makes memtable reader skip one a range tombstone for a certain pattern of deletions and under certain sequence of events. _rt_stream contains the result of deoverlapping range tombstones which had the same position, which were sipped from all the versions. The result of deoverlapping may produce a range tombstone which starts later, at the same position as a more recent tombstone which has not been sipped from the partition version yet. If we consume the old range tombstone from _rt_stream and then refresh the iterators, the refresh will skip over the newer tombstone. The fix is to drop the logic which drains _rt_stream so that _rt_stream is always merged with partition versions. For the problem to trigger, there have to be multiple MVCC versions (at least 2) which contain deletions of the following form: [a, c] @ t0 [a, b) @ t1, [b, d] @ t2 c > b The proper sequence for such versions is (assuming d > c): [a, b) @ t1, [b, d] @ t2 Due to the bug, the reader will produce: [a, b) @ t1, [b, c] @ t0 The reader also needs to be preempted right before processing [b, d] @ t2 and iterators need to get invalidated so that lsa_partition_reader::do_refresh_state() is called and it skips over [b, d] @ t2. Otherwise, the reader will emit [b, d] @ t2 later. If it does emit the proper range tombstone, it's possible that it will violate fragment order in the stream if _rt_stream accumulated remainders (possible with 3 MVCC versions). The problem goes away once MVCC versions merge. Fixes #10913 Fixes #10830 Closes #10914 (cherry picked from commit a6aef60) [avi: backport prerequisite position_range_to_clustering_range() too]

…e conditions There is a bug introduced in e74c3c8 (4.6.0) which makes memtable reader skip one a range tombstone for a certain pattern of deletions and under certain sequence of events. _rt_stream contains the result of deoverlapping range tombstones which had the same position, which were sipped from all the versions. The result of deoverlapping may produce a range tombstone which starts later, at the same position as a more recent tombstone which has not been sipped from the partition version yet. If we consume the old range tombstone from _rt_stream and then refresh the iterators, the refresh will skip over the newer tombstone. The fix is to drop the logic which drains _rt_stream so that _rt_stream is always merged with partition versions. For the problem to trigger, there have to be multiple MVCC versions (at least 2) which contain deletions of the following form: [a, c] @ t0 [a, b) @ t1, [b, d] @ t2 c > b The proper sequence for such versions is (assuming d > c): [a, b) @ t1, [b, d] @ t2 Due to the bug, the reader will produce: [a, b) @ t1, [b, c] @ t0 The reader also needs to be preempted right before processing [b, d] @ t2 and iterators need to get invalidated so that lsa_partition_reader::do_refresh_state() is called and it skips over [b, d] @ t2. Otherwise, the reader will emit [b, d] @ t2 later. If it does emit the proper range tombstone, it's possible that it will violate fragment order in the stream if _rt_stream accumulated remainders (possible with 3 MVCC versions). The problem goes away once MVCC versions merge. Fixes #10913 Fixes #10830 Closes #10914 (cherry picked from commit a6aef60)

tgrabiec added the type/bug label Jun 28, 2022

tgrabiec mentioned this issue Jun 28, 2022

memtable: Fix missing range tombstones during reads under certain rare conditions #10914

Closed

scylladb-promoter closed this as completed in a6aef60 Jun 30, 2022

scylladb-promoter added the Backport candidate label Jun 30, 2022

avikivity removed the Backport candidate label Jul 19, 2022

avikivity mentioned this issue Jul 19, 2022

Regression in test_reverse_reader_reads_in_native_reverse_order #10830

Closed

scylladb-promoter added the Backport candidate label Jul 21, 2022

DoronArazii added this to the 5.1 milestone Nov 8, 2022

avikivity removed the Backport candidate label Feb 22, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Reads of recent writes coming from memtable may temporarily miss some of the deletions under rare usage patterns #10913

Reads of recent writes coming from memtable may temporarily miss some of the deletions under rare usage patterns #10913

tgrabiec commented Jun 28, 2022

bhalevy commented Jun 28, 2022

tgrabiec commented Jun 28, 2022

avikivity commented Jul 19, 2022

Reads of recent writes coming from memtable may temporarily miss some of the deletions under rare usage patterns #10913

Reads of recent writes coming from memtable may temporarily miss some of the deletions under rare usage patterns #10913

Comments

tgrabiec commented Jun 28, 2022

bhalevy commented Jun 28, 2022

tgrabiec commented Jun 28, 2022

avikivity commented Jul 19, 2022