Сериализация транзакций. Методы сериализации транзакций

Для того, чтобы добиться изолированности транзакций, в СУБД необходимы методы регулирования совместного выполнения транзакций. План (способ) выполнения набора транзакций называется сериальным, если результат совместного выполнения транзакций эквивалентен результату некоторого последовательного выполнения этих же транзакций. Сериализация транзакций – это механизм их выполнения по некоторому сериальному плану. Обеспечение такого механизма является основной функцией компонента СУБД, ответственного за управление транзакциями. Система, в которой поддерживается сериализация транзакций, обеспечивает реальную изолированность пользователей. Основная реализационная проблема состоит в выборе метода сериализации набора транзакций, который не слишком ограничивал бы их параллельность. Тривиальным решением является действительно последовательное выполнение транзакций. Но существуют ситуации, в которых можно выполнять операторы разных транзакций в любом порядке с сохранением сериальности. Примерами могут служить только читающие транзакции, а также транзакции, не конфликтующие по объектам базы данных. Между транзакциями могут существовать следующие виды конфликтов: W-W– транзакция 2 пытается изменять объект, изменённый не закончившейся транзакцией 1; R-W– транзакция 2 пытается изменять объект, прочитанный не закончившейся транзакцией 1; W-R– транзакция 2 пытается читать объект, изменённый не закончившейся транзакцией 1. Практические методы сериализации транзакций основывается на учёте этих конфликтов.

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

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

Сначала рассмотрим метод двухфазного протокола синхронизационных захватов.

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

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

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

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

В первом столбце приведены возможные состояния объекта с точки зрения синхронизационных захватов. При этом ”–” соответствует состоянию объекта, для которого не установлен никакой захват. Транзакция, запросившая синхронизационный захват объекта БД, уже захваченный другой транзакцией в несовместимом режиме, блокируется до тех пор, пока захват с этого объекта не будет снят. Заметим, что слово “нет” в таблице соответствует описанным ранее возможным случаям конфликтов транзакций по доступу к объектам базы данных (WW, RW, WR). Совместимость S– захватов соответствует тому, что конфликт RR не существует.

Для обеспечения сериализации транзакций (третьего уровня изолированности) синхронизационные захваты объектов, произведённые по инициативе транзакций, можно снимать только при её завершении. Это требование порождает двухфазный протокол синхронизационных захватов– 2PL. В соответствии с этим протоколом выполнение транзакции разбивается на две фазы: Первая фаза транзакции – накопление захватов; Вторая фаза (фиксация или откат)– освобождение захватов. При соблюдении двухфазного протокола синхронизационных захватов действительно обеспечивается сериализация транзакций на третьем уровне изолированности. Основная проблема состоит в том, что следует считать объектом для синхронизационного захвата. В контексте реляционных баз данных возможны следующие виды захватываемых объектов:

Файл–физический (с точки зрения базы данных) объект, область хранения нескольких отношений и, возможно, индексов;

Отношение – логический объект, соответствующий множеству кортежей данного отношения;

Страница данных – физический объект, хранящий кортежи одного или нескольких отношений, индексную или служебную информацию;

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

При применении метода гранулированных синхронизационных захватов захваты могут запрашиваться по отношению к объектам разного уровня: файлам, отношениям и кортежам. Требуемый уровень объекта определяется тем, какая операция выполняется (например, для выполнения операции уничтожения отношения объектом синхронизационного захвата должно быть всё отношение, а для выполнения операции удаления кортежа – этот кортеж). Объект любого уровня может быть захвачен в режиме S или X. Вводится специальный протокол гранулированных захватов и новые типы захватов: перед захватом объекта в режиме S или X соответствующий объект, более верхнего уровня, должен быть захвачен в режиме IS, IX или SIX.

Захват IS (Intented for Shared lock) по отношению к некоторому составному объекту О означает намерение захватить некоторый входящий в О объект в совместном режиме. Например, при намерении читать кортежи из отношения R это отношение должно быть захвачено в режиме IS (а до этого в таком же режиме должен быть захвачен файл).

Захват IX (Intented for eXclusive lock) по отношению к некоторому составному объекту О означает намерение захватить некоторый входящий в О объект в монопольном режиме. Например, при намерении удалять кортежи из отношения R это отношение должно быть захвачено в режиме IX (а до этого в таком же режиме должен быть захвачен файл).

Захват SIX (Shared, Intented for eXclusive lock) по отношению к некоторому составному объекту О означает совместный захват всего этого объекта с намерением впоследствии захватывать какие–либо входящие в него объекты в монопольном режиме. Например, если выполняется длинная операция просмотра отношения с возможностью удаления некоторых просматриваемых кортежей, по экономичнее всего захватить это отношение в режиме SIX (а до этого захватить файл в режиме IS).

Довольно трудно описать словами все возможные ситуации. Ниже приведена таблица совместимости захватов:

Несмотря на привлекательность метода гранулированных синхронизационных захватов, следует отметить, что он не решает проблему фантомов (если, конечно, не ограничиться использованием захватов отношений в режимах S и X). Для решения этой проблемы необходимо перейти от захватов индивидуальных объектов базы данных, к захвату условий (предикатов), которым удовлетворяют эти объекты. Проблема фантомов не возникает при использовании для синхронизации уровня отношений именно потому, что отношение как логический объект представляет собой неявное условие для входящих в него кортежей. Захват отношения – это простой и частный случай предикатного захвата.

Поскольку любая операция над реляционной базой данных задаётся некоторым условием (то есть в ней указывается не конкретный набор объектов базы данных, над которыми нужно выполнить операцию, а условие, которому должны удовлетворять объекты этого набора), идеальным выбором было бы требовать синхронизационный захват в режиме S или X именно этого условия. Но если посмотреть на общий вид условия, допускаемых, например, в языке SQL, то становится непонятно, как определить совместимость двух предикатных захватов. Ясно, что без этого использовать предикатные захваты для синхронизации транзакций невозможно, а в общей форме проблема неразрешима. Но эта проблема сравнительно легко решается для случая простых условий.

В методе предикатных синхронизационных захватов рассматриваются простые условия. Условие простым, если оно является конъюнкцией простых предикатов, имеющих вид:

Имя атрибута {=, >,<} значение

Для простых условий совместимость предикатных захватов легко определяется на основе следующей геометрической интерпретации. Пусть R отношение с атрибутами а_1,...а_2,...,а_n, а m_1, m_2,..., m_n – множество допустимых значений a_1,a_2,...а_n соответственно (все эти множества – конечные). Тогда можно сопоставить R конечное n-мерное пространство возможных значений кортежей R. Любое простое условие “вырезает”m–мерный прямоугольник в этом пространстве (m<=n). Тогда S–X, X–S, X–X предикатные захваты от разных транзакций совместимы, если соответствующие прямоугольники не пересекаются.

Главным недостатком всех методов, основанных на синхронизационных захватах, является наличие тупиков между транзакциями, необходимость их определения и разрушения. Например тупик возникает между транзакциями Т1 и Т2 в следующем случае: транзакция Т1 и Т2 установили монопольные захваты объектов r1 и r2 соответственно; после этого Т1 требуется совместный захват r2, а Т2–совместный захват r1. Ни одна из транзакций не может продолжаться, следовательно, монопольные захваты не будут сняты, а совместные – не будут удовлетворены. Поскольку тупики возможны, и никакого естественного выхода из тупиковой ситуации не существует, то эти ситуации необходимо обнаружить и искусственно устранять. Основой обнаружения тупиковых ситуаций является построение (или постоянное поддержание) графа ожидания транзакций. Граф ожидания транзакций – это ориентированный двудольный граф, в котором существуют два типа вершин – вершины, соответствующие этим транзакциям, и вершины, соответствующие объектам захвата. В этом графе существует дуга, ведущая из вершины–транзакции к вершине–объекту, если для этой транзакции существует удовлетворённый захват объекта. В графе существует дуга из вершины–объекта к вершине–транзакции, если транзакция ожидает удовлетворения захвата объекта. Легко показать, что в системе существует ситуация тупика, если в графе ожидания транзакций имеется хотя бы один цикл. Для распознавания тупика периодически производится построение графа ожидания транзакций (как уже отмечалось, иногда граф ожидания поддерживается постоянно), и в этом графе ищутся циклы. Традиционной техникой (для которой существует множество разновидностей) нахождения циклов в ориентированном графе является редукция графа. Редукция состоит в том, что, прежде всего, из графа ожидания удаляются все дуги, исходящие из вершин–транзакций, в которые не входят дуги из вершин–объектов. (Это как бы соответствует той ситуации, что транзакции, не ожидающие удовлетворения захватов, успешно завершились и освободили захваты). Для тех вершин–объектов, для которых не осталось входящих дуг, но существуют исходящие, ориентация исходящих дуг изменяется на противоположную ориентацию (это моделирует удовлетворения захватов). После этого снова срабатывает первый шаг и так до тех пор, пока на первом шаге не прекратится удаление дуг. Если в графе остались дуги, то они обязательно образуют цикл. После того как найден цикл, в графе ожидания транзакций необходимо разрушить найденный тупик. Разрушение тупика начинается с выбора в цикле транзакций так называемой транзакции–жертвы, то есть транзакции, которой решено пожертвовать, чтобы обеспечить возможность продолжения работы других транзакций. Критерием выбора является стоимость транзакции, при этом жертвой выбирается самая дешёвая транзакция. Стоимость транзакции определяется на основе многофакторной оценки, в которую с разными весами входят время выполнения, число накопленных захватов, приоритет. После выбора транзакции–жертвы выполняется откат этой транзакции, который может носить полный или частичный характер. При этом освобождаются захваты, и может быть продолжено выполнение других транзакций. Такое насильственное устранение тупиковых ситуаций является нарушением принципа изолированности пользователей, которого невозможно избежать. Причем в централизованных системах стоимость построения графа ожидания сравнительно невелика, но она становится слишком большой в по–настоящему распределённых СУБД. Поэтому в таких системах обычно используются другие методы сериализации транзакций.

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

Основная идея метода временных меток, у которого существует множество разновидностей, состоит в следующем: если транзакция Т1 началась раньше транзакции Т2, то система обеспечивает такой режим выполнения, как если бы Т1 была целиком выполнена до начала Т2. Для этого каждой транзакции т предписывается временная метка t, соответствующая времени начала Т. при выполнении операции над объектом r транзакция Т помечает его своей временной меткой и типом операции (чтение или изменение). Перед выполнением операции над объектом r транзакция Т1 выполняет следующие действия: Проверяет, не закончилась ли транзакция Т, пометившая этот объект. Если Т закончилась, Т1 помечает объект r и выполняет свою операцию. Если транзакция Т не завершилась, то Т1 проверяет конфликтность операций. Если операции неконфликтны, при объекте r остаётся или проставляется временная метка с меньшим значением, и транзакция Т1 выполняет свою операцию. Если операции Т1 и Т конфликтуют, то если t(T)>t(T1) (т.е. транзакция Т является более “молодой”, чем Т1) производится откат Т и Т1 продолжает работу. Если же t(T)<t(T1) (T ”старше”T1), то Т1 получает новую временную метку и начинается заново.

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