[WIP] RFC: Index Build 4.x

[Astronomax]

Ревьюеры

• Основной ревьюер: @drewdzzz
• Второй ревьюер: @locker
• Тимлид: @sergepetrenko
• CTO: @sergos

Проблема

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

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

В Vinyl, прежде чем начать построение нового индекса, вызывается journal_sync(), чтобы дождаться CONFIRM на все prepared транзакции. В Memtx этого не происходит, поэтому возможна ситуация, при которой основной цикл построения вставит prepared (не confimed) тапл, который, например, висел в WAL-очереди еще до начала построения, и он не будет удален из индекса при откате на WAL-failure. То есть нам хотелось бы, чтобы если что-то и могло откатывать то это только параллельные транзакции, возникшие уже после того, как началось построение индекса.

На самом деле journal_sync() здесь будет мало, потому что есть еще несколько мест, где транзакция может повисать - очередь перед WAL, limbo, очередь перед limbo, возможно уже что-то еще.

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

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

Проблема имеет те же последствия, что и предыдущая - после отката транзакции тапл остается в индексе. В отличие от предыдущего тикета здесь проблема связана с теми таплами, которые возникли в процессе построения и попали правее курсора. На такие таплы не заводится rollback-триггер, поэтому никто не заберет эти таплы из строящегося индекса, если соответствующие им транзакции вдруг откатятся.

В качестве возможного решения можно было бы всегда вешать rollback-триггер независимо от того, по какую сторону от курсора находится тапл в момент вызова on_replace, при этом добавить в этот триггер логику, которая проверяла бы, прошел ли курсор по данному таплу к моменту отката, и если прошел, то производила бы соответствующий откат в строящемся индексе.

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

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

Эта проблема уже упоминалась выше: если в Memtx нет даже journal_sync() перед началом построения, то в Vinyl он есть, но оказывается, что его недостаточно, поскольку кроме WAL есть и другие очереди, в которых может висеть транзакция, прежде чем станет confirmed.

memtx: crash when building index with mvcc

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

Проблема заключается в том, что memtx_tx_invalidate_space по сути допускает неверное предположение о том, что можно просто взять и удалить из MVCC-стейта всю дополнительную информацию (в частности memtx_story), связанную с prepared транзакциями.

memtx_tx_invalidate_space сейчас делает следующее:

• удаляет все цепочки (все memtx_story) связанные с определенным спейсом
• откатывает все in-progress транзакции
• обновляет индексы таким образом, чтобы в них содержался актуальный стейт, т.е. таплы последних prepared/confirmed транзакций.

Так, конечно, делать нельзя сразу по многим причинам.

Например, представим, такую ситуацию:

• WAL долго находится в ожидании чего-то. В очереди на запись находится prepared транзакция txn.
• В это время случается какой-то DDL, который инвалидирует спейс (memtx_tx_invalidate_space). Он даже может не коммититься и не попадать в очередь WAL - достаточно будет просто box.begin() DDL() box.rollback().
• В результате в индексе отстается тапл tuple prepared транзакции txn. При этом связанная с ним story удалена, а вместе с ней потряна связь между таплом и соответствующим стейментом stmt транзакции txn.
• В это время приходят новые in-progress транзакции, которые выполняют replace с ключом из тапла tuple (первичным или вторичным - не важно). Для тапла tuple снова создается стори story', которая на этот раз уже не содержит ссылку на стейтмент stmt. При этом все эти реплейсы фактически применяются к индексу сразу, так чтобы сохранять инвариант, что верхушка цепочки физически находится в индексе

  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
  	* |- - - - - - - -|— — — — — -| — — — — —|— — — — — — -|— — — — — — — —

  .
• Новые in-progress стори выстраиваются в конец цепочки сразу после story'.
• txn откатывается. Откат выполняется через rollback_empty_stmt (т.к. ссылка на stmt отсутствует), который просто неглядя пореплейсит в индексе rollback_info->new_tuple на rollback_info->old_tuple.
• В итоге как минимум нарушается основной инвариант о том, что верхушка цепочки физически находится в индексе. Это в свою очередь приведет к тому, что, например, потеряется доступ к цепочке, из-за чего дальше поломается все что угодно.

В тикете приведен немного другой пример. Вместо того, чтобы выстраивать новые цепочки из in-progress стори, начиналось построение нового индекса. Как
ни странно, даже в этом случае у нас есть определенные проблемы. Потому что откат prepared стори не заметит никто опять же потому, что после memtx_tx_invalidate_space эта стори больше не связана со своим add_stmt стейтментом. В итоге тапл, успели вставить в строящийся вторичный индекс, а затем на ролбеке откатили его только из первичного. При этом несмотря на то, что в стори был добавлен соответствующий read-трекер, построение вторички не заабортилось опять же потому, что нет связи stmt -> story.

Только confirmed стори можно совсем безопасно безо всякой дополнительной логики отсоединить от add_stmt.

Одним из возможных решений этой проблемы было бы - при откате такого prepared стейтмента аборитить сначала все связанные in-progress транзакции, например, прямо из rollback_empty_stmt.

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

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

Проблема заключается в том, что процедура построения индексов в Vinyl пропускает некоторые сценарии, при которых возможно возникновение дубликатов в строящемся уникальном индексе. Проверка уникальности выполняется в двух местах:

• при вставке confirmed тапла tuple возникшего до построения (vy_stmt_lsn(tuple) <= build_lsn)
• и в on_replace триггере при обработке параллельных in-progress транзакций

В обоих случаях проверка устроена одинаково - vy_get в строящемся индексе по соответствующему ключу тапла tuple и сравнение первичного ключа tuple и того, что было прочитано vy_get. В первом случае изоляция - p_committed_read_view (т.е. READ_CONFIRMED), во втором vy_tx_read_view(tx) (т.е. в соответствии с уровнем изоляции in-progress транзакции, для который сработал on_replace). Оба выглядят странно.

В приведенном там репродьюсере происходит следующее:

• Цикл построения вставляет {1, 1}, йилдит.
• in-progress транзакция txn выполняет replace{3, 2}, проверяет дубликаты, ничего с ключом 2 не обнаруживает.
• txn коммитится, становится prepared, повисает в WAL.
• Построение продолжается, вставляет {2, 2}. Выполняет vy_get в p_committed_read_view, опять же ничего с ключом 2 не обнаруживает, потому что {3, 2} ещё не записался в WAL.
• Построение коммитится, тоже повисает в WAL.
• Оба txn и построение успешно записываются в WAL.

Кажется, что достаточно было бы изменить p_committed_read_view на p_global_read_view при вставке в цикле, чтобы пофиксить конкретно этот класс сценариев. Но возможно также стоило бы использовать p_committed_read_view и при проверке в on_replace для in-progress параллельных транзакций - я не проверял, но скорее всего можно воспроизвести проблему, если последовательно один за другим вставить два дубликата параллельно с построением индекса при заторможенном WAL. Все остальные ситуации обрабатываются в том числе благодаря двум вещам:

• Построение индекса завершается инвалидацией спейса и абортом всех in-progress транзакций на спейсе.
• Когда in-progress транзакция становится prepared, Vinyl итерируется по ее write_set и абортит все in-progress вставки с тем же ключом.

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

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

Построение Memtx индекса с MVCC, если опустить лишние детали, выглядит в данный момент следующим образом:

• Вызывается index_count, чтобы проверить, что индекс не пустой. index_count оставляет некоторые свои трекеры (gap_item_type = GAP_COUNT), чтобы гаранитровать корректность этого чтения.
• Создается итератор по основному индексу, который вставляет таплы в новый индекс. Этот итератор читает только таплы prepared транзакций и трекает все прочитанные ключи, а также интервалы между ними.
• Если теперь какая-либо параллельная транзакция выполнит replace в спейсе и закоммитится, построение индекса заабортится. Кажется, даже не важно, по какую сторону от курсора случится этот реплейс.

Таким образом, любая небольшая параллельная операция записи абортит долгую операцию построения индекса. Хочется, чтобы новая процедура построения индекса с MVCC позволяла совершать параллельные операции, чтобы это как можно реже приводило к аборту построения.

Требования

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

Возможное решение №1 (Антон Кузнец @Astronomax)

У этого решения даже есть реализация, которая проходит тесты и репродьюсеры из тикетов. На самом деле стоит сказать, что существующие в данный момент тесты слабо покрывают построение индексов.

Полностью красиво избежать специфических деталей, связанных с конкретными движками, при данном подходе, к сожалению, не получилось, далее обсудим, почему.
Поэтому процедура принимает от движка vtab с методами:

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

Далее увидим, для чего они нужны, и как реализованы в Memtx и Vinyl.

В общем предлагаемая процедура похожа на ту, которая работает сейчас в Memtx:

• Устанавливается on_replace для обработки параллельных replace. Основная причина, по которой он будет необходим - поиск дубликата в индексе Vinyl. Что именно он делает, и какая в нем необходимость, обсудим далее.
• При необходимости дожидается CONFIRM на все prepared транзакции, висящие в различных очередях: txn_limbo_flush, journal_sync. Примерно так же, как здесь:

  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);

• Запускается итератор по PK (ITER_ALL) и в цикле (далее будем называть "build-loop") вставляет таплы в индекс, периодически отдавая управление. Поскольку активная транзакция в файбере в этот момент отсутствует, итератор не оставляет никаких трекеров или чего-то подобного. В обоих случаях Memtx и Vinyl итератор читает prepared таплы. На самом деле, как мы увидим далее, даже с read-committed (read-prepared) изоляцией, цикл будет пропускать prepared таплы, поэтому, даже если итератор сам по себе будет читать только confirmed, это не сломает корректность.
• Когда итератор доходит до конца, происходит некоторая финализация vtab->finalize, необходмая пока только в Vinyl, обсудим дальше, что это такое.
• Отключаются все stmt-level триггеры накопленные к этому моменту, а также on_replace триггер.
• Инвалидируется спейс - абортятся все in-progress транзакции на спейсе. Важно: между этой инвалидацией и предыдущим пунктом не должно быть yield.

В процессе будут поддерживаться несколько структур:

• processed - мн-во ключей, которые build-loop должен пропустить, потому что их консистентность гарантируют stmt-level триггеры.
  Представим, что параллельно с build-loop происходит replace{tuple}, т.ч. tuple оказывается правее текущего положения курсора. Можно было бы отложить вставку таких таплов (сделать это ответственностью build-loop), как это реализовано сейчас.
• write_set (только для unique индексов) - нечто аналогичное write_set в Vinyl, маппинг build_key -> txn set. Можно сказать, что это мн-во "write points" параллельных транзакций. "write point" - это пара (key, txn), которая создается в момент, когда параллельная транзакция txn вставляет tuple, т.ч. build_key(tuple) = key. Используется для того, чтобы абортить конфликтующих in-progress writer-ов, и тем самым избегать дубликатов.
• not_confirmed (только для unique индексов): key -> int. Его назначение будет рассмотрено дальше.

on_replace:

• Проверяется валидность new_tuple для нового формата индекса.
• Для unique индекса выполняется проверка дубликатов - result = building_index.get(build_key(new_tuple)) и сравнение result == old_tuple. Если находится какой-то тапл result, отличный от old_tuple - это дубликат, new_tuple вставлять нельзя. В этом случае replace в транзакции завершается ошибкой, build-loop продолжает работать.
• Если проверка уникальности прошла успешно, во write_set добавляется (build_key(new_tuple), txn).
• На statement вешаются триггеры before_commit, on_commit, on_rollback.

before_commit (on_prepare):

• Вычисляется pk = primary_key(new_tuple ?: old_tuple).
• Далее нужно понять, находится ли уже old_tuple в индексе, чтобы корректно выполнить vtab->replace_in_progress. old_tuple уже находится в индексе:
  • Если pk $\in$ processed.
  • Если pk находится левее или ровно на build-курсоре - build-loop прошел через pk.
• Для unique индекса выполняется not_confirmed[build_key(old_tuple)]++. Назначение not_confirmed обсудим ниже, пока пропускаем.
• vtab->replace_in_progress(old_tuple or NULL, new_tuple).
• Если pk был правее курсора, pk добавляется в processed. Теперь build-loop пропустит этот PK и не продублирует уже примененное изменение.
• Для unique индекса соответствующий "write point" удаляется из write_set, т.к. транзакция перестала быть in-progress.
• Для unique индекса абортятся все остальные in-progress writer-ы из write_set по ключу build_key(new_tuple).
• Любая ошибка в триггере означает ошибку построения индекса - абортится build.

on_rollback:

• Если statement откатился в состоянии in-progress (не вызвал box.commit):
  • Из write_set удаляется соответствующий "write point".
• Иначе, если prepare к этому моменту уже успел выполниться:
  • Cоответствующий "write point" уже был удален в on_prepare.
  • Проверяется валидность old_tuple для нового формата индекса. Потому что возможно такое, что old_tuple был закоммичен до начала построения и для него никогда еще ни разу не выполнялась эта проверка.
  • Для unique индекса абортятся все in-progress writer-ы из write_set по ключу build_key(old_tuple).
  • Для unique индекса выполняется not_confirmed[build_key(old_tuple)]--. Назначение not_confirmed обсудим ниже, пока пропускаем.
  • vtab->rollback(old_tuple, new_tuple). Откатывает изменения, внесенные ранее из replace_in_progress: удаляет new_tuple, возвращает old_tuple. Что это означает для каждого конкретного движка, обсудим позже.
• Понятно, что при любой ошибке в триггере, не остается ничего другого, кроме как заабортить build.

on_commit (on_confirm):

• Снимаются все соответствующие stmt-level триггеры.

build-loop:

• Перед обработкой очередного tuple он очищает из processed ключи, лежащие строго левее текущего tuple.
• Если текущий tuple найден в processed, build-loop пропускает его целиком: этот PK уже был обработан через on_prepare/on_rollback.
• Проверяется валидность tuple для нового формата индекса.
• Для unique индексов выполняется проверка дубликатов. Если дубликат в индексе обнаружен, не остается ничего другого, кроме как забортить build.
• Проверяется not_confirmed[build_key(tuple)] == 0. Если > 0, построение абортится. Пока не говорим, почему.
• Для unique индекса абортятся все in-progress writer-ы из write_set по ключу build_key(tuple).
• vtab->replace_confirmed(tuple).
• Build-курсор сдвигается вперед.
• sleep(0) на каждый N-ой итерации.

Note

Важно учитывать, что некоторые триггеры могут йилдить. За время, пока файбер триггера "suspended", build-loop может успеть дойти до конца или заабортиться и освободить ресурсы, которые нужны триггеру. Это стоит учитывать при реализации.

Что такое not_confirmed, какую задачу решает?

К этому моменту может показаться, что всего того, что описано выше, достаточно для того, чтобы обеспечить корректное поведение на всем мн-ве возможных сценариев, однако есть еще как минимум одна проблема:

Представим себе ситуацию:

• Memtx MVCC либо Vinyl.
• В первичном индексе лежат таплы {1, 1}, {2, 2}, {3, 2}
• Build-loop останавливается на тапле {1, 1}
• Параллельно происходит replace{3, 3} в REPLACE_TXN, идет на запись в WAL и там зависает
• Build-loop просыпается, вставляет {2, 2} и засыпает. В предположении, что проверка дубликатов читает с read-committed (read-prepared) изоляцией, дубликат {3, 2} не обнаружатся ({3, 3} в этот момент уже prepared).
• Случается WAL error и REPLACE_TXN откатывается в {3, 2}. В этот момент необходимо проверить дубликаты, чтобы обнаружить пару дубликатов {2, 2},{3, 2}. Самое очевидное - выполнить get по ключу 2 в индексе. Однако в случае Vinyl есть проблема - get поилдит, что недопустимо при ролбеке.

При внимательном рассмотрении оказывается, что подобные "конфликты" (дубликаты) возникают именно между вставкой из основного цикла и параллельной вставкой из транзакции. Две вставки из основного цикла и даже, что не так очевидно, параллельные вставки из транзакций не создают такой проблемы между собой. Ниже обсудим, почему.

Несколько возможных решений этой проблемы:

• Build-loop заворачивает вставку тапла (каждого отдельно или некоторого батча) в транзакцию BUILD_TXN. Причем транзакция должна что-нибудь записать, чтобы пройти через WAL (например какую-то статистику в _index_local, чтобы не выглядело костыльно). Тогда с приведенным выше сценарием все нормально - BUILD_TXN откатится каскадно вместе с REPLACE_TXN. Но что, если REPLACE_TXN откатится до того, как BUILD_TXN вызовет box.commit (станет prepared)? К счастью, в том числе для таких ситуаций в процедуре предусмотрен write_set, благодаря которому REPLACE_TXN заабортит BUILD_TXN. Этот вариант как раз встретится дальше в возможном решении №2.
• При вставке {2, 2} из основного цикла проверять дубликаты дважды: один раз с изоляцией read-committed, второй с read-confimed. В on_replace достаточно будет одной проверки с on_replace. То есть, если перед началом построения были дубликаты, то построение может завершиться успешно только, если все они каким-то образом будут replaced до того, как до них дойдет build-курсор.
• not_confirmed. При переходе транзакции из in-progress в prepared инкрементировать счетчик not_confirmed[build_key(old_tuple)]++, а при переходе из prepared в confirmed/rollbacked - декрементировать. При вставке из build-loop проверять not_confirmed[build_key(tuple)] == 0. В приведенном выше сценарии в момент prepare replace{3, 3} выпонится not_confirmed[2]++. А далее build-loop попытается вставить {2, 2}, но т.к. not_confirmed[2] > 0, заабортит построение.

Ключевое различие в модели Memtx и Vinyl

Прежде чем рассмотреть vtab для обоих движков, стоит проговорить одно важное различие между Memtx и Vinyl.

В Memtx изменение индекса - это по сути немедленное изменение соответствующего дерева. Если в строящийся индекс из on_prepare был вставлен new_tuple, то при rollback его нужно так же явно удалить из этого дерева и при необходимости вернуть old_tuple. Поэтому в Memtx rollback - это index_replace в обратную к replace_in_progress сторону.

В Vinyl модель другая. Там изменение не переписывает индекс на месте, а дописывается в последовательность statement-ов (INSERT/REPLACE/DELETE/UPSERT), которые сначала живут в vy_tx и его write_set, а затем на prepare попадают в vy_mem соответствующего LSM через vy_lsm_set(). На confirm они подтверждаются через vy_lsm_commit_stmt(), а при rollback prepared-транзакции движок сам удаляет их из vy_mem через vy_lsm_rollback_stmt(). То есть в Vinyl rollback prepared writer-а обрабатывается полностью на стороне самого движка, а не снаружи.

Поэтому replace_in_progress для Vinyl и Memtx выглядят по-разному в реализации:

• В Memtx мы напрямую меняем строящийся индекс, как структуру.
• В Vinyl мы только добавляем в vy_tx statement-ы для строящегося LSM: surrogate DELETE для old_tuple и INSERT для new_tuple. Дальше их жизненным циклом управляет уже сам Vinyl.

Получается, что в Vinyl rollback в vtab может быть Noop, потому что фактический откат делает не index_build, а vy_tx_rollback() / vy_lsm_rollback_stmt().

В таком виде vtab получается следующим:

• replace_confirmed(index, tuple): вставка confirmed тапла tuple из build-loop.
  • Memtx: index_replace(index, NULL, tuple, DUP_INSERT).
  • Vinyl: прямая вставка statement-а в строящийся LSM (vy_build_insert_tuple()).
• replace_in_progress(index, old_tuple, new_tuple): обработка параллельной транзакции, вызывается из on_prepare.
  • Memtx: index_replace(index, old_tuple, new_tuple, DUP_REPLACE_OR_INSERT).
  • Vinyl: запись соответствующих statement-ов в vy_tx для строящегося индекса: DELETE(old_tuple) и/или INSERT(new_tuple) через vy_tx_set(). Дальше эти statement-ы на prepare будут записаны в vy_mem, а затем либо confirmed, либо откачены средствами Vinyl.
• rollback(index, old_tuple, new_tuple): откат параллельной prepared транзакции.
  • Memtx: явная обратная операция, по сути index_replace(index, new_tuple, old_tuple, ...).
  • Vinyl: Noop, потому что rollback prepared statement-ов уже выполняется движком при vy_tx_rollback().
• finalize(index): финализация, необходимая только Vinyl.
  • Memtx: Noop.
  • Vinyl: инициировать dump нового LSM, чтобы построенный индекс не пришлось пересобирать при recovery.

Возможное решение №2 (Андрей Саранчин @drewdzzz)

Начнем рассмотрение с основного каркаса - с того, что точно хотелось бы включить в это решение, а дальше различные дополнительные решения будем рассматривать и принимать по ходу.

Во-первых, build-loop теперь будет заворачивать вставку целого батча таплов в транзакцию BUILD_TXN.
Примерно эта транзакция могла бы выглядеть таким образом:

• box.begin()
• Цикл по некоторому отрезку primary:
  • Получает очередной тапл tuple из итератора pk_iter. Memtx/Vinyl MVCC будут отслеживать, что прочиталось в этом месте.
  • Проверка дубликатов
    • res = index.get(build_key(tuple)) <------------- ???
    • Проверка res == NULL
    • Если обнаружили дубликат в этом месте, абортим построение.
  • Во write_set добавляется (build_key(tuple), BUILD_TXN)
  • index_replace. Нетранзакционный. Т.е. не попадает в stmts транзакции. В принципе будет странно и даже не очень понятно, как бы он мог быть транзакционным. Здесь вставка происходит только в один индекс, и ролбек соответственно, тоже при необходимости нужно будет осуществить только в одном этом индексе, в то время как REPLACE-statement означает атомарную вставку в спейс в целом (во все его индексы). А если это не statement, тогда не понятно, как эту вставку откатывать, если вдруг откатится BUILD_TXN, например, по конфликту с параллельной транзакцией. Для этого придется, видимо, пригородить что-то дополнительное в build-loop.
  • pk_iter.next().
• Транзакция должна что-нибудь записать, чтобы пройти через WAL, чтобы иметь каскадный роллбек. Например, в этом месте можно обновить прогресс в _index_local.
• box.commit()

Warning

Еще одну важную вещь я заметил, пока писал пункт про index_get(build_key(tuple)). Конкретно в реализации решения №1 используется index_get_internal, который в Memtx реализован таким образом (memtx_tree_index_get_internal), что при включенном MVCC он еще дополнительно ищет по цепочке видимую для читающей транзакции версию (memtx_tx_tuple_clarify). Но проблема в том, что Memtx MVCC не обрабатывает строящиеся индексы, т.е. не поддерживает для них цепочку версий и разрешение конфликтов. Если вызывать index_get_internal на строящемся Memtx индексе, то Memtx MVCC попытается проитерироваться по цепочке. Здесь он обратится к story->link[index->dense_id], которого нет (link аллоцированы в предположении, что индекса с таким dense_id еще не существует), и получится segfault. В предложенном решении №1 этого не происходит по счастливой случайности. Там все чтения index_get_internal делаются с read-prepared (is_prepared_ok = true) изоляцией, а все параллельные вставки происходят именно в on_prepare (before_commit). То есть index_get_internal всегда вызывается в момент, когда в индексе лежит видимый prepared тапл, поэтому цикл всегда завершается на первой же итерации, ни разу не обратившись к link[index->dense_id]. Вообще, что в решении №1, что в решении №2 нам нужен просто сырой get в структуре, без всякого итерирования по истории, поэтому скорее всего придется просто поменять что-то в интерфейсе engine_vtab, чтобы там появлился сырой get (просто обертка над memtx_tree_find). Но опять же для Vinyl это будет выглядеть странно, потому что там все совсем по-другому. Не так уж понятно, что такое "сырой" get для Vinyl. В vinyl история в каком-то смысле отслеживается даже для строящегося индекса. В Vinyl есть свои внутренние statemtents на каждый индекс отдельно. Как только параллельная транзакция добавляет Vinyl-statement (building_index:REPLACE()) изменение попадает в историю. Для Vinyl этот get можно было бы определить как get с изоляцией read_prepared, т.е. "get last tuple in index history".

on_replace для параллельных транзакций:

• Проверка дубликатов в индексе.
• Во write_set добавляется (build_key(tuple), BUILD_TXN)
• index_replace. Нетранзакционный для Memtx MVCC - имеется ввиду, что Memtx MVCC в текущем своем виде не выстраивает историю изменений для строящегося вторичного индекса, не ослеживает дубликаты, конфликты, связанные со строящимся вторичным индексом. Насчет

Одним из минусов решения №1 является то, что параллельная вставка справа от курсора оставляет флаг в мапе processed, откуда дальше этот флаг удалится только, когда курсор пересечет соответствующий первичный ключ. То есть флаг появляется в on_prepare и дальше не удаляется ни в on_confirm ни в on_rollback. Таким образом, это в худшем случае O(кол-во транзакций, случившихся параллельно с построением) дополнительной памяти. Хотелось бы справиться хотя бы за O(макс. кол-во одновременно активных in-progress/prepared транзакций). Если это принципиально, можно будет вынести в требования выше. На самом деле не совсем понятно, почему это важно, ведь пропорциональное кол-во памяти все равно будет выделено под соответствующие таплы.

Поэтому здесь хотелось бы вернуть старый подход, и вставлять в триггерах только то, что попадает левее курсора, тем самым избежать дополнительных пометок в виде processed.

[Gerold103]

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