Материал: Базы данных и их безопасность. Плотников Д.Г

Рис. 6.1. Граф предшествования

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

Упорядочивание по просмотру

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

С2, состоящих из одних и тех же операций, входящих в состав n транзакций Т1, Т2….Тn, являются эквивалентными по просмотру, если выполняются следующие три условия.

Для каждого элемента данных а1: если транзакция Т1 прочла исходное значение а1 в графике С1, эта же транзакция Т1 должна прочесть исходное значение а1 в графике С2.

Для каждой операции чтения элемента данных а1 транзакцией Тi в графике С1: если считанное значение элемента а1 было записано транзакцией Тj, то и в графике С2 транзакция Тi должна считывать значение элемента а1, записанное транзакцией Tj.

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

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

171

Каждый конфликтно упорядоченный график в то же время является упорядоченным по просмотру, однако обратное утверждение неверно.

Пример упорядоченного по просмотру графика, который не является конфликтно упорядоченным

В примере (табл. 6.6) для транзакций Т4 и Т5 не соблюдается правило вынужденной записи (здесь слепая запись).

Таблица 6.6 Пример упорядоченного графика, не являющийся конфликтно

упорядоченным

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

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

В табл. 6.7. представлен пример восстанавливаемости. Вместо commit в Т1 делается откат. Транзакция Т2 уже

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

172

Т2, поскольку она использовала значение, которое должно быть отменено. Т. е. этот график не обладает свойством восстанавливаемости и поэтому является некорректным.

Таблица 6.7

Пример восстанавливаемости

Восстанавливаемый график – это график, в котором для каждой пары транзакций Тi и Tj выполняется следующее правило: если транзакция Тj считывает элемент данных, предварительно записанный транзакцией Ti, то фиксация результатов транзакции Ti должна выполняться до фиксации результатов транзакции Tj.

6.3. Методы управления параллельностью

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

173

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

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

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

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

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

174

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

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

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

Пример неверного графика с использованием блокировок

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

S={блокировка записи(Т1, а1), чтение (Т1, а1), запись(Т1, а1), снятие блокировки (Т1, а1),

блокировка записи (Т2, а1), чтение (Т2, а1), запись (Т2, а1), снятие блокировки (Т2, а1),

блокировка записи (Т2, в1), чтение (Т2, в1), запись (Т2, в1), снятие блокировки (Т2, в1), commit (Т2),

блокировка записи (Т1, в1), чтение (Т1, в1), запись (Т1, в1), снятие блокировки (Т1, в1), commit (Т1) }

Результат выполнения графика может быть различным: если Т1 выполняется до Т2, то а1 =220, в1 = 400 если Т2 выполняется до Т1, то а1 =210, в1 = 340.

Отсюда видно, что график не является упорядоченным.

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

175