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

Транзакция обладает 4 свойствами: атомарность, согласованность, изоляция и долговечность (АСИД)
Атомарность означает, что выполняется всё или ничего.

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

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

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

Восстановление системы

Система должна быть готова к восстановлению не только после небольших (например, невыполнение операций какой-либо транзакции), но и после глобальных нарушений типа сбоев в питании ЦПУ. Глобальные нарушения поражают сразу все транзакции. Существуют два вида глобальных нарушений.

· отказ системы (например, сбои в питании). Их называют аварийным отказом программного обеспечения.
· отказы носителей (например, поломка готовок дискового накопителя). аварийный отказ аппаратуры.
В 1-м случае для восстановления системы вводятся контрольные точки, которые фиксируются в журнале (см.рис.3.3). Пусть в момент времени Т₂ происходит сбой системы.

Рис.3.3. Этапы выполнения транзакций.

Транзакция Т₁ – полностью сохраняется; Т₂, Т₄ – перезапускаются;

Т₃ и Т₅ – отменяются.

3.2. Параллелизм операций над БД

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

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

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

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

3.3. Проблемы параллельных процессов

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

1 – проблема потери результатов обновления,
2 – проблема незафиксированной зависимости,

3 - чтение «грязных» данных,
4 – проблема несовместимого анализа.
1). Проблема потери результатов обновления

Рис.3.4. Потеря результатов обновления.

А – элемент БД; Т1, Т2 – транзакции; t-время

Транзакция Т1 извлекает кортеж А в t1; Транзакция Т2 извлекает кортеж А в t2;
Транзакция Т1 обновляет кортеж А (на основе значений, полученных в момент времени t1) в t3; Транзакция Т2 обновляет тот же кортеж А (на основе значений, полученных в момент t2, которые имеют те же значения, что и в t1) в момент t4. Однако результат операции обновления, выполняемой транзакцией Т1 будет утерян, поскольку в момент времени t4 она не будет учтена и потому будет «отменена» операцией обновления, выполненной транзакции Т2.

Пример 3.1. Пусть имеем две транзакции Т1 и Т2, обе эти транзакции представляют собой прогон программы Р.

P: А =5; READ A; A=A+1; WRITE A;

Выполнение программы представлено на рис.3.5.

Рис.3.5. Выполнение программы Р.

Легко заметить (см.рис.3.5.), что хотя каждая транзакция добавляла к А единицу, его значение возросло лишь на 1. Это представляет серьёзную проблему, если, например А – число мест, проданных на определённый авиарейс.

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

Рис.3.6. Незафиксированная зависимость

Транзакция Т1 выполняется на основе фальшивого предположения, что кортеж А имеет некоторое значение в момент времени t2, тогда как на самом деле он имеет некоторое значение, существовавшее ещё в момент времени t1. В итоге после выполнения Т1 будет получен неверный результат. Надо иметь ввиду, что отмена выполнения Т2 может произойти не по вине Т2, а, например, в результате краха системы.

3). Чтение «грязных» данных (фиктивные элементы - фантомы):

Рис.3.7. Чтение «грязных» данных

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

Транзакция Т1 дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция Т2, которая добавляет строку, удовлетворяющую условию отбора α. Т1 ничего не знает о существовании Т2, и так как сама она ничего не меняет в базе данных, то ожидает, что после повторного отбора будут отобраны те же самые строки. Результат: Транзакция Т1 в двух одинаковых выборках строк получит разные результаты.

4). Проблема несовместимого анализа

Транзакция Т1 выполняет анализ по всей таблице, например, подсчитывает общую сумму денег на счетах клиентов банка для главного бухгалтера. Пусть на всех счетах находятся одинаковые суммы, например, по 1000у.е. Пусть имеются три счёта S1, S2, S3 и везде по 1000у.е.. Транзакция Т2 в этот момент выполняет перевод 500у.е. c счёта S3 на S1. Общая сумма по всем счетам не меняется.

Рис.3.8. Несовместимый анализ

Т1 – подводит баланс. Т2 – переводит суммы с одного счета на другой.
Результат: Sum=2500, а должно быть Sum=3000. Это произошло из-за параллельной работы.

Конфликт транзакций

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

Различают конфликты:
· W-W (Запись-Запись). Первая транзакция изменила объект и не закончилась. Вторая пытается изменить этот объект. Результат – потеря обновления.
· R-W (Чтение-Запись) Первая транзакция прочитала объект и не закончилась. Вторая транзакция пытается изменить этот объект. Результат – несовместный анализ.
· W-R (Запись-Чтение). 1-я транзакция изменила объект и не закончилась. 2-я пытается прочитать этот объект. Результат – чтение двух «грязных» файлов.
Конфликты типа R-R (Чтение-чтение) отсутствуют, т.к. данные при чтении не изменяются.

Графики запуска транзакций могут быть:

1. Последовательные – если транзакции выполняются строго по очереди.
2. Чередующиеся – если график содержит чередующиеся элементарные операции транзакций.
В первом случае процесс замедляется, но зато выполняется правило.
Два графика называются эквивалентными, если при их выполнении будет получен один и тот же результат. График запроса транзакции называется верным (сериализуемым), если он эквивалентен какому-либо последовательному запросу.

Замечание:
При выполнении двух различных последовательных (а, следовательно, верных) графиков, содержащих один и тот же набор транзакций, могут быть получены различные результаты. Пусть Т1 выполняет действие «сложить X с 1», а транзакция Т2 – «Удвоить X». Тогда последовательный график {Т1, Т2} даст результат 2(Х+1), а последовательный график {Т2, Т1} даст результат 2Х+1. Таким образом, может существовать несколько верных графиков запуска транзакций, приводящих к разным результатам при одном и том же начальном состоянии базы данных. Существуют два способа разрешить конкуренции между транзакциями.

1. «Притормаживать» некоторые транзакции (таким образом обеспечить, чтобы конкурирующие транзакции выполнялись в разное время).

2. Предоставить конкурирующим транзакциям «разные» экземпляры данных

1-ый реализуется путём использования блокировок

2-ой реализуется путём использования данных из журнала транзакций.

3.4. Элементы блокировки.

База данных может быть разбита на элементы, то есть на части, которые можно блокировать. Блокируя некоторый элемент, транзакция может препятствовать доступу других транзакций к этому элементу до тех пор, пока они не разблокируют его.
Природа и размер элементов являются спорными вопросами. Можно видеть большие элементы, подобные отношениям, или малые, такие как отдельные кортежи и даже компоненты кортежей. Выбор больших элементов сокращает накладные расходы системы по поддержанию блокировок, тогда как выбор малых элементов даёт возможность параллельного исполнения многих транзакций. Если типичная транзакция читает или модифицирует один кортеж, который она находит с помощью индекса, то целесообразно трактовать кортежи как элементы. Если же типичная транзакция производит соединение двух или более отношений и тем самым требует доступа ко всем кортежам этих отношений, уместно в качестве элементов выбрать отношения.
Рассмотрим теперь программу, которая при взаимодействии с базой данных не только читает, но и записывает её элементы, но и блокирует и разблокирует их. Условимся, что элемент должен быть блокирован до начала чтения или записи и что операция блокировки действует как примитив синхронизации. Это означает, что если транзакция пытается блокировать уже блокированный элемент, ей приходится ждать, пока блокировка не будет снята по команде разблокирования, которая выполняется транзакцией, устанавливающей блокировку.
Каждая программа, в конце концов, должна разблокировать любой элемент, который она блокировала. Расписание элементарных шагов двух или более транзакций, такое, что выполняются указанные выше правила, касающиеся блокировок, называются легальным.
Пример 3.2. Программу Р из примера 3.1 можно было бы записать с блокировками следующим образом:

P: LOCK A; READ A; A: =A+1; WRITE A; UNLOCK A;

Пусть Т1 и Т2 - две исполнимых программы Р. При выполнении Т1 произойдёт блокировка. Если Т2 начинается до завершения Т1, то система заставит её ждать A: =A+1

Т1 |----------------------|

Т2 - - - - - - - - |--------------------|

Совместным результатом окажется увеличение А на 2.

Бесконечное ожидание и тупики

Пусть существует механизм блокировки. В примере 2 блокировка предоставляется Т2 после снятия её транзакцией Т1. Рассмотрим теперь иную ситуацию. Пусть во время пребывания Т2 в состоянии ожидания транзакция Т3 только запрашивает блокировку А, и этот запрос выполняется раньше, чем запрос Т2. Далее, в то время, когда блокировку установила транзакция Т3, её запрашивает Т4, чьё требование удовлетворяется после разблокирования А транзакцией Т3 и т.д. Очевидно, при этом не исключена возможность того, что Т2 будет бесконечно находиться в состоянии ожидания.

Т1: LOCK A; UNLOCK A;

T2: – – – – – – – -– – – – – – – - - - - - - - - -
T3: LOCK A; UNLOCK A; T4: LOCK A; UNLOCK A; T5:..

Тогда как некоторые другие транзакции постоянно осуществляют блокировку А, хотя и существуют неограниченное число моментов, когда транзакция Т2 имеет шансы заблокировать А. Состояние такого рода называют бесконечным ожиданием. Подобная проблема потенциально может возникнуть в любой обстановке, предусматривающей параллельное исполнение процессов. Простой способ избежать бесконечного ожидания заключается в том, что система предоставления блокировок должна регулировать все неудовлетворённые немедленно запросы и предоставлять возможность блокировки элемента А после его разблокирования первый запросившей её транзакции из числа ожидающих. Эта стратегия (" первым вошёл - первым обслуживается") устраняет бесконечные ожидания.

Более серьёзная проблема, которая возникает при параллельной обработке - это так называемые «тупики».

Пример 3.3. Пусть имеются две транзакции Т1 и Т2, основными действиями, которых при параллельной обработке являются следующие:

Т1: lock A; lock B; unlock A; unlock B;

T2: lock B; lock A; unlock B; unlock A;

Здесь не имеет значения, что конкретно делают с элементами А и В эти транзакции. Пусть они начинают использоваться примерно в одно и то же время. Транзакция Т1 запрашивает блокировку А и её запрос удовлетворяется. Точно так же удовлетворяется запрос транзакции Т2 на блокировку В затем Т1 запрашивает блокировку В и вынуждает ждать, поскольку этот элемент заблокирован транзакцией Т2. Аналогично Т2 запрашивает блокировку А и должна ждать, пока Т1 разблокирует А. Таким образом ни одна транзакция не может продолжаться. Каждая из них ожидает пока другая разблокирует требуемый для неё элемент. Поэтому Т1 и Т2 будут ждать бесконечно.
Ситуация, при которой каждая из множеств S двух или более транзакций ожидает, когда ей будет предоставлена возможность заблокировать элемент, заблокированный в данный момент времени какой-либо иной транзакцией их данного множества S, называют тупиком.
Так как все транзакции находятся в состоянии ожидания, то одна из них не может разблокировать элемент, необходимый для продолжения другой транзакции из S. Поэтому ожидание для них становится бесконечным.

Способы предотвращения тупиков

1). Потребовать, чтобы каждая транзакция единовременно запрашивала все нужные ей блокировки. В нашем примере система предоставила бы блокировку как А, так и В для транзакции Т1, если бы она запросила блокировку первой. После завершения Т1 обе эти блокировки могли бы быть установлены для Т2, то есть Т2 должна ждать.
2). Ввести произвольное линейное упорядочивание элементов и потребовать, чтобы все транзакции запрашивали блокировки в этом порядке.

Пусть в нашем примере А предшествует В, тогда затребовав блокировку А перед В, Т2 обнаруживает, что А уже заблокирована Т1. Элемент В не был ещё заблокирован для Т2. поэтому для Т1 доступна блокировка В, когда она будет запрашиваться. При завершении Т1 блокировки на А и В снимаются и Т2 может продолжаться.
3). Ничего не предпринимать для их предотвращения, а периодически проверять запросы на блокировки и выявлять, не возникло ли тупиковой ситуации. Облегчает предотвращение такой проверки алгоритм построения графа, вершины которого представляют транзакции, а дуга T1-> Т2 означает, что транзакция Т2 ожидает выполнения её запроса на блокировку элемента, заблокированного в данный момент транзакцией Т2. каждый цикл указывает тупик. Если же циклов нет, не существует и тупиков. В случае обнаружения тупика следует произвести рестарт хотя бы для одной из попавших в него транзакций и её воздействие на БД должно быть аннулировано.

3.5. Расписание транзакций

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

Т1: LOCK A; UNLOCK A;

---------------------------------------------------------T2: LOCK A; UNLOCK A;

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

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

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

Т1: READ A; A: =A-10; WRITE A; READ B; B: =B+10; WRITE B;

T2: READ B; B: =B-20; WRITE B; READ C; C: =C+20; WRITE C;

Понятно, что любое последовательное расписание обладает свойством постоянства суммы A+B+C.

Пример расписания: А+В+С

Последовательное:

Т1 Т2
READ A
A=A-10
WRITE A
READ B
B=B+10
WRITE B
READ B
B=B-20
WRITE B
READ C
C=C+20
WRITE C
Сериализуемое:
Т1 Т2
READ A

READ B
A=A-10

B=B-20
WRITE A

WRITE B
READ B

READ C
B=B+10

C=C+20
WRITE B

WRITE C
Несериализуемое:

Т1 Т2
READ A
A=A-10
READ B
WRITE A
B=B-20
READ B
WRITE B
B=B+10
READ C
WRITE B
C=C+20
WRITE C

Рис.3.9. Расписания транзакций

Отметим, что в последнем случае величина B увеличивается, а не уменьшается на 10 в силу того, что Т1 читает В прежде, чем Т2 записывает новые уменьшенные значения В. Предотвратить это сложно.

В случае, когда допускаются произвольные операции с элементами невозможно проверить, дают ли два расписания одинаковый результат при всех начальных значениях элементов. На практике делаются некоторые упрощающие предположения относительно операций, выполняемых над элементами. Удобно предположить, в частности, что одинаковые их значения можно получить только при одной и той же последовательности операций. Поэтому нельзя считать, что (А+10)-20 и (А+20)-30 продуцируют одни и те же значения. Игнорируя алгебраические свойства арифметики, мы совершаем лишь «нефатальные» ошибки. Но зато расписание никогда не рассматривается как сериализуемое, если оно не является таким («фатальная» ошибка).
Нефатальные ошибки могут исключить некоторые параллельные операции и тем самым сделать систему более медленной. Однако в отличие от фатальных ошибок, при этом никогда не могут быть получены некорректные результаты.

Протоколы и расписания

Как было показано выше, произвольные транзакции при их параллельном исполнении могут приводить к бесконечному ожиданию, тупиковым ситуациям и несериализуемому расписанию. Для исключения подобных ситуаций имеются два инструмента.
· 1-й планировщик - часть системы базы данных, которая служит арбитром между конфликтующими запросами. Планировщик может основываться на стратегии " первым вошёл - первым обслуживается" исключения бесконечного ожидания. Планировщик может также справляться с тупиками и несериализуемостью при помощи рестарта одной или более транзакций.

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