 |
Функции СУБД по защите данных. Параллелизм
|
|
|
|
Три проблемы параллелизма
Термин параллелизм означает возможность одновременной обработки СУБД нескольких транзакций с доступом к одним и тем же данным в один и тот же момент времени. В этом случае при обработке правильно составленных транзакций могут возникнуть ситуации, которые приведут к получению неправильного результата из-за взаимных помех между транзакциями. Основные проблемы, возникающие при параллельной обработке транзакции:
1. Проблема потери результатов обновления
2. Проблема возникновения незафиксированной зависимости
3. Проблема несовместимого анализа
1. Проблема потери результатов обновления
| Тр.А | Время | Тр.В |
| Извлекает кортеж Р | T1 | |
| T2 | Извлекает кортеж Р | |
| Обновляет кортеж Р | T3 | |
| T4 | Обновление |
Рис.1
В момент времени t1 Тр.А извлекает некоторый кортеж Р.
В момент времени t2 Тр.В извлекает некоторый кортеж Р.
В момент времени t3 Тр.А обновляет кортеж Р на основании значений, полученных в момент времени t1.
В момент времени t4 Тр.В обновляет кортеж Р на основании значений, полученных в момент времени t2, который имеет те же значения, что и в момент времени t1.
Результат операции обновления, выполненный транзакцией А будет утерян, поскольку в момент времени T4 она не будет учтена и потому будет отменена операцией обновления транзакции В.
2. Проблема возникновения незафиксированной зависимости
| Тр.А | Время | Тр.В |
| t1 | Обновление кортежа Р | |
| Извлечение кортежа Р | t2 | |
| t3 | Отмена выполнения Тр. |
Рис.2a
Проблема 2 появляется, если с помощью некоторой транзакции осуществляется извлечение, а еще хуже обновление некоторого кортежа, который в данный момент обновляется другой транзакцией и это обновление еще не закончено
|
|
|
Транзакция А в момент t2 встречается с невыполненным обновлением. Предположим, что это обновление отменяется в момент времени t3. Таким образом транзакция А выполняется на основании фальшивого предположения, что кортеж Р имеет некоторые значения в момент времени t2, хотя на самом деле он имеет значения в момент времени t1. В итоге выполнения транзакции А будет получен неверный результат. Об этой ситуации мы говорили, что транзакция А зависит от невыполненного обновления в момент времени t2 (рис.2а).
| Тр.А | Время | Тр.В |
| t1 | Обновление кортежа Р | |
| Обновление кортежа Р | t2 | |
| t3 | Отмена транзакции |
Рис.2б
Транзакция А обновляет невыполненное изменение и результат обновления утрачивается в момент времени t3, поскольку отмена выполнения транзакции В в момент времени t3 приводит к восстановлению кортежа Р к исходному значению в момент времени t1 (2б).
3. Проблема несовместимого анализа
На рис.3 показаны Тр.А и Тр.В, которые выполняются для кортежей со счетами (СЧЕТ).
Транзакция А - найти итоговый баланс.
Транзакция В - перевести сумму 10 со СЧЕТА3 не СЧЕТ1.
СЧЕТ1 40 СЧЕТ2 50 СЧЕТ3 30
| . Тр.А | Время | Тр.В |
| Извлечение кортежа СЧЕТ1 (сум=40) | t1 | - |
| Извлечение кортежа СЧЕТ2 (сум=90) | t2 | - |
| - | t3 | Извлечение кортежа СЧЕТ3 |
| - | t4 | Обновления СЧЕТ3 30->20 |
| - | t5 | Извлечение кортежа СЧЕТ1 |
| - | t6 | Обновления СЧЕТ1 40->50 |
| - | t7 | Завершение транзакци |
| Извлечение СЧЕТ3 сум=110 (а не 120) | t8 |
Рис.3
Из-за взаимных помех транзакций получен неверный результат. В этом случае говорят, что транзакция А встретилась с несовместимым состоянием и на его основании был выполнен несовместный анализ.
Блокировка
Описанные выше проблемы могут быть разрешены с помощью методики управления параллельным выполнением процесса под названием блокировка. Ее основная идея:
В случае, когда для выполнения некоторой транзакции необходимо, чтобы некоторый объект, обычно это кортеж, не изменялся непредсказуемо и без ведома этой транзакции, такой объект блокируется.
|
|
|
Алгоритм блокировки.
1. Предположим, что в системе поддерживаются два типа блокировок:
* блокировка без взаимного доступа (монопольная блокировка, x-блокировка, eXclusive);
* блокировка с взаимным доступом (s-блокировка);
x-блокировка записи
s-блокировка чтения
2. Если транзакция А блокирует кортеж Р x-блокировкой, то запрос другой транзакции В с блокировкой этого кортежа будет отменен.
3. Если транзакция А блокирует кортеж Р s-блокировкой, то
- запрос транзакции В на x-блокировку будет отвергнут;
- запрос транзакции В на s-блокировку будет принят.
Эти правила можно представить в виде матрицы совместимости.
| X | S | Без блокировки | |
| X | N | N | Y |
| S | N | Y | Y |
| Без блокировки | Y | Y | Y |
Теперь введем протокол доступа к данным, который позволит избежать проблем параллелизма.
1. Транзакция, предназначенная для извлечения кортежа прежде всего должна наложить s-блокировку на этот кортеж.
2 Транзакция, предназначенная для обновления кортежа прежде всего должна наложить x-блокировку на этот кортеж.
3. Если запрашиваемая блокировка со стороны транзакции В отвергается из-за конфликта с некоторой другой блокировкой со стороны транзакции А, то транзакция В переходит в состояние ожидания. В будет находиться в состоянии ожидания, пока не будет снята блокировка со стороны транзакции А.
В системе должны быть предусмотрены способы устранения бесконечно долгого ожидания (зависания).
4. X- блокировки сохраняются вплоть до конца выполнения транзакции.
Рассмотрим описанные выше проблемы с учетом применения протокола блокировки.
Операция обновления для Тр. А в t3 не будет выполнена, поскольку она является неявным запросом с заданием x- блокировки для кортежа Р, и этот запрос вступает в конфликт с s- блокировкой, уже заданной Тр. В. Тр. А переходит в ожидание. В t4 по аналогичным причинам Тр. В переходит в ожидание. Возникает новая проблема.
| Тр.А | t | Тр.В |
| Извлечение кортежа Р. (Задание s-блокировки для Р) | t1 | - |
| - | t2 | Извлечение кортежа Р. (Задание s-блокировки для Р) |
| Обновление кортежа Р. (Задание x-блокировки для Р) Ожидание | t3 | |
| Ожидание | t4 | Обновление кортежа Р. (Задание x-блокировки для Р) Ожидание |
Рис.1*
|
|
|
| Тр.А | t | Тр.В |
| - | t1 | Обновление кортежа Р. (Задание x-блокировки для Р) |
| Извлечение кортежа Р. (Задание s-блокировки для Р) Ожидание | t2 | - |
| Ожидание | t3 | Отмена выполнения транзакции (Снятие x-блокировки) |
| Извлечение кортежа Р. (Задание s-блокировки) | t4 |
Рис.2*а
| Тр.А | t | Тр.В |
| - | t1 | Обновление кортежа Р. (Задание x-блокировки) |
| Обновление кортежа Р. (Задание x-блокировки) Ожидание | t2 | - |
| Ожидание | t3 | Отмена выполнения транзакции (Снятие x-блокировки) |
| Обновление кортежа Р. (Задание x-блокировки) | t4 |
Рис.2*б
| Тр.А | t | Тр.В |
| Извлечение кортежа СЧЕТ1 Задание s-блокировки (сум=40) | t1 | - |
| Извлечение кортежа СЧЕТ2 Задание s-блокировки (сум=90) | t2 | - |
| - | t3 | Извлечение кортежа СЧЕТ3 Задание s-блокировки |
| - | t4 | Обновление кортежа СЧЕТ3 Задание x-блокировки 30 -> 20 |
| - | t5 | Извлечение кортежа СЧЕТ1 Задание s-блокировки |
| - | t6 | Обновление кортежа СЧЕТ1 Задание x-блокировки Ожидание |
| Извлечение кортежа СЧЕТ3 Задание s-блокировки Ожидание | t7 | Ожидание |
Рис.3*
В некоторых ситуациях использование блокировок приводит к возникновению другой проблемы - тупиковой ситуации.
Тупиковая ситуация возникает, когда две или более транзакции одновременно находятся в состоянии ожидания, причем для продолжения работы каждая из транзакций ожидает прекращения выполнения другой.
Для обнаружения тупиковой ситуации следует обнаружить цикл в диаграмме состояния ожидания, то есть в том перечне транзакций, которые ожидают окончание выполнения других транзакций. В некоторых системах для обнаружения тупиковой ситуации используется хронометраж выполнения транзакций и сообщение о возникновении тупиковой ситуации поступает, если транзакция не выполняется за некоторое предписанное время. Поиск выхода из тупиковой ситуации состоит в выборе одной из заблокированных транзакций в качестве жертвы и отмене ее выполнения. Таким образом с нее снимается блокировка и выполнение другой транзакции может быть возобновлено.
|
|
|
“Способность к упорядочению” - общепринятый критерий правильности выполнения транзакций. Чередующееся выполнение заданного множества транзакций будет верным, если оно упорядочено, то есть при его выполнении будет получен такой же результат, как и при последовательном выполнении этих же транзакций.
Отдельные транзакции считаются верными, если при их выполнении БД переходит из одного непротиворечивого состояния в другое непротиворечивое состояние.
2. Следовательно, выполнение транзакций одна за другой в любой последовательности тоже является верным.
3. Чередующееся выполнение транзакций является верным, если оно эквивалентно некоторому последовательному выполнению, т.е. если оно подлежит упорядочению.
На рисунках 1, 2a, 2б, 3 проблема заключалась в том, что чередующееся выполнение транзакции не было упорядоченным. Основное значение, предложенное схемой блокировки заключается в принудительном упорядочении транзакции.
На рисунке 2*а, 2*б чередующееся выполнение эквивалентно сначала выполнению транзакции В, потом А.
На рисунках 1* и 3* показана тупиковая ситуация.
Если отменить транзакцию А (рис.1* и рис.3*), то чередующееся выполнение вновь станет эквивалентно последовательному выполнению транзакций (сначала В, затем А).
Для заданного набора транзакций любой порядок их выполнения называется графиком запуска. Выполнение транзакции по одной называется последовательным графиком. Непоследовательное выполнение - чередующимся графиком. Два графика называются эквивалентными, если при их выполнении будет получен одинаковый результат. Таким образом график запуска является верным, если он эквивалентен некоторому последовательному графику запуска.
4.2.3. Поддержка блокировок в SQL
В стандарте языка SQL не предусмотрена поддержка явным образом возможности блокировки. Однако, утверждение SET TRANSACTION содержит среди своих характеристик так называемый «уровень изоляции» “Уровень изоляции” используется для описания степени вмешательства параллельных транзакций в работу данной транзакции. “Уровень изоляции” обычно рассматривают как свойство транзакции.
Стандарт языка SQL поддерживает четыре уровня изоляции.
Самый низкий уровень READ UNCOMMITED - уровень незавершенного считывания.
READ COMMITED - Уровень завершенного считывания.
REPEATABLE READ - уровень повторяемого считывания.
Самый высокий уровень SERIALIZABLE - способность к упорядочиванию (устанавливается по умолчанию).
Если все транзакции выполняются на этом уровне, то чередующееся выполнение любого множества параллельных транзакций может быть упорядочено.
|
|
|
“Степень дробления блокировок” находится в обратной зависимости от параллелизма. Чем меньше объект, тем больший параллелизм.
Пример. Транзакция Т хочет задать x-блокировку. В ответ система должна проверить не заблокирован ли объект со стороны другой транзакции. Для избежания подобных ситуаций вводят протокол предварительной блокировки, в соответствии с которым прежде чем накладывать блокировку на кортеж следует наложить ее на все отношение. Следует отметить, что на уровне отношений блокировки задаются неявным образом. Однако многие системы предусматривают явное задание блокировок с помощью разного рода утверждений LOCK.
|
|
|
