35. Сериализация транзакций.
Во избежание подобных ситуаций (незафиксированные изменения, проблемы промежуточных данных, проблемы несогласованных данных, проблемы строк-признаков, см. вопрос 33-34) требуется разработать определенную процедуру, обеспечивающая согласованность выполнения параллельных транзакций, т.е. изолированность транзакций. Эта процедура в СУБД носит название сериализации транзакций. Для поддержки параллельной работы транзакции строится специальный план. План выполнения набора транзакций называется сериальным, если результат совместного выполнения транзакций эквивалентен результату некоторого последовательного выполнения этих же транзакций.
Сериализация транзакций - это механизм выполнения транзакций по некоторому сериальному плану. Обеспечение такого механизма является основной функцией компонента СУБД, ответственного за управление транзакциями.
Данная дисциплина опирается на следующие правила:
В процессе выполнения транзакции программа «видит» только согласованные состояния базы данных; пользователь никогда не может получить доступ к незафиксированным изменениям в данных, достигнутым в результате действия другой программы;
Если две транзакции А и В выполняются параллельно, то СУБД полагает, что результат будет такой же, как если бы: - транзакция А выполнялась бы первой, а за ней - выполнялась другая транзакция В, т.е. последовательно.
Основная реализационная проблема состоит в выборе сериализации набора транзакций, который не слишком бы ограничивал их параллельность; наиболее простым может быть выбор последовательного выполнения транзакций. Между транзакциями могут возникать следующие виды конфликтов:
W - W - транзакция 2 пытается изменить объект, измененный незаконченной транзакцией 1;
R - W - транзакция 2 пытается изменить объект 1, прочитанный незаконченной транзакцией 1;
W - R - транзакция 2 пытается прочитать объект, измененный не законченной транзакцией 1.
Существующие практические методы сериализации основываются на учете этих конфликтов.
Методы сериализации транзакций.
Существует два базовых подхода к сериализации транзакций: подход, метод, основанный на синхронизационных захватах (блокировках) объектов базы данных, и подход, основанный на использовании временных меток. Для каждого из этих подходов могут существовать пессимистические и оптимистические варианты решения; первые отличаются тем, что применяются в тех ситуациях, когда конфликты возникают часто и распознаются и разрешаются немедленно при их возникновении; вторые - основываются на том, что результаты всех операций на объектами базы данных сохраняются в рабочей памяти транзакций. Рассмотрим некоторые методы сериализации транзакций с учетом их пессимистических разновидностей.
36. Синхронизационные блокировки. Тупики и их разрешение.
Синхронизационные блокировки.
Этот метод считается наиболее распространенным для централизованных СУБД, в том числе для систем архитектуры «клиент-сервер», и основан на соблюдении двухфазного протокола синхронизационных блокировок (захватов) объектов. Суть этого протокола состоит в том, что перед выполнением любой операции в транзакции Т над объектом базы данных А, от имени транзакции Т запрашивается синхронизационный захват объекта А в соответствующем режиме.
Основными режимами синхронизационных захватов (блокировок) являются:
совместный (взаимный) режим - S (Shared), означающий разделяемый захват объекта и требуемый для выполнения операции чтения объекта;
монопольный захват - X (eXclusive), означающий монопольный захват объекта и требуемый для выполнения операций занесения, удаления и модификации.
Захваты объектов несколькими транзакциями по чтению совместимы, т.е. нескольким транзакциям разрешено одновременное чтение одного и того же объекта; захват объектов одной транзакцией по чтению не совместим с захватом другой транзакцией того же объекта по записи; захваты одного объекта разными транзакциями по записи не совместимы (рис.3).
|
|
X |
S |
|
- |
да |
да |
|
X |
нет |
нет |
|
S |
нет |
да |
Рис.3
“-” соответствует состоянию объекта, для которого не установлен никакой захват; транзакция, запросившая синхронизационный захват объекта базы данных, уже захваченный другой транзакцией, блокируется до тех пор, пока захват этого объекта не будет снят.
“нет” - конфликтные ситуации, рассмотренные ранее.
На основании X- и S- блокировок может быть основан протокол доступа к данным:
Транзакция, предназначенная для извлечения объекта базы данных, должна осуществить наложение S- блокировки на выбранный объект базы данных.
Транзакция, предназначенная для обновления объекта базы данных, должна осуществить наложение X-блокировки на объект базы данных.
Если запрашиваемая блокировка со стороны второй транзакции отвергается из-за конфликта с некоторой другой блокировкой со стороны первой транзакции, то вторая транзакция переходи в режим ожидания.
X-блокировки не снимаются до конца выполнения транзакции (или до выполнения операторов COMMIT, ROLLBACK).
Для обеспечения сериализации транзакций синхронизационные захваты объектов, произведенные по инициативе транзакции, можно снимать только после ее завершения. Это требование порождает двухфазный протокол синхронизационных захватов - 2 PL (Two-Phase Locks). В соответствии с этим протоколом выполнение транзакции разбивается на две фазы: накопление захватов и освобождение захватов (после фиксации или отката).
Таким образом, механизм блокировок разрешает проблемы, связанные с доступом нескольких пользователей к одним и тем же данным. Однако его применение существенно замедляет выполнение самой транзакции, что вызвано необходимостью ожидания освобождения занятых данных. Здесь возникает вопрос, что считать объектом для синхронизационного захвата: страницу данных, файл, отношение кортеж? Чем крупнее объект синхронизационного захвата, тем меньше синхронизационных захватов будет задерживаться в системе, тем меньше накладные расходы. Но при такой ситуации появляется вероятность увеличения числа конфликтов транзакций и тем самым уменьшается допускаемая степень их параллельного выполнения. Если СУБД реализована таким образом, что может захватывать для выполнения транзакции отдельные строки, то скорость обработки существенно повысится. Блокировка на уровне строк позволяет достигнуть максимальной производительности за счет того, что объект (запись) является минимальной структурной единицей базы данных.
Тупиковые ситуации (dead-locks).
Одним из наиболее чувствительных недостатков метода сериализации транзакций на основе синхронизационных захватов является возникновение тупиков (взаимных блокировок) (dead - locks) между транзакциями. При возникновении подобной ситуации две или более транзакций находятся во взаимном ожидании освобождения блокировок, удерживаемых каждой из них. Рассмотрим пример возникновения тупика: пусть транзакции Т1и Т2 установили монопольные захваты, соответственно, объектов А1 и А2, после этого транзакция Т1 требуется совместный захват А2, а транзакции Т2 - совместный захват А1. Ни одна транзакция не может продолжиться, монопольные захваты не смогут быть сняты, следовательно, совместные захваты не будут удовлетворены. Поскольку тупики возможны, и никакого естественного выхода из них не может быть, то необходимо такие ситуации обнаруживать и искусственно устранять.
Существует два общих метода обработки тупиковых ситуаций: предупреждение этих ошибочных ситуаций и выявление взаимных блокировок с последующим их устранением.
При использовании метода предупреждения тупиков СУБД заранее определяет ситуации, в которых транзакции могут вызывать появление этой нежелательной ошибки, и предотвращает их возникновение. Один из возможных подходов предупреждения тупиковых ситуаций состоит в установлении порядка выполнения транзакций на основе использования временных меток. Например, известный метод «Ожидание-отмена» требует, чтобы новые транзакции ожидали завершения старых; в противном случае, транзакция отменяется и перезапускается стой же самой временной меткой. Рано или поздно, эта транзакция станет самой старой из активных транзакций, и поэтому не сможет быть отменена.
Второй подход к обработке тупиковых ситуаций носит название метода выявления взаимных блокировок. В этом случае СУБД допускает появление подобных ситуаций в системе, однако затем распознает их появление и организует выход из сложившейся тупиковой ситуации. Этот метод более прост в реализации, и поэтому нашел практическое применение.
Основой обнаружения тупиковых ситуаций является построение (или постоянное поддержание) графа ожидания транзакций (wait-for-graph – WFG). Граф ожидания транзакций - это ориентированный двудольный граф, вершинами которого являются транзакции и объекты захвата, т.е. граф отражает зависимость транзакций друг от друга. Транзакция Тi зависит от транзакции Тj, если транзакция Тj заблокировала элемент данных, необходимый для продолжения работы транзакции Тi. Граф ожидания строится следующим образом:
-для каждой выполняющейся транзакции создается отдельная вершина;
-
отдельное
направленное ребро (дуга) Тi Tj создается
для каждого случая, когда транзакция
Ti ожидает освобождения элемента,
заблокированного транзакцией Tj .
Если в системе существует ситуации тупика, то в графе ожидания транзакций имеется хотя бы один цикл (петлю).
Поскольку наличие петли является необходимым условием существования в системе тупиковой ситуации, для выявления этих ситуаций периодически в системе проводится генерирование графа ожиданий и анализ его на наличие циклов. Важным условием является определение интервала между последовательными генерациями графа, т.к. при слишком большом интервале может пройти незамеченным потенциальная тупиковая ситуация, при слишком малом временном промежутке – выявление взаимных блокировок создаст значительные перегрузки в системе.
В случае нахождения тупиковой ситуации необходимо обеспечить возможность продолжения работы хотя бы для части транзакции, попавшей в тупик. Разрушение тупика начинается с выбора в цикле транзакции - жертвы, т.е. транзакции, которой решено пожертвовать, чтобы обеспечить возможность продолжения работы других транзакций. Критерием выбора является минимизация стоимости транзакции; стоимость определяется на основе многофакторной оценки, в которую входят с разными весами время выполнения, число накопленных захватов, приоритет.
После выбора транзакции - жертвы производится ее откат, что обеспечивает продолжение работы другим транзакциям. Такое насильственное устранение тупиковых ситуаций является нарушением принципа изолированности.