Лекция (2) (1121831), страница 8
Текст из файла (страница 8)
Тогда блокировка объекта o в режиме X в транзакции T1 не совместима с блокировкой этого объекта в режимах X, S, IX, IS или SIX в транзакции T2. Действительно, блокировка объекта o в режиме X в транзакции T1 направлена на то, чтобы изменять объект o целиком. Несовместимость блокировки объекта o в режиме X в транзакции T1 с его блокировкой в режиме X или IX в транзакции T2 устраняет конфликты транзакций T1 и T2 вида W/W. Несовместимость блокировки объекта o в режиме X в транзакции T1 с его блокировкой в режиме S или IS в транзакции T2 устраняет конфликты транзакций T1 и T2 вида W/R. Наконец, несовместимость блокировки объекта o в режиме X в транзакции T1 с его блокировкой в режиме SIX в транзакции T2 устраняет конфликты транзакций T1 и T2 вида W/R и W/W.
Блокировка объекта o в режиме S в транзакции T1 совместима с блокировкой этого объекта в режимах S или IS в транзакции T2, поскольку эти блокировки в транзакциях T1 и T2 направлены только на то, чтобы только читать некоторые объекты o', входящие в o. Блокировка объекта o в режиме S в транзакции T1 не совместима с блокировкой этого объекта в режимах X, IX или SIX в транзакции T2, поскольку любая из этих блокировок направлена на то, чтобы изменять в транзакции T2 объект o целиком или какой-либо объект o', входящий в o. Несовместимость блокировки объекта o в режиме S в транзакции T1 с блокировкой этого объекта в режимах X, IX или SIX в транзакции T2, тем самым, устраняет конфликты транзакций T1 и T2 вида R/W.
Блокировка объекта o в режиме IХ в транзакции T1 совместима с блокировкой этого же объекта в режимах IS или IX в транзакции T2. Действительно, блокировка объекта o в режиме IX в транзакции T1 направлена на то, чтобы в этой транзакции изменять какой-либо объект o', входящий в o, а блокировка этого же объекта в режиме IS в транзакции T2 – на то, чтобы читать в транзакции T2 какой-либо объект o'', входящий в o. Если объекты o' и o'' – разные, то конфликт транзакций T1 и T2 не возникнет. Если o' = o'', то перед изменением этот объект будет заблокирован в транзакции T1 в режиме X, а перед чтением – в транзакции T2 в режиме S. Несовместимость этих блокировок позволит избежать конфликта транзакций T1 и T2 вида W/R, и для этого не требуется несовместимость блокировок IX и IS объекта o. Аналогично обосновывается совместимость блокировок IX и IX. Блокировка IХ не совместима с блокировкой S, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида W/R. Блокировка IХ не совместима с блокировкой X, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида W/W. Наконец, блокировка IХ не совместима с блокировкой SIX, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида W/R или W/W.
Блокировка объекта o в режиме IS в транзакции T1 совместима с блокировкой этого же объекта в режимах S, IS, IX или SIX в транзакции T2. Совместимость с блокировкой в режиме S или IS уже обосновывалась. Покажем, что блокировка объекта o в режиме IS в транзакции T1 совместима с блокировкой того же объекта в режиме IX в транзакции T2. Действительно, блокировка объекта o в режиме IS в транзакции T1 направлена на то, чтобы в этой транзакции читать какой-либо объект o', входящий в o, а блокировка этого же объекта в режиме IX в транзакции T2 – на то, чтобы в транзакции T2 изменять какой-либо объект o'', входящий в o. Если объекты o' и o'' – разные, то конфликт транзакций не возникнет. Если o' = o'', то перед чтением этот объект будет заблокирован в транзакции T1 в режиме S, а перед изменением – в транзакции T2 в режиме X. Несовместимость этих блокировок позволит избежать конфликта транзакций T1 и T2 вида R/W, и для этого не требуется несовместимость блокировок IS и IX объекта o. Аналогично можно показать совместимость блокировок IS и SIX. Несовместимость блокировок IS и X очевидна, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида R/W.
Блокировка объекта o в режиме SIX в транзакции T1 позволяет этой транзакции читать любой объект o', входящий в o, без его дополнительной блокировки и изменять любой объект o', входящий в o, с его предварительной блокировкой в режиме X. Эта блокировка совместима с блокировкой объекта o в режиме IS в транзакции T2. Действительно, блокировка объекта o в режиме IS в транзакции T2 направлена на то, чтобы в транзакции T2 читать какой-либо объект o', входящий в o. Перед этим в транзакции T2 должна быть установлена блокировка объекта o' в режиме S. К этому моменту у объекта o' может отсутствовать явная блокировка, установленная в транзакции T1, что, в соответствии с семантикой блокировки SIX, означает наличие неявной блокировки o' по чтению. Очевидно, что в этом случае конфликт транзакций T1 и T2 не возникает. К этому же моменту у объекта o' может иметься блокировка в режиме X, установленная в транзакции T1. В этом случае запрос блокировки объекта o' в режиме S удовлетворен не будет, и конфликт транзакций T1 и T2 вида W/R будет предотвращен без потребности в несовместимости блокировок SIX и IS. Блокировка объекта o в режиме SIX в транзакции T1 не совместима с блокировкой объекта o в режиме X в транзакции T2, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида R/W. Блокировка объекта o в режиме SIX в транзакции T1 не совместима с блокировкой объекта o в режиме S или IS в транзакции T2, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида W/R при доступе к некоторым объектам o', входящим в o. Наконец, блокировка объекта o в режиме SIX в транзакции T1 не совместима с блокировкой объекта o в режиме IX или SIX в транзакции T2, поскольку иначе мог бы проявиться конфликт транзакций T1 и T2 вида R/W при доступе к некоторым объектам o', входящим в o.
Предикатные синхронизационные блокировки
Несмотря на привлекательность метода гранулированных синхронизационных захватов, следует отметить, что он не решает проблему фантомов (если, конечно, не ограничиться использованием блокировок таблиц в режимах S и X). Давно известно, что для решения этой проблемы необходимо перейти от блокировок индивидуальных («физических») объектов базы данных, к блокировке условий (предикатов), которым удовлетворяют эти объекты. Проблема фантомов не возникает при использовании для блокировок уровня таблиц именно потому, что таблица как логический объект представляет собой неявное условие для входящих в него кортежей. Блокировка таблицы – это простой и частный случай предикатной блокировки.
Поскольку любая операция над реляционной базой данных задается некоторым условием (т.е. в ней указывается не конкретный набор объектов базы данных, над которыми нужно выполнить операцию, а условие, которому должны удовлетворять объекты этого набора), идеальным выбором было бы требовать синхронизационную блокировку в режиме S или X именно этого условия. Но если посмотреть на общий вид условий, допускаемых, например, в языке SQL, то становится абсолютно непонятно, как определить совместимость двух предикатных блокировок. Ясно, что без этого использовать предикатные блокировки для сериализации транзакций невозможно, а в общей форме проблема неразрешима.
Один из компромиссных подходов предлагался участниками проекта System R. Подход основывался на том, что при открытии сканирования таблицы по индексу в RSS передается дополнительная информация (диапазон сканирования), которая ограничивает множество кортежей, среди которых не должны возникать фантомы.
Опираясь на наличие этой информации, предлагалось ввести в систему блокировок System R элементы предикатных блокировок. Заметим сначала, что в System R блокировки сегментов (файлов), таблиц и кортежей технически трактовались единообразно, как блокировки идентификаторов кортежей (tid'ов). При блокировке кортежа на самом деле блокировался его tid. При блокировке сегмента или таблицы на самом деле блокировался tid описателя соответствующего объекта во внутренних таблицах-каталогах сегментов или таблиц.
Предлагалось расширить систему синхронизации, разрешив применять блокировки к паре «идентификатор индекса, интервал значений ключа этого индекса». К такой паре можно было применять блокировки в любом из допустимых режимов, причем две такие блокировки считались совместимыми в том и только в том случае, если они были совместимы в соответствии с приведенной таб. 13.2 или указанные диапазоны значений ключей не пересекались.
При наличии такой возможности, если открывается сканирование таблицы через индекс, то таблица блокируется в режиме IS, и в этом же режиме блокируется пара «идентификатор индекса, диапазон сканирования». При занесении (удалении) кортежа таблица блокируется в режиме IX, и в этом же режиме для каждого индекса, определенного на данной таблице отношении, блокируется пара «идентификатор индекса, значение ключа из затрагиваемого операцией кортежа». Это позволяет избежать конфликтов читающих транзакций с теми изменяющими транзакциями, которые затрагивают диапазоны сканирования читающих транзакций. При этом решается проблема фантомов, и параллельность транзакций ограничивается «по существу», т.е. только в тех случаях, когда их параллельное выполнение создает проблемы.
Заметим сразу, что описанное решение проблемы фантомов далеко от идеального. Во-первых, по-прежнему при сканировании таблиц без использования индексов отсутствие фантомов можно гарантировать только при блокировке всего отношения в режиме S. Во-вторых, даже при сканировании по индексу условие реальной выборки кортежа часто может быть гораздо строже простого указания диапазона сканирования, а это значит, что блокировка этого диапазона будет слишком сильной, т.е. затронет более широкое множество кортежей, чем то, которое будет реальным результатом сканирования.
Известно следующее более совершенное решение. Будем называть простым условием конъюнкцию простых предикатов сравнения, имеющих вид имя_поля { = > < } значение. В типичных СУБД, поддерживающих двухуровневую организацию (языковой уровень и уровень управления внешней памяти), в интерфейсе подсистемы управления памятью (которая обычно заведует и сериализацией транзакций) допускаются только простые условия. Подсистема языкового уровня производит компиляцию оператора SQL со сложным условием в последовательность обращений к подсистеме управления памятью, в каждом из которых содержатся только простые условия.
Более точно, простое условие явно указывается в операции открытия сканирования таблицы (напрямую или через индекс; в последнем случае оно конъюнктивно соединяется с условием, задаваемым диапазоном сканирования). Кроме того, при открытии сканирования всегда можно указать, для какой цели оно будет использоваться: для выборки кортежей, для их удаления или для их обновления (это известно компилятору SQL). Кроме того, неявные условия задаются операциями вставки и удаления кортежей (конъюнктивное логическое выражение, состоящее из простых предикатов вида имя_поля = значение для всех полей таблицы), а также операциями обновления кортежей (конъюнктивное логическое выражение, состоящее из простых предикатов вида имя_поля = значение для всех обновляемых полей таблицы). Поэтому в случае типовой организации SQL-ориентированной СУБД простые условия можно использовать как основу предикатных захватов.
Для простых условий совместимость предикатных блокировок легко определяется на основе следующей геометрической интерпретации. Пусть Tab – таблица с полями a1, a2, ..., an, а m1, m2, ..., mn – множества допустимых значений a1, a2, ..., an соответственно (естественно, все эти множества – конечные). Тогда можно сопоставить Tab конечное n-мерное пространство возможных значений кортежей Tab. Легко видеть, что любое простое условие, представляющее собой конъюнкцию простых предикатов, «вырезает» в этом пространстве k-мерный прямоугольник (k ≤ n).
Достаточно очевидно следующее утверждение:
Пусть имеются два простых условия scond1 и scond2. Пусть транзакция T1 запрашивает блокировку scond1, а транзакция T2 – scond2 в режимах, которые были бы несовместимы, если бы scond1 и scond2 являлись не условиями, а объектами базы данных (S-X, X-S, X-X). Эти блокировки совместимы в том и только в том случае, когда прямоугольники, соответствующие scond1 и scond2, не пересекаются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
