УПРАВЛЕНИЕ ТРАНЗАКЦИЯМИ, СЕРИАЛИЗАЦИЯ ТРАНЗАКЦИЙ. МЕТОДЫ СЕРИАЛИЗАЦИИ ТРАНЗАКЦИЙ

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

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

Под транзакцией понимается такая неделимая, с точки зрения воздействия на БД, последовательность операторов манипулирования данными (чтения, удаления, вставки, модификации), что либо результаты всех операторов, входящих в транзакцию, отображаются в БД, либо воздействие полностью отсутствует. При завершении транзакции оператором COMMIT («зафиксировать») результаты гарантированно фиксируются во внешней памяти; при завершении транзакции оператором ROLLBACK («откат») результаты гарантированно отсутствуют во внешней памяти.

Транзакции и целостность БД

Понятие транзакции имеет непосредственную связь с понятием целостности БД. Очень часто БД может обладать такими ограничениями целостности, которые просто невозможно не нарушить, выполняя только один оператор изменения БД. Например, в БД СОТРУДНИКИ-ОТДЕЛЫ естественным ограничением целостности является совпадение значения атрибута ОТД РАЗМЕР в кортеже отношения ОТДЕЛЫ, описывающем данный отдел (например, отдел 320), с числом кортежей отношения СОТРУДНИКИ таких, что значение атрибута СОТРОТДНОМЕР равно 320. Как в этом случае принять на работу в отдел 320 нового сотрудника? Независимо от того, какая операция будет выполнена первой, вставка нового кортежа в отношение СОТРУДНИКИ или модификация существующего кортежа в отношении ОТДЕЛЫ, БД окажется в нецелостном состоянии.

Поэтому для поддержания подобных ограничений допускается нарушение целостности внутри транзакции, но с тем условием, чтобы к моменту завершения транзакции целостность была соблюдена. В системах с развитыми средствами ограничения и контроля целостности каждая транзакция начинается при целостном состоянии БД и должна оставить это состояние таковым после своего завершения. Несоблюдение этого условия приводит к тому, что вместо фиксации результатов транзакции происходит ее откат (т. е. вместо оператора COMMIT выполняется ROLLBACK), и БД остается в таком состоянии, в котором находилась к моменту начала транзакции, т. е. в целостном.

Различают два вида ограничений целостности: немедленно проверяемые и откладываемые. К немедленно проверяемым относятся такие ограничения, проверку которых бессмысленно или даже невозможно откладывать. Например, ограничение домена (возраст сотрудника не может превышать 150 лет). Более сложным ограничением является следующее: зарплата сотрудника не может быть увеличена за одну операцию более, чем на 100 000 рублей. Немедленно проверяемые ограничения целостности соответствуют уровню отдельных операторов языкового уровня СУБД. При их нарушениях не производится откат транзакции, а лишь отвергается соответствующий оператор.

Откладываемые ограничения целостности — это ограничения на БД, а не на какие-либо отдельные операции. По умолчанию такие ограничения проверяются в конце транзакции, и их нарушение вызывает автоматическую замену операторов COMMIT на ROLLBACK. Однако в некоторых системах поддерживается специальный оператор насильственной проверки ограничений целостности внутри транзакции. Если после выполнения такого оператора обнаруживается, что условия целостности не выполнены, пользователь может сам выполнить оператор ROLLBACK или постараться устранить причины нецелостного состояния БД внутри транзакции (видимо, это осмысленно только при использовании интерактивного режима работы).

Замечание. С точки зрения внешнего представления в момент завершения транзакции проверяются все откладываемые ограничения целостности, определенные в этой БД. Однако при реализации стремятся динамически выделить те ограничения целостности, которые действительно могли бы быть нарушены. Например, если при выполнении транзакции над БД СОТРУДНИКИ-ОТДЕЛЫ в ней не выполнялись операторы вставки или удаления кортежей из отношения СОТРУДНИКИ, то проверять упоминавшееся выше ограничение целостности не требуется (проверка подобных ограничений вызывает достаточно большую работу).

Изолированность пользователей

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

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

При соблюдении обязательного требования поддержания целостности БД возможны следующие уровни изолированности транзакций:

1) отсутствие потерянных изменений. Рассмотрим следующий сценарий совместного выполнения двух транзакций: Т1 и Т2. Т1 изменяет объект БД А. До завершения T1 Т2 также изменяет объект А. Т2 завершается оператором ROLLBACK (например, по причине нарушения ограничений целостности). Тогда при повторном чтении объекта А Т1 не видит изменений этого объекта, произведенных ранее. Такая ситуация называется ситуацией потерянных изменений. Естественно, она противоречит требованию изолированности пользователей. Чтобы избежать такой ситуации, требуется, чтобы до завершения Т1 никакая другая транзакция не могла изменять объект А. Отсутствие потерянных изменений является минимальным требованием к СУБД по части синхронизации параллельно выполняемых транзакций.
2) отсутствие чтения «грязных данных». Рассмотрим следующий сценарий совместного выполнения транзакций 1 и 2. Т1 изменяет объект БД А. Параллельно с этим Т2 читает объект А. Поскольку операция изменения еще не завершена, Т2 видит несогласованные — «грязные» данные (в частности, операция Т1 может быть отменена при проверке немедленно проверяемого ограничения целостности). Это тоже не соответствует требованию изолированности пользователей (каждый пользователь начинает свою транзакцию при согласованном состоянии БД и в праве ожидать видеть согласованные данные). Чтобы избежать ситуации чтения «грязных» данных, до завершения Т1, изменившей объект А, никакая другая транзакция не должна его читать (минимальным требованием является блокировка чтения объекта А до завершения операции его изменения в Т1).
3) отсутствие неповторяющихся чтений. Рассмотрим следующий сценарий. Т1 читает объект БД А. До завершения T1 Т2 изменяет объект А и успешно завершается оператором COMMIT. Т1 повторно читает объект А и видит его измененное состояние. Чтобы избежать неповторяющихся чтений, до завершения Т1 никакая другая транзакция не должна изменять объект А. В большинстве систем это является максимальным требованием к синхронизации транзакций, хотя, как мы увидим далее, отсутствие неповторяющихся чтений еще не гарантирует реальной изолированности пользователей.

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

К более тонким проблемам изолированности транзакций относится так называемая проблема кортежей-«фантомов», вызывающая ситуации, которые также противоречат изолированности пользователей. Рассмотрим следующий сценарий. Транзакция 1 выполняет оператор А выборки кортежей отношения R с условием выборки S (т. е. выбирается часть кортежей отношения R, удовлетворяющих условию 5). До завершения T1 Т2 вставляет в отношение R новый кортеж г, удовлетворяющий условию S, и успешно завершается. Т1 повторно выполняет оператор А, ив результате появляется кортеж, который отсутствовал при первом выполнении оператора. Конечно, такая ситуация противоречит идее изолированности транзакций и может возникнуть даже на третьем уровне изолированности транзакций. Чтобы избежать появления кортежей-«фантомов», требуется более высокий «логический» уровень синхронизации транзакций. Идеи такой синхронизации (предикатные синхронизационные захваты) известны давно, но в большинстве систем не реализованы.

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

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

План (способ) выполнения набора транзакций называется сериальным, если результат совместного выполнения транзакций эквивалентен результату некоторого последовательного их выполнения.

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

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

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

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

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

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

Практические методы сериализации транзакций основываются на учете этих конфликтов.

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

Существуют два базовых подхода к сериализации транзакций, основанных:

1) на синхронизационных захватах объектов БД;
2) использовании временных меток.

Суть обоих подходов состоит в обнаружении конфликтов транзакций и их устранении.

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

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

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

Основными режимами синхронизационных захватов являются:

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

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

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

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

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

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

Пример возникновения тупика между транзакциями Т1 и Т2:

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

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

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

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

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

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

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

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

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

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

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

Чтобы минимизировать число конфликтов между транзакциями, в некоторых СУБД (например, в Oracle) используется следующее развитие подхода. Монопольный захват объекта блокирует только изменяющие транзакции. После выполнения операции модификации предыдущая версия объекта остается доступной для чтения в других транзакциях.

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

Метод временных меток

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

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

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

Перед выполнением операции над объектом г транзакция Т1 выполняет следующие действия:

— проверяет, не закончилась ли транзакция Т, пометившая этот объект. Если Т закончилась, Т1 помечает объект г и выполняет свою операцию;
— если транзакция Т не завершилась, то Т1 проверяет конфликтность операций. Если операции неконфликтны, при объекте г остается или проставляется временная метка с меньшим значением, и транзакция Т1 выполняет свою операцию;
— если операции Т1 и Т конфликтуют, то если ?(Т) > /(Т1) (т. е. транзакция Т1 является более «молодой», чем Т), производится откат Т, и Т1 продолжает работу;
— если же /(Т) < /(Tl) (Т «старше» Т1), то Т1 получает новую временную метку и начинается заново.

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

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

Ш ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. Дайте определение транзакции.
2. Опишите уровни изолированности транзакций.
3. Дайте определение сериализации транзакций. Приведите примеры конфликтующих между собой транзакций.
4. Перечислите методы сериализации транзакций и их разновидности.
5. Опишите метод синхронизационных захватов. Как распознаются тупики?
6. Опишите метод временных меток.