Синхронизационный захват

Сериализация транзакций

В условиях многопользовательского режима СУБД должна иметь план сериализации транзакций– способ выполнения набора транзакций, при котором результат совместного их выполнения эквивалентен результату некоторого последовательного выполнения этих же транзакций.

Между транзакциями могут существовать следующие виды конфликтов:

• W-W - транзакция 2 пытается изменять объект, измененный не закончившейся транзакцией 1;

• R-W - транзакция 2 пытается изменять объект, прочитанный не закончившейся транзакцией 1;

• W-R - транзакция 2 пытается читать объект, измененный не закончившейся транзакцией 1.

Широко распространены два подхода к сериализации транзакций:

• синхронизационные захваты объектов БД,

• использование временных меток.

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

• Пессимистические методы, ориентированные на ситуации, когда конфликты возникают часто, конфликты распознаются и разрешаются немедленно при их возникновении.

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

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

В общих чертах протокол синхронизационного захватасостоит в том, что перед выполнением любой операции в транзакции T над объектом базы данных r от имени транзакции T запрашивается синхронизационный захват объекта r в соответствующем режиме (в зависимости от вида операции):

• совместный режим- S (Shared), означающий разделяемый захват объекта и требуемый для выполнения операции чтения объекта;

• монопольный режим- X (eXclusive), означающий монопольный захват объекта и требуемый для выполнения операций занесения, удаления и модификации.

Совместимость режимов показана в Табл. 59.

Табл. 59. Совместимость режимов в синхронизационном захвате

Транзакция выполняется в двухфазном режиме:

• первая фаза транзакции - накопление захватов;

• вторая фаза (фиксация или откат) - освобождение захватов.

Существуют тупики (deadlock).

1. Пусть транзакции T1 и T2 установили монопольные захваты объектов r1 и r2 соответственно;
2. после этого T1 требуется совместный захват r2, а T2 - совместный захват r1;
3. ни одна из транзакций не может продолжаться, следовательно, монопольные захваты не будут сняты, а совместные - не будут удовлетворены.

Проблема решается построением двудольного графа (первая половинка – вершины-объекты, вторая – вершины-транзакции). Deadlock соответствует цикл в графе (см. Рис. 27). СУБД, работающая по принципу синхронизационного захвата, должна всё время искать циклы в двудольном графе, чтобы распознать тупики.

Рис. 27. Тупик при синхронизационном захвате

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

Существуют расширения метода:

1. Гранулированные захваты (для составных объектов), вводятся дополнительные типы захватов;
2. Предикатные захваты – захватываются не объекты а предикаты (условия, которым удовлетворяют объекты), решается проблема фантомов.

В гранулированных захватахвводятся три дополнительных режима захвата. При захвате объекта в режиме S или X нужно захватить объект верхнего уровня в один из дополнительных режимов. Совместимость режимов показана в Табл. 61, описание дополнительных режимов – в Табл. 60. I*** по отношению к некоторому составному объекту O означает намерение захватить некоторый входящий в O объект в *** режиме.

Табл. 60. Дополнительные режимы в гранулированном захвате

Табл. 61. Совместимость режимов в гранулированном захвате

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

Будем называть простым условием конъюнкцию простых предикатов, имеющих вид «имя-атрибута { = > < } значение». Для простых условий совместимость предикатных захватов легко определяется на основе следующей геометрической интерпретации. Пусть R отношение с атрибутами a1, a2, ..., an, а m1, m2, ..., mn - множества допустимых значений a1, a2, ..., an соответственно (все эти множества - конечные). Тогда можно сопоставить R конечное n-мерное пространство возможных значений кортежей R. Любое простое условие "вырезает" m-мерный прямоугольник в этом пространстве (m <= n). Тогда S-X, X-S, X-X -предикатные захваты от разных транзакций совместимы, если соответствующие прямоугольники не пересекаются. Это иллюстрируется следующим примером, показывающим, что в каких бы режимах не требовала транзакция 1 захвата условия (1<=a<=4) & (b=5), а транзакция 2 - условия (1<=a<=5) & (1<=b<=3), эти захваты всегда совместимы. См. Рис. 28.

Рис. 28. Пространство предикатного захвата