Управление многоверсионным параллелизмом

Управление многоверсионным параллелизмом ( 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 _. ) < РТС ( Т _k ) ^{[ нужны разъяснения ]} объекта , чтобы операция записи ( WTS ) прошла успешно. Запись не может быть завершена , если есть другие незавершенные транзакции с более ранней меткой времени чтения ( RTS ) для того же объекта. Подобно тому, как вы стоите в очереди в магазине, вы не можете завершить транзакцию оформления заказа, пока те, кто перед вами, не завершат свою.

Повторить; каждый объект ( P ) имеет временную метку ( TS ), однако, если транзакция i _хочет выполнить запись в объект, и транзакция имеет временную метку ( TS ), которая более ранняя, чем текущая временная метка чтения объекта, TS ( Ti _T ) < RTS ( P ), затем транзакция прерывается и перезапускается. (Это связано с тем, что более поздняя транзакция уже зависит от старого значения.) В противном случае T _i создает новую версию объекта P и устанавливает временную метку чтения/записи TS новой версии на временную метку транзакции TS ← TS ( T _i ). ^[2]

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

Примеры

Параллельное чтение-запись

При Time = 1 состояние базы данных может быть:

Время	Объект 1	Объект 2
0	"Фу" от T0	«Бар» от Т0
1	«Привет» от Т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:

Время	Объект 1	Объект 2	Объект 3
0	"Фу" от T0	«Бар» от Т0
1	«Привет» от Т1
2		(удалено) T3	«Фу-Бар» от Т3

На момент 2 существует новая версия объекта 2, которая помечена как удаленная, и новый объект 3. Поскольку T2 и T3 работают одновременно, T2 видит версию базы данных до версии 2, т.е. до того, как T3 зафиксировал запись, поэтому T2 читает объект 2. ="Бар" и Объект 1="Привет". Именно так многоверсионное управление параллелизмом позволяет выполнять изолированное чтение моментальных снимков без каких-либо блокировок.

История

Управление многоверсионным параллелизмом подробно описано в статье 1981 года «Управление параллелизмом в системах распределенных баз данных». ^[3] и Фил Бернштейн Натан Гудман, тогда работавшие в Компьютерной корпорации Америки . В статье Бернштейна и Гудмана цитируется диссертация 1978 года. ^[4] Дэвида П. Рида , который довольно четко описывает MVCC и утверждает, что это оригинальная работа.

Первым коммерческим программным продуктом для баз данных с поддержкой MVCC был VAX Rdb/ELN , выпущенный в 1984 году. ^[5] и создан в Digital Equipment Corporation Джимом Старки . Старки продолжил: ^[6] для создания второй коммерчески успешной базы данных MVCC — InterBase . ^[7]

См. также

Ссылки

^ «Clojure — Ссылки и транзакции» . Clojure.org . Проверено 12 апреля 2019 г.
^ Рамакришнан Р. и Герке Дж. (2000). Системы управления базами данных. Осборн/МакГроу-Хилл.
^ Бернштейн, Филип А .; Гудман, Натан (1981). «Управление параллелизмом в системах распределенных баз данных» . Обзоры вычислительной техники ACM . 13 (2): 185–221. дои : 10.1145/356842.356846 .
^ Рид, ДП (1978). Именование и синхронизация в децентрализованной компьютерной системе . Диссертация Массачусетского технологического института (Диссертация). hdl : 1721.1/16279 . Проверено 12 ноября 2022 г.
^ Галлант, Джон (9 апреля 1984 г.). «RDB получает неоднозначное приветствие» . Компьютерный мир . Проверено 13 сентября 2021 г.
^ «Напоминание о Джиме Старки в списке рассылки Firebird (26 мая 2022 г.)» .
^ «Не очень техническое обсуждение многоверсионного управления параллелизмом» . firebirdsql.org . Проверено 12 ноября 2020 г.

Дальнейшее чтение

Герхард Вейкум, Готфрид Воссен, Транзакционные информационные системы: теория, алгоритмы и практика параллельного управления и восстановления , Морган Кауфманн, 2002 г., ISBN 1-55860-508-8

[1] «Clojure — Ссылки и транзакции» . Clojure.org . Проверено 12 апреля 2019 г.

[2] Рамакришнан Р. и Герке Дж. (2000). Системы управления базами данных. Осборн/МакГроу-Хилл.

[3] Бернштейн, Филип А .; Гудман, Натан (1981). «Управление параллелизмом в системах распределенных баз данных» . Обзоры вычислительной техники ACM . 13 (2): 185–221. дои : 10.1145/356842.356846 .

[4] Рид, ДП (1978). Именование и синхронизация в децентрализованной компьютерной системе . Диссертация Массачусетского технологического института (Диссертация). hdl : 1721.1/16279 . Проверено 12 ноября 2022 г.

[5] Галлант, Джон (9 апреля 1984 г.). «RDB получает неоднозначное приветствие» . Компьютерный мир . Проверено 13 сентября 2021 г.

[6] «Напоминание о Джиме Старки в списке рассылки Firebird (26 мая 2022 г.)» .

[7] «Не очень техническое обсуждение многоверсионного управления параллелизмом» . firebirdsql.org . Проверено 12 ноября 2020 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]