Перевод статьи «How does the 2PL (Two‑Phase Locking) algorithm work» Vlad Mihalcea.

Вступление

Алгоритм двухфазной блокировки (Two-Phase Locking, 2PL) — один из старейших механизмов управления параллелизмом, используемых реляционными СУБД для обеспечения целостности данных. В этой статье я расскажу, как работает алгоритм 2PL и как его можно реализовать на любом языке программирования.

Виды блокировок

Прежде чем приступить к обсуждению реализации алгоритма 2PL, очень важно объяснить, как работают блокировки чтения и записи. Блокировка на чтение, также известная как блокировка для совместного доступа (share lock), предотвращает запись в ресурс, но позволяет одновременное чтение другими пользователями. Блокировка на запись, также известная как блокировка для эксклюзивного доступа (exclusive lock), запрещает как операции чтения, так и операции записи в данный ресурс.

Если одна транзакция заблокировала ресурс на чтение, то другая транзакция тоже может заблокировать этот ресурс на чтение, но не может заблокировать его на запись. В случае, если ресурс заблокирован на запись, никакая другая транзакция не может заблокировать его ни на чтение ни на запись.

Некоторые СУБД, такие как PostgreSQL, MySQL или SQL Server, дают возможность заблокировать кортежи в таблице как на чтение так и на запись. Например, в PostgreSQL блокировка на чтение осуществляется командой SELECT FOR SHARE, а блокировка на запись командой SELECT FOR UPDATE. Другие СУБД, такие как Oracle, позволяют заблокировать кортежи только на запись с помощью инструкции FOR UPDATE.

Однако, использование блокировок на чтение и на запись не ограничивается только системами управления базами данных. Блокировки активно применяются в параллельном программировании для синхронизации доступа потоков выполнения (thread) в критическую секцию, чтобы избежать состояния гонки (race condition) при работе с общими ресурсами. Например, в Java вход в критическую секцию, определенную блоком sychronized, позволяет получить эксклюзивную блокировку. А начиная с версии 1.5 в Java появилась возможность разделить блокировку на чтение и блокировку на запись с помощью класса ReentrantReadWriteLock из пакета java.util.concurrent.

Двухфазная блокировка

Одних блокировок недостаточно для предотвращения конфликтов. Стратегия управления параллелизмом должна определять, как блокировки приобретаются и освобождаются, поскольку это также влияет на чередование выполнения транзакций. Алгоритм двухфазной блокировки (2PL) определяет стратегию управления блокировками для обеспечения строгой сериализуемости.

Протокол 2PL разделяет транзакцию на две части:

• фаза расширения (блокировки приобретаются, и ни одна блокировка не может быть освобождена)

• фаза сокращения (все блокировки освобождаются, и никакие другие блокировки не могут быть приобретены)

Для транзакции базы данных фаза расширения начинается с момента начала транзакции и продолжается до ее окончания, а фаза сокращения выполняется в момент фиксации или отката, так что в конце транзакции все полученные блокировки освобождаются.

На следующем рисунке показано, как 2PL координирует чередование выполнения транзакций:

1. Алиса и Боб получили блокировку на чтение для сообщения 1 с помощью инструкции PostgreSQL SELECT FOR SHARE.

2. Когда Боб попытался изменить сообщение 1 с помощью команды UPDATE, база данных остановила его транзакцию. Внесение изменений требует блокировку на запись, но она не может быть получена, пока существует хотя бы одна блокировка на чтение. Транзакция Боба вынуждена ждать, так как транзакция Алисы все еще удерживает блокировку на чтение для сообщения 1.

3. Только после того, как транзакция Алисы завершилась, блокировка на чтение для сообщения 1 была снята, и транзакция Боба смогла возобновить выполнение операции UPDATE.

4. Инструкция UPDATE привела к повышению уровня блокировки, которую захватила транзакция Боба для сообщения 1. Ранее это была блокировка на чтение, но команда UPDATE заменила её на эксклюзивную блокировку, которая не позволит другим транзакциям получить ни блокировку на чтение ни блокировку на запись для этого сообщения.

5. Алиса начала новую транзакцию и отправила запрос SELECT FOR SHARE, который требует получение блокировки на чтение для сообщения 1. Но база данных остановила выполнение этого запроса, так как транзакция Боба владеет блокировкой на запись этого сообщения.

6. Только после завершения транзакции Боба, блокировка сообщения была снята, и выполнение запроса SELECT Алисы было возобновлено.

Строгая сериализуемость

Алгоритм 2PL обеспечивает строгую сериализуемость, которая является золотым стандартом в области целостности данных. Строгая сериализуемость означает, что результат является как сериализуемым, так и линеаризуемым.

Две или более транзакции являются сериализуемыми, если связанные с ними операции чтения и записи чередуются таким образом, что результат эквивалентен некоторому последовательному выполнению. Например, если у нас есть две транзакции A и B, то при условии, что результат является либо A, B, либо B, A, эти две транзакции являются сериализуемыми. Для N транзакций результат должен быть эквивалентен одной из N! перестановок транзакций.

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

Заключение

Алгоритм 2PL (Two-Phase Locking) был представлен в 1976 году в статье "The Notions of Consistency and Predicate Locks in a Database System" K.P. Eswaran, J.N. Gray, R.A. Lorie и I.L. Traiger, в которой было продемонстрировано, что сериализуемость может быть достигнута, если все транзакции используют алгоритм 2PL.

Изначально все СУБД использовали 2PL для реализации сериализуемых транзакций, но со временем многие поставщики перешли на MVCC (Multi-Version Concurrency Control) механизмы управления параллелизмом.

В настоящее время только SQL Server по умолчанию использует алгоритм 2PL. Однако, если вы включите опции READ_COMMITTED_SNAPSHOT или ALLOW_SNAPSHOT_ISOLATION на уровне базы данных, то SQL Server переключится на использование MVCC.

Хотя механизм хранения данных InnoDB реализует поддержку MVCC в MySQL, однако, при переключении на уровень изоляции Serializable, база данных будет использовать алгоритм 2PL, поскольку блокировки будут устанавливаться как при операциях чтения, так и при операциях записи.

По этой причине очень важно понимать, как работает алгоритм 2PL и что он может гарантировать строгую сериализуемость.