Часть 2*

Поддержка атомарности, сохранности и непротиворечивости

Атомарность транзакции поддерживается журналом транзакций, в котором протоколируются все ее действия. Менеджер транзакций посылает журналу транзакций информацию о старте новой транзакции, и с этого момента в журнале ведется протокол действий транзакции. Журнал обеспечивает сохранение всех произведенных транзакцией изменений в случае ее успешной фиксации и аннулирование всех этих изменений – в случае неуспешного завершения (операция rollback, отказ приложения пользователя, отказ сервера во время обработки транзакции). Журнал транзакций обеспечивает и атомарность выполнения каждой операции модификации базы данных. Журнал обеспечивает выполнение действий, составляющих подобную операцию, над всеми элементами целевого множества. В случае возникновения ошибки при обработке любого из элементов целевого множества операции результаты всех уже выполненных действий операции, аннулируются. Таким образом, целевое множество либо изменяется целиком, либо не изменяется вовсе.

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

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

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

Подсистемы сервера, поддерживающие изолированность

Вопросы взаимодействия транзакций, обращающихся к одним и тем же данным, находятся в компетенции менеджера транзакций.

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

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

  • получение информации о непроданных билетах;
  • оформление продажи одного билета (занесение информации о пассажире - ФИО, данные о предюявленном документе, информации о льготах и других данных, влияющих на стоимость проезда);
  • пометка билета как проданного.

Пусть с обоих терминалов была запрошена информация о непроданных билетах. Очевидно, что в выборку попадут одни и те же данные (предположим, работают только эти два терминала). Затем каждый из операторов заносит информацию о пассажире, считает стоимость проезда. Билет продан. Но случилось так, что оба пассажира заказали один и тот же билет. Поскольку данное действие в информационной системе никак не контролируется, то оба пассажира «поедут» на одном и том же месте: один билет продан дважды. Это произошло потому, что при изменении данных о статусе билета как «проданного» никак не контролировалась возможность модификации одних и тех же данных с двух терминалов. При последовательном выполнении действий – сначала всех с первого терминала, а потом всех со второго – такого бы не произошло. Билет, проданный на первом терминале, просто не попал бы в выборку свободных билетов для второго.

Оказалось, что изолированность транзакций нарушена: параллельное выполнение дало результат, отличный от последовательного выполнения. В данном случае имела место зависимость рассматриваемых транзакций друг от друга. Обсудим этот вопрос подробнее.

Истории транзакций

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

Oa « Ob = D и Ia « Ob = D, a Б?  b

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

Пусть имеются две транзакции, состоящие из двух операций чтения и одной операции записи:

T1 = {R1.1, R1.2, W1.1} и
T2 = {R2.1, R2.2, W2.1}

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

R1.1, R1.2, W1.1, R2.1, R2.2, W2.1, или
R1.1, R2.1, R2.2, W2.1, R1.2, W1.1, или
R1.1, R2.1, R1.2, W1.1, R2.2, W2.1, или
R2.1, R2.2, W2.1, R1.1, R1.2, W1.1, или
R2.1, R1.1, R1.2, W1.1, R2.2, W2.1, или
R2.1, R1.1, R1.2, W1.1, R2.2, W2.1

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

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

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

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

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

Говорят, что две операции в истории транзакций конфликтуют, если они выполняются над одним обюектом данных от имени разных транзакций, и хотя бы одна из этих транзакций выполняет операцию записи. Конфликтующие операции могут возникать не только на отдельных обюектах данных, но и на их множествах, определяемых с помощью условий. В дальнейшем будем говорить: «Множество обюектов данных удовлетворяет условию P».

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

Говорят, что транзакция Т2 зависит от транзакции Т1 в истории Н, если Т2 считывает или обновляет обюекты данных, уже обновленные транзакцией Т1, или если Т2 обновляет обюекты данных, уже считанные или обновленные Т1.

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

Ниже для наглядности станем обозначать символом «->» зависимость транзакций; (T,R) будет обозначать операцию чтения транзакции T, (T,W) – операцию записи транзакции T. Формализм (T1,_) <0,1> (->) будет означать, что транзакция «T1» выполнила некоторую операцию, и в результате получился обюект данных «O», номер его версии по порядку – «1»; «_» обозначает R или W.

Пусть две транзакции T1 и T2 производят некоторые операции над обюектом данных O. Пусть первоначальная версия обюекта O – , а операции записи порождают версии и .

Зависимости ЧТЕНИЕб?ЧТЕНИЕ как таковой не существует, так как обе транзакции читают одну и ту же версию обюекта и не создают взаимозависимостей:

<0,1> (->) (T1,R) <0,1> (->) (T2,R) <0,1> (->)

Когда T1 считывает версию обюекта, а потом T2 пишет версию , между транзакциями T1 и T2 возникает зависимость ЧТЕНИЕб?ЗАПИСЬ:

<0,1> (->) (T1,R) <0,1> (->) (T2,W) <0,1> (->)

(T1 считывает O прежде, чем T2 его обновила).

Когда T1 пишет версию обюекта O, а потом T2 считывает версию , между транзакциями T1 и T2 возникает зависимость ЗАПИСЬб?ЧТЕНИЕ:

<0,1> (->) (T1,W) <0,2> (->) (T2,R) <0,2> (->)

(T2 обновляет O прежде, чем T1 его считала).

Когда T1 пишет версию обюекта O, а потом T2 пишет версию , между транзакциями T1 и T2 возникает зависимость ЗАПИСЬ > ЗАПИСЬ:

<0,1> (->) (T1,W) <0,2> (->) (T2,R) <0,3> (->)

(T1 обновляет O прежде, чем T2 его обновила).

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

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

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

Каждая из аномалий, описывающих феномены, имеет свое название: потерянное обновление (lost update), грязное чтение (dirty read), неповторяемое чтение (unrepeatable read).

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

Феномен «потерянное обновление»

Операции чтения транзакции T1 игнорируются транзакцией T2, которая выполняет операции записи над O, основываясь на первоначальной версии . Диаграмма описывает зависимость ЧТЕНИЕ -> ЗАПИСЬ -> ЗАПИСЬ,

DO: <0,1> (->) (T2,R) <0,1> (->) (T1,W) <0,2> (->) (T2,W) <0,3> (->)

но зависимость ЗАПИСЬ -> ЗАПИСЬ -> ЗАПИСЬ подобного графа также содержит феномен. Одно из обновлений будет потеряно.

В данном случае имеет место изменение незафиксированных данных транзакции. Незафиксированные данные транзакции еще называют «грязными» (dirty data).

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

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

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

Как возникает такая зависимость транзакций? Предположим, что система содержит информацию о положении точки на плоскости. Точка определяется двумя координатами (x,y). Пусть работают две транзакции, каждая их которых заносит информацию о точке, удовлетворяющей уравнению x = y. Выполняются операции модификации координаты x и модификации координаты y. Пусть T1 меняет значение v = (0,0) на v1 = (1,1), а T2 – на v2 = (2.2). Очевидно, что при выполнении операций в указанной ниже последовательности будет возникать рассогласование данных:

<0,1> (->) (T1,W(y)) <0,1> (->) (T2,W(y)) <0,2> (->) (T2,W(x)) <1,2> (->)

(T1,commit)(!!!) <1,2> (->) (!!!)(T2,W(x)) <2,2> (->) (T2,commit)(!!!) <2,2> (->)

Произошли два вида нарушений. Во-первых, изменения транзакции T1 оказались затерты по завершении транзакции T2. Во-вторых, в момент времени, помеченный (!!!), наблюдается рассогласование данных, а именно нарушение закона x = y. Эти данные оказались зафиксированными транзакцией T1 (она «ничего не знает» о параллельно работающей с ней T2). Это означает, что любая другая транзакция могла считать эти некорректные данные в момент времени (!!!); последствия рассогласования перестают быть контролируемыми.

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

<0,0> (->) (T1,W(y)) <0,1> (->) (T2,W(y)) <0,2> (->) (T2,rollback)

Аннулирование (T1,W(y)) и восстановление предыдущего значения y не удовлетворяет правилам согласованности, потому что в результате такого восстановления уничтожится и модификация y, сделанная второй транзакцией (T2,W(y)). Если же не восстанавливать предыдущие значения y, и вторая транзакция тоже выполняет откат, то также невозможно аннулировать (T2,W(y)), просто восстановив значение y, которое было до выполнения этой операции записи.

Зависимость D1. Феномен «грязное чтение»

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

D1: <0,1> (->) (T2,W) <0,2> (->) (T1,R) <0,2> (->) (T2,W)<0,3> (->)

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

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

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

Приведем пример возникновения такой зависимости транзакций – вновь с информацией о положении точки на плоскости. Пусть работают две транзакции, каждая их которых передвигает точку по кривой x+y = 120. Выполняются операции модификации координаты x и модификации координаты y; пусть каждая транзакция считывает значение точки и меняет значение так, чтобы y оказался меньше на 10, а x – больше на 10. Предположим, обе транзакции работают с точкой v = (10,110). Очевидно, что при выполнении в следующей последовательности операций будет возникать рассогласование данных:

<10,110> (->) (T1,R(x,y)) <10,110> (->) (T1,W(y)) <10,90> (->) (T2,R(x,y)) <10,90> (->)

<10,80> (->) (T2,W(x)) <20,80> (->) (T1,commit)(!!!)...

Произошло рассогласование данных: появилась точка (20,80), которая не удовлетворяет условию «x+y = 120». Транзакция T2 рассогласовала данные, и эти данные оказались зафиксированными транзакцией T2 (она «ничего не знает» о параллельно работающей с ней T1). Это означает, что любая другая транзакция может считать эти некорректные данные в момент времени (!!!); последствия рассогласования перестают быть контролируемыми.

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

Феномен «неповторяемое чтение»

T1 считывает обюект данных дважды, один раз перед транзакцией T2, и второй – после завершения T2 операцией commit, т.е. после фиксации изменений. Диаграмма описывает зависимость ЧТЕНИЕ б? ЗАПИСЬ б? ЧТЕНИЕ

D2: <0,1> (->) (T1,R) <0,1> (->) (T2,W) <0,2> (->) (T1,R) <0,2> (->)

Две операции чтения возвращают разные версии обюекта данных О.

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

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

в любом порядке. Полное описание данное феномена будет включать все четыре варианта завершения транзакций T1 и T2.

Приведем один неочевидный пример возникновения такой зависимости транзакций. Пусть выполняется две транзакции, которые передвигают точку по кривой x+y = 120, считывая координаты по одной. Также по одной выполняются операции модификации координаты x и модификации координаты y. Пусть каждая транзакция считывает значение координаты точки и модифицирует значение так, чтобы x оказался меньше на 10, а y – больше на 10. Обе транзакции работают с точкой v = (10,110). Допустим, последовательность операций каждой транзакции следующая:

-> (T,R(x)) > (T,W(x)) > (T,R(y)) > (T,W(y)) > (T,commit)

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

(10,110) (->) (T1,R((x)) x(T1)=10 (->) (T2,R(x)) x(T1)=10 (->) (T2,R(x)) x(T2)=10 (->)

(T2,R((y)) y(T2)=120 (->) (T2,commit) (0,120) (->) (T1,R(y)) y(T1)=120 (->)

(T2,W((y)) y(T2)=130 (->) (T2,commit) (0,130) (->) (!!!)

Действительно, рассогласование данных произошло: появилась точка (0,130), которая не удовлетворяет правилу «x+y = 120». Рассогласовала данные транзакция T2. Незафиксированных данных она не считывала, и тем не менее имеет место аномалия. Это означает, что любая другая транзакция может считать эти некорректные данные в момент времени (!!!); последствия рассогласования перестают быть контролируемыми. Рассогласование возникло из-за того, что на момент чтения второй координаты транзакцией T1 значение первой координаты точки устарело, но T1 об этом ничего не известно, так как она считала значение первой координаты до момента фиксации транзакции T1.

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

Продолжение в следующем номере.

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

Обработка отказов

Что делает сервер при отказе приложения?

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

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

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

При рестарте системы вызывается менеджер журнала, и сканируются все структуры журнала:

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

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