=====Многоверсионность MVCC =====

 

**Многоверсионность** (multiversion concurrency control) -- один из возможных способов организации доступа к данным. Из четырех классических требований ACID к управлению транзакциями этот механизм имеет непосредственное отношение к атомарности (транзакция либо выполняется полностью, либо полностью отменяется), согласованности (транзакция сохраняет целостность данных) и изоляции(одновременно выполняющиеся транзакции не должны влиять друг на друга).

Механизм состоит в поддержке на низком уровне одновременно нескольких версий данных. Транзакции не видят этого; они работают соснимком, который из многих версий составляет согласованную на определенный момент времени картину данных. В зависимости от уровня изоляции, снимок может определяться в момент начала транзакции (уровени repeatable read, serializable) или отдельно для каждой операции (уровень read committed).

Таким образом, транзакции смотрят на данные через призму снимков и могут видеть разную (но согласованную) информацию. Разумеется, снимок не является полной физической копией всех данных: это только логическое представление, и его можно организовать по-разному. Простой способ состоит в полном ограничении одновременного доступа: и изменений, и чтений. Но при эффективной реализации -- как в Постгресе и Оракле -- читающая транзакция никогда не будет заблокирована другими транзакциями, читающими или изменяющими те же данные -- каждая из них будет независимо работать со своей версией. Блокироваться будут только попытки изменить данные, которые уже изменены другой транзакцией, но еще не зафиксированы.

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

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

В реализациях особенно интересны несколько моментов:

  * Чем определяется «момент времени», как упорядочены события в системе?
  * Что является объектом многоверсионности? Несколько версий чего именно поддерживается в системе?
  * Как организована многоверсионность на низком уровне?
  * Как происходит фиксация и отмена изменений?
  * Как устроен снимок данных?

**Постгрес** использует последовательные номера транзакций; эти номера и определяют порядок событий.

Единицей многоверсионности служат строки таблиц. Табличный блок содержит набор версий строк (tuples), для каждой из которых хранятся номера двух транзакций: начальной (xmin) и конечной (xmax).

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

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

В системе имеется список статусов всех транзакций (CLOG). Фиксация или отмена транзакций выполняются изменением статуса в этом списке. Начальный и конечный номера транзакций в строках могут стать неактуальными, например, если транзакция была отменена. Затронутые блоки исправляются не сразу -- это было бы слишком накладно, -- а позже, сверяясь с CLOG.

Снимок данных состоит из ближайшего номера транзакции (который определяет текущий момент времени) и списка активных транзакций, еще не завершенных на данный момент. Когда транзакция читает данные, она должна увидеть в блоке только те строки, которые уже были зафиксированы и еще не были удалены в момент создания снимка (а также строки, созданные самой транзакцией). Информации в снимке и строках как раз достаточно, чтобы вычислить это условие.

 

{{:media:2015:11:17:mvcc_postgres.gif|Пример реализации MVCC в PostgreSQL}} 

**В Оракле** за упорядоченность отвечает SCN (system change number) -- счетчик, увеличивающийся как минимум при каждой фиксации или откате изменений.

Единицей многоверсионности служит блок; он всегда содержит актуальный на некоторый момент набор строк. При любом изменении данных в блоке (будь то вставка, удаление или обновление) в журнал отката записывается минимальная информация, необходимая для отмены этих изменений. При вставке строки это указание о ее удалении, при изменении -- старое значение изменившихся полей, и только при удалении -- вся строка полностью. Номер транзакции не является последовательным, а представляет собой ссылку на цепочку записей в журнале отката. Точно так же обстоит дело и с блоками индексов.

Каждый блок, будь то табличный или индексный, содержит ITL (interested transactions list) --  список транзакций, изменяющих этот блок, с указанием их статуса, момента начала и окончания. Эта информация определяет SCN блока -- момент, на который данные в блоке актуальны. Размер ITL ограничен, но его элементы могут использоваться повторно, как только соответствующая транзакция завершится.

Снимок данных определяется исключительно значением SCN. Чтобы получить в блоке согласованные данные, сначала откатываются изменения незафиксированных транзакций, если такие присутствуют в ITL. Затем одно за другим откатываются изменения уже зафиксированных транзакций, пока SCN блока не достигнет заданного снимком значения. Чтобы не повторять каждый раз эти действия, новая версия блока сохраняется в буферном кэше и используется транзакциями, пока не будет вытеснена.

Фиксация изменений выполняется простой сменой статуса транзакции в журнале отката. А вот отмена транзакции требует отката всех ее изменений, и это может занять столько же времени, сколько уже было потрачено на выполнение транзакции. И в том, и в другом случае статус транзакции в ITL измененных блоков может быть исправлен не сразу, а при первом обращении к блоку.

 

 

{{:media:2015:11:17:mvcc_oracle.gif|Пример реализации MVCC в Oracle}} 

Таковы основные идеи, заложенные в двух реализациях. Безусловно, в каждой есть свои тонкости, свои плюсы и минусы. Вот некоторые из них.

**Переполнение счетчика.** Под номер транзакции в Постгресе отведено 32 бита, поэтому в нагруженной системе вполне реально получить переполнение. Более того, поскольку в CLOG хранится список всех транзакций (хоть и очень компактный), увеличение разрядности привело бы к дополнительному расходу места на диске. Решение состоит в том, что CLOG считается кольцевым буфером, перезаписываются только старые транзакции, уже не влияющие на изоляцию, а точка «начала отсчета» периодически сдвигается вперед.

Разрядность SCN в Оракле составляет 48 бит, что позволяет не заботиться о переполнении.

**Хранение дополнительных версий** требует дискового пространства. Особенно остро вопрос стоит для Постгреса, ведь хранить приходится полные версии строк, а также ссылающиеся на них записи в индексных блоках. Чтобы освободить место, необходимо периодически очищать блоки от тех версий, которые не видны ни одной транзакции. Это действие может происходить как при обращении к блоку (что приводит к выполнению транзакцией «не своей» работы), так и на периодической основе в специальном процессе (VACUUM). Большое значение имеет оптимизация (HOT update), позволяющая не создавать записи в индексных блоках, если в новой версии строки не изменились проиндексированные поля, а заодно и выполняющая частичную очистку в рамках одного блока таблицы.

В Оракле размер данных, необходимых для поддержки версионности, несколько меньше за счет использования журнала отката. Но есть и проблема: место под журналы отката ограничено и поэтому журнал уже зафиксированной транзакции может быть перезаписан. Это может привести к невозможности отката блока до SCN снимка, особенно в случае долгоиграющей транзакции на фоне большой активности в системе (ошибка «snapshot too old»).

**Индексы** Постгреса не содержат информации о версионности, и по одному только индексу невозможно определить, какие значения попадают в снимок. Наличие «карты видимости», в которой отмечены гарантированно видимые всем транзакциям строки, позволяет методам доступа на основе индекса (index-only scans) работать эффективно, но в ряде случаев все равно приходится заглядывать в таблицу. Ораклу проще: в плане поддержки многоверсионности индекс ничем не отличается от таблицы.

**Фиксация и отмена транзакций** в Постгресе выполняются одинаково быстро. В случае Оракла это верно только для фиксации; отмена -- затратная операция.

**Блокировки **в Оракле устроены несколько более сложно. Перед тем, как первый раз изменить блок, транзакция должна записаться в ITL, а размер этого списка ограничен. Если с блоком уже работает максимально возможное количество транзакций, следующей придется ожидать освобождения элемента ITL. Это не только ограничивает степень параллелизма, но и может привести к неожиданным взаимоблокировкам.

**Снимок данных** Постгреса содержит список незавершенных транзакций, но эта информация доступна только на текущий момент. Это означает невозможность получить данные, согласованные на произвольный момент в прошлом, если в тот момент не был сделан снимок.

В Оракле снимок определяется только значением SCN, поэтому согласованные данные можно получить на любой момент в прошлом (flashback query), лишь бы в сегментах отката оставалась информация, достаточная для построения необходимых версий блоков данных.