Часть третья

Журнал «Открытые системы» продолжает публикацию обзорных статей, посвященных состоянию технологий управления транзакциями в системах баз данных.

В Части 1, которая была опубликована в апрельском выпуске журнала, содержались формальное и неформальное определение транзакции, а также рассматривались менеджер транзакций и журнал транзакций. В Части 2 (см. майский выпуск) речь шла об обработке сервером баз данных отказов информационной системы, а также о поддержке свойств атомарности, сохранности и непротиворечивости. Было начато рассмотрение проблемы изолированности транзакций.

Фантомы

Напомним, что выделение типов зависимостей транзакций позволяет привести все виды нарушения целостности данных, возникающие из-за неконтролируемого взаимодействия параллельных транзакций, к конечному набору феноменов. Один из них, феномен неповторяемого чтения становится особенно интересным, если транзакция T1 считывает не строго определенный объект данных, а некоторое множество объектов, удовлетворяющих условию P (см. Часть 2). Такую разновидность феномена неповторяемого чтения принято называть фантомом (phantom).

Зависимость D2.

Феномен P3 — Фантом (phantom)

T1 считывает множество объектов данных, удовлетворяющих условию P дважды: один раз перед началом выполнения транзакции T2, а другой — после ее завершения T2 операцией commit, т. е. после фиксации изменений. Транзакция же T2 меняет данные так, что после ее фиксации множество объектов, удовлетворяющих условию P, изменяется. Некоторые объекты данных, ранее попадавшие в выборку, теперь в нее не попадают (например, их значения изменились так, что условие P для них перестало выполняться, или эти объекты данных просто удалены), а некоторые объекты данных, ранее не попадавшие в выборку, теперь в нее попадают (например, добавились новые записи или модифицировались значения существующих записей так, что для них теперь P выполняется). Диаграмма описывает зависимость ЧТЕНИЕ -> ЗАПИСЬ -> ЧТЕНИЕ.

Две операции чтения возвращают разные наборы данных, удовлетворяющие условию P.

Феномен фантома будет наблюдаться при следующих последовательностях завершения транзакций

((T1, commit) или (T1, rollback)) и ((T2, commit) или (T2, rollback))

в любом порядке. Таким образом, полное описание этого феномена включает все четыре варианта завершения транзакций T1 и T2 и, соответственно, четыре графа зависимостей.

Феномены неповторяемого чтения и фантома имеют одну и ту же природу — модификация данных «под транзакцией» (зависимость D2), что и оказывает влияние на входной набор данных, который будет считан при повторном выполнении запроса. Принято различать эти две разновидности нарушения повторяемости чтения записей.

Предположим, что информационная система содержит информацию о положении точки на плоскости (x, y). Пусть работают две транзакции, каждая их которых передвигает точку по кривой x+y = 120, и считает статистику попадания точек в полосу x ё 0. Предположим, что было введено ограничение: в полосе x ё 0 должно быть не более 10 точек. Пусть в начальный момент работы системы в полосе x ё 0 находилось 9 точек. Пусть каждая транзакция запрашивает количество точек в полосе x ё 0 и, если их меньше 10, изменяет значение координат точки, чтобы она попала в полосу, а затем модифицирует статистику точек, находящихся в этой полосе. Пусть точки, которые могут модифицировать транзакции, различны, так что T1 пытается модифицировать точку (10, 110), чтобы она попала в полосу x ё 0, а T2 — точку (20, 100). Каждая транзакция выполняет следующие действия:

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

Произошло рассогласование данных — ни одна из транзакций не считывала незафиксированных записей другой транзакции, и тем не менее, если какая-либо транзакция попробует посчитать количество записей в диапазоне x ё 0 в момент времени (!!!), то их окажется 11, в то время как значение счетчика counter будет равно 10. Транзакция T2 рассогласовала данные, причем нефиксированных данных она не считывала, а аномалия имеется. Это означает, что любая другая транзакция может считать эти некорректные данные в момент времени (!!!). Последствия данного рассогласования перестают быть контролируемыми.

Рассогласование возникло из-за того, что к моменту модификации координат точки (x2, y2) = (20, 100) значение С устарело, поскольку транзакция T1 модифицировала множество записей, которые удовлетворяют x ё 0, и была зафиксирована в то время, когда T2 еще продолжала работать. Но транзакция T2 не знает о том, что множество записей, удовлетворяющих x ё 0, уже изменено, потому что она считала число записей до момента фиксации транзакции T1. Этот пример, помимо прочего, показывает необходимость введения строгих определений феноменов, поскольку в данном случае имеет место реализация потенциального конфликта.

Потенциальные и реальные аномалии

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

В самом деле, взглянем еще раз на феномен грязного чтения P1. Феномен запрещает четыре последовательности завершения транзакций T1 и T2, а именно:

((T1, commit) или (T1, rollback)) 
и ((T2, commit) или (T2, rollback)).

В то же время, реальные аномалии будут создавать лишь две последовательности:

((T1, rollback)) и ((T2, commit) в любом порядке).

Две другие последовательности

((T1, commit)) и ((T2, rollback) в любом порядке)

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

Определение изолированности транзакций

Определение. Транзакция T изолирована от других транзакций, если:

(0) T не изменяет "грязные данные" других транзакций.

(1) Изменения данных транзакции T не могут быть cчитаны или изменены другими транзакциями до выполнения операции COMMIT WORK транзакцией Т (до точки синхронизации транзакции T).

(2) T не считывает "грязных данных" других транзакций.

(3) Другие транзакции не обновляют какие-либо данные, считанные Т, до тех пор, пока Т не завершится выполнением операции (до точки синхронизации транзакции T).

Утверждения 0 и 1 исключают потерянные обновления, утверждение 2 изолирует транзакцию от грязного чтения, утверждение 3 предотвращает неповторяемое чтение и фантомы. Если все транзакции удовлетворяют условиям (0)-(3), то имеют место следующие свойства.

  • Непротиворечивость входных данных. Каждая транзакция считывает непротиворечивое состояние данных.
  • Изолированное выполнение. Любая последовательность выполнения операций множества транзакций М эквивалентна некоторой серийной (последовательной) истории. Это означает, что любая история эквивалентна истории без параллелизма, а каждое логическое подмножество истории эквивалентно выполнению операций без аномалий параллелизма.
  • Сохранность изменений. Если какая-то транзакция закончилась выполнением операции ROLLBACK WORK (откат), или произошел сбой в системе, повлекший вынужденный откат нескольких не закончившихся транзакций, то незафиксированные данные отката могут быть потеряны. Никакие обновления или сообщения зафиксированных (committed) транзакций не могут быть потеряны. Таким образом, сохраняется логическая непротиворечивость данных, и выполнение прерванных транзакций может быть возобновлено.

Уровни изолированности транзакций

Противоречие изолированности и параллельной работы транзакций

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

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

Напомним: две транзакции конфликтуют за объекты данных, если их входные (считываемые транзакцией) и выходные (модифицируемые транзакцией) множества объектов данных пересекаются. Как было показано в Части 2, все виды конфликтов сводятся к конечному числу феноменов.

Полностью совместить высокий уровень параллелизма обработки транзакций и высокий уровень их изолированности не удается. Поэтому идут по пути ослабления изолированности транзакций в пользу повышения уровня параллелизма. Вводится несколько степеней изолированности транзакций.

Степень 0. (0?) Транзакции степени 0? не обновляют «грязные» данные других транзакций, если эти «другие» транзакции имеют степень изолированности 1? или выше. Эту степень называют «анархией» (anarchy).

Степень 1. (1?) Транзакции степени 1? характеризуются отсутствием потерянных обновлений. Эту степень называют «чтением» (browse).

Степень 2. (2?) Транзакции степени 2? характеризуются отсутствием потерянных обновлений и грязного чтения данных. Эту степень называют «стабильностью курсора» (cursor stability).

Степень 3. (3?) Транзакции степени 3? характеризуются отсутствием потерянных обновлений и наличием повторяемого чтения, что включает отсутствие грязного чтения. Это «настоящая» изолированность. Эту степень называют «сериализуемостью» (serializable).

Изолированность степени 0? игнорирует все виды зависимостей транзакций (все феномены имеют место). Изолированность степени 1? запрещает зависимости ЗАПИСЬ ? ЗАПИСЬ (запрещен только феномен потерянное обновление). Изолированность степени 2? запрещает зависимость ЗАПИСЬ ? ЗАПИСЬ и зависимость ЗАПИСЬ ? ЧТЕНИЕ (запрещены феномены потерянного обновления и грязной записи). Изолированность степени 3? запрещает зависимость ЗАПИСЬ ? ЗАПИСЬ, ЗАПИСЬ ? ЧТЕНИЕ, ЧТЕНИЕ ? ЗАПИСЬ (запрещены феномены потерянного обновления, грязной записи, неповторяемое чтение, фантом).

К сожалению, из-за того, что названия уровней изолированности были стандартизованы гораздо позже того, как появилось множество реализаций, а определения феноменов в стандарте языка SQL ANSI X3.135-1992 не точны, в названиях уровней изолированности, которые употребляют разработчики СУБД для обозначения реализованных ими видов изолированности, присутствует значительная путаница.

Современные СУБД предлагают две основные техники доступа к разделяемым данным: посредством блокирования разделяемых данных и посредством порождения версий данных.

Техника блокирования

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

Совместность блокировок регулируется следующей матрицей:

Если для обеспечения изолированности транзакций используются блокировки, то система поддерживает пять операций над объектами данных (READ, WRITE, XLOCK, SLOCK, UNLOCK), а также три основных операции над транзакциями (BEGIN, COMMIT, ROLLBACK). READ и WRITE (ЧТЕНИЕ и ЗАПИСЬ) имеют обычное значение: READ возвращает значение именованного объекта в прикладную задачу, WRITE изменяет значение именованного объекта данных. Операция SLOCK предшествует операции чтения транзакции, XLOCK — операции записи. «S» в названии SLOCK означает разделяемую блокировку (Share lock): только операции чтения могут параллельно получать доступ к заблокированному объекту данных без нарушения изолированности. «X» в XLOCK означает эксклюзивную блокировку (eXclusive lock): эта операция может предшествовать как операции чтения, так и операции записи транзакции и исключает чтение и запись объекта данных другими транзакциями. Операция UNLOCK снимает блокировку. Операция BEGIN означает начало транзакции. Операция COMMIT просто снимает блокировки (все изменения транзакции сохраняются). Операция ROLLBACK должна сначала откатить все изменения транзакции, а потом снять все блокировки.

Говорят, что транзакция правильно сформирована, если всем операциям READ, WRITE и UNLOCK предшествуют операции наложения блокировки, и если каждая операция наложения блокировки непосредственно следует за соответствующей операцией UNLOCK.

Говорят, что транзакция двухфазная, если все ее операции LOCK предшествуют всем ее операциям UNLOCK. Двухфазная транзакция состоит из фазы возрастания T[1],..,T[j], в течение которой накладываются блокировки, и фазы сжатия T[j+1],...,T[n], в течение которой блокировки снимаются.

Основная теорема изолированности в терминах блокировок звучит так:

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

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

  • Проблема затрат ресурсов при блокировании большого количества объектов; она решается эскалацией блокировок - множество блокировок объектов данных (скажем, записей или страниц) заменяются одной более грубой блокировкой (например, n блокировок записей заменяются одной блокировкой страницы, n блокировок страниц - одной блокировкой таблицы).
  • Проблема взаимного блокирования двух транзакций, когда каждая из транзакций ждет освобождения объектов, блокированных другой транзакцией (такую ситуацию называют deadlock - "тупиковая ситуация"); она решается путем принудительного отката одной из транзакций-участников тупика, соответственно хранилище блокировок периодически сканируется на наличие тупика, что также требует определенных ресурсов.

Для обеспечения уровней изолированности транзакций ниже 3? достаточно блокирования определенных объектов данных. Единственный феномен, который сложно отслеживать при использовании техники блокирования, — это фантом. Чтобы обеспечить отсутствие фантомов, приходится блокировать собственно предикат (условие выборки).

Чтобы смягчить конфликты транзакций, используют различные приемы, например, tree locking (дерево блокировок) и блокировки Intent (фактически определяет «намерение» наложить более жесткую блокировку ниже по дереву блокировок, что позволяет сводить некоторые типы тупиков к задержкам), Direct Acyclic Graph locking (когда используются направленные графы блокировок) и другие.

Техника многоверсионности

Техника многоверсионности основана на том, что каждый объект данных логически представляется в виде цепочки версий. Каждая операция чтения или записи предваряется запросом соответствующей версии, и операция «привязывается» к этой версии. Пусть в информационной системе для простоты имеется всего один объект данных O, и его начальное значение V0. Транзакция T модифицирует версию объекта O с V0 на V1, а затем фиксируется. В информационной систему будут существовать уже две версии объекта O — старая V0 и новая V1. Очевидно, что намечается некоторая избыточность — зачем хранить две версии одного и того же объекта O. Версия V0 действительно избыточна, но только если на момент фиксации транзакции T нет ни одной не зафиксированной транзакции, которая считала или изменила версию V0 объекта O.

Если транзакция T считывает объект O (его версию V0), то эта версия хранится в информационной системе. Важно, чтобы при повторном чтении объекта O транзакция T считала именно версию V0. Очевидно, что если постоянно накапливать версии объекта данных, то рост объема информации становится неконтролируемым. Кроме того, при многоверсионности требуется знать про каждую версию, какая транзакция ее породила.

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

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

Предположим, что последовательно работают две транзакции, и каждая из них сначала читает объект данных O, потом модифицирует его и фиксируется. Путь в начальный момент времени версия O есть V0, транзакция T1 отрабатывает первой и модифицирует V0 на V1, а T2 — второй и модифицирует V0 на V2. Последовательность операций над O будет такой

Очевидно, что в момент времени (!!!) у объекта O есть две версии: V0 и V1. Причем T1 уже фиксировалась, а значит, V1 должна быть видима другим транзакциям. Это означает, что вместе с версией должна храниться некая информация о том, какая транзакция породила данную версию. Наличие такой информации позволит предотвращать феномены грязного чтения и грязной записи — вводится запрет на видимость тех версий, у которых метка транзакции отличается от метки данной транзакции, и транзакция-владелец версии не завершена. Хранение информации не только о времени старта транзакции, но и о времени фиксации транзакции, породившей версию объекта данных, позволит избежать неактуального чтения. Если не хранить эту информацию, то в приведенном примере транзакция T2 может считать версию V0, в то время как актуальной на момент старта T2 является версия V1. Таким образом, при использовании многоверсионности приобретают особую актуальность истории транзакций.

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

Первую проблему, как правило, решают путем ужесточения правила видимости: транзакция не видит никаких изменений объектов данных, которые были зафиксированы после ее старта, фактически получается, что транзакция получает снимок объектов данных на момент ее старта и с ним работает. Вторая же проблема характерна только для многоверсионности. Проблемы актуализации данных при использовании блокирования не возникают, так как отсутствует несколько версий одного объекта данных. Решается она путем ужесточения протокола отката транзакции — при фиксации транзакции происходит проверка наличия более фиксированных более старых версий объектов данных, которые модифицирует данная транзакция, чем те версии, которые данная транзакция считала, естественно «слепая запись» также запрещается (каждая операция записи предваряется неявной операцией чтения). Если есть такая фиксированная более поздняя версия (изменение данных «под транзакцией») — то это означает, что считанная транзакцией версия не актуальна и транзакция принудительно откатывается.

Продолжение в следующем выпуске журнала «Открытые системы».