Что такое управление многоверсионным параллелизмом (MVCC)

Почему возникают блокировки и конфликты в БД

Обычно людям сложно делать два дела одновременно: есть риск что-то потерять, упустить, неправильно понять. Так же обстоит дело с базами данных. 

Например, на маркетплейсе есть товар, который пользуется спросом в «Черную пятницу». В базе данных лежит информация об остатках на складе. Когда пользователь оформляет заказ, вносятся изменения в условную ячейку orders в базе данных. Одновременно с этим ячейка может читаться в рамках другой транзакции: например, для отображения информации у поставщика или у производителя. 

Считать сведения и внести изменения одновременно нельзя. Условно говоря, мы начинаем читать ячейку, когда в ней число 27. В тот же момент происходит транзакция изменения, и число меняется на 221. Читатель считывает число 221 и идет дальше, а затем осуществляется rollback — откат до первоначальных 27. В результате корректная цифра — 27, а у читателя — 221.

Сами транзакции чтения и записи могут занимать время, особенно когда работают не с ячейкой, а со строкой или целой таблицей на 120 млн строк.

Естественно, БД лежит на диске, разбивается на страницы и т.д. Но для простоты понимания разработчики используют таблицы, строки, ячейки. На изображении выше показано, что происходит при попытке параллельно считать, и записать данные. Чтобы минимизировать подобные проблемы, необходимо заблокировать ячейку/столбец/таблицу на время записи. Разработчик как бы говорит: «Дай мне запись на id=2 и поставь на нее блокировку, т.к. дальше я буду ее изменять». Новых изменений не будет до тех пор, пока не применятся текущие. Но блокировка означает, что остальные транзакции «становятся в очередь» и начинают накапливаться.

Почему нужна блокировка и какие проблемы она решает

Без блокировки разработчики могут столкнуться с нежелательными эффектами:

• потеря записи (lost_updates);
• чтение «неутвержденных данных» (грязное чтение, dirty read);
• неповторяющееся чтение или применение изменений в процессе чтения (non-repeatable read);
• добавление в процессе чтения (фантомы phantom_reads).

Обратите внимание, что транзакция в реляционных БД:

• может состоять из одной операции или последовательности операций (DELETE, INSERT, UPDATE);
• рассматривается БД как атомарное действие, то есть по принципу «все или ничего» (применяются или все операции в транзакции, или никакие. Не может быть ситуации, когда 2 из 5 операций выполнились, а 3 потерялись или не закоммитились);
• завершается или committed (применена, утверждена), или rollback (отменена, откатана).

lost_updates

Допустим, есть СУБД, в которой хранятся репозитории пользователей GitVerse. Она выглядит таким образом:

Допустим, пользователь решил изменить название репозитория с roadmap на roadmap1. В момент времени t1 транзакция записи еще не завершилась, ее состояние — partially committed (частично исполненная): изменения внесены, но еще не сохранены. И в это же время t1, когда имя изменено на roadmap2, но не было закоммичено, начинается вторая транзакция с изменениями имени на road2. В результате название репозитория изменится не на roadmap1, а сразу на roadmap2. Получается, мы потеряли roadmap1: транзакция не выполнилась. А если представить, что речь не о названии репозитория, а о банковской операции или заказе в интернет-магазине?

Чтобы решить проблему «потерянных транзакций», используется изоляция. В указанном примере — read uncommitted. На уровне кода прерывается вторая транзакция: она не выполняется до тех пор, пока изменения первой транзакции не будут применены. Новый «писатель» ждет, когда старый завершит работу и применит изменения. Только тогда транзакция сможет применить свои изменения.

dirty_read

Возможен другой вариант с примером выше. В момент t1 происходит изменение названия репозитория с repo на repo1. В этот же промежуток времени происходит чтение. Транзакция изменения имени с repo на repo1 прошла, но не была подтверждена. Если в этот момент изменение прервется или произойдет rollback, сведения откатятся до repo. 

Что получит вторая транзакция при попытке считать имя — repo или repo1? Она вернет repo1, хотя на самом деле его не существует: произошел откат до repo. Это происходит из-за проблемы «грязного чтения» (dirty read).

Что решить проблему, используют уровень изолированности read committed. Чтение строки возможно только тогда, когда транзакция по изменению имени будет подтверждена (закоммичена). Строка, в которой происходят изменения, временно блокируется для чтения. Читатель ждет, когда писатель завершит работу и применит (закоммитит) результаты.

non-repeatable read

Допустим, в БД происходит чтение первой строчки. В реальных БД операция может занимать длительное время. В момент времени t1, когда уже происходит чтение, запускается параллельная t2, изменяющая количество форков с 23 на 24. В это время первая считает id, repo_name и попадает к fors… и возвращает 24! Это неверно: изменения внесены в процессе чтения строки.  

Чтобы решить проблему, используют repeatable read. На время, пока идет чтение строки, блокируются все transaction по изменению. «Писатель» ждет, когда «читатель» закончит чтение строки.

phantom reads

Допустим, есть t1, которая читает всю таблицу. Для первой строки установлен repeatable read — она заблокирована для изменений. В то время, когда t1 читает таблицу, происходит t2, вставляющая две строки. На выходе та же ситуация, что и в примере выше, но только не с изменением строки, а с изменением таблицы. Причина в том, что не установлена блокировка существующих записей. Необходимо обеспечить конкурентный доступ.  

Для этого используется высший уровень изоляции — serializable. То есть при чтении таблицы блокируются любые транзакции на запись. Условно говоря, операция записи в таблицу «ждет очереди», пока завершается операция чтения. 

Уровни изоляции (isolation levels) и феномены (read phenomena) на примере БД PostgreSQL представлены в таблице ниже.

Почему блокировки транзакций не всегда хороши

На крупных проектах может быть больше 1000 «читателей» и «писателей» одновременно. Выстраивается очередь транзакционных процессов, которые нагружают оперативную память. Возникают конфликты. 

Возникают ситуации множественных блокировок, когда «писатели» ждут «читателей», «читатели» — «писателей», одни «писатели» — других и так далее. Если, например, на сайт одновременно зайдет миллион пользователей, система сломается (не вытянет, если запросы будут ждать друг друга). Частично проблему решает система резолвинга конфликтов — conflict resolve. Она отстреливает один из транзакционных процессов.

Но все равно необходим механизм, который: а) обеспечивал бы уровень изоляции; б) не становился причиной очередей и конфликтов.

Для этого используется snapshot isolation. Создаются виртуальные снимки БД (виртуальные защищенные образы). Каждая transaction работает как бы со своей собственной БД. Уровень изоляции остается высоким, но риска блокировки из-за долгих операций чтения гораздо меньше.

Что такое концепция управления многоверсионным параллелизмом (MVCC) в БД

MVCC (англ. multiversion concurrency control, управление параллельным доступом посредством многоверсионности) — метод обеспечения конкурентного доступа и один из механизмов СУБД для параллельного доступа к данным. Он гарантирует, что:

• все операции будут выполнены корректно;
• все данные будут валидны;
• ACID-принципы будут соблюдены.

ACID-принципы — это набор требований к транзакционным системам, обеспечивающий сохранность данных. Их можно рассматривать как список гарантий в поведении БД.

Разберем их детальнее. 

1. A (Atomicity, атомарность) — каждая транзакция будет или выполнена полностью, или не выполнена совсем. Это условно можно сравнить с переводом денег на карту. Когда один пользователь отправляет средства другому, есть два варианта развития событий: деньги придут адресату или останутся у адресанта. Не должно быть «промежуточного решения»: «деньги остались у банка отправителя», «деньги у банка получателя», «деньги у банка-корреспондента».
2. C (Consistency, консистентность, согласованность) — после транзакции БД остается консистентной. Если сравнивать с банковским переводом, то после завершения и подтверждения операции сумма на балансе не изменяется. Не должно быть ситуации, когда у пользователя было на счету 1000 рублей, он перевел 100 рублей, а баланс вместо положенных 900 руб. начал неконтролируемо изменяться: то 901, то 855, то 903.
3. I (Isolation, изолированность) — две запущенные транзакции не видят друг друга, во время выполнения одной из них другие не должны влиять на ее результат. Об изоляции мы рассказывали выше.
4. D (Durability, надежность, устойчивость) — если БД подтвердила выполнение транзакции, то сделанные изменения не будут отменены, когда перезагрузится сервер или обесточится система. Конечно, есть кейсы репликации и т.д., но в них мы не будем углубляться. 

Как работает управление многоверсионным параллелизмом (MVCC) 

MVCC подразумевает создание отпечатка БД — снапшота (snapshot). Каждый пользователь условно получает свою версию (образ) БД, где производит изменения. Они не видны другим операциям и процессам.

Например, есть две транзакции, которые хотят внести изменения одновременно. 

T №1 хочет записать:

string = ‘GitVerse’

T №2 изменяет значение:

string = ‘Хостинг’

№2 запустилась раньше. Для нее создается snapshot — образ БД.

№2 вносит изменения: string = ‘Хостинг’. Далее начинается фаза валидации: система смотрит, были ли транзакции, направленные на изменение нашей ячейки. Здесь возможны два варианта: 

• изменений не было — №2 перейдет в стадию «Commited» (утверждена), данные станут консистентными = обретут постоянство);
• изменения были внесены №1 — транзакция будет прервана.

Что происходит с t №1, которая началась позже? До того, как №2 перешла в стадию «Commit», создается снапшот БД для t №1 — виртуальный отпечаток БД, где и происходит транзакционный процесс. 

Т №1 внесла изменения в снапшот. В нем появилась строка ‘GitVerse’. На на фазе валидации транзакция будет прервана: изменения уже произошли, и их внесла T №2.

По сути, при MVCC происходит сохранение нескольких версий каждой строчки в БД. Каждая версия будет иметь временную метку (транзакционный идентификатор). Он указывает, какая версия строки будет видна каждой транзакции.

На скриншоте представлена схема, как работает концепция MVCC. При таком подходе:

• все транзакции работают со своим снимком БД (снапшотом);
• изменения, которые вносят пользователи, не видны другим пользователям до их применения («committed»);
• «читатели» не блокируют «писателей» и других «читателей»;
• писатели не блокируют читателей и других писателей (с исключениями).

Это и есть ответ на вопрос, почему такой вариант позволяет одновременно обрабатывать множество транзакций без возникновения конфликтов и блокировок.

Транзакционные идентификаторы: как PostgreSQL понимает и учитывает транзакции

Механизм может зависеть от конкретной СУБД. Чтобы учитывать транзакции, системе необходимо «помечать их». Для этого придуман идентификационный номер — txid (int32).

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

Таким образом, строчка в БД PostgreSQL выглядит как:

HeapTupleHeaderData содержит идентификаторы:

• xmin — кто создал tuple;
• xmax — кто пометил тупл как удаленный;
• cmin — № команды, кто добавил запись;
• cmax — № команды, кто удалил запись.
• ctid — номер страницы и порядковый номер указателя в массиве.

Когда происходит INSERT в таблицу, создается новый тупл (xmin=txid). При операции DELETE система использует xmax и помечает транзакции как удаленные. В случае с UPDATE можно сказать, что происходит одновременно DELETE + INSERT. Стоит разобраться на примере.

Примеры кода: концепция управления многоверсионным параллелизмом (MVCC)

Писать, тестировать и документировать код можно в GigaIDE Desktop. После скачивания и установки среды разработки необходимо создать проект и подключить БД. 

Чтобы работать было проще, стоит подключить GigaCode. AI-ассистент поддерживает более 30 языков программирования. В GigaIDE Desktop умный помощник доступен из коробки. Для VS Code и других сред разработки его можно легко настроить. Инструкции доступны после авторизации на gitverse.ru.

CREATE TABLE GitVerse_data (
  id serial PRIMARY KEY,
  username TEXT NOT NULL,
  email text,
  repo int
);
INSERT INTO GitVerse_data (username, email, repo) VALUES
('Sbertech', 'support@gitverse.ru', 1),
('Иванов', 'pr@cloud.ru', 2),
('GitVerse', 'sbertech@cloud.ru', 3),
('SberCloud', 'sbercloud@cloud.ru', 4);
SELECT pg_size_pretty(pg_total_relation_size('GitVerse_data'));
SELECT *, xmin, xmax, cmin, cmax, ctid FROM GitVerse_data;
select txid_current();
select * FROM pg_stat_user_tables WHERE relname = 'GitVerse_data';
INSERT INTO GitVerse_data (username, email, repo) VALUES
('GitVerse_admin', 'emailexample@gitverse.ru', 5);
DELETE FROM GitVerse_data WHERE id = 1;
SELECT *, xmin, xmax, cmin, cmax, ctid FROM GitVerse_data;

GigaCode за пару секунд объяснит, что происходит в файле. Достаточно запустить чат и ввести команду /explain <название файла>. 

AI-ассистент разработчика умеет генерировать документацию и тесты. 

А еще можно попросить его объяснить «шаг за шагом» (/explain_step_by_step). 

GigaCode пригодится как начинающим разработчикам, так и программистам с опытом.

Чтобы увидеть XID — идентификаторы распределенных транзакций — используется код:

SELECT *, xmin, xmax, cmin, cmax, ctid FROM GitVerse_data;

После удаления старая строка остается с пометкой, что она удалена. Новая запись вставляется. Апдейт не обновляет строку, а вставляет новую. Для проверки используют:

DELETE FROM GitVerse_data WHERE id = 1;

Минусы Multi Version Concurrency Control (MVCC)

Чтобы понять недостатки Multi Version Concurrency Control, стоит использовать простой код.

Создать таблицу:

CREATE TABLE GitVerse_repos (
  id serial PRIMARY KEY,
  repo char(100)
);
select * from GitVerse_repos;

Заполнить таблицу:

INSERT INTO GitVerse_repos(repo) SELECT 'Проект СберТеха' FROM generate_series(1,50);

Проверить размер:

SELECT pg_size_pretty(pg_total_relation_size('GitVerse_repos'));

Использовать команду, чтобы увидеть метаданные xmin, xmax, cmin, cmax, ctid:

SELECT *, xmin, xmax, cmin, cmax, ctid FROM GitVerse_repos;

Добавить запись, которая вносит изменения:

UPDATE GitVerse_repos SET repo = 'SberCloud';

Проверить размер после апдейта:

SELECT pg_size_pretty(pg_total_relation_size('GitVerse_repos'));

Проверить метаданные xmin, xmax, cmin, cmax, ctid после апдейта:

Было 24 Кб, стало 56 Кб: в два раза больше (х2!). При этом сама таблица как была на 50 записей, так и осталась. 

Результаты после вставки (INSERT):

Результаты после переименования repo с «Проект СберТеха» на «SberCloud»:

Как и отмечали выше, изменяется xmin. Также изменения происходят с ctid.

На примерах кода выше можно понять недостатки Multi Version Concurrency Control (MVCC):

• индексы ничего не знают про мультиверсионность;
• цепочки версий, которые создаются в процессе работы, засоряют память.

Неиспользованные строки в рамках незавершенных транзакций называются «мертвыми» (dead). Постепенно их становится больше, и это вызывает проблемы с производительностью. Мертвые строки:

• занимают место на диске;
• участвуют в UPDATE WHERE и SELECT;
• занимают место в памяти.

Нужно каким-то образом сжать их. Способы сделать это:

• vacuum — освобождает пространство, которое занимают мертвые строки, но не на уровне файловой системы;
• vacuum full — полностью переписывает таблицы в БД и тем самым сокращает их размер, освобождает пространство на уровне файловой системы;
• autovacuum — работает в фоне и запускает vacuum. 

Таким образом, MVCC — концепция, которая имеет как плюсы, так и минусы. Не на всех проектах MVCC обеспечивает оптимизацию и экономию ресурсов.

Реляционные БД, поддерживающие MVCC

MultiVersion Concurrency Control (MVCC) реализован в БД:

• PostgreSQL;
• Oracle Database (Оракул);
• Microsoft SQL Server (уровень изоляции моментального снимка);
• MySQL (механизм хранения InnoDB).

Работу в сценариях с высокой степенью параллелизма поддерживает Document Database Service — сервис создания экземпляров БД, совместимый c MongoDB. Концепция параллизима представлена и в Distributed Message Service for RocketMQ.

Общие выводы о концепции управления многоверсионным параллелизмом (MVCC)

1. MultiVersion Concurrency Control — механизм СУБД, обеспечивает параллельный доступ к БД и чтение/запись без блокировок. 
2. Концепция MVCC подразумевает использование снапшотов — снимков данных, с которым может работать каждый пользователь.
3. MVCC позволяет получить изоляцию любого уровня.
4. Механизм реализован в PostgreSQL, Oracle Database (Оракул), Microsoft SQL Server, MySQL.
5. Реализация MultiVersion Concurrency Control возможна в дисковых БД или In-memory-БД. 

MVCC актуален, если есть много блокирующих записей «читатель-писатель», «писатель-писатель», «писатель-читатель» (модификация БД). Как правило, при чтении («читатель-читатель») взаимные блокировки и конфликты минимальны.