Рубрики
Без рубрики

Как работает алгоритм 2PL (двухфазной блокировки)

Узнайте, как работает алгоритм 2PL (двухфазной блокировки) и как он может гарантировать целостность и сериализуемость данных в системе реляционных баз данных.

Автор оригинала: Vlad Mihalcea.

Вступление

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

В этой статье я собираюсь объяснить, как работает алгоритм 2PL и как вы можете реализовать его на любом языке программирования.

Как работает алгоритм 2PL (двухфазной блокировки)? @vlad_mihalcea объясняет. https://t.co/J4BtK3qQJn pic.twitter.com/pm12b3tE7t

Типы замков

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

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

Блокировка записи или эксклюзивная блокировка запрещает как операции чтения, так и операции записи на данном ресурсе.

Позволять Предотвращать Блокировка чтения
Предотвращать Предотвращать Блокировка записи

Некоторые системы баз данных, такие как PostgreSQL, MySQL или SQL Server, предлагают возможность получения блокировок чтения и записи для данного кортежа или диапазона кортежей. Другие системы баз данных, такие как Oracle, позволяют получать блокировки записи/исключения только с помощью предложения ДЛЯ ОБНОВЛЕНИЯ .

Оракул ДЛЯ ОБНОВЛЕНИЯ ДЛЯ ОБНОВЛЕНИЯ
SQL Server С (ЗАСОВ, УКЛЮЧИНА) С (БЛОКИРОВКОЙ, БЛОКИРОВКОЙ, БЛОКИРОВКОЙ)
PostgreSQL ДЛЯ ОБМЕНА ДЛЯ ОБНОВЛЕНИЯ
MySQL БЛОКИРОВКА В РЕЖИМЕ ОБЩЕГО ДОСТУПА ДЛЯ ОБНОВЛЕНИЯ

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

Однако блокировки чтения и записи не ограничиваются только системами баз данных. Хотя традиционно ввод блока Java synchronized позволяет получить эксклюзивную блокировку, начиная с версии 1.5, Java позволяет блокировать как чтение, так и запись с помощью объекта ReentrantReadWriteLock .

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

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

Для этой цели протокол 2PL определяет стратегию управления блокировками для обеспечения строгой сериализации.

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

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

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

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

  • И Алиса, и Боб получают блокировку чтения для данной записи post с помощью предложения SELECT FOR SHARE PostgreSQL.
  • Когда Боб пытается выполнить инструкцию UPDATE для записи post , его инструкция блокируется менеджером блокировок, поскольку инструкция UPDATE должна получить блокировку записи в строке post , в то время как Алиса все еще удерживает блокировку чтения для этой записи базы данных.
  • Только после того, как транзакция Алисы закончится и все ее блокировки будут разблокированы, Боб сможет возобновить свою операцию ОБНОВЛЕНИЯ.
  • Заявление Боба об ОБНОВЛЕНИИ приведет к обновлению блокировки, поэтому его ранее приобретенная блокировка чтения будет заменена эксклюзивной блокировкой, которая не позволит другим транзакциям получить блокировку чтения или записи для той же записи записи.
  • Алиса запускает новую транзакцию и выдает запрос SELECT FOR SHARE с запросом на получение блокировки чтения для той же записи post , но оператор блокируется менеджером блокировки, поскольку Боб владеет эксклюзивной блокировкой этой записи.
  • После того, как транзакция Боба будет зафиксирована, все его блокировки будут сняты, и запрос Алисы на выбор может быть возобновлен.

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

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

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

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

Вывод

Алгоритм 2PL (двухфазной блокировки) был введен в 1976 году в Понятия согласованности и блокировки предикатов в системе баз данных статья Капали Эсварана и Джима Грея (и др.), в которой показано, что сериализуемость может быть получена, если все транзакции будут использовать алгоритм 2PL.

Первоначально все системы баз данных использовали 2PL для реализации сериализуемых транзакций, но со временем многие поставщики перешли к механизмам управления параллелизмом MVCC (Управление параллелизмом с несколькими версиями).

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

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

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

Читайте ещё по теме: