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

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

История

Концепция блокировок как механизма синхронизации доступа к ресурсам возникла в ранних операционных системах и файловых системах. Применительно к базам данных идея двухфазной блокировки была формализована в 1970-х годах, в период активного развития реляционных СУБД и теории транзакций. Одним из ключевых вкладов стала работа К. П. Эсварана, Дж. Грея, Р. А. Лори и И. Л. Трейгера (1976 год), в которой были заложены основы теории сериализуемости и показано, что двухфазная блокировка является достаточным условием для обеспечения сериализуемости. Впоследствии протокол был реализован в большинстве коммерческих СУБД, таких как IBM DB2, Oracle Database, Microsoft SQL Server и PostgreSQL, став стандартным подходом к управлению параллелизмом.

Основные принципы

Фазы блокировки

Протокол 2PL предписывает транзакции строгий порядок операций с блокировками:

1. Фаза расширения (Growing Phase): транзакция может только захватывать новые блокировки (устанавливать блокировки на данные), но не может освобождать уже захваченные. В этой фазе транзакция получает доступ к данным, которые ей необходимо прочитать или изменить.
2. Фаза сжатия (Shrinking Phase): транзакция может только освобождать ранее захваченные блокировки, но не может захватывать новые. Эта фаза начинается после того, как транзакция решила, что больше не будет запрашивать доступ к новым данным.

Ключевым моментом является то, что транзакция не может перейти из фазы сжатия обратно в фазу расширения. Момент перехода между фазами называется точкой блокировки (lock point).

Типы блокировок

В рамках протокола 2PL обычно используются два основных типа блокировок:

• Разделяемая блокировка (Shared Lock, S-lock): устанавливается для операции чтения данных. Несколько транзакций могут одновременно удерживать разделяемые блокировки на одном и том же объекте данных.
• Исключительная блокировка (Exclusive Lock, X-lock): устанавливается для операции записи (вставки, обновления, удаления) данных. Только одна транзакция может удерживать исключительную блокировку на объекте, и никакая другая транзакция не может в это время удерживать ни разделяемую, ни исключительную блокировку на том же объекте.

Совместимость блокировок определяется следующим образом: S-блокировка совместима с S-блокировкой, но несовместима с X-блокировкой; X-блокировка несовместима ни с какой другой блокировкой.

Разновидности протокола

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

Базовая двухфазная блокировка (Basic 2PL)

Это классическая версия протокола, описанная выше. Транзакция может освободить блокировку в любой момент после окончания фазы расширения. Основной недостаток — возможность каскадного отката (cascading abort): если одна транзакция, освободившая блокировку, впоследствии откатывается, другие транзакции, которые уже прочитали изменённые ею данные, также должны быть отменены.

Строгая двухфазная блокировка (Strict 2PL)

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

Усиленная двухфазная блокировка (Rigorous 2PL)

Самая строгая версия. Транзакция удерживает все блокировки (как исключительные, так и разделяемые) до момента своего завершения. Это гарантирует не только отсутствие каскадного отката, но и упрощает реализацию восстановления после сбоев, однако может снижать уровень параллелизма.

Свойства и гарантии

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

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

Предотвращение аномалий

Протокол 2PL эффективно предотвращает следующие аномалии параллельного доступа:

• Потерянное обновление (Lost Update): когда две транзакции одновременно читают и изменяют одни и те же данные, и одно из изменений теряется.
• «Грязное» чтение (Dirty Read): когда транзакция читает данные, изменённые другой транзакцией, которая ещё не завершилась.
• Неповторяемое чтение (Non-repeatable Read): когда транзакция при повторном чтении тех же данных получает другой результат из-за изменений, внесённых другой транзакцией.
• Фантомное чтение (Phantom Read): когда набор строк, удовлетворяющих условию запроса, изменяется между двумя выполнениями запроса в одной транзакции из-за вставки или удаления строк другой транзакцией.

Недостатки и ограничения

Взаимные блокировки (Deadlocks)

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

Снижение параллелизма

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

Необходимость в управлении блокировками

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

Применение

Двухфазная блокировка является основным механизмом управления параллелизмом в большинстве традиционных реляционных СУБД, ориентированных на обеспечение строгой согласованности данных (ACID-транзакции). Она широко применяется в банковских системах, системах управления заказами, бухгалтерском учёте и других областях, где требуется высокая надёжность и предсказуемость результатов параллельного доступа. В современных распределённых системах и NoSQL-базах данных, где требования к производительности и масштабируемости часто преобладают над строгой согласованностью, 2PL может использоваться в ограниченном виде или заменяться другими механизмами, такими как многоверсионность (MVCC) или оптимистические блокировки.

Критика

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

Источники

• Эсваран, К. П., Грей, Дж., Лори, Р. А., Трейгер, И. Л. «The notions of consistency and predicate locks in a database system». Communications of the ACM, 1976.
• Грей, Дж., Рейтер, А. «Transaction Processing: Concepts and Techniques». Morgan Kaufmann, 1993.
• Сильбершатц, А., Корф, Г. Ф., Сударшан, С. «Системы баз данных: полный курс». Вильямс, 2012.
• Коннолли, Т., Бегг, К. «Базы данных: проектирование, реализация и сопровождение». Вильямс, 2003.
• Документация PostgreSQL: «Управление параллелизмом».