Карпова Т.С. Базы данных: модели, разработка, реализация

Подождите немного. Документ загружается.

Параллельное

выполнение

транзакций

241

Уровни изолированности пользователей

Достаточно

легко

убедиться,

что при

соблюдении

двухфазного протокола

син-

хронизационных

захватов

действительно

обеспечивается

полная

сериалнзация

транзакций.

Однако

иногда

приложению, которое выполняет

транзакцию,

не

сколько

важны

точные

данные,

сколько

скорость

выполнения

запросов.

Напри-

мер,

системах

поддержки

принятия

решении

по

электронным

торгам важно

просто иметь

представление

об

общей

картине

Торгов,

на

основании

которого

принимается

решение

об

повышении

или

снижении

ставок

и т. д. Для

смягче-

ния

требований

сериализашш

транзакций

вводится

понятие уровня

изолиро-

ванности

пользователя.

Уровни

изолированности

пользователей

связаны

проблемами,

которые

возни-

кают

при

параллельном

выполнении

транзакций

которые были

рассмотрены

нами

ранее.

Всего

введено

уровня

изолированности

пользователей. Самый

высокий

уро-

вень

изолированности

соответствует протоколу сериализашш

транзакции,

это

уровень

SERIALIZABLE,

Этот

уровень

обеспечивает

полную

изоляцию

транзакций

полную корректную обработку параллельных транзакций.

уровень изолированности

называется

уровнем

подтвержденного

чте-

ния —

REPEATABLE

READ.

На

этом

уровне

транзакция

не

имеет

доступа

промежу-

точным

или

окончательным

результатам

других

транзакций,

поэтому такие про-

блемы,

как

пропавшие

обновления,

промежуточные

или

несогласованные

данные,

возникнуть

не

могут.

Однако

во

время выполнения своей

транзакции

вы

може-

те

увидеть

строку,

добавленную

в БД

другой

транзакцией.

Поэтому

один

и тот

же

запрос, выполненный

течение

одной

транзакции,

может

дать

разные

ре-

зультаты,

то

есть

проблема

строк-призраков

остается.

Однако

если

такая про-

блема

критична,

лучше

се

разрешать

алгоритмически,

изменяя

алгоритм

обра-

ботки,

исключая

повторное

выполнение

запроса

одной транзакции.

Второй

уровень

изолированности

связан

подтвержденным

чтением,

он'назы-

вается

READ

COMHITED.

На

атом

уровне

изолированности

транзакция

не

имеет

доступа

промежуточным

результатам

других

транзакций,

поэтому

проблемы

пропавших

обновлений

промежуточных

данных

возникнуть

не

могут.

Однако

окончательные

данные,

полученные

ходе

выполнения

других

транзакции,

мо-

гут

быть

доступны нашей

транзакции.

При

этом

уровне

изолированности

транз-

акция

не

может обновлять

строку,

уже

обновленную

другой

транзакцией.

При

попытке выполнить

подобное,

обновление

транзакция

будет

отменена

автомати-

чески,

во

избежание

возникновения

проблемы

пропавшего

обновления.

наконец, самый

низкий

уровень

изолированности

называется

уровнем

непод-

твержденного,

или

грязного,

чтения.

Он

обозначается

как

READ

UNCOMMITED.

При

этом

уровне

изолированности

текущая

транзакция

видит

промежуточные

несогласованные

данные,

также

ей

доступны

строки-призраки.

Однако

да-

же

при

этом

уровне

изолированности

СУБД

предотвращает

пропавшие

обнов-

ления.

стандарте

SQL2

существует

оператор

задания

уровня

изолированности

вы-

полнения

транзакции.

Он

имеет

синтаксис:

242

Глава

И.

Модели

транзакций

SET

TRANSACTION

IZOLATION LEVEL

[{SERIALIZABLE

REPEATABLE

READ

COMMITED

READ

UNCOMHITED}]

[{READ

WRITE

READ

ONLY

}]

Дополнительно

этом

операторе

может быть

указано,

операции

какого типа

вы-

полняются

транзакции.

По

умолчанию

предполагается

уровень

SERIALIZABLE,

Если

задан уровень

READ

UNCOHHITED,

то

допустимы только

операции

чтения

транзакции,

поэтому

этом случае нельзя установить операции

READ

WRITE.

На

рис.

11.11

приведено соответствие уровней изолированности транзакций

про-

"блем,

возникающих

при

параллельном

выполнении

транзакций.

Уровень

изоляции

SERIALIZABLE

REPEATABLE

READ

HEAD

COMMITED

READ

UNCOMMITED

Появление

пропавших

обновлений

СУБД

предотвращает

СУБД

предотвращает

СУБД

предотвращает

СУБД

предотвращает

Появление

промежуточных

данных

СУБД

предотвращает

СУБД

предотвращает

СУБД

предотвращает

Может

произойти

Появление

несогласован-

ных

данных

СУБД

предотвращает

СУБД

предотвращает

Может

произойти

Может

произойти

Появление

строк-

призраков

СУБД

предотвращает

Может

произойти

Может

произойти

Может

произойти

Рис.11.11.

Уровни

изолированно'сти

транзакций

проблемы

многопользовательской

работы

разных коммерческих СУБД могут быть реализованы

не все

уровни

изолиро-

ванности,

это

необходимо выяснить

технической

документации.

Гранулированные

синхронизационные

захваты

Мы

уже

говорили,

что

объектами блокирования могут быть объекты разного

уровня,

начиная

целой

БД и

заканчивая

кортежем.

Понятно,

что чем

крупнее объект

синхронизационного

захвата (неважно,

какой

природы

этот объект

—

логический

или

физический),

тем

меньше

синхрониза-

ционных

захватов

будет

поддерживаться

системе,

и при

этом,

соответственно,

будут меньшие

накладные

расходы. Более того,

если

выбрать

качестве

уровня

объектов

для

захватов файл

или

отношение,

то

будет

решена

даже

проблема

фантомов

(если

это не

ясно

сразу,

посмотрите

еще

раз на

формулировку

про-

блемы фантомов

определение

двухфазного

протокола захватов),

Но

вся

беда

том,

что при

использовании

для

захватов крупных объектов воз-

растает

вероятность

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

тем

самым уменьшается допус-

каемая

степень

их

параллельного

выполнения.

Фактически

при

укрупнении

Параллельное

выполнение

транзакций

243

объекта

синхронизационного

захвата

мы

умышленно огрубляем

ситуацию

ви-

дим

конфликты

в тех

ситуациях,

когда

на

самом

деле

конфликтов нет.

Действи-

тельно,

если транзакция

Т1

обрабатывает

первую,

пятую

двадцатую строку

таблице

R1, но

блокирует

всю

таблицу,

то

транзакция

Т2,

которая

обрабаты-

вает

шестую

восьмую строки

той же

таблицы

не

сможет

получить

ним

дос-

туп,

хотя

на

уровне

строк

никаких

конфликтов

нет.

большинстве

современных систем используются

покортежпые,

то

есть постро-

ковые синхронизационные захваты.

Однако

нелепо

было

бы

применять

покортежную

блокировку

случае выполне-

ния, например,

операции

удаления всего отношения

пли

удаления

всех строк

отношении.

Подобные рассуждения привели

понятию

гранулированных

синхронизацион-

ных

захватов

разработке

соответствующего

механизма.

При

применении

этого додхода

синхронизационные

захваты могут запрашивать-

ся

по

отношению

объектам разного уровня: файлам, отношениям

кортежам.

Требуемый

уровень объекта определяется тем, какая операция выполняется

(например,

для

выполнения

операции

уничтожения

отношения

объектом син-

хронизационного захвата должно быть

все

отношение,

а для

выполнения

опера-

ции

удаления кортежа

—

этот

кортеж).

Объект любого уровня может быть

за-

хвачен

режиме

(разделяемом)

или X

(монопольном)-

Вводится специальный

протокол

гранулированных

захватов

определены

новые

типы

захватов:

перед

захватом

объекта

режиме

S или X

соответствующий

объект

более

высокого

уровня

должен

быть захвачен

режиме

IS. IX или

SIX.

IS'

(Intented

for

Shared

lock,

предваряющий разделяемую блокировку)

по

отно-

шению

некоторому составному объекту

означает

намерение

захватить

неко-

торый входящий

в 0

объект

совместном

режиме. Например,

при

намерении

читать

кортежи

из

отношения

R это

отношение

должно

быть захвачено

режи-

ме

IS (а до

этого

таком

лес

режиме

должен

быть захвачен

файл).

(Intented

for

exclusive

lock,

предваряющий

жесткую

блокировку)

по

отноше-

нию

некоторому составному объекту

означает

намерение

захватить некото-

рый

входящий

в 0

объект

монопольном

режиме.

Например,

при

намерении

удалять кортежи

из

отношения

R это

отношение

должно быть

захвачено

режи-

ме

IX (а до

этого

таком

же

режиме

должен быть захвачен

файл),

SIX

(Shared,

Intented

for

exclusive

lock,

разделяемая

блокировка

объекта,

предва-

ряющая

дальнейшие

жесткие

блокировки

его

составляющих)

по

отношению

некоторому составному объекту

означает совместный захват

всего

этого объ-

екта

намерением

впоследствии

захватывать

какие-либо

входящие

него объ-

екты

монопольном режиме.

Например,

если

выполняется

длинная

операция

просмотра

отношения

возможностью удаления некоторых

просматриваемых

кортежей,

то

экономичнее

всего

захватить

это

отношение

режиме

SIX (а до

этого захватить

файл

режиме IS),

Весьма трудно

описать

словами

все

возможные

ситуации.

Приведем полную

таблицу совместимости

захватов,

анализируя

которую

можно

выявить

все

слу-

чаи

(см.

табл.

11.2).

244

Глава

11.

Модели

транзакций

Таблица

11.2.

Матрица

совместимости

блокировок.

U\L2

Нет

блокировки

SIX

Да

Нет

Да

Нет

Да

Нет

Да

Нет

Да

Нот

Нет

Да

Нет

Да

Нет

Да

SIX

Да

Ист

Нет

Да

Нет

Протокол

гранулированных

захватов

требует

соблюдения

следующих

правил:

Прежде

чем

транзакция установит

S-блокировку

на

данный

кортеж,

она

долж-

на

установить

блокировку

IS или

другую, более сильную блокировку

на от-

ношение,

котором содержится данный

кортеж.

Прежде

чем

транзакция

установит

Х-блокировку

на

данный

кортеж,

она

должна

установить

IX-блокировку

или

другую более

сильную

блокировку

на

отно-

шение,

которое

входит

кортеж.

Блокировка

называется

более сильной

по

отношению

блокировке

тогда

только тогда, когда

для

любой

конфликтной

ситуации

(Нет

—

недопустимо)

столбце блокировки

L2 в

некоторой строке

матрицы

совместимости

блокировок

(см.

табл.

112)

существует

также

конфликт

столбце блокировки

той

же

строке.

Диаграмма

приоритетов

блокировок

приведена

на

рис.

11.12.

Предикатные

синхронизационные

захваты

Несмотря

на

привлекательность

метода

гранулированных

сппхроннзащюниых

захватов,

следует

отметить,

что он не

решает проблему

фантомов

(если,

конеч-

но,

не

ограничиться

использованием

захватов

отношений

режимах

X).

Известно,

что

проблема

фантомов

не

возникает,

если объектом

блокировки

яв-

ляется

целое

отношение.

Именно

это

свойство

послужило

основой

разработки

Параллельное

выполнение

транзакций

245

метода

предикатных

синхронизационных

захватов.

-этом

случае

мы

рассмат-

риваем

захват

отношения

—

простой

частный

случай

предикатного

захвата.

Суть

этого

метода

—

оценить

множество

кортежей,

которое

связано

с той или

иной

транзакций,

если

эти два

множества,

относящиеся

одному

отношению,

не

пересекаются,

то две

транзакции

могут

оперировать

ими

параллельно

без

взаимной

блокировки,

результаты

выполнения

обеих

транзакций

будут

кор-

ректными.

Поскольку

любая

операция

над

реляционной

базой

данных

задастся

некоторым

условием

(то

есть

пси

указывается

не

конкретный

набор

объектов

базы

дан-

ных,

над

которыми

нужно

выполнить

операцию,

условие,

которому

должны

удовлетворять

объекты

этого

набора),

идеальным

выбором

было

бы

требовать

синхронизационный

захват

режиме

пли

именно

этого

условия.

Но

если

по-

смотреть

на

общий

вид

условий,

допускаемых,

например,

языке

SQL,

то

ста-

новится

абсолютно

непонятно,

как

определить

совместимость

двух

предикатных

захватов.

Ясно,

что без

этого

использовать

предикатные

захваты

для

синхрони-

зации

транзакций

невозможно,

а в

общи'!

форме

проблема

неразрешима,

счастью,

эта

проблема сравнительно легко решается

для

случая простых усло-

вий.

Будем

называть

простым

условием

конъюнкцию

простых

предикатов,

имею-

щих

вид:

имя-атрибута

{

операция сравнения

}

значение

Здесь

операция

сравнения:

типичных

СУБД,

поддерживающих

двухуровневую

организацию

(языковой

Уровень

уровень

управления

внешней

памяти),

интерфейсе

подсистем управ-

ления памятью (которая обычно

заведует

ссриализацней

транзакций)

допус-

каются только простые

условия.

Подсистема

языкового

уровня

производит

компиляцию исходного оператора

со

сложным

условием

последовательность

обращений

ядру

СУБД,

каждом

из

которых

содержатся

только

простые

условия.

Следовательно,

случае

типовой

организации

реляционной

СУБД

простые

условия

можно

использовать

как

основу

предикатных

захватов,

Для

простых условий совместимость

предикатных

захватов легко определяется

на

основе

следующей

геометрической

интерпретации.

Пусть

R -

отношение

атрибутами

,....

а„,

т„

,....

т„

множества

допустимых

значений

,....

а„

соответственно

(все

эти

множества

конечные). Тогда

можно

Сопоста-

вить

конечное

n-мерное пространство

возможных

значении

кортежей

R, Лю-

бое

простое

условие

«вырезает»

т-мерный

прямоугольник

этом пространстве

(т

<«

п).

Тогда

3-Х,

X-S,

Х-Х

предикатные

захваты

от

разных

транзакций

совместимы,

если

соответствующие

прямоугольники

не

пересекаются.

Это

иллюстрируется следующим

примером,

показывающим,

что в

каких

бы

ре-

жимах

не

требовала

транзакция

захвата условия

(1<=а«=4)

(Ь=5),

тран-

закция

2 -

условия

(1<-=а<=5)

(1<=Ь<»3),

эти

захваты

всегда

совместимы.

Пример;

(п

Заметим,

что

предикатные

захваты простых

условий

описываются

таблицами,

немногим

отличающимися

от

таблиц

традиционных

синхронизаторов.

246

Глава

11.

Модели

транзакций

Метод

временных

меток

Альтернативный

метод

сериалнзации

транзакций, хорошо работающий

усло-

виях

редких конфликтов транзакций

и не

требующий построения графа ожида-

ния

транзакций,

основан

на

использовании

временных

меток.

Основная идея метода

(у

которого существует множество

разновидностей)

со-

стоит

следующем:

если

транзакция

Т1

началась раньше транзакции

Т2, то

сис-

тема

обеспечивает

такой

режим

выполнения,

как

если

бы Т1

была

целиком

вы-

полнена

до

начала

Т2,

Для

этого каждой транзакции

предписывается

временная

метка

соответ-

ствующая времени начала

Т. При

выполнении операции

над

объектом

транзак-

ция

помечает

его

своей временной меткой

типом

операции

(чтение

или из-

менение).

Перед

выполнением

операции

над

объектом

транзакция

Т1

выполняет следую-

щие

действия;

Проверяет,

не

закончилась

ли

транзакция

Т,

пометившая этот объект.

Если

закончилась,

Т1

помечает объект

выполняет свою операцию.

Если транзакция

Т не

завершилась,

то Т1

проверяет

конфликтность

опера-

ций.

Если операции неконфликтны,

при

объекте

остается

или

проставляет-

ся

временная метка

меньшим

значением,

транзакция

Т1

выполняет

свою

операцию.

Если операции

Т1 и Т

конфликтуют,

то

если

t<T)

t(Tl)

(то

есть

транзакция

является более

«молодой»,

чем

Т1), производится откат

Т и

продолжает

работу.

Если

же

t(T)

tm>

(Т

«старше» Т1),

то Т1

получает

новую временную метку

начинается

заново,

недостаткам метода временных меток

относятся

потенциально

более

частые

откаты транзакций,

чем в

случае

использования

синхронизационных

захватов.

Это

связано

тем,

что

конфликтность транзакций определяется более

груоо.

Параллельное выполнение транзакций

247

Кроме

того,

распределенных системах

не

очень просто вырабатывать глобаль-

ные

временные

метки

отношением

полного

порядка (это отдельная большая

наука).

Но

распределенных

системах

эти

недостатки

окупаются тем,

что не

нужно

распознавать тупики,

а как мы

уже

отмечали,

построение

графа

ожидания

рас-

пределенных

системах

стоит

очень дорого.

ГЛАВА

Встроенный

SQL

Язык

SQL,

как мы уже

видели

главе

предназначен

для

организации доступа

базам данных.

При

этом предполагается,

что

доступ

к БД

может быть осуще-

ствлен

двух

режимах:

интерактивном

режиме

и в

режиме

выполнения

при-

кладных

программ

(приложений).

Эта

двойственность

SQL

создает

ряд

преимуществ;

Все

возможности интерактивного языка запросов доступны

и в

прикладном

программировании.

Можно

интерактивном режиме отладить

основные

алгоритмы обработки

информации,

которые

дальнейшем

могут быть готовыми вставлены

рабо-

тающие

приложения.

SQL

действительно

является

языком

по

работе

базами

данных,

но в

явном

виде

он не

является языком программирования,

нем

отсутствуют

традицион-

ные

операторы,

организующие

циклы,

позволяющие

объявить

использовать

внутренние

переменные, организовать

анализ

некоторых

условий

возможность

изменения

хода

программы

зависимости

от

выполненного

условия.

общем

случае можно назвать

SQL

подъязыком,

который служит исключительно

для

управления

базами

данных.

Для

создания приложений, настоящих программ

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

программирования,

которые

операторы языка

SQL

будут

встраиваться.

Базовыми

языками

программирования

могут быть языки

С,

COBOL,

PL/1,

Pascal.

Существуют

два

способа

применения

SQL в

прикладных

программах;

Встроенный

SQL.

При

таком подходе операторы

SQL

встраиваются

непо-

средственно

исходный

тегст

программы

на

базовом

языке.

При

компиля-

ции

программы

со

встроенными

операторами

SQL

используется

специальный

препроцессор

SQL,

который

преобразует

исходный

текст

исполняемую

программу.

Интерфейс

программирования

приложении

(API

application program

interface),

При

использовании

данного

метода

прикладная

программа

взаимодействует

СУБД путем

применения

специальных

функции.

Вызывая

эти

функции,

программа передает СУБД операторы

SQL и

получает обратно результаты

запросов,

этом случае

не

требуется

специализированный

препроцессор,

249

Процесс

выполнения

операторов

SQL

может

быть

условно

разделен

на 5

этапов

(см. рис.

12.1).

1„

На

первом

этапе

выполняется

синтаксический

анализ оператора

SQL.

На

этом

этапе проверяется

корректность

записи

SQL-оператора

соответствии

пра-

вилами

синтаксиса.

На

этом этапе проверяется

корректность

параметров

оператора

SQL:

имей

отношений,

имей

нолей

данных,

привилегии

пользователя

по

работе

ука-

занными

объектами.

Здесь

обнаруживаются

семантические

ошибки.

3. На

этом

этапе

проводится

оптимизация

запроса.

СУБД

проводит

разделение

целостного

запроса

на ряд

минимальных

операций

оптимизирует

последо-

вательность

их

выполнения

точки

зрения

стоимости

выполнения

запроса.

На

этом этапе

строится

несколько

планов

выполнения

запроса

выбирается

из

них

одни

оптимальный

для

данного

состояния

БД.

4. На

четвертом

этапе

СУБД

генерирует

двоичную

версию

оптимального

плана

запроса,

подготовленного

па

этапе

Двоичный

план

выполнения

запроса

СУБД

фактически

является эквивалентом объектного

кода

программы.

5. И

наконец,

только

на

пятом этапе СУБД

реализует

(выполняет)

разработан-

ный

план,

тем

самым выполняя оператор SQL.

250

Глава

12.

Встроенный

SQL

Следует

отметать,

что

перечисленные

этапы отличаются

по

числу

обраще-

ний

к БД и по

процессорному времени,

требуемому

для их

выполнения*

Син-

таксический

анализ проводится очень

быстро,

он не

требует

обращения

сис-

темным

каталогам

БД.

Семантический

анализ

уже

требует работы

базой

мета-данных,

то

есть

системными каталогами

БД,

поэтому

при

выполнении

этого этапа происходит

обращение

системному каталогу

серьезная работа

ним. Этап, связанный

оптимизаций плана запроса, требует работы

не

только

системным каталогом,

но и со

статистической

информацией

БД,

которая

характеризует

текущее

состояние

всех

отношений,

используемых

запросе,

их

физическое расположение

на

страницах

сегментах внешней памяти,

В си-

лу

указанных причин этап оптимизации наиболее трудоемкий

длительный

процессе выполнения запроса. Однако если

не

проводить этап оптимиза-

ции,

то

стоимость

(время)

выполнения неоптимизированного запроса может

несколько

раз

превысить стоимость оптимизированного запроса. Время,

по-

траченное

на

оптимизацию запроса,

лихвой компенсирует затраты

на вы-

полнение неоптимизированного

запроса.

Этапы

выполнения операторов

SQL

одни

и те же как в

интерактивном режиме,

так

внутри приложений. Однако

при

работе

готовым приложением

многие

этапы СУБД может

выполнить

заранее.

Особенности

встроенного

SQL

При

объединении операторов

SQL с

базовым языком программирования долж-

ны

соблюдаться

следующие

принципы:

Операторы

SQL

включаются непосредственно

текст программы

на

исход-

ном

языке

программирования.

Исходная

программа

поступает

на

вход пре-

процессора SQL, который компилирует операторы SQL.

Встроенные операторы

SQL

могут ссылаться

на

переменные базового языка

программирования.

Встроенные операторы

SQL

получают результаты SQL-запросов

помощью

переменных

базового языка

программирования.

Q Для

присвоения

неопределенных

значений

-(NULL)

атрибутам

отношений

БД

используются специальные функции.

Q Для

обеспечения

построчной

обработки

результатов запросов

во

встроенный

SQL

добавляются несколько

новых

операторов, которые отсутствуют

инте-

рактивном

SQL.

Операторы

манипулирования

данными

не

требуют

изменения

для их

встраивания

программный

SQL

Однако оператор поиска

(SELECT)

потребовал

изменений.

Стандартный оператор

SELECT

возвращает набор

данных,

релевантный

сформи-

рованным

условиям

запроса.

интерактивном

SQL

этот

полученный

набор

данных просто выводится

на

консоль

пользователя

и он

может просмотреть

по-

лученные

результаты.

Встроенный

оператор

SELECT

должен создавать структуры