[
https://issues.apache.org/jira/browse/CASSANDRA-18798?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17769480#comment-17769480
]
Jaroslaw Kijanowski commented on CASSANDRA-18798:
-------------------------------------------------
Hey [~henrik.ingo]
I've run the list-append Elle test with sstabledump
The Elle transaction checker found an incompatible order for the register "5".
{code:java}
{:type :ok, :process 10, :value [[:r 3 []] [:r 5 []]], :tid 8, :n 1, :time
1695795515655894713}
{:type :ok, :process 1, :value [[:r 3 []] [:append 5 1501]], :tid 3, :n 1,
:time 1695795515678515373}
{:type :ok, :process 7, :value [[:r 1 [3002]] [:r 5 [1501]]], :tid 0, :n 1,
:time 1695795515722077204}
{:type :ok, :process 4, :value [[:append 5 3501]], :tid 7, :n 1, :time
1695795515732133433}
{:type :ok, :process 5, :value [[:append 5 2501]], :tid 5, :n 1, :time
1695795515747637933}
{:type :ok, :process 2, :value [[:append 5 2001]], :tid 4, :n 1, :time
1695795515762421482}
{:type :ok, :process 1, :value [[:append 5 1502] [:append 1 1503]], :tid 3, :n
2, :time 1695795516713422487}
{:type :ok, :process 9, :value [[:append 4 1002] [:append 5 1003]], :tid 2, :n
2, :time 1695795516750631050}
{:type :ok, :process 7, :value [[:append 3 1] [:append 5 2]], :tid 0, :n 2,
:time 1695795516768838437}
{:type :ok, :process 6, :value [[:append 1 4502] [:append 5 4503]], :tid 9, :n
2, :time 1695795516822389151}
{:type :ok, :process 1, :value [[:append 5 1504] [:append 3 1505]], :tid 3, :n
3, :time 1695795517729108770}
{:type :ok, :process 4, :value [[:append 4 3503] [:append 5 3504]], :tid 7, :n
3, :time 1695795517807197845}
{:type :ok, :process 10, :value [[:append 5 4003] [:append 3 4004]], :tid 8, :n
4, :time 1695795518717487386}
{:type :ok, :process 1, :value [[:r 5 [2001 1501 2501 3501 1502 1003 2 4503
1504 3504 4003]] [:append 2 1506]], :tid 3, :n 4, :time 1695795518748688923}
{code}
Process 10 reads an empty array.
Process 1 appends 1501.
Process 7 reads that 1501.
Then there are several appends starting with process 4.
Finally process 1 reads 2001 1501 2501 ...
The value 2001 written by process 2 is preceding the value 1501 read by process
7 earlier.
Now to the sstabledump output:
{code:java}
{
"partition": {
"key": [
"5"
],
"position": 0
},
"rows": [
{
"type": "row",
"position": 18,
"cells": [
{
"name": "contents",
"path": [
"b169b440-5cfd-11ee-ac8a-0dac7fcac316"
],
"value": 2001,
"tstamp": "1695795516969001"
},
{
"name": "contents",
"path": [
"b169b44a-5cfd-11ee-ac8a-0dac7fcac316"
],
"value": 1501,
"tstamp": "1695795516963000"
},
{
"name": "contents",
"path": [
"b16b61f0-5cfd-11ee-834b-b92cec395904"
],
"value": 2501,
"tstamp": "1695795516969000"
},
{
"name": "contents",
"path": [
"b16c2540-5cfd-11ee-834b-b92cec395904"
],
"value": 3501,
"tstamp": "1695795516965000"
},
...
]
}
]
} {code}
In short, the order of the list in the sstable is:
{code:java}
2001 1695795516969001 appended by process 2
1501 1695795516963000 appended by process 1 and read by process 7, before
process 2 appended 2001 above
2501 1695795516969000 appended by process 5
3501 1695795516965000 appended by process 4 {code}
And when sorted by the tstamp value:
{code:java}
1501 1695795516963000
3501 1695795516965000
2501 1695795516969000
2001 1695795516969001 {code}
> Appending to list in Accord transactions uses insertion timestamp
> -----------------------------------------------------------------
>
> Key: CASSANDRA-18798
> URL: https://issues.apache.org/jira/browse/CASSANDRA-18798
> Project: Cassandra
> Issue Type: Bug
> Components: Accord
> Reporter: Jaroslaw Kijanowski
> Priority: Normal
> Attachments: image-2023-09-26-20-05-25-846.png
>
>
> Given the following schema:
> {code:java}
> CREATE KEYSPACE IF NOT EXISTS accord WITH replication = {'class':
> 'SimpleStrategy', 'replication_factor': 3};
> CREATE TABLE IF NOT EXISTS accord.list_append(id int PRIMARY KEY,contents
> LIST<bigint>);
> TRUNCATE accord.list_append;{code}
> And the following two possible queries executed by 10 threads in parallel:
> {code:java}
> BEGIN TRANSACTION
> LET row = (SELECT * FROM list_append WHERE id = ?);
> SELECT row.contents;
> COMMIT TRANSACTION;"
> BEGIN TRANSACTION
> UPDATE list_append SET contents += ? WHERE id = ?;
> COMMIT TRANSACTION;"
> {code}
> there seems to be an issue with transaction guarantees. Here's an excerpt in
> the edn format from a test.
> {code:java}
> {:type :invoke :process 8 :value [[:append 5 352]] :tid 3 :n 52
> :time 1692607285967116627}
> {:type :invoke :process 9 :value [[:r 5 nil]] :tid 1 :n 54
> :time 1692607286078732473}
> {:type :invoke :process 6 :value [[:append 5 553]] :tid 5 :n 53
> :time 1692607286133833428}
> {:type :invoke :process 7 :value [[:append 5 455]] :tid 4 :n 55
> :time 1692607286149702511}
> {:type :ok :process 8 :value [[:append 5 352]] :tid 3 :n 52
> :time 1692607286156314099}
> {:type :invoke :process 5 :value [[:r 5 nil]] :tid 9 :n 52
> :time 1692607286167090389}
> {:type :ok :process 9 :value [[:r 5 [303 304 604 6 306 509 909 409 912
> 411 514 415 719 419 19 623 22 425 24 926 25 832 130 733 430 533 29 933 333
> 537 934 538 740 139 744 938 544 42 646 749 242 546 547 548 753 450 150 349 48
> 852 352]]] :tid 1 :n 54 :time 1692607286168657534}
> {:type :invoke :process 1 :value [[:r 5 nil]] :tid 0 :n 51
> :time 1692607286201762938}
> {:type :ok :process 7 :value [[:append 5 455]] :tid 4 :n 55
> :time 1692607286245571513}
> {:type :invoke :process 7 :value [[:r 5 nil]] :tid 4 :n 56
> :time 1692607286245655775}
> {:type :ok :process 5 :value [[:r 5 [303 304 604 6 306 509 909 409 912
> 411 514 415 719 419 19 623 22 425 24 926 25 832 130 733 430 533 29 933 333
> 537 934 538 740 139 744 938 544 42 646 749 242 546 547 548 753 450 150 349 48
> 852 352 455]]] :tid 9 :n 52 :time 1692607286253928906}
> {:type :invoke :process 5 :value [[:r 5 nil]] :tid 9 :n 53
> :time 1692607286254095215}
> {:type :ok :process 6 :value [[:append 5 553]] :tid 5 :n 53
> :time 1692607286266263422}
> {:type :ok :process 1 :value [[:r 5 [303 304 604 6 306 509 909 409 912
> 411 514 415 719 419 19 623 22 425 24 926 25 832 130 733 430 533 29 933 333
> 537 934 538 740 139 744 938 544 42 646 749 242 546 547 548 753 450 150 349 48
> 852 352 553 455]]] :tid 0 :n 51 :time 1692607286271617955}
> {:type :ok :process 7 :value [[:r 5 [303 304 604 6 306 509 909 409 912
> 411 514 415 719 419 19 623 22 425 24 926 25 832 130 733 430 533 29 933 333
> 537 934 538 740 139 744 938 544 42 646 749 242 546 547 548 753 450 150 349 48
> 852 352 553 455]]] :tid 4 :n 56 :time 1692607286271816933}
> {:type :ok :process 5 :value [[:r 5 [303 304 604 6 306 509 909 409 912
> 411 514 415 719 419 19 623 22 425 24 926 25 832 130 733 430 533 29 933 333
> 537 934 538 740 139 744 938 544 42 646 749 242 546 547 548 753 450 150 349 48
> 852 352 553 455]]] :tid 9 :n 53 :time 1692607286281483026}
> {:type :invoke :process 9 :value [[:r 5 nil]] :tid 1 :n 56
> :time 1692607286284097561}
> {:type :ok :process 9 :value [[:r 5 [303 304 604 6 306 509 909 409 912
> 411 514 415 719 419 19 623 22 425 24 926 25 832 130 733 430 533 29 933 333
> 537 934 538 740 139 744 938 544 42 646 749 242 546 547 548 753 450 150 349 48
> 852 352 553 455]]] :tid 1 :n 56 :time 1692607286306445242}
> {code}
> Processes process 6 and process 7 are appending the values 553 and 455
> respectively. 455 succeeded and a read by process 5 confirms that. But then
> also 553 is appended and a read by process 1 confirms that as well, however
> it sees 553 before 455.
> process 5 reads [... 852 352 455] where as process 1 reads [... 852 352 553
> 455] and the latter order is returned in subsequent reads as well.
> [~blambov] suggested that one reason for that behavior could be the way how
> unfrozen lists are updated. The backing datatype is a _kind of a map_ which
> uses insertion timestamps as indexes which are used to sort the list when the
> list is composed from chunks from various sources/sstables before being
> returned to the client.
> In such a case it indeed can happen, that process 5 reads [... 852 352 455]
> but later process 1 reads [... 852 352 553 455] because 553 has been
> _appended_ with an earlier timestamp than 455 but it has been _committed_
> with a later timestamp.
> Now with Accord we have the timestamp _of the transaction_ at hand. Could
> Accord use that for the index instead? Which would lead to the correct
> behavior? The value 553 has been appended after 455 and using the transaction
> id/timestamp as the list index would place it properly in the underlying map,
> wouldn't it?
> Steps to reproduce:
>
> {code:java}
> git clone https://github.com/datastax/accordclient.git
> git checkout append-to-list-index
> lein run --list-append -t 10 -r 1,2,3,4,5 -n 1000 -H <host-ips> -s `date
> +%s%N` > test-la.edn
>
> curl -L -o elle-cli.zip
> https://github.com/ligurio/elle-cli/releases/download/0.1.6/elle-cli-bin-0.1.6.zip
> unzip -d elle-cli elle-cli.zip
> java -jar elle-cli/target/elle-cli-0.1.6-standalone.jar --model list-append
> --anomalies G0 --consistency-models strict-serializable --directory out-la
> --verbose test-la.edn
> {code}
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
