Non-serializable execution (lost update) when a recode is deleted

[feeblefakie]

Environment

• Version 2.0.0
• with SERIALIZABLE

How to reproduce

CREATE TRANSACTION TABLE foo.foo (
  id TEXT PARTITIONKEY,
  value TEXT
);

• Initial state:

id	value	tx_version (tx metadata)
foo	2	1

• Steps

  • T1: start
  • T1: Read a record that has id = foo and put the value into A. If the record does not exist, put 0.
    • (id, value, tx_version) = ("foo", 2, 1)
  • T2: start
  • T2: Delete a record that has id = foo
  • T2: commit
  • T3: start
  • T3: Read a record that has id = foo and put the value into B. If the record does not exist, put 0.
  • T3: Add 1 to B and put
    • (id, value, tx_version) = ("foo", 1, 1)
  • T3: commit
  • T1: Add 1 to A and put
    • (id, value, tx_version) = ("foo", 3, 2)
  • T1: commit

• Actual states :

id	value	tx_version
foo	3	2

The above state can NOT be produced by T1, T2 and T3 in some serial order, which means the execution is not serializable.

• T1->T3->T2 and T3->T1->T2
  no record

• T2->T1->T3 and T2->T3->T1

id	value	tx_version
foo	2	2

• T1->T2->T3 and T3->T2->T1

id	value	tx_version
foo	1	1

[Yonezawa-T2]

Cheap solution: randomize initial version.
Precise solution: check tx_id and tx_version in the prepare phase.

Randomizing initial version almost fix the issue except 1/2^32 of collision.

tx_id is a UUIDv4 value newly generated for each transaction, so the collision is neglectable. Checking two values may impact the performance, although it might not be significant.

[feeblefakie]

@Yonezawa-T2 Thanks. That randomize solution sounds a bit tricky and makes verification more difficult.
Checking tx_id additionally might be good enough for this.

I feel introducing logical delete and guaranteeing monotonic version increase would probably be good from many perspectives as well. Physical delete is a bit scary from verification perspective actually. (it depends how well C*/underlining conditional delete is implemented)

[feeblefakie]

It is closed since it is fixed.
@Yonezawa-T2 Thank you very much for the report.