Модель конфликтов транзакций. Граф предшествования

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

Для проверки упорядоченности графиков используется граф предшествования (граф упорядоченности).

Определение. Для графика выполнения множества транзакций S = {A, B} граф предшествования представляет собой ориентированный граф G = (V, E), состоящий из множества вершин V – определяющих выполняемые транзакции и множества ориентированных ребер или дуг E – формируемых следующим образом:

1. Создается вершина, соответствующая каждой транзакции.

2. Создается дуга A → B, если транзакция B считывает значение элемента данных, записанного транзакцией A.

3. Создается дуга A → B, если транзакция B записывает значение в элемент данных, после того, как он был считан транзакцией A.

4. Создается дуга A → B, если транзакция B записывает значение в элемент данных, после того, как он был записан транзакцией A.

Если в графе предшествования, соответствующем чередующемуся графику S, существует дуга A ® B, то в любом последовательном графике S¢, транзакция A должна предшествовать транзакции B.

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

Например. Построим граф предшествования для примера графика демонстрирующего проблему потери обновления (см. график выше).

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

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

Различают два типа блокировок:

• Монопольные блокировки (X-блокировки, X-locks - eXclusive locks) - блокировки без взаимного доступа (блокировка записи).
• Разделяемые блокировки (S-блокировки, S-locks - Shared locks) - блокировки с взаимным доступом (блокировка чтения).

Если транзакция A блокирует объект при помощи X -блокировки, то всякий доступ к этому объекту со стороны других транзакций отвергается.

Если транзакция A блокирует объект при помощи S -блокировки, то

• запросы со стороны других транзакций на X -блокировку этого объекта будут отвергнуты,
• запросы со стороны других транзакций на S -блокировку этого объекта будут приняты.

Правила взаимного доступа к заблокированным объектам можно представить в виде таблицы совместимости блокировок. Если транзакция A определила блокировку на некоторый объект, а транзакция B после этого пытается наложить еще одну блокировку на этот же объект, то успешность блокирования транзакцией B объекта описывается таблицей 1:

Таблица 1. Матрица совместимости S- и X-блокировок

Три случая, когда транзакция B не может блокировать объект, соответствуют трем видам конфликтов между транзакциями.

Доступ к объектам базы данных на чтение и запись должен осуществляться в соответствии со следующим протоколом доступа к данным:

1. Прежде чем прочитать объект, транзакция должна наложить на этот объект S -блокировку.

2. Прежде чем обновить объект, транзакция должна наложить на этот объект X -блокировку. Если транзакция уже заблокировала объект S -блокировкой (для чтения), то перед обновлением объекта S -блокировка должна быть заменена X -блокировкой.

3. Если блокировка объекта транзакцией B отвергается оттого, что объект уже заблокирован транзакцией A, то транзакция B переходит в состояние ожидания. Транзакция B будет находиться в состоянии ожидания до тех пор, пока транзакция A не снимет блокировку объекта.

4. X -блокировки, наложенные транзакцией A, сохраняются до конца транзакции A.

Управление блокировками осуществляется из программного обеспечения, и осуществляется на уровне пользовательского соединения. Блокировка указывает, что пользователь имеет право на использование соответствующего ресурса. К ресурсам, которые может блокировать пользователь, относятся строка данных, страница данных, экстент (8 страниц), таблица или вся база данных.

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

Пользователь не может владеть блокировкой, конфликтующей с блокировкой, которой уже владеет другой пользователь.

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

Система управления блокировками автоматически захватывает и освобождает блокировки в соответствии с действиями пользователей. Для управления блокировками не требуется никаких действий со стороны DBA (администратора базы данных) или программиста.

Блокировки объектов БД разделяются следующим образом:

• Блокировка самой базы данных.
• Блокировка файлов базы данных.
• Блокировка таблиц базы данных.
• Блокировка страниц (Единиц обмена с диском, обычно 2-16 Кб. На одной странице содержится несколько строк одной или нескольких таблиц).
• Блокировка отдельных строк таблиц.
• Блокировка отдельных полей.

Кроме того, можно блокировать индексы, заголовки таблиц или другие объекты.

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

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

Устно. Современные СУБД, как правило, поддерживают минимальный уровень блокировки на уровне строк или страниц. (В старых версиях настольной СУБД Paradox поддерживалась блокировка на уровне отдельных полей.).

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

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

Вводятся следующие типы блокировок:

• Преднамеренная блокировка с возможностью взаимного доступа (IS-блокировка - Intent Shared lock) или Разделяемое намерение. Указывает, что в транзакции предполагается наложить на ресурс разделяемую блокировку.

Накладывается на некоторый составной объект T и означает намерение блокировать некоторый входящий в T объект в режиме S -блокировки. Например, при намерении читать строки из таблицы T, эта таблица должна быть заблокирована в режиме IS (до этого в таком же режиме должен быть заблокирован файл).

• Преднамеренная блокировка без взаимного доступа (IX-блокировка - Intent eXclusive lock) или Монопольное намерение. Указывает, что в транзакции предполагается наложить на ресурс монопольную блокировку.

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

• Преднамеренная блокировка, как с возможностью взаимного доступа, так и без него (SIX-блокировка - Shared Intent eXclusive lock) или Разделяемо-монопольное намерение. Указывает, что в транзакции предполагается наложить разделяемую блокировку на одни ресурсы и монопольную блокировку на другие ресурсы.

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

Устно. IS, IX и SIX -блокировки должны накладываться на сложные объекты БД (таблицы, файлы). Кроме того, на сложные объекты могут накладываться и блокировки типов S и X. Для сложных объектов (например, для таблицы базы данных) таблица совместимости блокировок имеет следующий вид:

Таблица 2 Расширенная таблица совместимости блокировок

Более точная формулировка протокола преднамеренных блокировок для доступа к данным выглядит следующим образом:

1. Прежде чем транзакция наложит S-блокировку на данный кортеж, она должна наложить IS - блокировку или другую более сильную блокировку на отношение, в котором содержится данный кортеж.

2. Прежде чем транзакция наложит Х-блокировку на данный кортеж, она должна наложить IХ - блокировку или другую более сильную блокировку на отношение, в котором содержится данный кортеж

Понятие относительной силы блокировок можно описать при помощи диаграммы приоритета (сверху - более сильные блокировки, снизу - более слабые):

Таблица 3 Диаграмма приоритета блокировок

Устно. Протокол преднамеренных блокировок не определяет однозначно, какие блокировки должны быть наложены на родительский объект при блокировании дочернего объекта. Например, при намерении задать S -блокировку строки таблицы, на таблицу, включающую эту строку, можно наложить любую из блокировок типа IS, S, IX, SIX, X. При намерении задать X-блокировку строки, на таблицу можно наложить любую из блокировок типа IX, SIX, X.

Устно. Рассмотрим, как разрешается проблема фиктивных элементов (фантомов) с использованием протокола преднамеренных блокировок для доступа к данным.

Транзакция A дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция B, которая добавляет новую строку, удовлетворяющую условию отбора.

Транзакция B перед попыткой вставить новую строку должна наложить на таблицу IX-блокировку, или более сильную (SIX или X). Тогда транзакция A, для предотвращения возможного конфликта, должна наложить такую блокировку на таблицу, которая не позволила бы транзакции B наложить IX-блокировку. По таблице совместимости блокировок определяем, что транзакция A должна наложить на таблицу S, или SIX, или X-блокировку. (Блокировки IS недостаточно, т.к. эта блокировка позволяет транзакции B наложить IX-блокировку для последующей вставки строк).

Время	Транзакция A	Транзакция B
	S-блокировка таблицы (с целью потом блокировать строки) - успешна	---
	S-блокировка строк, удовлетворяющих условию . (Заблокировано n строк)	---
	Выборка строк, удовлетворяющих условию . (Отобрано n строк)	---
	---	IX-блокировка таблицы (с целью потом вставлять строки) - отвергается из-за конфликта с S-блокировкой, наложенной транзакцией A
	---	Ожидание…
	---	Ожидание…
	S-блокировка строк, удовлетворяющих условию . (Заблокировано n строк)	Ожидание…
	Выборка строк, удовлетворяющих условию . (Отобрано n строк)	Ожидание…
	COMMIT блокировки снимаются	Ожидание…
	---	IX-блокировка таблицы (с целью потом вставлять строки) - успешна
	---	Вставка новой строки, удовлетворяющей условию .
	---	COMMIT
	Транзакция A дважды читает один и тот же набор строк Все правильно

Результат. Проблема фиктивных элементов (фантомов) решается, если транзакция A использует преднамеренную S-блокировку или более сильную.

Замечание. Т.к. транзакция A собирается только читать строки таблицы, то минимально необходимым условием в соответствии с протоколом преднамеренных блокировок является преднамеренная IS-блокировка таблицы. Однако этот тип блокировки не предотвращает появление фантомов. Таким образом, транзакцию A можно запускать с разными уровнями изолированности - предотвращая или допуская появление фантомов. Причем, оба способа запуска соответствуют протоколу преднамеренных блокировок для доступа к данным.