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

Многоверсионный параллелизм (англ. Multiversion Concurrency Control, MVCC) — это механизм управления конкурентным доступом к данным в системах управления базами данных (СУБД) и файловых системах, при котором каждый пишущий транзакция создаёт новую версию изменяемой записи, а не блокирует её для других читающих транзакций. В отличие от традиционных блокировочных протоколов, MVCC позволяет читателям видеть согласованное состояние данных на момент начала своей транзакции, не дожидаясь завершения пишущих транзакций. Это обеспечивает высокую степень параллелизма и снижает количество конфликтов, особенно в системах с интенсивным чтением и редкими обновлениями.

История

Концепция многоверсионного параллелизма впервые была предложена в 1970-х годах в контексте развития реляционных баз данных. Одной из первых реализаций стала система Rdb (Digital Equipment Corporation), а затем Postgres (предшественник PostgreSQL), разработанная в Калифорнийском университете в Беркли под руководством Майкла Стоунбрейкера. В 1980-х годах идея получила теоретическое обоснование в работах Филипа Бернштейна, Натана Гудмана и других исследователей, формализовавших протоколы многоверсионного упорядочивания.

В 1990-х годах MVCC был внедрён в коммерческие СУБД, такие как Oracle (с версии 7.0, 1992 год) и Microsoft SQL Server (с версии 2005 года, в виде опции READ_COMMITTED_SNAPSHOT). В 2000-х годах механизм стал стандартом для многих современных СУБД, включая PostgreSQL (с 1996 года), MySQL (с версии 5.0, 2005 год, в движке InnoDB) и Firebird. В 2010-х годах MVCC начал применяться в нереляционных системах, таких как Couchbase и MongoDB (с версии 4.0, 2018 год), а также в файловых системах, например, ZFS и Btrfs.

Принцип работы

MVCC основан на хранении нескольких версий одного и того же объекта данных. Каждая транзакция, выполняющая запись (INSERT, UPDATE, DELETE), создаёт новую версию записи, помечая её временной меткой или идентификатором транзакции. Читающие транзакции получают доступ к версии, которая была актуальна на момент их начала, игнорируя более поздние изменения. Это позволяет избежать блокировок между чтением и записью.

Версионирование данных

В типичной реализации MVCC каждая строка таблицы содержит дополнительные поля:

• Идентификатор создавшей транзакции (xmin) — указывает, какая транзакция создала данную версию.
• Идентификатор удалившей транзакции (xmax) — указывает, какая транзакция пометила версию как удалённую (или обновлённую).
• Указатель на предыдущую версию — для построения цепочки версий (например, в PostgreSQL через слоты в общей памяти).

При обновлении строки старая версия не удаляется физически, а помечается как неактуальная. Новая версия вставляется с новым идентификатором транзакции. Читающая транзакция выбирает версию, у которой xmin меньше или равен её идентификатору, а xmax больше или равен (или отсутствует).

Изоляция транзакций

MVCC поддерживает различные уровни изоляции транзакций по стандарту SQL:

• Read Committed — транзакция видит только зафиксированные версии данных на момент выполнения каждого запроса.
• Repeatable Read — транзакция видит только зафиксированные версии на момент начала транзакции (snapshot isolation).
• Serializable — snapshot isolation с дополнительными проверками на конфликты (например, через обнаружение сериализационных аномалий).

Уровень Read Uncommitted в системах с MVCC обычно эквивалентен Read Committed, так как чтение незафиксированных версий может нарушить целостность данных.

Управление версиями

Старые версии данных, которые больше не нужны ни одной активной транзакции, удаляются в процессе сборки мусора (vacuum в PostgreSQL, purge в MySQL/InnoDB). Этот процесс может быть автоматическим или запускаться вручную. Сборка мусора удаляет версии, которые не видны ни одной текущей транзакции, освобождая место в хранилище.

Преимущества и недостатки

Преимущества

• Высокий параллелизм чтения — читатели не блокируются писателями и наоборот, что критично для систем с большим количеством запросов на чтение (например, веб-приложения, аналитические системы).
• Отсутствие взаимоблокировок (deadlocks) при чтении — читатели никогда не ждут блокировок, так как работают со снимком данных.
• Согласованность данных — каждая транзакция видит целостное состояние базы данных, без «грязных» чтений и неповторяющихся чтений (на уровне Repeatable Read).
• Простота реализации для разработчиков — приложения могут выполнять долгие запросы на чтение, не опасаясь блокировок от параллельных обновлений.

Недостатки

• Рост объёма данных — хранение нескольких версий увеличивает потребление дискового пространства и памяти. Требуется регулярная сборка мусора.
• Сложность реализации — механизм требует тщательного управления версиями, идентификаторами транзакций и синхронизацией.
• Снижение производительности при частых обновлениях — каждая запись создаёт новую версию, что может привести к фрагментации данных и замедлению операций вставки.
• Аномалии сериализации — на уровне snapshot isolation возможны аномалии, такие как потерянные обновления или фантомные чтения, которые требуют дополнительных механизмов (например, предикатных блокировок).

Применение

Реляционные СУБД

• PostgreSQL — использует MVCC с момента первой версии. Каждая транзакция получает уникальный идентификатор (XID). Старые версии хранятся в таблицах, а сборка мусора выполняется процессом autovacuum.
• MySQL (InnoDB) — реализует MVCC через undo-логи, которые хранят старые версии строк. Читатели используют consistent read view.
• Oracle Database — использует MVCC с версии 7.0. Старые версии хранятся в сегментах отката (undo segments).
• Microsoft SQL Server — поддерживает snapshot isolation с версии 2005 года. Версии строк хранятся в tempdb.

Нереляционные системы

• MongoDB — с версии 4.0 поддерживает многоверсионность на уровне документов в рамках транзакций.
• Couchbase — использует MVCC для обеспечения согласованности в распределённой среде.
• Apache Cassandra — применяет версионирование на основе временных меток для разрешения конфликтов при записи.

Файловые системы

• ZFS — копирование при записи (copy-on-write) позволяет создавать снимки (snapshots) и восстанавливать предыдущие состояния.
• Btrfs — использует аналогичный механизм для поддержки снимков и подтомов.

Интересные факты

• В PostgreSQL идентификаторы транзакций (XID) являются 32-битными числами, что ограничивает общее количество транзакций до 4 миллиардов. Для предотвращения переполнения используется механизм «заморозки» (freeze).
• В Oracle Database MVCC позволяет читать данные без блокировок даже при выполнении длительных транзакций, что делает её популярной в системах реального времени.
• Механизм MVCC в MySQL/InnoDB может приводить к «разрастанию» undo-логов при долгих транзакциях, что требует мониторинга и настройки.

Критика и альтернативы

Основная критика MVCC связана с накладными расходами на хранение версий и сборку мусора. В системах с высокой интенсивностью обновлений (например, OLTP) рост объёма данных может снижать производительность. Альтернативой являются блокировочные протоколы (например, двухфазная блокировка) или оптимистическое управление конкурентным доступом (OCC), которое не требует хранения версий, но может приводить к частым откатам транзакций.

В распределённых системах, таких как Google Spanner или CockroachDB, MVCC комбинируется с глобальными часами (TrueTime) для обеспечения согласованности в масштабе кластера.

Источники

• Bernstein, P. A., Goodman, N. (1981). «Concurrency Control in Distributed Database Systems». ACM Computing Surveys.
• Stonebraker, M. (1987). «The Design of the POSTGRES Storage System». VLDB.
• Gray, J., Reuter, A. (1993). «Transaction Processing: Concepts and Techniques». Morgan Kaufmann.
• PostgreSQL Documentation. «Chapter 13. Concurrency Control».
• MySQL Documentation. «InnoDB Multi-Versioning».
• Oracle Database Concepts. «Multiversion Read Consistency».