memtx: rework transaction rollback by CuriousGeorgiy · Pull Request #7312 · tarantool/tarantool

CuriousGeorgiy · 2022-06-27T10:33:02Z

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

Korablev77 · 2022-07-13T10:53:19Z

src/box/memtx_tx.c

+	if (stmt->add_story != NULL)
+		memtx_tx_history_rollback_added_story(stmt);
 	if (stmt->del_story != NULL)
-		memtx_tx_story_unlink_deleted_by(stmt->del_story, stmt);


Nit: I'd move 'if' also to the function. Also comments outside scope (e.g. {}) start from /**

I followed the existing style:

tarantool/src/box/memtx_tx.c

Lines 2315 to 2325 in 8f799cd

void

memtx_tx_history_prepare_stmt(struct txn_stmt *stmt)

{

assert(stmt->txn->psn != 0);

if (stmt->add_story != NULL) {

memtx_tx_history_prepare_insert_stmt(stmt);

} else {

assert(stmt->del_story != NULL);

memtx_tx_history_prepare_delete_stmt(stmt);

}

Could you please provide a reference to the style guide? I was not able to find this rule.

Korablev77 · 2022-07-13T11:54:20Z

src/box/txn.c

 		stmt->space = NULL;
 		stmt->row = NULL;
 	}
+	txn->psn = 0;


Don't get this change: why do you assign psn to txn_last_psn and then nullify it?

Because we rollback only part of the transaction (up to savepoint).

Refactored this into a separate function with an appropriate comment.

When a space is deleted, all transactions need to be aborted and all their stories need to be removed immediately out of order: currently we artificially rollback statements — instead call this statement removal to logically distinguish it from rollback. It differs in the sense that the whole space's tuple history is teared down instead — no more transaction managing is going to be done as opposed to rollback of an individual transaction. Needed for tarantool#7343 NO_CHANGELOG=refactoring NO_DOC=refactoring NO_TEST=refactoring

alyapunov

LGTM, but please check my comments.

alyapunov · 2022-09-27T11:24:33Z

src/box/memtx_tx.c

 			/* The story is in chain, but not at top. */
 			continue;
 		}
+		if (link->in_index == NULL)


Could you please and a simple test case that shows that rolled back story does not affect index:count()?

Added two test cases for the correct handling of rolled back and read-view stories.

alyapunov · 2022-09-27T11:53:05Z

src/box/memtx_tx.c

-			if ((tracker->index_mask & index_mask) == 0)
-				continue;
-			memtx_tx_handle_conflict(stmt->txn, tracker->reader);
+		for (struct memtx_story *read_story =


It seems that it is an overkill.

Removed this loop as redundant: we assume that readers of previously prepared transactions are conflicted by induction.

alyapunov · 2022-09-27T11:57:21Z

src/box/txn.c

 static void
 txn_rollback_to_svp(struct txn *txn, struct stailq_entry *svp)
 {
+	txn->psn = ++txn_last_psn;


This place need to be commented well.

Refactored this into a separate function with an appropriate comment.

alyapunov · 2022-09-27T11:58:13Z

src/box/txn.c

 void
 txn_complete_fail(struct txn *txn)
 {
+	txn->psn = ++txn_last_psn;


This place need to be commented well too.

Moved this to txn_rollback, added an assertion here, and commented on this assignment.

`struct memtx_story` has a `space` field, which is basically used to identify that a tuple is unlinked from the history chain in `memtx_tx_index_invisible_count_slow` (though this can be determined by its presence in the index) and is used to get the space's index in `memtx_tx_story_link_top` (though it can be retrieved from the older story's link field): remove this redundant field. Needed for tarantool#7343 NO_CHANGELOG=<refactoring> NO_DOC=<refactoring> NO_TEST=<refactoring>

CuriousGeorgiy · 2022-09-27T14:16:49Z

Filed a report on linter FP tarantool/checkpatch#42.

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. If there is an older story in the history chain, we can relink the rollbacked story's reader to it, but if the rollbacked story is the only one left, we need to retain it, because it stores the reader list needed for conflict resolution — such stories are distinguished by the rollbacked flag, and there can be no more than one such story located strictly at the end of a given history chain (which means a story can be fully unlinked from some indexes and present at the end of others). There are several nuances we need to account for: Firstly, such rollbacked stories must be impossible to read from an index: this is ensured by `memtx_tx_story_is_visible`. Secondly, rollbacked transactions need to be treated as prepared with stories that have `add_psn == del_psn`, so that they are correctly deleted during garbage collection. After this logical change we have the following partially ordered set over tuple stories: ———————————————————————————————————————————————————————> serialization time |- - - - - - - -|— — — — — -|— — — — — |— — — — — — -|— — — — — — — - | No more than | Committed | Prepared | In-progress | One dirty | one rollbacked| | | | story in index | story | | | | |- - - - - - - -|— — — — — -| — — — — —|— — — — — — -|— — — — — — — — Closes tarantool#7343 NO_DOC=bugfix

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. Rollbacked stories need to be handled in a special way: they are present at the end of some history chains and completely unlinked from others (which also implies they are not present in the corresponding indexes). `memtx_tx_story_full_unlink` is called in two contexts: 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 tarantool#7490 NO_CHANGELOG=<internal bugfix not user observable> NO_DOC=<bugfix>

coveralls · 2022-09-27T15:10:20Z

Coverage decreased (-0.01%) to 84.318% when pulling 9f4e55e on CuriousGeorgiy:memtx-rework-tx-rollback into 1d9645f on tarantool:master.

drewdzzz · 2022-09-28T08:03:54Z

src/box/memtx_tx.c

+			if (link->older_story != NULL) {
+				assert(!story->rollbacked);
+				memtx_tx_story_set_status(story,
+							  MEMTX_TX_STORY_USED);
+				return;
+			}
+		}
+		if (!rlist_empty(&link->nearby_gaps)) {
 			memtx_tx_story_set_status(story,
 						  MEMTX_TX_STORY_TRACK_GAP);


If we have a story, that is used to track gap on primary index (it is not on top) and is on top of secondary index, then order of setting statuses is violated. We can iterate over the indexes twice, but I doubt it's worth it.

Yeah, I also thought about it, but I don't like having another loop here.

CuriousGeorgiy added complicated memtx teamC mvcc labels Jun 27, 2022

CuriousGeorgiy self-assigned this Jun 27, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch 3 times, most recently from 24dcf44 to 426a340 Compare July 4, 2022 08:46

CuriousGeorgiy marked this pull request as ready for review July 4, 2022 08:54

CuriousGeorgiy requested review from alyapunov and drewdzzz July 4, 2022 08:54

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch from 426a340 to d30b855 Compare July 4, 2022 08:54

CuriousGeorgiy assigned alyapunov and drewdzzz and unassigned CuriousGeorgiy Jul 4, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch 3 times, most recently from 595a5d9 to 6b6bdef Compare July 5, 2022 06:53

CuriousGeorgiy requested a review from Korablev77 July 5, 2022 08:28

CuriousGeorgiy assigned Korablev77 Jul 5, 2022

CuriousGeorgiy added the bug Something isn't working label Jul 5, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch 3 times, most recently from 8b6e2e9 to 53794c6 Compare July 7, 2022 04:40

Korablev77 reviewed Jul 13, 2022

View reviewed changes

Korablev77 approved these changes Jul 13, 2022

View reviewed changes

CuriousGeorgiy unassigned Korablev77 Jul 15, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch from 53794c6 to 2f5349a Compare July 20, 2022 06:55

drewdzzz removed their assignment Jul 28, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch 4 times, most recently from 8c422c4 to a096f8a Compare September 23, 2022 18:04

CuriousGeorgiy assigned alyapunov and drewdzzz and unassigned CuriousGeorgiy Sep 23, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch 3 times, most recently from 4f6e5ef to fe955c8 Compare September 25, 2022 16:57

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch 3 times, most recently from 63a43c9 to 15bfe84 Compare September 26, 2022 13:42

alyapunov approved these changes Sep 27, 2022

View reviewed changes

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch from 15bfe84 to eee8611 Compare September 27, 2022 14:07

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch from eee8611 to e6717e4 Compare September 27, 2022 14:32

CuriousGeorgiy added the full-ci Enables all tests for a pull request label Sep 27, 2022

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch from e6717e4 to 6e292aa Compare September 27, 2022 14:41

CuriousGeorgiy removed the full-ci Enables all tests for a pull request label Sep 27, 2022

CuriousGeorgiy added 2 commits September 27, 2022 17:48

CuriousGeorgiy force-pushed the memtx-rework-tx-rollback branch from 6e292aa to 9f4e55e Compare September 27, 2022 14:48

CuriousGeorgiy added the full-ci Enables all tests for a pull request label Sep 27, 2022

drewdzzz reviewed Sep 28, 2022

View reviewed changes

drewdzzz assigned CuriousGeorgiy Sep 28, 2022

alyapunov merged commit c8eccfb into tarantool:master Sep 28, 2022

	void
	memtx_tx_history_prepare_stmt(struct txn_stmt *stmt)
	{
	assert(stmt->txn->psn != 0);

	if (stmt->add_story != NULL) {
	memtx_tx_history_prepare_insert_stmt(stmt);
	} else {
	assert(stmt->del_story != NULL);
	memtx_tx_history_prepare_delete_stmt(stmt);
	}

Conversation

CuriousGeorgiy commented Jun 27, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

CuriousGeorgiy Jul 14, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

CuriousGeorgiy Sep 27, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alyapunov left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

CuriousGeorgiy Sep 27, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

CuriousGeorgiy Sep 27, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

CuriousGeorgiy commented Sep 27, 2022

Uh oh!

coveralls commented Sep 27, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

CuriousGeorgiy commented Jun 27, 2022 •

edited

Loading

CuriousGeorgiy Jul 14, 2022 •

edited

Loading

CuriousGeorgiy Sep 27, 2022 •

edited

Loading

CuriousGeorgiy Sep 27, 2022 •

edited

Loading

CuriousGeorgiy Sep 27, 2022 •

edited

Loading