tarantool
memtx: rework transaction rollback
When we rollback a transaction statement, we relink its read trackers to a newer story in the history chain, if present (6c990a7), but we do not handle the case when there is no newer story.
In order to fix this, we need to retain stories added by rollbacked transactions, because they store the reader list needed for conflict resolution.
There are several nuances we need to account for:
Firstly, such stories must be impossible to read from an index: this is
ensured by memtx_tx_tuple_clarify.
Secondly, rollbacked transactions need to be treated as prepared with
stories that have add_psn == del_psn the stories they add need to be
'sunk' to the level of prepared transactions, so now we have the following
totally ordered set over tuple stories:
———————————————————————————————————————————————————————> serialization time
|— — — — — —|— — — — — |— — — — — — | — — — — — — — —
|Committed +|Prepared +| In-progress| One dirty story
|rollbacked |rollbacked| | in index
|— — — — — —| — — — — —|— — — — — — |— — — — — — — — —
Last, but not least, we also need to consider the following shadowing
effect: if a rollbacked story is on top of the history chain and there are
older stories in the history chain, it can possibly shadow a story of a
prepared or committed tuple, which is not de jure deleted, so instead of
simply deleting the story's tuple from the index, we need to replaced with
the tuple of an older story. In order for this to work, though, we also
need to retain stories of committed and prepared tuples which are not
de jure deleted (have a zero del_psn), if there are newer stories in the
history chain which could possibly shadow them.
Closes #7343
memtx: fix transaction manager MVCC invariant violation
We hold the following invariant in MVCC: the story at the top of the history chain is present in index.
If a story is subject to be deleted from index and there is an older story in the history chain, the older story starts to be at the top of the history chain and is not present in index, which violates our invariant: explicitly check for this case when evaluating whether a story can be garbage collected and add an assertion to check the invariant above is not violated.
memtx_tx_story_full_unlink is called in two context: space deletion, in
which we delete all stories, and garbage collection step — the former case
can break the invariant described above, while the latter must preserve it,
hence add two different functions for the corresponding contexts.
Closes #7490
Coverage decreased (-0.01%) to 84.318% when pulling 9f4e55e13a1b00f115677cc10c88e1e0dbd818da on CuriousGeorgiy:memtx-rework-tx-rollback into 1d9645f7be123d9150e71f24e6f2a533c5438a50 on tarantool:master.
