Управление многоверсионным параллелизмом ( MCC или MVCC ) — это метод управления параллелизмом без блокировки, обычно используемый системами управления базами данных для обеспечения одновременного доступа к базе данных и в языках программирования для реализации транзакционной памяти . [1]
Без управления параллелизмом, если кто-то читает из базы данных одновременно с записью в нее кого-то другого, вполне возможно, что читатель увидит наполовину написанный или противоречивый фрагмент данных. Например, при банковском переводе между двумя банковскими счетами, если читатель читает баланс в банке, когда деньги были сняты с исходного счета и до того, как они были зачислены на целевой счет, может показаться, что деньги исчезли с банковского счета. банк. Изоляция — это свойство, обеспечивающее гарантии одновременного доступа к данным. Изоляция реализуется посредством протокола управления параллелизмом . Самый простой способ — заставить всех читателей дождаться завершения записи, что называется блокировкой чтения-записи . Известно, что блокировки создают конфликты , особенно между транзакциями длительного чтения и транзакциями обновления. MVCC стремится решить проблему, сохраняя несколько копий каждого элемента данных. Таким образом, каждый пользователь, подключенный к базе данных, видит снимок базы данных в определенный момент времени. Любые изменения, внесенные автором записи, не будут видны другим пользователям базы данных до тех пор, пока изменения не будут завершены (или, в терминах базы данных: до тех пор, пока транзакция не будет зафиксирована).
Когда базе данных MVCC необходимо обновить часть данных, она не перезаписывает исходный элемент данных новыми данными, а вместо этого создает более новую версию элемента данных. Таким образом, сохраняется несколько версий. Версия, которую видит каждая транзакция, зависит от реализованного уровня изоляции. Наиболее распространенный уровень изоляции, реализуемый с помощью MVCC, — это изоляция моментальных снимков . При изоляции моментальных снимков транзакция отслеживает состояние данных на момент ее запуска.
MVCC обеспечивает согласованное представление на определенный момент времени . Транзакции чтения в рамках MVCC обычно используют временную метку или идентификатор транзакции, чтобы определить, какое состояние БД следует читать, и читать эти версии данных. Таким образом, транзакции чтения и записи изолированы друг от друга без необходимости блокировки. Однако, несмотря на то, что блокировки не являются необходимыми, они используются некоторыми базами данных MVCC, такими как Oracle. При записи создается более новая версия, а при одновременном чтении осуществляется доступ к более старой версии.
MVCC ставит задачу удаления версий, которые устарели и никогда не будут прочитаны. В некоторых случаях реализуется процесс периодической проверки и удаления устаревших версий. Часто это процесс остановки мира, который просматривает всю таблицу и перезаписывает ее с использованием последней версии каждого элемента данных. PostgreSQL может использовать этот подход в процессе VACUUM FREEZE. Другие базы данных разделяют блоки хранения на две части: часть данных и журнал отмены. Часть данных всегда сохраняет последнюю зафиксированную версию. Журнал отмены позволяет воссоздать более старые версии данных. Основное ограничение этого последнего подхода заключается в том, что при наличии рабочих нагрузок с интенсивным обновлением в части журнала отмены не хватает места, а затем транзакции прерываются, поскольку им не может быть предоставлен моментальный снимок. Для документо-ориентированной базы данных это также позволяет системе оптимизировать документы, записывая целые документы на смежные разделы диска — при обновлении весь документ может быть перезаписан, а не вырезан по частям или сохранен в связанном, несвязанном виде. Непрерывная структура базы данных.
MVCC использует метки времени ( TS ) и увеличивающие идентификаторы транзакций для достижения согласованности транзакций . MVCC гарантирует, что транзакции ( T ) никогда не придется ждать, чтобы прочитать объект базы данных ( P ), поддерживая несколько версий объекта. Каждая версия объекта P имеет как временную метку чтения ( RTS ), так и временную метку записи ( WTS ), которая позволяет конкретной транзакции Ti читать самую последнюю версию объекта, которая предшествует временной метке чтения транзакции RTS ( Ti ) .
Если транзакция T i хочет выполнить запись в объект P , и существует еще одна транзакция T k , происходящая с тем же объектом, RTS чтения временной метки ( Ti ) должна предшествовать временной метке чтения RTS ( T k ), т. е. RTS ( Ti ) < RTS ( T k ) [ необходимы пояснения ] , чтобы операция записи объекта ( WTS ) прошла успешно. Запись не может быть завершена, если есть другие незавершенные транзакции с более ранней меткой времени чтения ( RTS ) для того же объекта. Подобно тому, как вы стоите в очереди в магазине, вы не можете завершить транзакцию оформления заказа, пока те, кто перед вами, не завершат свою.
Повторить; каждый объект ( P ) имеет временную метку ( TS ), однако, если транзакция T i хочет выполнить запись в объект, и транзакция имеет временную метку ( TS ), которая более ранняя, чем текущая временная метка чтения объекта, TS ( Ti ) < RTS ( P ), затем транзакция прерывается и перезапускается. (Это связано с тем, что более поздняя транзакция уже зависит от старого значения.) В противном случае T i создает новую версию объекта P и устанавливает временную метку чтения/записи TS новой версии на временную метку транзакции TS ← TS ( T i ). [2]
Недостатком этой системы является стоимость хранения нескольких версий объектов в базе данных. С другой стороны, чтение никогда не блокируется, что может быть важно для рабочих нагрузок, в основном связанных с чтением значений из базы данных. MVCC особенно хорошо умеет реализовывать настоящую изоляцию моментальных снимков , что другие методы управления параллелизмом часто делают либо не полностью, либо с высокими затратами производительности.
При Time = 1 состояние базы данных может быть:
T0 написал Объект 1="Foo" и Объект 2="Bar". После этого T1 записал Object 1="Hello", оставив Object 2 его исходное значение. Новое значение объекта 1 заменит значение 0 для всех транзакций, которые начинаются после фиксации T1, и в этот момент версия 0 объекта 1 может быть удалена сборщиком мусора.
Если длительная транзакция T2 запускает операцию чтения объекта 2 и объекта 1 после фиксации T1 и существует параллельная транзакция обновления T3, которая удаляет объект 2 и добавляет объект 3 = «Foo-Bar», состояние базы данных будет выглядеть следующим образом: время 2:
На момент 2 существует новая версия объекта 2, которая помечена как удаленная, и новый объект 3. Поскольку T2 и T3 выполняются одновременно, T2 видит версию базы данных до версии 2, т.е. до того, как T3 зафиксировал запись, поэтому T2 читает объект 2. ="Бар" и Объект 1="Привет". Именно так многоверсионное управление параллелизмом позволяет выполнять изолированное чтение моментальных снимков без каких-либо блокировок.
Управление многоверсионным параллелизмом довольно подробно описано в статье 1981 года «Управление параллелизмом в системах распределенных баз данных» [3] Фила Бернштейна и Натана Гудмана, которые тогда работали в Компьютерной корпорации Америки . В статье Бернштейна и Гудмана цитируется диссертация Дэвида П. Рида [4] 1978 года, в которой довольно четко описывается MVCC и утверждается, что это оригинальная работа.
Первым коммерческим программным продуктом для баз данных с поддержкой MVCC был VAX Rdb/ELN , выпущенный в 1984 году [5] и созданный в Digital Equipment Corporation Джимом Старки . Старки продолжил [6] создание второй коммерчески успешной базы данных MVCC — InterBase . [7]