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

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

История

Предпосылки возникновения

До появления MVCC традиционные СУБД (например, ранние версии IBM DB2 или SQL/DS) использовали механизмы блокировок на уровне строк или страниц. При таком подходе транзакция, изменяющая данные, блокирует их до момента фиксации (commit), что может приводить к взаимоблокам (deadlocks) и снижению пропускной способности при большом количестве одновременных запросов.

Разработка и внедрение

Теоретические основы MVCC были заложены в 1970-х годах в работах Джима Грея и других исследователей в области систем управления базами данных. Первой коммерческой реализацией MVCC стала InterBase (разработана в 1980-х годах компанией Interbase Software, позже приобретена Borland). В 1996 году в СУБД Oracle 7 появилась одна из самых влиятельных реализаций MVCC. Затем метод был реализован в PostgreSQL (начиная с версии 6.0, 1997 год), InnoDB (MySQL, с версии 3.23, 2001 год) и других системах.

Современное состояние

Сегодня MVCC является стандартом де-факто для большинства реляционных и нереляционных (NoSQL) СУБД: Oracle, PostgreSQL, MySQL (InnoDB), Microsoft SQL Server (в режиме Read Committed Snapshot Isolation), SQLite (начиная с версии 3.7.0), CockroachDB, FoundationDB и другие. В системах управления версиями данных, таких как Git, также применяются схожие принципы ветвления и слияния версий.

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

Версионность данных

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

Снимки данных (snapshots)

Транзакция при запуске получает идентификатор и видит все версии записей, созданные транзакциями, завершившимися ранее её начала. Версии, созданные после её запуска или не фикcированные ей самой, игнорируются. Это реализует изоляцию транзакций без использования блокировок чтения.

Управление временными метками

Система использует глобальный счётчик идентификаторов транзакций (Transaction ID, TXID). Каждая новая транзакция получает уникальный TXID. При чтении данных СУБД сравнивает TXID версии с текущим состоянием видимости (visibility) транзакции.

Очистка старых версий

Процесс очистки (vacuum) удаляет версии записей, которые больше не видны ни одной активной транзакции. В PostgreSQL за это отвечает фоновый процесс autovacuum. В InnoDB аналогичную роль выполняет обход буфера отката (undo log). Если очистка не выполняется своевременно, объём данных может чрезмерно расти.

Виды реализации MVCC

Append-Only (добавление новых записей)

Новая версия записывается как отдельная строка в основном хранилище данных. Применяется в PostgreSQL, где старые версии могут находиться на страницах в общем табличном пространстве. При чтении выбирается наиболее поздняя, но видимая версия.

Undo-лог (откатные сегменты)

Старая версия вытесняется в отдельный лог отката (undo segment), а основная строка содержит последнюю зафиксированную версию. При чтении, если версия невидима, система обращается к undo-логу для восстановления предыдущего состояния. Используется в Oracle, InnoDB, Microsoft SQL Server.

Copy-on-Write (копирование при записи)

Каждая новая версия создаётся путём полного копирования изменённых страниц или строк. Применяется в CouchDB и ZFS (файловая система), а также в некоторых NoSQL-решениях.

Уровни изоляции и MVCC

Read Committed

Транзакция видит все зафиксированные изменения, произошедшие до начала выполнения текущего оператора (а не всей транзакции). Это может привести к неповторяемому чтению (non-repeatable read). Реализовано в Oracle и PostgreSQL (по умолчанию).

Repeatable Read

Транзакция видит только данные, зафиксированные на момент её начала. Это устраняет неповторяемое чтение, но может вызывать ошибки сериализации при конкурентной записи. Используется в PostgreSQL (по умолчанию) и InnoDB.

Serializable

Наивысший уровень изоляции, обеспечивающий полную сериализуемость транзакций. Достигается комбинацией MVCC с дополнительными блокировками предикатов (predicate locks) или обнаружением конфликтов (serializable snapshot isolation, SSI). Реализован в PostgreSQL (с версии 9.1) и Oracle.

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

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

Недостатки

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

Применение

• Реляционные СУБД: Oracle, PostgreSQL, MySQL (InnoDB), Microsoft SQL Server, MariaDB, SAP HANA, CockroachDB.
• NoSQL-системы: MongoDB (начиная с версии 4.0), CouchDB, FoundationDB, Tarantool.
• Системы управления версиями: Git, Mercurial (используют модели ветвления, схожие с MVCC).
• Облачные системы: Google Spanner, Amazon Aurora, Yandex ClickHouse (частичная поддержка MVCC для обеспечения ACID-свойств).

Сравнение с традиционными блокировками

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

• В PostgreSQL каждая транзакция имеет уникальный 32-битный номер, что может привести к переполнению (wrap-around) при длительной работе. Для предотвращения этого используется процедура «заморозки» (freeze) старых транзакций.
• В Oracle MVCC реализована таким образом, что читающие запросы никогда не блокируются, даже при ожидании фиксации писателя.
• В SQLite MVCC применяется в режиме WAL (Write-Ahead Logging), где записи сначала попадают в журнал, а затем накапливаются в основном файле.
• В NoSQL-системе FoundationDB используется механизм «версионированных временных рядов», позволяющий просматривать состояние базы на любой момент в прошлом.

Источники

• Gray J., Reuter A. «Transaction Processing: Concepts and Techniques». Morgan Kaufmann, 1993.
• Hellerstein J., Stonebraker M., Hamilton J. «Architecture of a Database System». Foundations and Trends in Databases, 2007.
• Документация PostgreSQL (Глава 13. Concurrency Control).
• Документация MySQL InnoDB (InnoDB Multi-Versioning).
• Документация Oracle Database (Concurrency Control).
• Bernstein P., Goodman N. «Multiversion Concurrency Control — Theory and Algorithms». ACM Transactions on Database Systems, 1983.
• Melnik S. et al. «Dremel: Interactive Analysis of Web-Scale Datasets» (описание MVCC в Google Spanner).