Многовариантный контроль параллелизма ( MCC или MVCC ) - это метод управления параллелизмом, обычно используемый системами управления базами данных для обеспечения одновременного доступа к базе данных и в языках программирования для реализации транзакционной памяти . [1]
Описание [ править ]
Без контроля параллелизма, если кто-то читает из базы данных одновременно с записью в нее, возможно, что читатель увидит наполовину записанные или несогласованные фрагменты данных. Например, при совершении банковского перевода между двумя банковскими счетами, если читатель считывает баланс в банке, когда деньги были сняты с исходного счета и до того, как они были внесены на целевой счет, может показаться, что деньги исчезли из банк. Изоляция - это свойство, обеспечивающее гарантии одновременного доступа к данным. Изоляция реализуется с помощью протокола управления параллелизмом . Самый простой способ - заставить всех читателей ждать, пока писатель не закончит, что называется блокировкой чтения-записи.. Известно, что блокировки создают конкуренцию, особенно между транзакциями длительного чтения и транзакциями обновления. MVCC стремится решить проблему, сохраняя несколько копий каждого элемента данных. Таким образом, каждый пользователь, подключенный к базе данных, видит моментальный снимок базы данных в определенный момент времени. Любые изменения, внесенные писателем, не будут видны другим пользователям базы данных до тех пор, пока изменения не будут завершены (или, в терминах базы данных: пока транзакция не будет зафиксирована).
Когда базе данных MVCC необходимо обновить фрагмент данных, она не будет перезаписывать исходный элемент данных новыми данными, а вместо этого создает более новую версию элемента данных. Таким образом, хранится несколько версий. Версия, которую видит каждая транзакция, зависит от реализованного уровня изоляции. Наиболее распространенный уровень изоляции, реализованный с помощью MVCC, - это изоляция моментальных снимков . С изоляцией моментального снимка транзакция наблюдает за состоянием данных, как когда транзакция началась.
MVCC обеспечивает согласованные представления на определенный момент времени . В транзакциях чтения в MVCC обычно используется метка времени или идентификатор транзакции, чтобы определить, какое состояние БД читать, и прочитать эти версии данных. Таким образом, транзакции чтения и записи изолированы друг от друга без какой-либо блокировки. Однако, несмотря на то, что в блокировках нет необходимости, они используются некоторыми базами данных MVCC, такими как Oracle. Запись создает новую версию, а одновременное чтение обеспечивает доступ к более старой версии.
MVCC представляет проблему, как удалить версии, которые устарели и никогда не будут прочитаны. В некоторых случаях реализован процесс периодического просмотра и удаления устаревших версий. Часто это процесс остановки мира, который просматривает всю таблицу и перезаписывает ее последней версией каждого элемента данных. PostgreSQL применяет этот подход в своем процессе VACUUM. Другие базы данных разделяют блоки хранения на две части: часть данных и журнал отмены. В части данных всегда сохраняется последняя зафиксированная версия. Журнал отмены позволяет восстанавливать старые версии данных. Основное неотъемлемое ограничение этого последнего подхода заключается в том, что при наличии рабочих нагрузок с интенсивным обновлением в части журнала отмены не хватает места, а затем транзакции прерываются, поскольку им не может быть предоставлен их моментальный снимок. Длядокументно-ориентированная база данных, она также позволяет системе оптимизировать документы путем записи целых документов на смежные разделы диска - при обновлении можно переписать весь документ, а не вырезать отдельные фрагменты или поддерживать в связанной, несмежной базе данных структура.
Реализация [ править ]
MVCC использует временные метки ( TS ) и увеличивающие идентификаторы транзакций для достижения согласованности транзакций . MVCC гарантирует, что транзакция ( T ) никогда не должна ждать, чтобы прочитать объект базы данных ( P ), поддерживая несколько версий объекта. Каждая версия объекта P имеет метку времени чтения ( RTS ) и метку времени записи ( WTS ), которая позволяет конкретной транзакции T i читать самую последнюю версию объекта, которая предшествует метке времени чтения RTS транзакции ( Tя ).
Если транзакция T i хочет записать в объект P , и есть также другая транзакция T k, происходящая с тем же объектом, RTS времени чтения ( T i ) должен предшествовать Read Timestamp RTS ( T k ), т. Е. RTS ( T i ) < RTS ( T k ) [ требуется пояснение ] для успешного выполнения операции записи объекта ( WTS ). НаписатьНевозможно завершить, если есть другие невыполненные транзакции с более ранней отметкой времени чтения ( RTS ) для того же объекта. Подобно тому, как стоять в очереди в магазине, вы не можете завершить свою транзакцию, пока те, кто перед вами, не завершат свою.
Чтобы повторить; каждый объект ( P ) имеет метку времени ( TS ), однако, если транзакция T i хочет записать в объект, а транзакция имеет метку времени ( TS ), которая предшествует текущей метке времени чтения объекта, TS ( T i ) < RTS ( P ), то транзакция прерывается и перезапускается. (Это связано с тем, что более поздняя транзакция уже зависит от старого значения.) В противном случае T i создает новую версию объекта P и устанавливает временную метку чтения / записи TS.новой версии к метке времени транзакции TS ← TS ( T i ). [2]
Недостатком этой системы является стоимость хранения нескольких версий объектов в базе данных. С другой стороны, чтение никогда не блокируется, что может быть важно для рабочих нагрузок, в основном связанных с чтением значений из базы данных. MVCC особенно хорошо умеет реализовывать настоящую изоляцию моментальных снимков , что часто делают другие методы управления параллелизмом либо не полностью, либо с высокими затратами на производительность.
Примеры [ править ]
Параллельное чтение-запись [ править ]
При Time = 1 состояние базы данных может быть:
| Время | Объект 1 | Объект 2 |
|---|---|---|
| 0 | "Фу", автор: T0 | "Бар" от Т0 |
| 1 | "Привет" от Т1 |
T0 написал Object 1 = "Foo" и Object 2 = "Bar". После этого T1 написал Object 1 = "Hello", оставив объекту 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] по Фил Бернштейн и Натан Goodman, а затем на работу в Computer Corporation Америки . В статье Бернстайна и Гудмана цитируется диссертация Дэвида П. Рида 1978 года [4] , в которой довольно четко описывается MVCC и утверждается, что это оригинальная работа.
Первая перевозка груза, коммерческое программное обеспечение базы данных продукт отличая MVCC был VAX Rdb / ELN , созданный в Digital Equipment Corporation по Джим Старки . Старки создал вторую коммерчески успешную базу данных MVCC - InterBase . [5]
См. Также [ править ]
- Список баз данных, использующих MVCC
- Чтение-копирование-обновление
- Управление параллелизмом на основе временных меток
- Векторные часы
- Система контроля версий
Ссылки [ править ]
- ^ «Clojure - Ссылки и транзакции» . clojure.org . Проверено 12 апреля 2019 .
- Перейти ↑ Ramakrishnan, R., & Gehrke, J. (2000). Системы управления базами данных. Осборн / Макгроу-Хилл.
- ^ Бернштейн, Филип А .; Гудман, Натан (1981). «Управление параллелизмом в распределенных системах баз данных» . ACM Computing Surveys .
- ↑ Рид, Дэвид П. (21 сентября 1978 г.). «Именование и синхронизация в децентрализованной компьютерной системе» . Диссертация в Массачусетском технологическом институте . Архивировано из оригинального 25 октября 2005 года . Проверено 18 февраля 2006 года .
- ^ "Не очень техническое обсуждение Multi Version Concurrency Control" . firebirdsql.org . Проверено 12 ноября 2020 .
Дальнейшее чтение [ править ]
- Герхард Вейкум, Готфрид Фоссен, Транзакционные информационные системы: теория, алгоритмы и практика управления параллельным выполнением и восстановления , Морган Кауфманн, 2002, ISBN 1-55860-508-8
