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

Two-phase locking
Эта статья о контроль параллелизма. Консенсус по фиксации в распределенной транзакции см. Протокол двухфазной фиксации.

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

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

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

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

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

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

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

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

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

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

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

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

Двухфазная блокировка и ее особые случаи

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

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

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

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

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

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

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

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

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

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

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

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

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 предоставляет, как упоминалось выше, полезные Строгость и Заказ обязательств характеристики.

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

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

  1. SS2PL против S2PL: оба обеспечивают сериализуемость и строгость. Поскольку S2PL является суперклассом SS2PL, он может, в принципе, обеспечивать больший параллелизм. Тем не менее, преимущества параллелизма обычно практически не замечаются (точно такая же блокировка существует для обоих, с практически не намного более ранним снятием блокировки для S2PL), и накладные расходы на работу с механизмом конца фазы 1 в S2PL, отдельно от завершения транзакции , не оправдано. Кроме того, хотя SS2PL предоставляет Заказ обязательств, S2PL нет. Это объясняет предпочтение SS2PL над S2PL.
  2. Особенно до 1990 г., но также и после, во многих статьях и книгах, например, (Bernstein et al. 1987, p. 59),[1] термин «строгий 2PL» (S2PL) часто определялся протоколом блокировки «снимать все блокировки только после завершения транзакции», который является протоколом SS2PL. Таким образом, «Strict 2PL» не могло быть там названием пересечения Strictness и 2PL, которое больше, чем класс, генерируемый протоколом SS2PL. Это вызвало недоумение. С явным определением S2PL как пересечения строгости и 2PL, нового названия SS2PL и явного различия между классами S2PL и SS2PL, статьи (Breitbart et al. 1991)[3] и (Раз 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 несравнимы (т. Е. Ни один класс не содержит другой класс).

Резюме - отношения между классами

Расписание классов сдерживания: Стрелка от класса A к классу B указывает, что класс A строго содержит B; отсутствие направленного пути между классами означает, что классы несопоставимы. Недвижимость по сути блокирующий, если это может быть выполнено только путем блокировки операций доступа к данным транзакции до тех пор, пока определенные события не произойдут в других транзакциях. (Раз 1992)

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

Тупики в 2PL

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б Филип А. Бернштейн, Вассос Хадзилакос, Натан Гудман (1987): Контроль параллелизма и восстановление в системах баз данных, Издательство Addison Wesley Publishing Company, ISBN 0-201-10715-5
  2. ^ Герхард Вейкум, Готфрид Фоссен (2001): Системы транзакционной информации, Эльзевьер, ISBN 1-55860-508-8
  3. ^ Юрий Брейтбарт, Димитриос Георгакопулос, Марек Русинкевич, Авраам Зильбершатц (1991): «О строгом планировании транзакций», IEEE Transactions по разработке программного обеспечения (TSE), сентябрь 1991 г., том 17, выпуск 9, стр. 954-960, ISSN 0098-5589
  4. ^ Йоав Раз (1992): «Принцип упорядочивания обязательств или гарантии сериализуемости в гетерогенной среде множества автономных менеджеров ресурсов, использующих атомарные обязательства» В архиве 2007-05-23 на Wayback Machine (PDF), Материалы восемнадцатой Международной конференции по очень большим базам данных (VLDB), стр. 292-312, Ванкувер, Канада, август 1992 г., ISBN 1-55860-151-1 (также DEC-TR 841, Корпорация цифрового оборудования, Ноябрь 1990 г.)
  5. ^ Йоав Раз (1991): «Порядок строгих обязательств на основе блокировки, или Как улучшить параллелизм в диспетчерах ресурсов на основе блокировки», DEC-TR 844, декабрь 1991 г.
  6. ^ Принципы обработки транзакций; ISBN 9780080948416; Глава 6 Страница 152