[
https://issues.apache.org/jira/browse/CASSANDRA-21781?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Michael Semb Wever updated CASSANDRA-21781:
-------------------------------------------
Description:
A filtered read limited to one partition can return a row that a range
tombstone deletes. It needs:
* replicas that diverge: one replica holds a range tombstone, another holds an
older row inside that range;
* a newer live row inside the range, on the replica that holds the tombstone;
* a single-partition read with a {{LIMIT}} or a page size, and a row filter
({{{}ALLOW FILTERING{}}} or SAI), at a consistency level that uses replica
filtering protection.
The read returns the deleted row when a page boundary of replica filtering
protection falls inside the range tombstone. Unpaged reads without a {{LIMIT}}
are not affected, and nor are reads spanning several partitions.
h3. Reproduction
Two nodes, RF 2, read repair off. Each write goes to one replica only.
{code:java}
CREATE TABLE ks.t (k int, c int, v int, PRIMARY KEY (k, c)) WITH read_repair =
'NONE';
-- node 2
INSERT INTO ks.t (k, c, v) VALUES (0, 0, 1) USING TIMESTAMP 1;
INSERT INTO ks.t (k, c, v) VALUES (0, 5, 1) USING TIMESTAMP 1;
-- node 1
INSERT INTO ks.t (k, c, v) VALUES (0, 0, 0) USING TIMESTAMP 2;
DELETE FROM ks.t USING TIMESTAMP 2 WHERE k = 0 AND c > 0 AND c <= 10;
INSERT INTO ks.t (k, c, v) VALUES (0, 1, 1) USING TIMESTAMP 3;
INSERT INTO ks.t (k, c, v) VALUES (0, 7, 1) USING TIMESTAMP 3;
-- either coordinator, CONSISTENCY ALL
SELECT c FROM ks.t WHERE k = 0 AND v = 1 LIMIT 2 ALLOW FILTERING;
{code}
Expected {{{}1, 7{}}}. Actual {{{}1, 5{}}}: row {{c = 5}} is deleted by the
range tombstone at timestamp 2.
h3. Cause
CASSANDRA-20639 made replica filtering protection consume a limited
single-partition read in pages of {{LIMIT}} rows, to avoid needless short read
protection reads. After each page, {{populate()}} queues each replica's
{{PartitionBuilder}} again, and the page's protected partition drains the
builder's {{contents}} queue.
When a page ends inside a range tombstone, the open marker leaves with that
batch. The next page for that replica holds only the close marker, so a stale
row from another replica inside the range is no longer shadowed when the
replicas' protected partitions merge.
In the reproduction, the first page is {{c = 0, 1}} and ends inside the
tombstone opened after {{{}c = 0{}}}. Protection then drops {{{}c = 0{}}}, as
node 1 holds {{{}v = 0{}}}, so the coordinator needs a second page. That page,
{{{}c = 5, 7{}}}, has no open marker for node 1, and node 2's {{c = 5}} is
returned.
h3. Fix
Track, per replica, whether a range tombstone is open in the merge listener.
Keep consuming rows past {{LIMIT}} until every open tombstone has closed, so no
page boundary falls inside one.
{code:java}
while ((i < command.limits().count() || mergeListener.hasOpenMarker()) &&
currentRowIterator.hasNext())
{code}
A tombstone spanning many rows makes its page that large. Before
CASSANDRA-20639 every limited read consumed whole partitions, so this is no
worse than the earlier behaviour, and the cached-rows thresholds still apply.
An alternative keeps pages bounded: close the open marker at the end of a page
and reopen it at the start of the next, using boundary bounds at the last
consumed clustering. That needs a per-page snapshot of the builder contents,
since the pages share one queue; it is more code for a case that is uncommon.
The patch applies to {{cassandra-6.0}} and {{trunk}} with line offsets only.
h3. How it was found
Harry fuzz testing for CASSANDRA-11745 (paging by bytes) on 6.0 found filtered
single-partition reads returning deleted rows. Byte paging hit it more often
than row paging, since its pages end at different rows. (The same seed on
cassandra-6.0 before CASSANDRA-11745 returned the deleted row with one-row
pages.)
was:
A filtered read limited to one partition can return a row that a range
tombstone deletes. It needs:
* replicas that diverge: one replica holds a range tombstone, another holds an
older row inside that range;
* a newer live row inside the range, on the replica that holds the tombstone;
* a single-partition read with a {{LIMIT}} or a page size, and a row filter
({{{}ALLOW FILTERING{}}} or SAI), at a consistency level that uses replica
filtering protection.
The read returns the deleted row when a batch boundary of replica filtering
protection falls inside the range tombstone. Unpaged reads without a {{LIMIT}}
are not affected, and nor are reads spanning several partitions.
h3. Reproduction
Two nodes, RF 2, read repair off. Each write goes to one replica only.
{code:java}
CREATE TABLE ks.t (k int, c int, v int, PRIMARY KEY (k, c)) WITH read_repair =
'NONE';
-- node 2
INSERT INTO ks.t (k, c, v) VALUES (0, 0, 1) USING TIMESTAMP 1;
INSERT INTO ks.t (k, c, v) VALUES (0, 5, 1) USING TIMESTAMP 1;
-- node 1
INSERT INTO ks.t (k, c, v) VALUES (0, 0, 0) USING TIMESTAMP 2;
DELETE FROM ks.t USING TIMESTAMP 2 WHERE k = 0 AND c > 0 AND c <= 10;
INSERT INTO ks.t (k, c, v) VALUES (0, 1, 1) USING TIMESTAMP 3;
INSERT INTO ks.t (k, c, v) VALUES (0, 7, 1) USING TIMESTAMP 3;
-- either coordinator, CONSISTENCY ALL
SELECT c FROM ks.t WHERE k = 0 AND v = 1 LIMIT 2 ALLOW FILTERING;
{code}
Expected {{{}1, 7{}}}. Actual {{{}1, 5{}}}: row {{c = 5}} is deleted by the
range tombstone at timestamp 2.
h3. Cause
CASSANDRA-20639 made replica filtering protection consume a limited
single-partition read in batches of {{LIMIT}} rows, to avoid needless short
read protection reads. After each batch, {{populate()}} queues each replica's
{{PartitionBuilder}} again, and the batch's protected partition drains the
builder's {{contents}} queue.
When a batch ends inside a range tombstone, the open marker leaves with that
batch. The next batch for that replica holds only the close marker, so a stale
row from another replica inside the range is no longer shadowed when the
replicas' protected partitions merge.
In the reproduction, the first batch is {{c = 0, 1}} and ends inside the
tombstone opened after {{{}c = 0{}}}. Protection then drops {{{}c = 0{}}}, as
node 1 holds {{{}v = 0{}}}, so the coordinator needs a second batch. That
batch, {{{}c = 5, 7{}}}, has no open marker for node 1, and node 2's {{c = 5}}
is returned.
h3. Fix
Track, per replica, whether a range tombstone is open in the merge listener.
Keep consuming rows past {{LIMIT}} until every open tombstone has closed, so no
batch boundary falls inside one.
{code:java}
while ((i < command.limits().count() || mergeListener.hasOpenMarker()) &&
currentRowIterator.hasNext())
{code}
A tombstone spanning many rows makes its batch that large. Before
CASSANDRA-20639 every limited read consumed whole partitions, so this is no
worse than the earlier behaviour, and the cached-rows thresholds still apply.
An alternative keeps batches bounded: close the open marker at the end of a
batch and reopen it at the start of the next, using boundary bounds at the last
consumed clustering. That needs a per-batch snapshot of the builder contents,
since the batches share one queue; it is more code for a case that is uncommon.
The patch applies to {{cassandra-6.0}} and {{trunk}} with line offsets only.
h3. How it was found
Harry fuzz testing for CASSANDRA-11745 (paging by bytes) on 6.0 found filtered
single-partition reads returning deleted rows. Byte paging hit it more often
than row paging, since its pages end at different rows. (The same seed on
cassandra-6.0 before CASSANDRA-11745 returned the deleted row with one-row
pages.)
> Replica filtering protection resurrects rows deleted by a range tombstone
> that spans a batch boundary
> -----------------------------------------------------------------------------------------------------
>
> Key: CASSANDRA-21781
> URL: https://issues.apache.org/jira/browse/CASSANDRA-21781
> Project: Apache Cassandra
> Issue Type: Bug
> Components: Consistency/Coordination
> Reporter: Michael Semb Wever
> Assignee: Michael Semb Wever
> Priority: Normal
> Fix For: 5.0.x, 6.0.x, 7.x
>
>
> A filtered read limited to one partition can return a row that a range
> tombstone deletes. It needs:
> * replicas that diverge: one replica holds a range tombstone, another holds
> an older row inside that range;
> * a newer live row inside the range, on the replica that holds the tombstone;
> * a single-partition read with a {{LIMIT}} or a page size, and a row filter
> ({{{}ALLOW FILTERING{}}} or SAI), at a consistency level that uses replica
> filtering protection.
> The read returns the deleted row when a page boundary of replica filtering
> protection falls inside the range tombstone. Unpaged reads without a
> {{LIMIT}} are not affected, and nor are reads spanning several partitions.
> h3. Reproduction
> Two nodes, RF 2, read repair off. Each write goes to one replica only.
> {code:java}
> CREATE TABLE ks.t (k int, c int, v int, PRIMARY KEY (k, c)) WITH read_repair
> = 'NONE';
> -- node 2
> INSERT INTO ks.t (k, c, v) VALUES (0, 0, 1) USING TIMESTAMP 1;
> INSERT INTO ks.t (k, c, v) VALUES (0, 5, 1) USING TIMESTAMP 1;
> -- node 1
> INSERT INTO ks.t (k, c, v) VALUES (0, 0, 0) USING TIMESTAMP 2;
> DELETE FROM ks.t USING TIMESTAMP 2 WHERE k = 0 AND c > 0 AND c <= 10;
> INSERT INTO ks.t (k, c, v) VALUES (0, 1, 1) USING TIMESTAMP 3;
> INSERT INTO ks.t (k, c, v) VALUES (0, 7, 1) USING TIMESTAMP 3;
> -- either coordinator, CONSISTENCY ALL
> SELECT c FROM ks.t WHERE k = 0 AND v = 1 LIMIT 2 ALLOW FILTERING;
> {code}
> Expected {{{}1, 7{}}}. Actual {{{}1, 5{}}}: row {{c = 5}} is deleted by the
> range tombstone at timestamp 2.
> h3. Cause
> CASSANDRA-20639 made replica filtering protection consume a limited
> single-partition read in pages of {{LIMIT}} rows, to avoid needless short
> read protection reads. After each page, {{populate()}} queues each replica's
> {{PartitionBuilder}} again, and the page's protected partition drains the
> builder's {{contents}} queue.
> When a page ends inside a range tombstone, the open marker leaves with that
> batch. The next page for that replica holds only the close marker, so a
> stale row from another replica inside the range is no longer shadowed when
> the replicas' protected partitions merge.
> In the reproduction, the first page is {{c = 0, 1}} and ends inside the
> tombstone opened after {{{}c = 0{}}}. Protection then drops {{{}c = 0{}}},
> as node 1 holds {{{}v = 0{}}}, so the coordinator needs a second page. That
> page, {{{}c = 5, 7{}}}, has no open marker for node 1, and node 2's {{c = 5}}
> is returned.
> h3. Fix
> Track, per replica, whether a range tombstone is open in the merge listener.
> Keep consuming rows past {{LIMIT}} until every open tombstone has closed, so
> no page boundary falls inside one.
> {code:java}
> while ((i < command.limits().count() || mergeListener.hasOpenMarker()) &&
> currentRowIterator.hasNext())
> {code}
> A tombstone spanning many rows makes its page that large. Before
> CASSANDRA-20639 every limited read consumed whole partitions, so this is no
> worse than the earlier behaviour, and the cached-rows thresholds still apply.
> An alternative keeps pages bounded: close the open marker at the end of a
> page and reopen it at the start of the next, using boundary bounds at the
> last consumed clustering. That needs a per-page snapshot of the builder
> contents, since the pages share one queue; it is more code for a case that is
> uncommon.
> The patch applies to {{cassandra-6.0}} and {{trunk}} with line offsets only.
> h3. How it was found
> Harry fuzz testing for CASSANDRA-11745 (paging by bytes) on 6.0 found
> filtered single-partition reads returning deleted rows. Byte paging hit it
> more often than row paging, since its pages end at different rows. (The same
> seed on cassandra-6.0 before CASSANDRA-11745 returned the deleted row with
> one-row pages.)
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
