###### tags: `Транзакции`

# Транзакционный DDL

## Ревьюеры
| Реализация | @UNera | @locker | @alyapunov |
|-------------------------| ------ | ------- | ----------- |
|Global Transaction Lock | lgtm* | - | - |
|Space Transaction Lock | - | - | - |
|Transaction Space Cache | - | lgtm | - |
|Versioned Cache | - | - | - |
|Versioned Tuple Pointers | - | - | - |

*Дима за самый простой в реализации вариант. Кажется, что это GTL.

**Justification:**

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

* [Transactional DDL research (create/alter space/index in transaction) ](https://github.com/tarantool/tarantool/issues/600)
* [space:truncate() + space:count() do not work with mvcc](https://github.com/tarantool/tarantool/issues/6007)
* [memtx: make stable DDL operations in mvcc mode](https://github.com/tarantool/tarantool/issues/6138)
* [Test transactional DDL more thoroughly](https://github.com/tarantool/tarantool/issues/4349)
* [Make all box.schema functions transactional](https://github.com/tarantool/tarantool/issues/4348)

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

---

### Введение

*Альтером* (изменением) объекта (схемы) будем называть его создание, удаление или апдейт (обновление).

*DDL операцией* будем считать изменение тапла из следующих системных спейсов:
- _space;
- _index;
- _trucante;
- _user;
- _schema;
- _func;
- _collation;
- _priv;
- _cluster;
- _sequence/_sequence_data/_space_sequence;
- _trigger;
- _fk_constraint;
- _ck_constraint;
- _func_index.

#### Как работает DDL

Любая DDL операция условно состоит из двух шагов: DML операция (`space:replace()`) в соответствующий системный спейс и последующий вызов `on_replace` триггера. До момента вызова триггера весь процесс обработки запроса в целом такой же, как и для любого другого спейса и DML запроса. В `on_replace` триггере же происходит обновление метаданных - исходный тапл парсится и по полученным значениям создается соответствующее новое определение метаданных (`object def`), а затем изменяются и сами объекты, которые лежат в глобальных кешах (`struct space`, `index`, `func` и т.д.). Как правило, изменение объектов метаданных происходит сразу, то есть до коммита операции. На случай если операция по каким-то причинам заканчивается неудачно (например, из-за ошибки записи на диск), устанавливаются `on_commit` и `on_rollback` триггеры. В большинстве случаев, `on_commit` триггер является no-op, так как модификация метаданных и так происходит ДО коммита. `on_rollback` в свою очередь, очевидно, откатывает результат операции. Кроме того, обычно в триггерах так же инкрементируется `schema_version` (но в случае роллбека значение не откатывается).

#### DDL в транзакциях сейчас

На данный момент с выключенным `MVCC` режимом DDL операции возможны в транзакциях только если они не приводят к илдам. Илдить могут две DDL операции: альтер спейса и альтер индекса. Если включить MVCC, то илды разрешены только у первой операции в транзакции; все последующие операции так же не могут илдить (иначе, транзакция абортится). Если параллельно обрабатывается несколько транзакций с илдящими операциями, то транзакция которая первая полностью закончила обработку операции и изменила значение в кеше - побеждает (остальные будут зааборчены).

Отдельно стоит выделить DDL операции относящиеся к спейсам, индексам и пользователям/ролям (`_space`, `_index` и `_priv`/`_user`), так как триггеры и обновление метаданных в них устроены наименее тривиальным способом.

#### space:alter()

Как и почти любой другой `on_replace` DDL триггер, вся логика в нем разбита на три случая: создание, удаление и обновление объекта. Создание и удаление проходят достаточно просто: мы проверяем привелегии, проводим какие-то дополнительные семантические проверки (например, убеждаемся, что у удаляемого спейса нет индексов) и удаляем/вставляем в `space_cache` соответствующий объект (по id). При создании спейса устанавливается `rollback` триггер, который в случае ошибки удаляет объект из кеша и освобождает память. Аналогично при удалении - `rollback` триггер возвращает спейс в кеш. Сложнее обстоит с альтером спейса. У спейса может обновиться имя, формат, `field coun`t и некоторые другие параметры (`user`, `temporary`, `is_sync`). При обновлении формата может понадобиться обновить определения индексов (без их перестроения, по крайней мере в случае мемтикса; винил здесь не затрагивается), check констрейнтов и верифицировать все хранящиеся таплы на предмет соответсвия новому формату. Последняя операция может приводить к илдам. В целом, для альтера создается новый (эфемерный) объект метаданных, который является копией исходного. Данный объект проходит все модификации и в случае успеха подменяет исходный (copy-modify-swap). Для каждой операции обновления создается временный объект `AlterSpaceOp` с соответствующими функциями `prepare`, `commit`, `alter`. Стоит заметить, что объекты спейсов хранятся в двух кешах одновременно: кроме кеша по id существует еще кеш для поиска по имени (`spaces_by_name`). Обновление этих кешей должно быть консистентным.

#### index:alter()

Так же как и в случае со спейсами, наименее тривиальная часть касается именно обновления индексов. В целом, рассматриваются две ситуации: когда нужно полностью перестраивать индекс, и когда можно обойтись только обновлением определения (в последнем случае все равно может понадобиться проверка соответствия таплов новому формату). Операция перестроения (или построения) индекса с помощью итератора проходит по всем таплам первичного индекса и вставляет их поочердено в новый индекс. Так как эта операция может занять много времени, то она илдит каждые `n` обработанных таплов. Если во время илда происходит `replace` уже вставленного в создаваемый индекс тапла, то этот `replace` должен как-то попасть и в новый индекс (несмотря на то, что итератор по первичному индексу уже прошел модифицированный тапл). Для этого на спейс устанавливается `on_replace` триггер, который перенаправляет такие `replace`'ы в новый индекс. В остальном операция похожа на `space:alter()`: точно так же для альтера индекса создается копия исходного объекта, потом происходит его модификация и в случае успеха - swap с оригинальным индексом.

#### priv:alter()

Основная сложность с привилегиями и пользователями заключается в способе их хранения и обновления. Количество пользователей/ролей системно ограничено - их может быть не более 32 (не случайно). Поэтому массив пользователей просто задан в глобальной области видимости (`users`), где нулевой и первый элементы заранее отведены под гостя и админа. Пользователи и роли реализуются за счет одного и того же механизма. Каждый пользователь и роль представлены одной и той же структурой - `struct user` (далее под `user`'ом будет пониматься именно роль или пользователь). В случае роли в структуре хранится мапа (битовый массив) пользователей или ролей, которым данная роль была предоставлена; в случае пользователя или роли - хранится еще мапа из ролей, которые были предоставлены данному объекту. Кроме того, `user` имеет внутренний кеш эффективных привелегий, хранящийся в красно-черном дереве. Каждый `user` имеют уникальный `auth_token` (грубо говоря, позиция в массиве `users`). Во время грантования привилегий мы заново пересчитываем все эффективные привилегии для `user`'a, рекурсивно проходя по графу зависимостей ролей.

## Варианты реализации

### Упрощенные варианты

#### UNera: Global Transaction Lock

Есть предположение, что большинству пользователей параллельный транзакционный DDL вообще не нужен. Необходима лишь возможность выполнить несколько DDL/DML операций в одной транзакции (чтобы можно было атомарно накатить какие-то изменения в схеме данных) - надобности в существовании других транзакций в этот момент нет. Таким образом, задачу можно сильно упростить, введя Global Transaction Lock (GTL - аналог GIL) для транзакций содержащих DDL операции. Транзакция включающая в себя DDL операцию не приступает к выполнению, пока существует хотя бы одна другая открытая (и начавшаяся ДО DDL транзакции) транзакция. Пока такие транзакции есть, файбер в котором выполняется DDL просто илдит; при вызове `box.begin()` в этот момент из других файберов - они отправляются в `sleep` и добавляются в очередь ожидания (будут запущены после окончания работы транзакции с GTL). Как только активных транзакций не остается, транзакция владеющая GTL начинает свое выполнение. Внутри такой транзакции возможны любые операции (DDL, DML) над любыми объектами (спейсы, индексы, пользователи и т.д.) и илды (но при этом файберы, в которых будет обращение в бокс будут сразу засыпать и передавать управление GTL). Выполнение другого кода не связанного с TX потоком разрешается.

DDL операции в автокоммит режиме будут работать как и сейчас. Для того, чтобы начать GTL транзакцию пользователь должен будет указать это в `box.begin()`: `box.begin{type=global/system}`. Операции с DDL в обычных транзакциях запрещаются. Альтернативно можно считать, что транзакция становится GTL как только выполняется первый DDL statement. В этот момент GTL зависает до момента, пока все транзакции не закончатся/отвалятся по таймауту. Можно так же оставить текущее поведение - DDL транзакция в момент модификации какого-либо глобального кеша насильно убивает все остальные транзакции.

Pros:

- Относительно простая и понятная реализация.

Cons:

- При долгих DDL операциях (построение индекса) БД будет зависать;
- DDL транзакции стартуют не сразу - надо дожидаться окончания всех online транзакций (или убивать их насильно);
- Поломка обратной совместимости: если у пользователей был код, где внутри обычных транзакций выполнялся какой-то DDL, то теперь он не будет работать (с учетом нового синтаксиса `box.begin{type=system}` и глобальной блокировки БД);
- Невозможность выполнения нескольких транзакций параллельно (сознательно идем на это упрощение).

Утверждения Димы О.:

- Работа с DDL - крайне редкое явление. `schema_id` на долго работающих серверах редко превышает значения в несколько сотен;
- Ради редких кейзов мутить транзакционный DDL - “стрелять из пушки по воробьям”;
- При транзакционной работе с большим объемом данных (например добавление столбика `not null`), всё равно для пользователя это будет выглядеть как глобальная блокировка.

Какие проблемы надо порешать:

- при невзятом GIL проверка на него должна быть очень дешёвой
- после смены схемы возможно в lua/C сохранятся ссылки на таплы, полученные в предыдущей (предыдущих) схеме, с этим надо уметь жить.

#### Space Transaction Lock

Вместо глобальной блокировки всего TX потока можно попробовать сделать Transaction Lock Per Space: в момент DDL операции над каким-то объектом транзакция помечает его своим ID. При обращении из другой транзакции к такому объекту бросаем ошибку `"object is locked by another transaction"`. Точно так же все on the fly транзакции относящиеся к залоченому объекту или прибиваем, или ждем их окончания. Блокировка снимается в момент коммита/роллбека транзакции. В такой реализации появляется проблема одновременного создания объекта с одним и тем же уникальным ID из двух разных транзакций. В качестве простого решения, можно сделать такие объекты видимые между транзакциями. То есть, даже если транзакция еще не закомичена, но уже добавила новый объект в кеш - он становится видимым для других транзакций (но обратиться к нему они не могут, так как на нем есть блокировка).

Pros:

- Не надо вводить GTL и отправлять файберы в `sleep`/очередь;
- Не надо вводить новый тип транзакций;
- Можно выполнять транзакции параллельно;
- Возможно даже читать из другой транзакции пока спейс залочен (но не понятно надо ли это кому-то).

Cons:
- При построении индекса спейс будет все еще недоступен;
- Наверное нужен какой-то механизм для ожидания снятия блокировки со спейса в случае, когда в одной транзакции надо модифицировать несколько объектов.

### Полноценный транзакционный DDL

#### Транзакционный кеш

Идея заключается в следующем: каждая транзакция хранит у себя локальный кеш с измененными спейсами. Сейчас при альтере в `on_replace` триггере спейса/индекса создается НОВЫЙ объект спейса с пустыми (возможно измененными) индексами и (возможно) новым форматом/именем. Индексы, которые при альтере не требуют перестроения просто переносятся в новый спейс (pointers swap); те, которые требуют перестроения - строятся заново. После этого новая копия спейса замещает в кеше старый объект. Во время коммита старая копия удаляется; при роллбеке индексы/формат возвращаются на место. Тогда для реализации транзакционного DDL достаточно сказать, что объекты хранящиеся в глобальном кеше - это закомиченные изменения, а спейсы в локальном кеше транзакции- это uncommitted changes. Во время коммита мы синхронизируем транзакционный кеш с глобальным (просто замещаем спейсы из глобального - локальными изменениями). При этом в каждом спейсе храним `schema_version`, при несовпадении версий имеем конфликт. Альтернативно можно при коммите DDL транзакции сразу абортить все другие делающие изменения в данном спейсе.

`space_by_id()` будет выглядеть следующем образом:

struct space *
space_by_id(uint32_t id)
{
	struct txm *tx = in_txn();
	mh_int_t space;
	if (tx != NULL) {
		space = mh_i32ptr_find(tx->spaces, id, NULL);
		if (space != mh_end(tx->spaces))
			return (struct space *) mh_i32ptr_node(tx->spaces, space)->val;
	}
	space = mh_i32ptr_find(spaces, id, NULL);
	if (space == mh_end(spaces))
		return NULL;
	return (struct space *) mh_i32ptr_node(spaces, space)->val;
}

При этом на исходный спейс вешается on_replace триггер, который форвардит DML запросы в спейсы, которые находятся в локальных кешах. Если replace несовместим с форматом локального спейса (по типам или уникальности ключей), то транзакцию проводящую такую DDL операцию абортим (так как `on_replace` триггер форвардит только закомиченные операции, то это не критично - DML точно уже будет несовместим со схемой в транзакции и она будет и так конфликтной). Кроме того, так как копии спейсов содержат ссылки на оригинальные индексы, то необходимо вводить `reference counter`'a в индексах (или абортить все активные относящиеся к спейсу транзакции).

Pros:
- Код в alter.cc хорошо спроектирован под данную реализацию;
- Практически полноценный транзакционный DDL, который можно совмещать с DML;
- Отсутствие блокировок и возможные проблем с ними (например, deadlock'и);
- Не надо абортить активные транзакции до момента коммита DDL.

#### Версионированный кеш

Вместо поиска по `object_id` в кеше, мы ищем по `object_id + tx_id`. То есть, в момент когда транзакция модифицирует какой-то объект метаданных, она создает его полную или частичную копию и добавляет в свой список. Например, реализация `object_by_id()` может выглядеть как:

void *
object_by_id(uint32_t id)
{
	void *head = object_cache_find_by_id(id);
	if (head == NULL)
		return NULL;
	foreach_entry(obj, head, in_objects) {
		if (obj->tx_id == in_txn()->id)
			return obj;
	}
	assert(head->tx_id == 0);
	return obj;
}

void *
object_by_id_committed(uint32_t id)
{
	return object_cache_find_by_id(id);
}

В целом, общий враппер для всех объектов метаданных может выглядеть так:

struct txm_ddl_object {
	uint32_t id;
	uint32_t tx_id;
	uint32_t schema_version;
	rlist next;
	bool is_deleted;
	void *object;
}

 committed 
+----------+   +-----------+   +-----------+
| tx_id = 0|-->| tx_id = x |-->| tx_id = y |
+----------+   +-----------+   +-----------+

Закомиченный объект будет хранится в голове списка и иметь нулевой `tx_id`. Кроме того, в каждом объекте будем хранить версию на момент модификации объекта. Для упрощения будем считать, что если на момент коммита версия закомиченного объекта больше, чем объекта который будет закоммичен, то такую ситуацию считаем конфликтной и откатываем транзакцию:

if (schema_version(object_by_id_committed(obj->id)) > schema_version(obj))
    txn_abort();

Если версии совпадают (а это значит, что никакая другая транзакция не провела закомиченной модификации объекта), то мы обнуляем `tx_id` у соответствующего объекта и инкрементируем его версию. На момент модификации объекта мы создаем его полную или частичную копию и добавляем его в список с соответствующей id транзакции и текущей версией. В случае роллбека мы просто удаляем объект из списка и освобождаем память. Если объект удаляется DDL операцией, мы добавляем его в список с флагом `is_deleted`. Если в этой же транзакции происходит создание объекта с таким же id, то удаленный объект все так же остается в списке, само удаление мы откладываем до коммита. При этом DML операции из текущей транзакции мы уже применяем по отношению к новому объекту, в то время как операции из других транзакций - к оригинальному (или локальной копии в случае модификации).

Pros:
- Нет оверхеда при выключенном MVCC; почти нет оверхеда при отсутствии DDL операций при включенном MVCC;
- Реализация версионированного кеша не пересекается с кодом MVCC.
- Интуитивно понятный механизм работы.
- Вводить транзакционные операции можно по-частям, переделывая кеши объектов метаданных по очереди.

#### Метаданные в таплах

Альтернатива версионированному кешу - хранить метаданные прямо в таплах системных спейсов. То есть указатель на соотвествующий объект метаданных будет лежать в конце тапла, после полезной нагрузки. Тогда для того чтобы получить указатель на соответствующий объект метаданных надо будет сделать лукап тапла в спейсе и получить указатель на объект как ```tuple_data() + tuple_bsize()```:

+-------------------+-------------+------------+
| offN | ... | off1 | MessagePack | MetaData * |
+-------------------+-------------+------------+

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

extern struct space *_space;

struct space *
space_by_id(uint32_t id)
{
    struct index *pk = _space->index[0];
    char key[4];
    mp_encode_uint(key, id);
    struct iterator *it = index_create_iterator(pk, ITER_EQ, key, 1);
    struct tuple *tuple;
    if (iterator_next(it, &tuple) != 0)
        return NULL;
    return (struct space *) (tuple_data(tuple) + tuple_bsize(tuple));
}

Аналогичным образом можно написать реализацию `space_by_name()` и геттеров для других системных спейсов.

Тут мы можем полностью избавиться от спейс кеша; вместо этого поддерживаем указатели в таплах в консистентном состоянии после выполнения DDL операций в `on_replace` триггерах. Во время бутстрапа MVCC вообще можно считать выключенным, поэтому тут никаких изменений. Основной плюс данной реализации - она отлично ложится на MVCC. Если транзакция проводит DDL операцию и модифирует тапл в системном спейсе, то она автоматически будет видеть только свои изменения. Конфликтные ситуации так же будут разруливаться автоматически самим транзакционным движком.

Pros:
- Универсальный подход, будет работать со всеми DDL операциями одинаково;
- Хорошо ложится на текущуюю реализацию MVCC;

Cons:
- Доступ к `struct space` в этом случае будет медленее (надо бенчать, но лукап в одной хештаблице явно быстрее, чем поиск тапла по спейсу). То есть потенциальное замедление доступа к метаданным даже при выключенном MVCC.

### Ожидаемое поведение

Вне зависимости от выбранной реализации, поведение при выполнении транзакционных DDL операций подразумевается одинаковым.

#### _space

При создании двух спейсов с одинаковым `space_id`, first to be committed wins (как и при любой другой MVCC транзакции). Все остальные транзакции лучше абортить сразу (при коммите первой транзакции), так как иначе придется как-то обрабатывать DML запросы относящиеся ко спейсам с этим id (при вставке в закомиченный спейс нам незачем форвардить эту операцию в спейс, который обречен; более того, данная операция только приведет к лишним конфликтам, которых можно избежать - например, если у создаваемых спейсов разные форматы).

Во время удаления спейса помечаем его tombstone (`is_deleted`) в соответствующей транзакции; далее действуем так, как будто объекта уже нет (`object_by_id()` возвращает NULL).

Незакомиченные изменения формата будут так же видны другим транзакциям. Так что если одна online транзакция меняет формат, в другой транзакции невозможно вставить тапл неудовлетворяющий хотя бы одному из форматов in-progress транзакций.

`create_space("t")`
**X** - операция невозможна
**Y** - операция возможна

| TX1 | autocommit |
| -------- | -------- |
| create_space("t") **X** | - |
| drop_space("t") **Y** | - |
| create_space("t") **Y** | - |
| - | drop_space("t") **Y** |
| commit() **X** | - |

| TX1 | autocommit |
| -------- | -------- |
| create_space("t") **X** | - |
| - | drop_space("t") **Y** |
| create_space("t") **Y** | - |
| - | create_space("t") **Y** |
| commit() **X** | - |

| TX1 | autocommit |
| -------- | -------- |
| alter_format(format1) **Y** | - |
| - | insert({"doesn't fit format1"}) **X** |
| - | alter_format(format2) **Y** |
| insert({"doesn't fit format2"}) **X** | - |
| commit() **X** | - |

#### _index

При изменении констрейнтов другие транзакции так же видят данные изменения (как и в случае с форматом спейсов). Это необходимо, так как таплы нужно вставлять во все индексы, даже если их создание или альтер не были закомиченны. Поэтому вставляемые данные должны удовлетворять всем форматам. При этом при необходимости (например, при добавлении новых key parts или изменении уникальности индекса) мы создаем новую копию индекса и полностью его перестраиваем. Изменения уже перенесенных таплов из первичного индекса нам все так же нужен `on_replace` триггер. Только теперь таплы которые он форвардит сразу помечаются как `dirty` и для транзакции они уже не видны. При удаления индекса он помечается tombstone, но остается в списке индексов до операции коммита.

#### _priv

Из-за иерархического устройсвта ролей и пользователей кажется, что самый простой и рабочий вариант - хранить внутри каждой транзакции копию всех (по-крайней мере активных) пользователей и привилегий. То есть, при первой модификации внутри транзакции пользователей, мы копируем всю иерархию пользователей. Это может оказаться долго и дорого по памяти; с другой стороны - операция редкая и специфичная. Во время коммита, соответственно заменяем на обновленные значения. Возможно пока вообще запретить изменение привилегий внутри транзакций.

### Прочее

Отдельная проблема - создание Луашных оберток для транзакционных DDL операций: [Make all box.schema functions transactional](https://github.com/tarantool/tarantool/issues/4348)

### Проблема приоритета

Боюсь, что если мы сделаем транзакционный кэш - этого будет мало. Насколько я понимаю, пользователи хотя делать online DDL + mass DML, а поскольку DML может приводить к конфликтам, а приоритет у транзакций в порядке коммита - DDL+mass DML всегда будет отваливаться.

Есть предположение, что нам придется сделать что-то вроде приоритетной транзакции. Но с другой стороны тогда массово начнут отваливаться все остальные транзакции.

### Проблема памяти

С глобальным локом можно складировать undo/redo лог на диск. Но в онлайне такое не получится. А значит это double памяти, и совершенно непонятно, как сделать транзакцию online DDL + mass DML в виниле.

### TODO

Надо собрать несколько use кейсов, который хотят реальные пользовали, и что они ожидают от Решения. После этого мы должны понять, какие кейсы мы можем решить (и как!), а какие-нет. Нужно обсуждать У меня сложилось ощущение, что все наши space cache им не помогут.