[WIP] RFC: Index Build 4.x

[Astronomax]

Reviewers

• Primary reviewer: @drewdzzz
• Secondary reviewer: @locker
• Team lead: @sergepetrenko
• CTO: @sergos

Problem

Memtx doesn't wait for prepared transactions to become committed on yielding DDL

https://github.com//issues/10930

In Vinyl, journal_sync() is called before starting to build a new index so that the code waits for CONFIRM on all prepared transactions. This does not happen in Memtx, so the main build loop may insert a prepared (but not yet confirmed) tuple that, for example, had already been stuck in the WAL queue before the build started, and that tuple will not be removed from the index if the transaction is rolled back due to a WAL failure. In other words, ideally, the only things that should be able to roll back changes in the new index are parallel transactions that appeared after index build had already started.

In fact, journal_sync() alone would not be enough here, because there are several more places where a transaction may get stuck: the queue before WAL, limbo, the queue before limbo, and possibly something else as well.

Memtx doesn't handle rollback of concurrent writers on yielding DDL

https://github.com//issues/10931

This problem has the same consequence as the previous one: after a transaction rolls back, the tuple remains in the index. Unlike the previous issue, here the problem is related to tuples that appeared during index build and ended up to the right of the cursor. No rollback trigger is installed for such tuples, so nothing will remove them from the building index if the corresponding transactions are rolled back.

One possible solution would be to always install a rollback trigger regardless of which side of the cursor the tuple is on when on_replace is called, and add logic to that trigger that checks whether the cursor has already passed this tuple by the time rollback happens. If it has, the trigger would perform the corresponding rollback in the building index.

Vinyl doesn't wait for writers to be confirmed by replicas on yielding DDL

https://github.com//issues/10929

This problem was already mentioned above: Memtx does not even have journal_sync() before index build starts, while Vinyl does, but it turns out to be insufficient, because WAL is not the only queue where a transaction may be stuck before it becomes confirmed.

memtx: crash when building index with mvcc

https://github.com//issues/12261

The problem is that memtx_tx_invalidate_space essentially makes an invalid assumption that it is safe to simply remove all extra information related to prepared transactions from MVCC state, in particular memtx_story.

At the moment, memtx_tx_invalidate_space does the following:

• removes all chains (all memtx_story) associated with a given space
• rolls back all in-progress transactions
• updates indexes so that they contain the current state, i.e. tuples of the latest prepared/confirmed transactions.

This is clearly unsafe for many reasons.

For example, consider the following situation:

• WAL spends a long time waiting for something. A prepared transaction txn is sitting in the queue waiting to be written.
• Meanwhile, some DDL happens that invalidates the space (memtx_tx_invalidate_space). It does not even have to commit or enter the WAL queue: box.begin() DDL() box.rollback() is already enough.
• As a result, the index still contains tuple tuple of prepared transaction txn. However, the corresponding story was deleted, and together with it the connection between the tuple and the corresponding transaction statement stmt was lost.
• New in-progress transactions then arrive and execute replace with a key from tuple tuple (primary or secondary, it does not matter). A new story story' is created for tuple tuple, but this time it no longer contains a reference to statement stmt. At the same time, all these replaces are effectively applied to the index immediately in order to preserve the invariant that the top of the chain is physically present in the index:

  tarantool/src/box/memtx_tx.c

  Lines 2972 to 2976 in 1e3c241

  	* —————————————————————————————————————————————————> serialization time
  	* |- - - - - - - -|— — — — — -|— — — — — |— — — — — — -|— — — — — — — -
  	* | Rolled back | Committed | Prepared | In-progress | One dirty
  	* | | | | | story in index
  	* |- - - - - - - -|— — — — — -| — — — — —|— — — — — — -|— — — — — — — —

  .
• New in-progress stories are added to the end of the chain immediately after story'.
• txn is rolled back. The rollback goes through rollback_empty_stmt (because the reference to stmt is missing), which blindly replaces rollback_info->new_tuple with rollback_info->old_tuple in the index.
• As a result, at the very least, the main invariant that the top of the chain is physically present in the index is broken. This, in turn, will lead to arbitrary further breakage, for example, the chain may become inaccessible.

The issue contains a slightly different example. Instead of building new chains from in-progress stories, it starts building a new index. Surprisingly, even in that case there are still certain problems. The rollback of a prepared story is not noticed by anyone, again because after memtx_tx_invalidate_space that story is no longer linked to its add_stmt statement. As a result, the tuple manages to be inserted into the building secondary index, and then on rollback it is removed only from the primary index. Even though the corresponding read tracker was added to the story, secondary index build does not abort, again because the stmt -> story connection is missing.

Only confirmed stories can be detached from add_stmt completely safely and without any extra logic.

One possible solution to this problem would be to abort all related in-progress transactions first when such a prepared statement is rolled back, for example directly from rollback_empty_stmt.

vinyl: building a unique index can end up with duplicates in it

https://github.com//issues/12284

The problem is that the index build procedure in Vinyl misses certain scenarios in which duplicates may appear in the building unique index. Uniqueness is checked in two places:

• when inserting a confirmed tuple tuple that existed before the build (vy_stmt_lsn(tuple) <= build_lsn)
• and in the on_replace trigger when handling parallel in-progress transactions

In both cases the check is implemented in the same way: vy_get in the building index by the corresponding key of tuple tuple, then compare the primary key of tuple with whatever was returned by vy_get. In the first case the isolation is p_committed_read_view (i.e. READ_CONFIRMED), in the second case it is vy_tx_read_view(tx) (i.e. according to the isolation level of the in-progress transaction for which on_replace fired). Both choices look suspicious.

The reproducer from the issue does the following:

• The build loop inserts {1, 1} and yields.
• An in-progress transaction txn executes replace{3, 2}, checks for duplicates, and finds nothing for key 2.
• txn commits, becomes prepared, and gets stuck in WAL.
• The build continues and inserts {2, 2}. It performs vy_get in p_committed_read_view and again finds nothing for key 2, because {3, 2} has not yet been written to WAL.
• The build commits and also gets stuck in WAL.
• Both txn and the build are successfully written to WAL.

It seems that simply changing p_committed_read_view to p_global_read_view when inserting in the build loop would be enough to fix this specific class of scenarios. However, it might also make sense to use p_committed_read_view in the on_replace check for parallel in-progress transactions as well. I have not verified this, but it is likely possible to reproduce the problem if two duplicates are inserted one after another in parallel with index build while WAL is slowed down. All other situations are handled, among other things, thanks to two facts:

• Index build finishes by invalidating the space and aborting all in-progress transactions on that space.
• When an in-progress transaction becomes prepared, Vinyl iterates over its write_set and aborts all in-progress inserts with the same key.

Allow to write to space on background index build with MVCC enabled

https://github.com//issues/10170

If we omit unimportant details, Memtx index build with MVCC currently looks like this:

• index_count is called to check that the index is not empty. index_count leaves certain trackers (gap_item_type = GAP_COUNT) to guarantee the correctness of this read.
• An iterator over the primary index is created, and this iterator inserts tuples into the new index. The iterator reads only tuples of prepared transactions and tracks all keys it has read, as well as the intervals between them.
• If any parallel transaction now executes replace in the space and commits, index build aborts. It seems that it does not even matter which side of the cursor that replace happens on.

Thus, any small parallel write operation aborts a long-running index build. What we want is a new index build procedure with MVCC that allows parallel writes and handles them correctly so that index build aborts as rarely as possible.

Requirements

• Correct behavior, including in all scenarios listed above.
• Preferably, this should be a single procedure shared by Memtx and Vinyl, depending as little as possible on engine-specific details.
• In the Memtx MVCC case, the procedure should allow parallel operations and handle them correctly so that index build aborts as rarely as possible.
• In MVCC scenarios, we would also like parallel insertion of a duplicate into a building unique index to abort the insertion in most cases rather than the build.
• The procedure must run separately from the DDL transaction (fiber()->txn == NULL) so that it can later be used in the context of non-blocking build: https://github.com/orgs/tarantool/discussions/11018.

Possible Solution №1 (Anton Kuznets @Astronomax)

This solution even has an implementation that passes the tests and issue reproducers. It is worth noting, though, that the current tests do not cover index build very well.

Unfortunately, with this approach it was not possible to avoid engine-specific details in a completely clean way; we will discuss why below.
Therefore, the procedure takes an engine-provided vtab with the following methods:

• replace_confirmed(index, tuple)
• replace_in_progress(index, old_tuple, new_tuple)
• rollback(index, old_tuple, new_tuple)
• finalize(index)

We will see below what they are needed for and how they are implemented in Memtx and Vinyl.

In general, the proposed procedure is similar to what currently works in Memtx:

• Install on_replace to handle parallel replace operations. The main reason it is needed is duplicate lookup in a Vinyl index. We will discuss later what exactly it does and why it is needed.
• If necessary, wait for CONFIRM on all prepared transactions stuck in various queues: txn_limbo_flush, journal_sync. Roughly the same as here:

  tarantool/src/box/checkpoint.c

  Lines 69 to 74 in 9ec082b

  	if (txn_limbo_flush(&txn_limbo) != 0)
  	return -1;
  	if (do_journal_rotation)
  	return journal_begin_checkpoint(out);
  	memset(out, 0, sizeof(*out));
  	return journal_sync(&out->vclock);

• Start a PK iterator (ITER_ALL) and, in a loop (which we will call the "build-loop" below), insert tuples into the index while periodically yielding. Since there is no active transaction attached to the fiber at this moment, the iterator leaves no trackers or anything like that. In both Memtx and Vinyl the iterator reads prepared tuples. In fact, as we will see later, even with read-committed (read-prepared) isolation the loop will skip prepared tuples, so correctness would not break even if the iterator itself only read confirmed tuples.
• Once the iterator reaches the end, some finalization vtab->finalize is performed. It is needed only for Vinyl for now; we will discuss what it is later.
• Disable all statement-level triggers accumulated so far, as well as the on_replace trigger.
• Invalidate the space, i.e. abort all in-progress transactions on that space. Important: there must be no yield between this invalidation and the previous step.

The following structures are maintained during the process:

• processed: the set of keys that build-loop must skip because their consistency is guaranteed by statement-level triggers.
  Suppose a parallel replace{tuple} happens while build-loop is running, such that tuple ends up to the right of the current cursor position. Such tuples could be deferred and made the responsibility of build-loop, which is how it is implemented now.
• write_set (unique indexes only): something similar to Vinyl's write_set, a mapping build_key -> txn set. It can be viewed as the set of "write points" of parallel transactions. A "write point" is a pair (key, txn) created at the moment a parallel transaction txn inserts tuple, such that build_key(tuple) = key. It is used to abort conflicting in-progress writers and thus avoid duplicates.
• not_confirmed (unique indexes only): key -> int. Its purpose will be discussed later.

on_replace:

• Validate new_tuple against the new index format.
• For a unique index, check duplicates: result = building_index.get(build_key(new_tuple)), then compare result == old_tuple. If some tuple result different from old_tuple is found, that is a duplicate and new_tuple must not be inserted. In this case the replace in the transaction fails with an error, while build-loop keeps running.
• If the uniqueness check passes, add (build_key(new_tuple), txn) to write_set.
• Install before_commit, on_commit, and on_rollback triggers on the statement.

before_commit (on_prepare):

• Compute pk = primary_key(new_tuple ?: old_tuple).
• Next, we need to understand whether old_tuple is already present in the index in order to call vtab->replace_in_progress correctly. old_tuple is already in the index if:
  • pk $\in$ processed.
  • pk is to the left of or equal to the build cursor, i.e. build-loop has already passed pk.
• For a unique index, perform not_confirmed[build_key(old_tuple)]++. We will discuss the purpose of not_confirmed later, so for now just skip it.
• vtab->replace_in_progress(old_tuple or NULL, new_tuple).
• If pk was to the right of the cursor, add pk to processed. Now build-loop will skip this PK and will not duplicate the already applied change.
• For a unique index, remove the corresponding "write point" from write_set because the transaction is no longer in-progress.
• For a unique index, abort all other in-progress writers from write_set for key build_key(new_tuple).
• Any error in the trigger means index build has failed, so the build is aborted.

on_rollback:

• If the statement rolled back while still in-progress (i.e. box.commit was never called):
  • Remove the corresponding "write point" from write_set.
• Otherwise, if prepare had already happened by that time:
  • The corresponding "write point" has already been removed in on_prepare.
  • Validate old_tuple against the new index format. This is needed because old_tuple may have been committed before the build started and therefore might never have been validated before.
  • For a unique index, abort all in-progress writers from write_set for key build_key(old_tuple).
  • For a unique index, perform not_confirmed[build_key(old_tuple)]--. We will discuss the purpose of not_confirmed later, so for now just skip it.
  • vtab->rollback(old_tuple, new_tuple). This rolls back changes previously made by replace_in_progress: remove new_tuple, restore old_tuple. We will discuss later what exactly this means for each engine.
• Obviously, if any error occurs in the trigger, the only remaining option is to abort the build.

on_commit (on_confirm):

• Remove all corresponding statement-level triggers.

build-loop:

• Before processing the next tuple, remove from processed all keys that are strictly to the left of the current tuple.
• If the current tuple is found in processed, build-loop skips it entirely: this PK has already been handled via on_prepare/on_rollback.
• Validate tuple against the new index format.
• For unique indexes, check duplicates. If a duplicate is found in the index, the only option left is to abort the build.
• Check not_confirmed[build_key(tuple)] == 0. If it is > 0, abort the build. We are not discussing why just yet.
• For a unique index, abort all in-progress writers from write_set for key build_key(tuple).
• vtab->replace_confirmed(tuple).
• Advance the build cursor.
• sleep(0) on every Nth iteration.

Note

It is important to keep in mind that some triggers may yield. While the trigger fiber is suspended, build-loop may manage to finish or abort and free resources that the trigger still needs. This must be taken into account in the implementation.

What is not_confirmed, and what problem does it solve?

At this point it may seem that everything described above is enough to ensure correct behavior across the full set of possible scenarios. However, there is still at least one more problem:

Consider the following situation:

• Memtx MVCC or Vinyl.
• The primary index contains tuples {1, 1}, {2, 2}, {3, 2}
• Build-loop stops on tuple {1, 1}
• In parallel, replace{3, 3} happens in REPLACE_TXN, goes to WAL, and gets stuck there
• Build-loop wakes up, inserts {2, 2}, and goes to sleep again. Assuming duplicate checks read with read-committed (read-prepared) isolation, duplicate {3, 2} is not detected ({3, 3} is already prepared at this point).
• A WAL error happens and REPLACE_TXN rolls back to {3, 2}. At this point we need to check duplicates in order to detect duplicate pair {2, 2}, {3, 2}. The most obvious thing would be to perform get by key 2 in the index. However, in Vinyl this is a problem because get yields, which is not allowed during rollback.

On closer inspection, it turns out that such "conflicts" (duplicates) arise specifically between an insertion from the main loop and a parallel insertion from a transaction. Two insertions from the main loop, and even, less obviously, parallel inserts from transactions, do not create this problem between themselves. We will discuss why below.

Several possible solutions to this problem:

• Wrap insertion of a tuple from build-loop (either each tuple individually or some batch) into transaction BUILD_TXN. The transaction must also write something in order to pass through WAL, for example some progress statistic in _index_local, so that this does not look too hacky. Then the scenario above works correctly because BUILD_TXN is rolled back transitively together with REPLACE_TXN. But what if REPLACE_TXN rolls back before BUILD_TXN calls box.commit (becomes prepared)? Fortunately, the procedure also has write_set specifically for such situations, so REPLACE_TXN will abort BUILD_TXN. This option will appear again later in possible solution №2.
• When inserting {2, 2} from the main loop, check duplicates twice: once with read-committed isolation, once with read-confirmed. In on_replace, one check is enough. That means that if duplicates existed before the build started, the build may complete successfully only if all of them are somehow replaced before the build cursor reaches them.
• not_confirmed. Increment not_confirmed[build_key(old_tuple)]++ when a transaction transitions from in-progress to prepared, and decrement it when the transaction transitions from prepared to confirmed/rolled back. When inserting from build-loop, check not_confirmed[build_key(tuple)] == 0. In the scenario above, when replace{3, 3} is prepared, it performs not_confirmed[2]++. After that, build-loop attempts to insert {2, 2}, but because not_confirmed[2] > 0, it aborts the build.

The key difference between the Memtx and Vinyl models

Before considering vtab for both engines, it is worth explicitly stating one important difference between Memtx and Vinyl.

In Memtx, an index change is essentially an immediate modification of the corresponding tree. If new_tuple was inserted into the building index from on_prepare, then on rollback it must be explicitly removed from that tree and, if necessary, old_tuple must be restored. Therefore, in Memtx rollback is index_replace in the reverse direction relative to replace_in_progress.

In Vinyl the model is different. There, a change does not rewrite the index in place, but instead appends statements (INSERT/REPLACE/DELETE/UPSERT) to a sequence of statements that first live in vy_tx and its write_set, and then on prepare are flushed into the corresponding LSM's vy_mem via vy_lsm_set(). On confirm they are confirmed via vy_lsm_commit_stmt(), and when a prepared transaction is rolled back, the engine itself removes them from vy_mem via vy_lsm_rollback_stmt(). In other words, in Vinyl rollback of a prepared writer is handled entirely by the engine itself, not externally.

Therefore, replace_in_progress for Vinyl and Memtx looks different in implementation:

• In Memtx we modify the building index directly as a data structure.
• In Vinyl we only add statements to vy_tx for the building LSM: a surrogate DELETE for old_tuple and an INSERT for new_tuple. After that, their lifecycle is managed by Vinyl itself.

As a result, in Vinyl rollback in vtab can be Noop, because the actual rollback is done not by index_build, but by vy_tx_rollback() / vy_lsm_rollback_stmt().

In this form, vtab looks as follows:

• replace_confirmed(index, tuple): insert a confirmed tuple tuple from build-loop.
  • Memtx: index_replace(index, NULL, tuple, DUP_INSERT).
  • Vinyl: direct insertion of a statement into the building LSM (vy_build_insert_tuple()).
• replace_in_progress(index, old_tuple, new_tuple): handle a parallel transaction, called from on_prepare.
  • Memtx: index_replace(index, old_tuple, new_tuple, DUP_REPLACE_OR_INSERT).
  • Vinyl: write corresponding statements into vy_tx for the building index: DELETE(old_tuple) and/or INSERT(new_tuple) via vy_tx_set(). These statements will then be written to vy_mem on prepare, and later either confirmed or rolled back by Vinyl itself.
• rollback(index, old_tuple, new_tuple): roll back a parallel prepared transaction.
  • Memtx: an explicit reverse operation, essentially index_replace(index, new_tuple, old_tuple, ...).
  • Vinyl: Noop, because rollback of prepared statements is already performed by the engine during vy_tx_rollback().
• finalize(index): finalization needed only for Vinyl.
  • Memtx: Noop.
  • Vinyl: trigger dump of the new LSM so that the built index does not have to be rebuilt during recovery.

Possible Solution №2 (Andrey Saranchin @drewdzzz)

Base part

Let us start with the core framework, i.e. with the parts that we definitely would like to include in this solution, and then consider additional options along the way.

First, build-loop now wraps insertion of an entire batch of tuples into transaction BUILD_TXN.

Roughly speaking, this transaction could look as follows:

• box.begin()
• Iterate over some range of the primary:
  • Get the next tuple tuple from iterator pk_iter. Memtx/Vinyl MVCC will track what was read at this point.
  • Duplicate check
    • res = index.get(build_key(tuple)) <------------- ???
    • Check res == NULL
    • If a duplicate is found here, abort the build.
  • Add (build_key(tuple), BUILD_TXN) to write_set
  • index_replace. It is non-transactional, i.e. it does not become a statement of the transaction. In principle this would look odd and it is not even very clear what it would mean for it to be transactional. Here the insertion happens into only one index, so rollback, if needed, must also be done only in that one index, whereas a REPLACE statement means an atomic insertion into the space as a whole, i.e. into all its indexes. And if this is not a statement, then it is unclear how to roll such an insertion back if BUILD_TXN itself rolls back, for example due to a conflict with a parallel transaction. Most likely, this would require additional machinery in build-loop.
  • pk_iter.next().
• The transaction must write something in order to pass through WAL and have cascading rollback. For example, it could update progress in _index_local.
• box.commit()

Warning

While writing the paragraph about index_get(build_key(tuple)), I noticed one more important thing. In the implementation of solution №1, index_get_internal is used. In Memtx, index_get_internal is implemented in such a way (memtx_tree_index_get_internal) that when MVCC is enabled it additionally searches the chain for the version visible to the reading transaction (memtx_tx_tuple_clarify). The problem is that Memtx MVCC does not handle building indexes, i.e. it does not maintain version chains or conflict resolution for them. If index_get_internal is called on a building Memtx index, Memtx MVCC will attempt to iterate the history chain. At that point it will access story->link[index->dense_id], which does not exist (link was allocated under the assumption that the index with that dense_id does not yet exist), which leads to a segfault. In proposed solution №1 this does not happen, but only by accident. There all index_get_internal reads are performed with read-prepared (is_prepared_ok = true) isolation, and all parallel inserts happen specifically in on_prepare (before_commit). That means index_get_internal is always called at a moment when the index contains a visible prepared tuple, so the loop always terminates on the very first iteration without ever accessing link[index->dense_id]. In both solution №1 and solution №2 what we really need is just a raw get in the data structure, without any history traversal, so most likely something in engine_vtab would have to change so that it exposes a raw get there (just a wrapper over memtx_tree_find). But for Vinyl this would look strange, because everything works very differently there. It is not really obvious what a "raw" get should mean for Vinyl. In a sense, Vinyl does track history even for the building index. Vinyl has its own internal statements for each index separately. As soon as a parallel transaction adds a Vinyl statement (building_index:REPLACE()), the change enters history. For Vinyl, this get could be defined as get with read_prepared isolation, i.e. "get the last tuple in index history".

There is also a question about the iterator. In the first solution, there was one iterator for the whole build-loop without a transaction, so it tracked nothing. Here we need transactional iterators, one per BUILD_TXN. But then we somehow need to remember the position where the iterator of the previous BUILD_TXN stopped, so that the next one can continue from there. And this must remain correct in the presence of parallel inserts. It is not yet clear to me whether this can be done and how?

on_replace for parallel transactions:

• Duplicate check in the index.
• Add (build_key(tuple), BUILD_TXN) to write_set.
• index_replace.

on_prepare for parallel transactions REPLACE_TXN and transaction BUILD_TXN:

• In the case of a parallel transaction, it is possible to install on_prepare (before_commit) on each individual statement. In the case of BUILD_TXN, since inserts do not create statements, it might be possible to do it via a txn-level before_commit trigger, which currently does not exist, just like the statement-level one.
• Abort in-progress duplicates via write_set.

One drawback of solution №1 is that a parallel insertion to the right of the cursor leaves a flag in the processed map, and that flag will only be removed later when the cursor crosses the corresponding primary key. In other words, the flag appears in on_prepare and is not removed later in either on_confirm or on_rollback. Thus, in the worst case this is O(number of transactions that happened in parallel with the build) additional memory. Ideally we would like to limit this to at least O(max number of simultaneously active in-progress/prepared transactions). If this turns out to matter, it can be added to the requirements above. It is not even entirely clear why this matters, since a proportional amount of memory will anyway be allocated for the corresponding tuples.

Therefore, here we would like to return to the old approach and insert from triggers only what ends up to the left of the cursor, thus avoiding additional marks in the form of processed.

Overall, everything described above is just a rough outline of what would likely be worth fixing in this solution №2. We will now select the remaining pieces.

More variable part

Parallel insertion into a build-loop batch raises many questions.
Suppose the next batch starts from build-cursor. Let us call the cursor position at some point during batch iteration build-cursor'. Since index.get may yield in Vinyl, it makes sense to keep track of build-cursor'. build-cursor'' is the cursor position at the end of the current batch (and the start of the next batch). At the start of each new build-loop transaction only build-cursor and build-cursor' are known.

Parallel insertion (on_replace) to the left of build-cursor

The simplest case is insertion to the left of build-cursor by a parallel transaction. In that case on_replace immediately inserts the tuple into the index. It is obvious that rolling such a tuple back must be the responsibility of the on_rollback trigger.

Parallel insertion (on_replace) between build-cursor and build-cursor'

Now suppose a parallel insertion happens somewhere between build-cursor and build-cursor'.

In this case on_replace could, for example:

• Call index_replace
• Not call index_replace, and instead
  • either abort BUILD_TXN and restart the transaction for this batch so that build-cursor' traverses this range again and picks up the tuple on its own
  • or abort REPLACE_TXN (REPLACE_TXN aborts itself)
  • or put the tuple into some list that BUILD_TXN will later process somehow

Regardless of what on_replace does in this situation, there are 4 possible variants of the order in which BUILD_TXN and REPLACE_TXN change their states.

Suppose on_replace directly calls index_replace in such cases. Then:

• In variants 1 and 2, Memtx/Vinyl MVCC will abort BUILD_TXN at the moment REPLACE_TXN is prepared. After that BUILD_TXN restarts, and we end up in the situation "parallel on_replace between build-cursor' and build-cursor'' called index_replace". BUILD_TXN would then somehow need to understand that the tuple has already been inserted by on_replace and must be skipped.
• Variant 5 is good. If BUILD_TXN aborts, then REPLACE_TXN is also rolled back transitively. And if BUILD_TXN successfully becomes confirmed, then what happens to REPLACE_TXN afterwards does not matter much, as long as it restores the correct tuple in case it is eventually rolled back.
• Variant 6. If BUILD_TXN successfully becomes confirmed, then this becomes the simple case "on_replace to the left of build-cursor". If BUILD_TXN aborts, then after restart we again get the situation "parallel on_replace between build-cursor' and build-cursor'' called index_replace", which we will discuss next.

So in the end all the complexity is reduced to parallel on_replace between build-cursor' and build-cursor'' that called index_replace. The key is to solve that case.

Suppose on_replace does not call index_replace in such cases, aborts BUILD_TXN, but does not abort itself.

This is even simpler: all variants are immediately reduced to the case parallel on_replace to the right of build-cursor' did not call index_replace (the transaction restarts and build-cursor' ends up to the left of the insertion). Again, one would need some way to make sure BUILD_TXN does not insert this tuple a second time.

on_replace does not call index_replace and aborts REPLACE_TXN (itself).

This is clearly fine. It remains only to consider parallel insertion to the right of build-cursor'.

on_replace does not call index_replace, but leaves the tuple in some list.

What could happen with this list in principle? In a private discussion with Andrey, I think we considered the option where BUILD_TXN would process this list before handling the next batch.

This option has a lot of complications:

• BUILD_TXN would have to inspect this list before each next batch in primary key order, determine which entries are already to the left of build-cursor and which are still to the right, and call index_replace for some of them.
• For each such entry it would have to remember the state of the transaction that produced it: in-progress, prepared, confirmed, rolled back. Since reading the list is not tracked in any way and MVCC knows nothing about it, there are problems related to the fact that one of the tuples in the list may be rolled back. In particular, it may roll back in-progress -> rolled back, while BUILD_TXN is already prepared and sitting in WAL. In that case it becomes completely unclear how that insertion should be rolled back. Most likely, the tuple should not be added to the list immediately; at the very least on_prepare should be installed and the tuple should be added there.

In principle this is probably implementable, but it looks unnecessarily complex.

Parallel on_replace between build-cursor' and build-cursor'' called index_replace

Now consider a parallel insertion to the right of build-cursor'. Recall that this is exactly the case to which all the complexity was reduced in the paragraph about on_replace between build-cursor and build-cursor' that immediately calls index_replace.

The main problem here is that as soon as on_replace to the right of build-cursor' calls index_replace itself, BUILD_TXN then has to somehow learn that this tuple has already been applied to the index externally. If BUILD_TXN later reaches this tuple and knows nothing about it, it will try to insert it a second time. We again come back to the need to keep some analogue of processed, and everything becomes even more complicated.

Parallel on_replace to the right of build-cursor' did not call index_replace

Consider the following situation:

• on_replace(old_tuple, new_tuple) happens to the right of build-cursor'
  • on_replace only checks duplicates
  • updates write_set
• Suppose REPLACE_TXN then gets stuck in in-progress for a long time.
• During that time build-cursor' passes through new_tuple. Since the tuple is in-progress, BUILD_TXN will not read it. But it will definitely read old_tuple, because that one is at least prepared, and will insert it into the building index.
• BUILD_TXN successfully commits and becomes confirmed.
• As a result, BUILD_TXN ends up somewhere to the right, but the tuple was inserted neither from on_replace nor from BUILD_TXN.
• REPLACE_TXN becomes prepared:
  • REPLACE_TXN can now look at build-cursor and build-cursor' to decide what to do.
  • In this scenario build-cursor at that moment will already be somewhere to the right (for example, if we move build-cursor on confirm of BUILD_TXN). Then REPLACE_TXN could do one of the following:
    • call index_replace itself on prepare of REPLACE_TXN. Calling index_replace on prepare looks strange, but perhaps it would be possible.
    • roll back. In that case everything is fine.
    • install an on_confirm (on_commit) trigger that would put this tuple into some list from which BUILD_TXN would later fetch it. But then one has to look carefully at the situation where build-loop has already finished while prepared REPLACE_TXN was still stuck in WAL. If after that it gets confirmed and puts the tuple into the list, build-loop will never look at that list again.

Rollbacks seem somewhat better for this approach.

Consider the following situation:

• on_replace(old_tuple, new_tuple) happens to the right of build-cursor'
  • on_replace only checks duplicates
  • updates write_set
• box.commit is called on REPLACE_TXN; the transaction becomes prepared and gets stuck in WAL.
• During that time build-cursor' passes through new_tuple. Since the tuple is prepared, BUILD_TXN reads it and inserts it into the building index.
• Then, if BUILD_TXN gets prepared, everything is fine: even if REPLACE_TXN is rolled back on a WAL error, BUILD_TXN will also be rolled back together with it.
• If REPLACE_TXN rolls back before prepare of BUILD_TXN, then REPLACE_TXN should look at build-cursor and build-cursor': if the tuple is between them, then BUILD_TXN should probably be rolled back. In any case, it will be rolled back automatically because the iterator in build-loop tracked this key while passing through it.

Final variant for solution №2

If we choose the most acceptable options from all the variants above, the algorithm becomes the following:

• BUILD_TXN reads the primary in batches with read-prepared isolation and maintains two cursors:
  • build-cursor: the last position that is guaranteed to be reflected in the building index and completed by previous batches.
  • build-cursor': the current position inside the active batch.
• While reading the batch, BUILD_TXN does not call index_replace immediately. It only accumulates a pending batch. The batch is physically applied to the building index on prepare of BUILD_TXN via a separate txn-level trigger. This is fundamentally important, otherwise it would be hard to roll the batch back correctly on an MVCC conflict or WAL error.
• on_replace to the left of build-cursor immediately calls index_replace. This is the simplest case: build-loop will never return there again, and rollback/confirm can be handled by triggers.
• on_replace between build-cursor and build-cursor' does not call index_replace, but aborts the current BUILD_TXN. After restart, the batch reads that range again, now taking the new version into account, and inserts the correct tuple by itself.
• on_replace to the right of build-cursor' does not call index_replace, but only:
  • checks duplicates;
  • updates write_set;
  • installs triggers on REPLACE_TXN.
• On prepare, REPLACE_TXN compares its primary key with the current build-cursor:
  • if the key is already to the left of build-cursor, then build-loop has already passed that key, and now REPLACE_TXN itself must apply its change to the building index via something like replace_in_progress from solution №1;
  • if the key is still to the right of build-cursor, nothing needs to be done: a future batch will itself see the already prepared/confirmed state and insert the correct tuple.
• On rollback, REPLACE_TXN acts symmetrically:
  • first, it must check whether on_prepare was actually executed for this statement. Trigger state needs a separate flag like "the change was applied from on_prepare".
  • if on_prepare was not executed or returned before calling replace_in_progress, there is nothing to roll back.
  • otherwise on_rollback compares the same primary key pk = primary_key(new_tuple ?: old_tuple) with the current build-cursor:
    • if pk is to the left of or equal to build-cursor, then the change should already have been reflected in the building index, and it must be rolled back via rollback(old_tuple, new_tuple);
    • if pk is to the right of build-cursor, then build-loop either has not yet passed this key, or, if it has, it will be rolled back thanks to MVCC. Nothing needs to be done.

Warning

However, this approach still has at least one unresolved problem, which makes it look questionable.
Suppose BUILD_TXN read some tuple from primary and included it into its pending batch. It does not matter whether this tuple was prepared or already confirmed at read time. What matters is that on prepare, BUILD_TXN wants to physically apply the corresponding insertion to the building index. But if BUILD_TXN itself later rolls back, these tuples must then be rolled back from the new index.
For Vinyl, this is a problem: an inserted confirmed tuple may manage not only to get into vy_mem, but also to be dumped. After that, rollback of BUILD_TXN no longer looks like a normal transaction rollback. It is no longer rollback of a prepared statement performed by the engine.

[Gerold103]

Эта штука как-то адресует проблему блокирующего создания индексов в синхронной репликации?

[Astronomax]

Да.

• Процедура должна выполняться отдельно от DDL транзакции (fiber()->txn == NULL), чтобы в дальнейшем использовать ее в контексте неблокирующего построения https://github.com/orgs/tarantool/discussions/11018.

[Gerold103]

Найс, спасибо!

[Astronomax]

The discussion has been moved to Confluence.