Базы данных. Вводный курс

Сергей Кузнецов

Назад Содержание Вперёд

Предикатные синхронизационные блокировки

Несмотря на привлекательность метода гранулированных синхронизационных захватов, следует отметить, что он не решает проблему фантомов (если, конечно, не ограничиться использованием блокировок таблиц в режимах 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, не пересекаются.

Это утверждение действительно очевидно (каждому k-мерному прямоугольнику в n-мерном пространстве возможных значений кортежей Tab соответствует некоторое подмножество возможных значений кортежей, и отсутствие пересечения у двух прямоугольников гарантирует отсутствие конфликтов транзакций), но для наглядности на рис. 13.5 приводится иллюстрирующий пример, показывающий, что в каких бы режимах не требовала транзакция T1 блокировки условия (0 < a < 5) & (b = 5), а транзакция T2 – блокировки условия (0 < a <6) & (0 < b <4), эти блокировки всегда будут совместимы.

Рис. 13.5. Простые условия, блокировки которых совместимы

Интересно, что при поддержке такой системы блокировок простых условий можно обойтись без гранулированных блокировок. В частности, чтобы гарантированно заблокировать таблицу целиком, достаточно заблокировать условие &1in (min(mi) < имя_поляi < max(mi)). Чтобы заблокировать базу данных, достаточно заблокировать условие, являющееся конъюнкцией условий блокировки всех таблиц этой базы данных.

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

13.3.2. Синхронизационные тупики, их распознавание и разрушение

Одним из наиболее чувствительных недостатков метода сериализации транзакций на основе синхронизационных блокировок является возможность возникновение тупиков (deadlocks) между транзакциями. Синхронизационные тупики возможны при применении любого из рассмотренных выше вариантов механизмов блокировок.

На рис. 13.6 показан простой сценарий возникновения синхронизационного тупика между транзакциями T1 и T2:

Рис. 13.6. Ситуация синхронизационного тупика между транзакциями T1 и T2

• транзакции T1 и T2 устанавливают монопольные блокировки объектов o1 и o2 соответственно;
• после этого T1 требуется совместная блокировка объекта o2, а T2 – совместная блокировка объекта o1;
• ни одно из этих требований блокировки не может быть удовлетворено, следовательно, ни одна из транзакций не может продолжаться; поэтому монопольные блокировки объектов никогда не будут сняты, а требования совместных блокировок не будут удовлетворены.

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

Обнаружение тупиковых ситуаций

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

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

Пример применения алгоритма редукции к графу ожидания транзакций показан на рис. 13.7 (в целях упрощения примера предполагается, что все блокировки являются монопольными, т.е. для каждой вершины-объекта имеется не более одной входящей дуги). В этом случае редукция состоит в том, что, прежде всего, из графа ожидания (начальное состояние которого показано на рис. 13.7 (a)) удаляются все дуги, исходящие из вершин-транзакций, в которые не входят дуги из вершин-объектов. (Это основывается на том разумном предположении, что транзакции, не ожидающие удовлетворения запроса блокировок, могут успешно завершиться и освободить блокировки). Кроме того, удаляются дуги, входящие в вершины-транзакции, из которых не исходят, ведущие к вершинам-объектам (транзакции, ожидающие удовлетворения блокировок, но не удерживающие заблокированные объекты, не могут быть причиной тупика). Для тех вершин-объектов, для которых не осталось входящих дуг, но существуют исходящие, ориентация одной из исходящих дуг (выбираемой произвольным образом) изменяется на противоположную (это моделирует удовлетворение запроса блокировки). Состояние графа после выполнения первого шага редукции показано на рис. 13.7 (b). После этого снова повторяются описанные действия (cостояние графа после выполнения второго шага редукции показано на рис. 13.7 (c)), и так до тех пор, пока не прекратится удаление дуг. Если в графе остались дуги, то они обязательно образуют цикл (см. рис. 13.7 (c)).

Рис. 13.7. Применение алгоритма редукции к графу ожидания транзакций

Предположим теперь, что нам удалось найти цикл в графе ожидания транзакций. Что делать теперь?

Разрушение тупиков

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

Выбрать «жертву» не так уж легко, поскольку для этого могут использоваться различные, зачастую противоречивые критерии. С одной стороны, было бы разумно жертвовать наиболее «богатой» транзакцией, т.е. той транзакцией, которая удерживает наиболее число блокировок объектов. В этом случае после принудительно завершения такой транзакции освободилось бы наибольшее число объектов, что с большой вероятностью привело бы к исчезновению тупиковой ситуации. Но, с другой стороны, «богатая» транзакция, скорее всего, выполнялась дольше других транзакций. На ее выполнение уже затрачено большое количество системных ресурсов и, вероятно, она скоро завершится самостоятельно. Поэтому этот выбор может оказаться в системном отношении не самым удачным.

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

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

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

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

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

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

13.3.3. Метод временных меток

Альтернативный метод сериализации транзакций, хорошо работающий в условиях редкого возникновения конфликтов транзакций и не требующий построения графа ожидания транзакций, основан на использовании временных меток. Основная идея метода временных меток (Timestamp Ordering, TO), у которого существует множество разновидностей, состоит в следующем: если транзакция T1 началась раньше транзакции T2, то система обеспечивает такой сериальный план, как если бы транзакция T1 была целиком выполнена до начала T2.

Для этого каждой транзакции T предписывается временная метка t(T), соответствующая времени начала выполнения транзакции T. При выполнении операции над объектом o транзакция T помечает его своими идентификатором, временной меткой и типом операции (чтение или изменение).

Перед выполнением операции над объектом o транзакция T2 выполняет следующие действия:

• Проверяет, помечен ли объект o какой-либо транзакцией T1. Если не помечен, то помечает этот объект своей временной меткой и типом операции и выполняет операцию. Конец действий.
• Иначе транзакция T2 проверяет, не завершилась ли транзакция T1, пометившая этот объект. Если транзакция T1 закончилась, то T2 помечает объект o и выполняет свою операцию. Конец действий.
• Если транзакция T1 не завершилась, то T2 проверяет конфликтность операций. Если операции неконфликтны, то при объекте o запоминается идентификатор транзакции T2, остается или проставляется временная метка с меньшим значением, и транзакция T2 выполняет свою операцию.
• Если операции транзакций T2 и T1 конфликтуют, то если t(T1) > t(T2) (т.е. транзакция T1 является более «молодой», чем T2), то производится откат T1 и всех других транзакций, идентификаторы которых сохранены при объекте o, и T2 выполняет свою операцию.
• Если же t(T1) < t(T2) (T1 «старше» T2), то производится откат T2; T2 получает новую временную метку и начинается заново.

К недостаткам метода TO относятся потенциально более частые откаты транзакций, чем в случае использования синхронизационных захватов. Это связано с тем, что конфликтность транзакций определяется более грубо. Кроме того, в распределенных системах не очень просто вырабатывать глобальные временные метки с отношением полного порядка (это отдельная большая наука).

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

Назад Содержание Вперёд