Dgraph transactions violated causal consistency

[siliunobi]

We found transactional causal consistency (TCC) anomalies on the Dgraph Cluster. According to https://dgraph.io/docs/design-concepts/consistency-model/ , Dgraph provides Snapshot Isolation that is stronger than TCC.

TCC Definition
The causal consistency we checked is defined in the SOSP’11 paper “Don’t settle for eventual: scalable causal consistency for wide-area storage with COPS” (Section 3.1), as well as in the POPL’17 paper "On verifying causal consistency".

Experimental Setup
In our experiment we set up the cluster on a local machine with 3 server nodes. Here is the configuration information:

Dgraph Version == 21.03.2

server_node = 3
client_num(session_num) = 2
client_stub_num = 1
txn_per_session = 10
operation_per_txn = 10
key_number = 20
key_distribution = uniform

We are using a simple table schema, just containing key-value pairs, e.g., key=10, value=5. Keys are initialized to value 0. Note that, for each write on a key, the value (generated by the workload generator) is unique.

Anomaly Found
One anomaly was found on five transactions from two sessions, where r/w(A,B) denotes read/write value B on key A:

txn4 and txn6 have “write-read” order on key 19, denoted by txn4 ->wr txn6; txn13 and txn6 have write-read order on key 0, i.e., txn13 → txn6. The “wr” order means two transactions contain write/read operations on the same key with the same value respectively, thus the transaction with write operation should happen before the transaction contains the read operation.

To satisfy transactional causal consistency txn13 must be ordered before txn4 because we already know txn4 → txn6 and txn13 → txn6 and txn6 read the value of key 19 written by txn4. Thus we have commit order txn13 ->co txn4 (see the bottom for the definition of commit order). However, txn4 can reach txn13 via txn4 ->so txn5 ->wr txn11 ->so txn12 ->so txn13. Hence, there is a cycle between txn13 and txn4 that violates TCC.

The dataset is given at https://github.com/20211202na/dgraph_data/blob/main/data.txt

Reproducibility

1. We use github.com/20211202na/dgraph_data/blob/main/data_generation.py to deal with the client-side logic (e.g., generating txn workloads)

2. For each run, “histories” of txns (values read and/or written) for all clients are also collected and printed.

3. We then invoke the checker (the function run_oopsla_graph) in github.com/20211202na/dgraph_data/blob/main/run_verification.py to verify if the history violates transactional causal consistency.

Note that, since we are doing random testing (e.g., workloads are generated probabilistically), it’s hard to reproduce a specific anomaly. However, we observed 5 to 8 violating histories per 100 histories with the setup posted. We believe that anomalies manifest with sufficiently large number of runs.

[joshua-goldstein]

Hi @siliunobi. Many thanks for your feedback. We are interested in learning more about your results and methodology. If you have time, please send an email to contact@dgraph.io with any relevant results/data you might have. We would be happy to schedule a time to talk and learn more about your work.

[siliunobi]

Email sent. Cheers!

[harshil-goel]

@siliunobi Thanks a lot for this detailed explanation of how the transaction violation could occur. I went through your code, and it seems like whenever you are doing one transaction, the reads are actually happening on another transaction. Because of this, the transactional consistency is not being proved here. Consider the following example:
Txn 4
W(2,20,0,4)
W(1,10,0,4)

Txn 5
R(2,0,0,5)
R(1,10,0,5)

This diagram violates casual consistency . Txn5 read value of 1 properly, so it should be after Tnn4 has commited. However Txn5 read the stale value of 2, causing a casual consitency issue. However, since we know that for every read, we are creating a new transaction, the example looks like
Txn 4
W(2,20,0,4)
W(1,10,0,4)

Txn 5
R(2,0,0,5)

Txn 6
R(1,10,0,5)

This case is okay and doesn't violate any consistencies.

You call (func: op_query in data_generation.py)client.txn(read_only=True. This starts a new transaction for the read requests. If you pass the txn to this function, just like the function for write(op_update), then the reads would a part of the same txn. I made this change, and I haven't' seen the issue till now, I will let it run for a day or two to make sure there are no issues in DGraph otherwise.

Let me know if my analysis sounds right or if you have any other questions. Thanks a lot again for the effort and for this great tool.

[siliunobi]

@harshil-goel Thanks for your response! Could you plz elaborate your analysis? I didn't quite get it. In particular, could you plz show me a counterexample returned by our tool on your side and explain why you don't think that is a CC violation?

[joshua-goldstein]

@siliunobi It looks like a bug in the script generating the data. In the loop on this line here you are creating a new transaction from the client with txn = client.txn(). Then in this line here you are doing a read query. However inside that function here you are calling response = client.txn(read_only=True).query(query, variables=variables) which is creating a new transaction each time it is invoked (instead of using the transaction created at the beginning of the while loop).

Basically writes and reads are being recorded as occurring in one transaction, when in fact each time a read is happening it is occurring in a new transaction. @harshil-goel noticed this because the reads and writes that are being recorded as occurring one transaction actually had different start timestamps, which didn't make sense.