metBD (1084482), страница 22

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

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

• вершин, соответствующих каждой из транзакций;

• направленных ребер Ti->Tj, где транзакция Ti считывает значение элемента, записанного транзакцией Tj;

• направленных ребер Ti->Tj, где транзакция Tj записывает значение в элемент данных после того, как он был считан транзакцией Ti.

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

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

Рассмотрим две транзакции, график выполнения которых представлен в табл.40.

Таблица 40

Здесь в транзакции Т1 100 рублей передается со счета в1 на счет а1. Транзакция Т2 увеличивает текущее значение каждого из этих счетов на 10%. Граф предшествования для данного графика представлен на рис. 3:

а1

в1

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

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

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

Существует и несколько других типов упорядочивания, которые выдвигают менее строгое определение эквивалентности графиков, чем то, которое дается в случае конфликтной упорядоченности. Одно из этих определений называют упорядочиванием по просмотру. Два графика С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.

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

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

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

Таблица 41

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

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

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

Таблица 42

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 43

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

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.

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

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

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

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

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

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

Пример устранения проблемы потерянного обновления.

Таблица 44

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

Характеристики

Список файлов книги