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

В базах данных и обработки транзакций , двухфазное замок ( 2PL ) является управление параллельным методом , который гарантирует сериализуемость . ^{[1] [2]} Это также имя результирующего набора расписаний транзакций (историй) базы данных . Протокол использует блокировки , применяемые транзакцией к данным, которые могут блокировать (интерпретируемые как сигналы для остановки) другим транзакциям доступ к тем же данным в течение срока действия транзакции.

По протоколу 2PL блокировки накладываются и снимаются в два этапа:

1. Фаза расширения: блокировки приобретаются, но блокировки не снимаются.
2. Фаза усадки: блокировки снимаются, а блокировки не возникают.

Базовый протокол использует два типа блокировок: общие и эксклюзивные блокировки. Уточнения основного протокола могут использовать больше типов блокировок. Используя блокировки, которые блокируют процессы, 2PL может быть подвержен взаимоблокировкам , возникающим в результате взаимной блокировки двух или более транзакций.

Блокировки доступа к данным [ править ]

замок- системный объект, связанный с общим ресурсом, таким как элемент данных элементарного типа, строка в базе данных или страница памяти. В базе данных блокировка объекта базы данных (блокировка доступа к данным) может потребоваться транзакцией перед доступом к объекту. Правильное использование блокировок предотвращает нежелательные, неправильные или несогласованные операции с общими ресурсами другими параллельными транзакциями. Когда к объекту базы данных с существующей блокировкой, полученной одной транзакцией, требуется доступ для другой транзакции, система проверяет существующую блокировку для объекта и тип предполагаемого доступа. Если существующий тип блокировки не разрешает этот конкретный тип попытки одновременного доступа, транзакция, пытающаяся получить доступ, блокируется (в соответствии с заранее определенным соглашением / схемой). На практике,блокировка объекта не блокирует напрямую операцию транзакции с объектом, а скорее блокирует эту транзакцию от получения другой блокировки для того же объекта, которая должна удерживаться / принадлежать транзакции перед выполнением этой операции. Таким образом, с помощью механизма блокировки необходимая блокировка операций управляется соответствующей схемой блокировки блокировки, которая указывает, какой тип блокировки блокирует какой тип блокировки.

Используются два основных типа замков:

• Блокировка записи ( исключительная блокировка ) связана с объектом базы данных транзакцией (терминология: «транзакция блокирует объект» или «получает блокировку для него») перед записью (вставкой / изменением / удалением) этого объекта.
• Блокировка чтения ( разделяемая блокировка ) связана с объектом базы данных транзакцией перед чтением (получением состояния) этого объекта.

Общие взаимодействия между этими типами блокировки определяются поведением блокировки следующим образом:

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

Существует несколько вариаций и усовершенствований этих основных типов блокировок с соответствующими вариантами поведения блокировки. Если первая блокировка блокирует другую блокировку, две блокировки называются несовместимыми ; в противном случае замки совместимы . Часто типы блокировок, блокирующие взаимодействия, представлены в технической литературе таблицей совместимости блокировок . Ниже приведен пример общих основных типов блокировки:

Таблица совместимости замков

Тип замка	блокировка чтения	блокировка записи
блокировка чтения		Икс
блокировка записи	Икс	Икс

X указывает на несовместимость, т. Е. Случай, когда блокировка первого типа (в левом столбце) на объекте блокирует блокировку второго типа (в верхней строке) от захвата того же объекта (другой транзакцией). Объект обычно имеет очередь ожидающих запрошенных (транзакциями) операций с соответствующими блокировками. Первая заблокированная блокировка для операции в очереди устанавливается, как только существующая блокирующая блокировка снимается с объекта, а затем выполняется соответствующая операция. Если блокировка для операции в очереди не блокируется какой-либо существующей блокировкой (одновременное существование нескольких совместимых блокировок для одного и того же объекта), она устанавливается немедленно.

Комментарий: В некоторых публикациях записи в таблице просто помечены как «совместимые» или «несовместимые», или соответственно «да» или «нет».

Двухфазная синхронизация и ее частные случаи [ править ]

Двухфазная блокировка [ править ]

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

1. Фаза расширения (также известная как фаза роста): блокировки приобретаются, но блокировки не снимаются (количество блокировок может только увеличиваться).
2. Фаза сжатия (также известная как фаза сжатия): блокировки снимаются, но блокировки не приобретаются.

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

Как правило, без явного знания о транзакции в конце фазы 1, она безопасно определяется только тогда, когда транзакция завершила обработку и запросила фиксацию. В этом случае все блокировки могут быть сняты сразу (фаза 2).

Консервативная двухфазная синхронизация [ править ]

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

Строгая двухфазная блокировка [ править ]

Чтобы соответствовать протоколу S2PL, транзакция должна соответствовать 2PL и снимать свои (исключительные) блокировки записи только после того, как она закончилась, то есть была либо зафиксирована, либо прервана . С другой стороны, блокировки чтения (разделяемые) регулярно снимаются во время фазы 2. Этот протокол не подходит для B-деревьев, потому что он вызывает Узкое место (в то время как B-деревья всегда начинают поиск от родительского корня). ^{[ необходима цитата ]}

Сильная строгая двухфазная синхронизация [ править ]

или строгость , или строгое планирование , или жесткая двухфазная синхронизация

Для соблюдения строгой строгой двухфазной блокировки (SS2PL) протокол блокировки освобождает как записи (исключительные), так и чтения (общие) блокировки, применяемые транзакцией только после завершения транзакции, то есть только после завершения выполнения ( готовности ) и становится либо совершенным, либо прерванным. Этот протокол также соответствует правилам S2PL. Транзакция, подчиняющаяся SS2PL, может рассматриваться как имеющая фазу 1, которая длится всю продолжительность выполнения транзакции, а не фазу 2 (или вырожденную фазу 2). Таким образом, фактически осталась только одна фаза, и «двухфазность» в названии, кажется, все еще используется из-за исторического развития концепции от 2PL, а 2PL является суперклассом. Свойство расписания SS2PL также называют строгостью.. Это также имя класса расписаний, обладающих этим свойством, и расписание SS2PL также называется «строгим расписанием». Термин «жесткость» свободен от ненужного наследия «двухфазности», а также не зависит от какого-либо (блокирующего) механизма (в принципе, могут использоваться другие блокирующие механизмы). Соответствующий механизм блокировки объекта иногда называют строгим 2PL .

SS2PL является частным случаем S2PL, т. Е. Класс расписаний SS2PL является надлежащим подклассом S2PL (каждое расписание SS2PL также является расписанием S2PL, но существуют расписания S2PL, которые не являются SS2PL).

SS2PL был предпочтительным протоколом управления параллелизмом для большинства систем баз данных и использовался с первых дней их появления в 1970-х годах. Доказано, что он является эффективным механизмом во многих ситуациях и обеспечивает, помимо сериализуемости, также строгость (особый случай безкаскадной возможности восстановления), которая играет важную роль для эффективного восстановления базы данных , а также упорядочение обязательств (CO) для участия в распределенных средах, где CO используются решения на основе распределенной сериализуемости и глобальной сериализуемости . Являясь подмножеством CO, эффективная реализация распределенного SS2PL существует безраспределенный диспетчер блокировок (DLM), а распределенные взаимоблокировки (см. ниже) разрешаются автоматически. Тот факт, что SS2PL, используемый в системах с несколькими базами данных, обеспечивает глобальную сериализуемость, был известен за годы до открытия CO, но только с CO пришло понимание роли протокола атомарной фиксации в поддержании глобальной сериализуемости, а также наблюдение за автоматической разрешение распределенных тупиков (см. подробный пример Distributed SS2PL). На самом деле, SS2PL, наследование свойств восстанавливаемости и CO, более важно, чем подмножество 2PL, которое само по себе в своей общей форме, помимо простого механизма сериализуемости (однако сериализуемость также подразумевается CO), неизвестно наделить SS2PL любыми другими значительными качествами. 2PL в его общей форме, а также в сочетании со строгостью, т. Е. Строгим 2PL (S2PL), как известно, не используются на практике. Популярный SS2PL не требует маркировки «конец фазы 1», как это делают 2PL и S2PL, и поэтому его проще реализовать. Кроме того, в отличие от общей 2PL, SS2PL предоставляет, как упоминалось выше, полезные свойства упорядочивания Strictness и Commitment .

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

Комментарии:

1. SS2PL против S2PL: оба обеспечивают сериализуемость и строгость. Поскольку S2PL является суперклассом SS2PL, он может, в принципе, обеспечивать больший параллелизм. Тем не менее, преимущества параллелизма обычно практически не замечаются (точно такая же блокировка существует для обоих, с практически не намного более ранним снятием блокировки для S2PL), и накладные расходы на работу с механизмом конца фазы 1 в S2PL, отдельно от завершения транзакции. , не оправдано. Кроме того, в то время как SS2PL обеспечивает упорядочивание по обязательствам , S2PL - нет. Это объясняет предпочтение SS2PL над S2PL.
2. Особенно до 1990 года, но также и после, во многих статьях и книгах, например (Bernstein et al. 1987, p. 59), ^[1] термин «строгий 2PL» (S2PL) часто определялся протоколом блокировки «Release все блокируется только после завершения транзакции », что является протоколом SS2PL. Таким образом, «Strict 2PL» не могло быть там названием пересечения Strictness и 2PL, которое больше, чем класс, генерируемый протоколом SS2PL. Это вызвало недоумение. С явным определением S2PL как пересечения строгости и 2PL, нового названия SS2PL и явного различия между классами S2PL и SS2PL, статьи (Breitbart et al. 1991) ^[3] и (Raz 1992) ^{[4 ]} намеревались устранить путаницу: первый использовал название «строгость», а второй - «SS2PL».
3. Существует более общее свойство, чем SS2PL (суперкласс расписания), строгое обязательное упорядочивание (Strict CO или SCO), которое также обеспечивает сериализуемость, строгость и CO и имеет аналогичные накладные расходы на блокировку. В отличие от SS2PL, SCO не блокирует конфликт чтения-записи (блокировка чтения не блокирует получение блокировки записи; и SCO, и SS2PL имеют одинаковое поведение для конфликтов записи-чтения и записи-записи) за счет возможной задержки commit, и при таком типе конфликта SCO имеет более короткое среднее время завершения транзакции и лучшую производительность, чем SS2PL. ^[5] В то время как SS2PL подчиняется приведенной выше таблице совместимости блокировок , SCO имеет следующую таблицу:

Совместимость замков для SCO

Тип замка	блокировка чтения	блокировка записи
блокировка чтения
блокировка записи	Икс	Икс

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

Резюме - отношения между классами [ править ]

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

Тупики в 2PL [ править ]

Блокирует блокировку операций доступа к данным. Взаимная блокировка между транзакциями приводит к тупиковой ситуации , когда выполнение этих транзакций приостанавливается и завершение невозможно. Таким образом, тупиковые ситуации необходимо разрешить, чтобы завершить выполнение этих транзакций и освободить связанные вычислительные ресурсы. Тупик - это отражение потенциального цикла в графе приоритета , который произошел бы без блокировки. Тупиковая ситуация разрешается путем прерывания транзакции, связанной с таким потенциальным циклом, и прерывания цикла. Это часто обнаруживается с помощью графа ожидания (графа конфликтов, блокированных блокировками от материализации; конфликты, не материализованные в базе данных из-за заблокированных операций, не отражаются в графе приоритета и не влияют насериализуемость ), который указывает, какая транзакция «ожидает» снятия блокировки с помощью какой транзакции, а цикл означает тупик. Для прерывания цикла достаточно прерывания одной транзакции за цикл. Если транзакция была прервана из-за разрешения тупиковой ситуации, приложение должно решить, что делать дальше. Обычно приложение перезапускает транзакцию с самого начала, но может отложить это действие, чтобы дать другим транзакциям достаточно времени для завершения, чтобы избежать возникновения новой тупиковой ситуации. ^[6]

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

Когда SS2PL эффективно используется в распределенной среде, то глобальные взаимоблокировки из-за блокировки порождают тупиковые ситуации с голосованием в 2PC и автоматически разрешаются с помощью 2PC (см. Упорядочивание обязательств (CO) в разделе Точная характеристика тупиков с голосованием по глобальным циклам ; Нет ссылок кроме статей CO, как известно, это замечают). В общем случае 2PL глобальные взаимоблокировки аналогично автоматически разрешаются точкой синхронизации.протокол завершения фазы 1 в распределенной транзакции (точка синхронизации достигается "голосованием" (уведомление о завершении фазы 1) и распространяется участникам распределенной транзакции так же, как точка принятия решения в атомарной фиксации; в по аналогии с точкой принятия решения в CO, конфликтующая операция в 2PL не может произойти до конечной точки синхронизации фазы 1, с тем же результирующим тупиком голосования в случае глобального тупика доступа к данным; тупик голосования (который также является блокировкой на основе глобального тупика) автоматически разрешается протоколом, прерывающим некоторую вовлеченную транзакцию с отсутствующим голосом, обычно с использованием тайм-аута ).

Комментарий :

Когда данные распределяются между участниками протокола атомарной фиксации (например, 2PC), автоматическое глобальное разрешение тупиковых ситуаций не упоминается в исследовательской литературе по базам данных, хотя тупиковые ситуации в таких системах были довольно интенсивной областью исследований:

• Для CO и его особого случая SS2PL автоматическое разрешение протокола атомарной фиксации было замечено только в статьях CO. Однако на практике было замечено, что во многих случаях глобальные взаимоблокировки очень редко обнаруживаются специальными механизмами разрешения, меньше, чем можно было ожидать («Почему мы видим так мало глобальных взаимоблокировок?»). Причина, вероятно, в тупиках, которые разрешаются автоматически и, следовательно, не обрабатываются и не учитываются механизмами;
• Для 2PL в целом автоматическое разрешение с помощью (обязательного) протокола точки синхронизации конца фазы (который имеет тот же механизм голосования, что и протокол атомарной фиксации, и такая же обработка отсутствующих голосов при тупике голосования, что приводит к разрешению глобального тупика) не упоминался до сегодняшнего дня (2009 г.). Практически используется только специальный случай SS2PL, когда не требуется синхронизация конца фазы в дополнение к протоколу атомарной фиксации.

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

См. Также [ править ]

• Сериализуемость
• Lock (информатика)

Ссылки [ править ]