Реферат: Deadlocks

Что такое взаимоблокировки и как с ними бороться

Иван Бодягин

Введение

Проблема взаимоблокировок в реальном приложении может привести к порче достаточно большого количества нервных клеток, и в то же время довольно скудно описана. Цель данной статьи – хотя бы отчасти восполнить этот досадный пробел и объяснить, что такое взаимоблокировки и как с ними бороться. В качестве подопытной свинки выбран Microsoft SQL Server, однако теоретическая часть также относится и к другим серверам баз данных, хотя бы отчасти применяющим блокировочный механизм для обеспечения корректности параллельной обработки транзакций, например, DB2, Oracle, Informix и даже Interbase.

Основные понятия

Разговор о взаимоблокировках сложно вести, не располагая некоторой базовой терминологией. Здесь я попытаюсь изложить необходимый минимум основных понятий и терминов. Эта часть никоим образом не претендует на полноту, поэтому в случае возникновения каких-либо вопросов рекомендую обратиться к литературе упомянутой ниже. Те же, кто в блокировках, как таковых, разбирается в достаточной степени, могут смело пропустить этот раздел.

Блокировки

Удивительно, но на форумах достаточно часто появляются вопросы, из текста которых становится ясно, что автор попросту перепутал термины «блокировка» (lock) и «взаимоблокировка» (deadlock). Во избежание подобных недоразумений начнем с самого начала.

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

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

Типы блокировок

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

Read Lock – блокировка чтения, она же «коллективная», она же «разделяемая». Смысл этой блокировки в том, что она совместима с точно такими же блокировками. Иными словами, на один и тот же ресурс может быть наложено сколь угодно много коллективных блокировок. В терминологии MSSQL эта блокировка называется Shared Lock, или сокращенно S.

Write Lock – блокировка записи, она же «монопольная», она же «эксклюзивная». Эта блокировка не совместима ни с Read Lock, ни сама с собой, ни с каким либо другим типом блокировок. То есть в один момент времени на один объект может быть наложена только одна монопольная блокировка. Эта блокировка в терминологии MSSQL называется Exclusive Lock, или же сокращенно X.

Update Lock – это промежуточная блокировка, блокировка «обновления». Она совместима с Read Lock, но не совместима с Write Lock и сама с собой. Иными словами на один объект могут быть одновременно наложены одна блокировка обновления, ни одной монопольной блокировки и сколь угодно много коллективных блокировок. Этот тип блокировок введен как раз для снижения риска возникновения взаимоблокировки. Каким именно образом, будет объяснено ниже.

Блокировки намерения

Вышеописанными тремя типами возможные типы блокировок не ограничиваются. Нас также будут интересовать так называемые «блокировки намерения» (Intent Lock)

Дело в том, что объекты в БД выстраиваются в своеобразную иерархию Таблица->Страница->Запись. Любая из вышеупомянутых блокировок может быть наложена на любой из этих объектов.

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

Из возможных типов блокировок нас интересуют (здесь и далее используется терминология Microsoft SQL Server):

Intent Share – коллективная блокировка намерения, сокращенно IS.

Intent Exclusive – монопольная блокировка намерения, сокращенно IX.

Все упомянутые блокировки вместе образуют так называемую «Матрицу совместимости» (Compatibility Matrix)

Таблица 1

В таблице 1 “Yes” означает, что блокировки совместимы, то есть могут быть одновременно наложены на один и тот же объект, а “No” означает, что не совместимы.

Протокол двухфазной блокировки

Важную роль в обеспечении корректной параллельной обработки транзакций играет «протокол двухфазной блокировки» (Two Phase Locking – 2PL). Существует соответствующая теорема, в которой доказывается, что если транзакция удовлетворяет протоколу двухфазной блокировки, то она корректна, то есть результат ее выполнения не зависит от других транзакций.

Суть 2PL в том, что нельзя снять однажды наложенную блокировку до тех пор, пока не наложены все блокировки, необходимые транзакции. Таким образом, работа с блокировками в транзакции делится на две фазы: фаза наложения блокировок и фаза снятия. В практических реализациях, как правило, применяется строгий протокол двухфазной блокировки – Strict 2PL. Его особенность в том, что фаза снятия блокировок наступает после фиксации транзакции.

Уровни изоляции

Как уже говорилось, в идеальном случае результат выполнения транзакции не должен зависеть от остальных транзакций, сколько бы одновременно их не выполнялось. Но, к сожалению, этот идеальный случай накладывает сильные ограничения на параллельную обработку, практически выстраивая транзакции в очередь. Однако в большинстве случаев такая строгость не нужна, и поэтому были введены так называемые «уровни изоляции» (Isolation Level), которые определяют степень параллелизма выполнения транзакций. Чем ниже уровень изоляции, тем выше степень параллелизма и тем больше риск «неправильного» выполнения транзакции.

В стандарте ANSI SQL вводятся четыре уровня изоляции. И по названиям, и по поведению уровни изоляции в Microsoft SQL Server полностью соответствуют описанным в стандарте.

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

1. Read Uncommitted – самый низкий уровень изоляции. Позволяет читать "грязные" данные незафиксированых транзакций, отсюда и название феномена – «грязное чтение» (Dirty Read). Суть феномена в том, что если первая транзакция запишет какие-то данные, вторая их прочитает, а потом первая транзакция будет отменена, то получится, что вторая транзакция прочитала данные, которые никогда не существовали.

2. Read Committed – при этом уровне изоляции грязное чтение невозможно, то есть второй транзакции не дадут прочитать данные первой до тех пор, пока первая транзакция не зафиксируется. Но при этом уровне изоляции все еще возможна аномалия неповторяющегося чтения. Суть этого феномена в том, что если первая транзакция один раз прочитала данные, а потом вторая их изменила и зафиксировалась, то повторное чтение тех же данных первой транзакцией вернет уже измененные данные.

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

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

Особенности Microsoft SQL Server

Ввиду того, что все практические эксперименты будут проводиться на Microsoft SQL Server 2000, необходимо также описать некоторые особенности внутренней механики этого сервера.

Для работы с блокировками сервер идентифицирует каждый объект. Для этого используются идентификаторы ресурса (Resource) и объекта (ObjId). Для разных типов объектов эти идентификаторы отличаются. Нас будут интересовать следующие объекты:

TAB – таблица. Идентификатор объекта "целое число", например 26173590. Поскольку таблица – объект чисто логический, идентификатора ресурса она не имеет.

PAG – страница данных. Виртуальная страница данных принадлежит конкретной таблице, поэтому идентификатор объекта совпадает с идентификатором таблицы, данные которой размещены на этой странице. В то же время страница имеет физический эквивалент – страницу данных в файле, поэтому имеется также идентификатор ресурса. Он представляет собой комбинацию идентификатора файла данных (fileId) и номера страницы внутри файла (pageId), например, 1: 1723

RID – запись. Виртуальная запись принадлежит странице, поэтому так же, как и в случае со страницей, ObjId совпадает со страничным и, соответственно, табличным идентификаторами. Физический эквивалент также присутствует – это слот в странице данных, соответственно, есть и идентификатор ресурса, который состоит из идентификатора файла данных, идентификатора страницы данных и, наконец, идентификатора записи внутри страницы. Например, 1:1723:2

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

Этот запрос вернет все блокировки, наложенные на указанную таблицу, с вот такими данными: SPID – идентификатор пользовательской сессии, DBID – идентификатор базы данных, ObjID – идентификатор объекта, ObjName – имя объекта, Type – тип объекта, Resource – идентификатор ресурса, Mode – тип блокировки, Status – статус блокировки.

Что же касается уровней изоляции, то, как уже было сказано, они полностью соответствуют стандарту ANSI SQL. Следует обратить особое внимание, что уровнем изоляции по умолчанию является READ COMMITTED. Иными словами, если не предпринять ряд специальных усилий, то в некоторых случаях возможны различные нарушения изолированности транзакций.

Взаимоблокировка

Большинство способов обеспечения параллелизма, хотя бы отчасти основанных на блокировках, подвержено взаимоблокировкам (deadlock). И хотя известны достаточно остроумные алгоритмы, позволяющие не допускать подобных ситуаций в принципе, в коммерческих приложениях они почти не встречаются. Microsoft SQL Server здесь не является исключением, и также подвержен взаимоблокировкам (они же «мертвые блокировки» или «тупиковые ситуации»).

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

Встроенные способы определения взаимоблокировок

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

Timeout based

Самый простой способ – это ввести некоторое фиксированное время ожидания (timeout), и если транзакция оказалась заблокированной больше этого времени, то считать, что она вошла в тупиковую ситуацию и отменять ее. Недостатки этого способа очевидны – нет стопроцентной гарантии, что отмененная транзакция была одной из участниц взаимоблокировки. Увеличение времени тайм-аута повышает эту вероятность, но одновременно увеличивает время обнаружения действительно намертво заблокированных транзакций. А это, в свою очередь, ведет к увеличению времени простоя запросов, не участвующих во взаимоблокировке, но ожидающих ресурсов, захваченных намертво заблокированными транзакциями.

Wait-for graph based

Существуют и более удачный способ определения взаимоблокировок (хотя и более трудоемкий). Для этого менеджер блокировок строит направленный граф, который называется «графом ожидания» (wait-for graph). В вершинах этого графа находятся транзакции, а в ребрах – зависимости. Например, ребро Ti->Tj появляется в том случае, если Ti ждет, пока Tj освободит какой-нибудь объект. Таким образом, если в графе ожидания возникает цикл (T1->T2->…->Tn->T1), то T1 ждет сама себя, как и все остальные n транзакций в цикле, следовательно, транзакции заблокированы намертво. В данном случае обнаружение взаимоблокировок сводится к нахождению замкнутых циклов в графе ожидания. Сами зависимости в граф добавляются и уничтожаются по мере получения и снятия блокировок, технически в этом ничего сложного нет. Сложность лишь в том, как часто менеджер блокировок должен проверять граф ожидания на наличие циклов. Теоретически это можно делать каждый раз при добавлении новой зависимости, однако делать проверки так часто слишком накладно, поскольку, как правило, количество обычных блокировок намного выше мертвых, к тому же сама взаимоблокировка никуда не денется и дождется, пока за ней придут. Поэтому проверять наличие циклов можно либо когда в граф добавляется какое-то фиксированное количество граней, либо опять же, по истечении некоего таймаута. Но здесь, в отличие от предыдущего способа, гарантируется, что будет найдена именно мертвая блокировка, а также, что мы обнаружим все мертвые блокировки, а не только те, которые продержались достаточно долго.

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

Объем работы, проделанный транзакцией (вся эта работа будет утеряна в случае отмены).

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

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

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

Timestamp based

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

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

«ожидание-гибель» (wait-die). Если транзакция T1 «старше» Т2, тогда транзакции Т1 разрешается пребывать в состоянии ожидания на блокировке. Если же Т1 «младше» T2, тогда Т1 откатывается.

«ранение-ожидание» (wound-wait). Если транзакция T1 «старше» T2, тогда T1 «ранит» T2; ранение обычно носит «смертельный» характер – транзакция Т2 откатывается, если только к моменту получения «ранения» T2 не оказывается уже завершенной. В этом случае Т2 «выживает» и отката не происходит. Если же Т1 «младше» Т2, тогда Т1 разрешается находиться в состоянии ожидания на блокировке.

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

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

Реализация в Microsoft SQL Server

В Microsoft SQL Server используется механизм устранения взаимоблокировок на основе графа ожидания. Граф строится при каждом запросе блокировки. По истечении некоего тайм-аута просыпается монитор блокировок, и если он обнаруживает, что какая-то транзакция ждет слишком долго, инициируется процесс нахождения замкнутого цикла в графе ожидания. В случае обнаружения мертвой блокировки происходит откат одной из транзакций, участвующих в цикле. «Жертва» вычисляется в зависимости от объема проделанной работы, которая в свою очередь определяется по количеству записей в журнале транзакций, которые необходимо откатить. Однако есть возможность указать серверу, какую транзакцию предпочтительнее видеть в качестве «жертвы», с помощью команды:

Здесь @deadlock_var – переменная в диапазоне от 1 до 12, чем меньше число, тем ниже приоритет; LOW соответствует 3, а NORMAL – 6.

Но как бы сервер не старался, все, что он сможет сделать по своей инициативе – это отменить одну из транзакций. Самостоятельно Microsoft SQL Server отмененную транзакцию заново не запускает, а возвращает сообщение об ошибке. Поэтому в клиентском приложении необходимо предусмотреть обработку данной ситуации и, возможно, перезапуск отмененной транзакции. Однако по ряду причин целиком полагаться на обработку подобных ошибок в приложении не следует, это последний рубеж обороны по защите нервов конечного пользователя. Недостатки от перекладывания всей ответственности на клиента в данном случае таковы:

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

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

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

Возможные причины возникновения взаимоблокировок

В свете всего вышеописанного почетной обязанностью разработчика является сведение вероятности мертвой блокировки к минимуму, а в идеале – к нулю, что является достаточно сложной, но вполне разрешимой задачей.

Строго говоря, все случаи взаимоблокировки сводятся к нарушению порядка доступа к объектам. Далее разберем несколько примеров транзакций, потенциально способных привести к тупиковой ситуации. Но перед этим, чтобы примеры были более наглядными, надо выбрать базу для экспериментов (например стандартную Northwind) и создать в ней табличку для дальнейших опытов. Для этого достаточно выполнить в Query Analyzer’е вот такой скрипт:

Первый пример

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

Первая транзакция - T1.

Вторая транзакция - T2.

Если эти транзакции стартуют одновременно, то произойдет взаимоблокировка по причине очевидного нарушения порядка доступа. T1 сначала обращается к записи X = 1, а затем к записи X = 3. Т2 же, наоборот, сначала обращается к записи X = 3, а затем к X = 1.

Рисунок 1. Порядок обращения к записям, приводящий к взаимоблокировке.

При одновременном старте Т1 захватывает запись X = 1, в это время Т2 успевает захватить запись X = 3. Затем T1 хочет захватить запись X = 3, но она уже захвачена T2, поэтому T1 ожидает T2 на блокировке, и в граф добавляется ребро T1->T2. Примерно в это же время T2 хочет захватить запись X = 1, которая также уже захвачена T1. В графе ожидания появляется второе ребро T2->T1 и он становится цикличным. Ну а поскольку подобная ситуация без грубого вмешательства неразрешима, то одна из транзакций будет отменена, другая же, пользуясь тем, что блокировка исчезла, спокойно завершит свою работу.

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

Второй пример

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

Очень часто встречается примерно такая последовательность операторов в одной транзакции:

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

Выполним вышеприведенный T-SQL-код из транзакций T1 и T2. Чтобы имитировать возможное развитие событий при параллельной работе будем выполнять транзакции по частям. Сначала половину T1, затем целиком T2, а потом оставшуюся часть T1. Эффект будет точно таким же, как если бы в реальном приложении между двумя операторами T1 успела бы пролезть транзакция T2. На самом деле для получения взаимоблокировки достаточно, чтобы между двумя операторами T1 успел втиснуться только первый оператор T2, дальнейший порядок операций уже не важен.

Итак, выполним первую часть T1 в одном из окон Query Analyser’а:

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

Иными словами, мы наложили коллективную блокировку (S) на конкретную запись (RID 1:17495:1), и две коллективные блокировки намерения (IS) выше по иерархии, на страницу и таблицу. Откроем новое соединение с той же базой в новом окне QA и попытаемся выполнить эту же транзакцию целиком:

Блокировок, естественно, добавилось:

Те, что (в моем случае) от spid 54 – это наложенные ранее, от первой транзакции, а те, у которых spid 61 - от второй. С блокировками намерения все то же самое, они запрошены и успешно получены. А вот с эксклюзивными ситуация такая: сначала, выполняя SELECT, мы получили разделяемую блокировку на ту же запись (RID 1:17495:1), что и первая транзакция. Затем нам понадобилось туда же записать, а для этого надо сконвертировать коллективную блокировку S до X. Однако сделать это не получается, так как мешает S-блокировка на ту же запись от первой транзакции. Что мы и видим в третьей снизу строчке, статус эксклюзивной блокировки (X) CNVT – конвертирование. То есть SELECT выполнился, но до UPDATE дело не дошло, T2 ждет, пока T1 освободит запись X=2, чтобы наложить эксклюзивную блокировку.

Переключимся обратно в первое окно и попытаемся завершить T1:

Теперь и T1 будет ждать, пока T2 освободит свою коллективную блокировку. Таким образом, транзакции будут ожидать друг друга, цикл в графе ожидания замкнется и, некоторое время спустя, когда менеджер блокировок это обнаружит, одна из транзакций будет отменена. Приложение, запустившееее, получитсообщение 1205 овзаимоблокировке (Transaction (Process ID 61) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction), а другая транзакция завершится успешно.

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

Способы устранения

Поскольку взаимоблокировка произошла из-за того, что транзакции удерживали коллективные блокировки и потом попытались их повысить до эксклюзивных, то, в принципе, помочь избежать неприятностей в данном случае сможет понижение уровня изоляции до READ COMMITED. При этом коллективная блокировка не будет держаться до конца транзакции, а снимется сразу после завершения чтения, а значит, обновить записи ничто не помешает. Но тогда вместо взаимоблокировки мы вполне можем получить неверные данные, так как между SELECT и UPDATE сможет втиснуться другая транзакция, которая изменит Y и данные, полученные SELECT’ на момент UPDATE, окажутся неактуальными, чего в некоторых случаях допускать нельзя.

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

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

Третий пример

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

Подготовим две транзакции в разных окнах QA и, соответственно, в разных подключениях.

Первая транзакция: T1

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

Вторая транзакция: T2

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

Запустив T1, а затем, переключившись и запустив T2, мы получим взаимоблокировку. Обратите внимание, что на первый взгляд транзакции вполне безобидны. Более того, условия никак не пересекаются по диапазонам, в первом случае затрагиваются строки X = 4 и X = 6, а во втором X = 2. Можно пойти еще дальше, и изменить в T2 условие таким образом:

Тогда условия выборки не будет пересекаться даже по полям! Но взаимоблокировка все равно произойдет.

Как уже упоминалось выше, в реальной ситуации найти виновные транзакции бывает достаточно проблематично, так как по умолчанию известен только процесс, запустивший транзакцию-«жертву» и, как правило, этого недостаточно.

Определение «виновных» транзакций

Существует возможность заставить сервер выдать более полную информацию об ошибке. Однако не следует этой возможностью злоупотреблять, так как производительность сервера при этом серьезно понижается. Для более тонкой настройки сервер поддерживает флаги трассировки (trace flags). Некоторые из этих флагов предназначены для получения более полной информации об ошибках. Флаги устанавливаются с помощью команды DBCC TRACEON (flag,…), а снимаются, соответственно с помощью DBCC TRACEOFF (flag,…).

Вот краткий перечень флагов, которые могут пригодиться при отлове взаимоблокировок:

1204 – сбор расширенной информации о взаимоблокировке.

3605 – выдача информации в EventLog.

3406 – выдача информации в файл errorlog.

-1 – сбор информации изо всех сессий.

1206 – сбор информации не только о блокировках, участвующих во тупиковой ситуации (что делает флаг 1204), но и об остальных блокировках, наложенных заблокированными транзакциями.

1200 – сбор информации о порядке наложения блокировок (недокументированный).

Сейчас нас интересует флаг под номером 1204 – выдача расширенной информации о взаимоблокировке, получить же информацию при выставленном флаге можно двумя способами.

Запустить SQL Profiler, специальную программу для отслеживания работы сервера, и настроить в ней перехват ошибок (event class Errors and Warnings: Exception and Error Log), а затем выставить флаг трассировки 3605. В этом случае вся дополнительная информация о работе SQL-сервера будет сбрасываться в Event Log и перехватываться профайлером, где ее в последствии можно будет посмотреть.

Выставить флаг отладки 3406. В этом случае вся дополнительная информация будет сбрасываться в файл errorlog, который по умолчанию находится в каталоге LOG директории SQL сервера.

Итак, сначала установим флаги в одном из окон QA, выполнив следующую команду:

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

Здесь представлена информация о замкнутом цикле в графе ожидания, в цикл входят 2 узла (Node:1 и Node:2). Информация об узлах следующая: транзакции T2 (Node:1) нужна строка RID 7:1:50:1 для изменения (Requested By:\Mode U), владеет этой транзакцией процесс с идентификатором 51 (Requested By:\SPID:51). Однако на эту строку уже наложена эксклюзивная блокировка (Grant List:\Mode: X) процессом с идентификатором 53 (Grant List:\SPID: 53). Сама блокировка нужна, чтобы выполнить оператор UPDATE (Statement Type: UPDATE). Далее идет текст пакета, в котором блокировка была запрошена. Точно так же описан и второй узел графа, только там нужна строка RID 7:1:50:3, которой владеет транзакция, уже описанная в первом узле.

Отсюда становится понятно, за какие ресурсы передрались эти транзакции. Но зачем при выполнении оператора UPDATE транзакции T1 потребовалась строка, которой уже владеет T2 (как было уже замечено, по условиям они не пересекаются), пока не ясно. И при этом непонятно, почему T2 удерживала блокировку – ведь по идее она должна была отработать и зафиксироваться, или откатиться, но блокировку снять. Поскольку других транзакций в это время не работало, значит, виновата та же T1.

Анализ ситуации

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

Запустим первую часть T1 (до WAITFOR), предварительно выставив флаг трассировки, и посмотрим, что за блокировки и в каком порядке накладываются.

Получим примерно следующую картину, с точностью до констант:

Сначала сервер накладывает эксклюзивную блокировку намерения IX на таблицу Tbl (TAB 6:2034106287), поскольку в эту таблицу собирается записывать. Далее накладывается блокировка намерения обновления IU на первую страницу в таблице (PAG 6:1:17495). Поскольку в этой таблице нет индекса, то, чтобы найти нужную запись, необходимо прочитать по очереди все записи, входящие в таблицу, а чтобы прочитать запись, ее надо предварительно заблокировать, что мы и наблюдаем.

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

Как только находится нужная запись, блокировка на страницу конвертируется в IX:

затем блокировка на запись конвертируется в X:

и производится изменение записи. Блокировка этой записи, естественно, до конца транзакции не снимается.

Поскольку сервер не знает, что он уже выбрал все записи, удовлетворяющие условию, то он продолжает перебирать по очереди все, что осталось, накладывая и снимая соответствующую блокировку на каждую запись. Если после выполнения этой части транзакции посмотреть на наложенные блокировки, то мы увидим эксклюзивную блокировку записи x = 4 (RID 1:17495:3) и эксклюзивные блокировки намерения выше по иерархии, на страницу и таблицу:

Как и следовало ожидать, больше подходящих записей не нашлось, ничего не обновилось, а значит, других блокировок удерживать не надо.

Теперь переключимся во второе окно и выполним T2, также с выставленным флагом отслеживания порядка наложения блокировок:

Затем переключимся обратно в первое окно и завершим выполнение первой транзакции:

После этого произойдет мертвая блокировка, о чем сервер нам и сообщит.

Переключимся опять в окно с T2 (надеюсь, эти скачки не слишком утомительны) и посмотрим, каков был порядок наложения блокировок в T2:

Начало такое же, как и в T1, что, в общем, закономерно: IX – на таблицу, IU – на страницу. Затем U на первую запись, чтобы затем прочитать и выяснить, подходит она нам или нет. Если не подходит, снимаем блокировку и переходим к следующей записи.

Следующая запись подходит, и начинается тот же процесс, что и в первом запросе T1. Конвертируем блокировку на страницу в IX, на запись – в эксклюзивную (X), и производим обновление. Эта блокировка, как и в T1, не снимается. Опять же, поскольку сервер не знает, что он выбрал все записи, удовлетворяющие условию, указанному в WHERE, то он продолжает перебирать оставшиеся записи по очереди. Вот тут и начинаются отличия: Запись X = 4 (RID 6:1:17495:3) удерживается эксклюзивной блокировкой (X), наложенной T1, ведь T1 мы не зафиксировали. И как только T2 доберется до этой записи, то она будет вынуждена ждать на блокировке до тех пор, пока T1 не отменится или не зафиксируется, так как U и X блокировки не совместимы, что мы и наблюдаем:

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

Теперь переключимся в первое окно к T1 и посмотрим, что происходило после старта второй части этой транзакции:

Запрашивается IU на страницу и U на первую запись, все для того же самого – чтобы убедиться, подходит запись или нет. Первая запись не подходит, и блокировка снимается. А вторая запись уже эксклюзивно заблокирована транзакцией T2, которая успела влезть между двумя Update'ами. Вот тут-то и происходит взаимоблокировка.

Рисунок 2. Взаимоблокировка из-за многократного перебора записей.

Без излишних подробностей можно описать происходящее примерно так:

T1 перебирает все записи по очереди, сначала блокируя их (U), убеждается, что запись не нужна и снимает блокировку, до тех пор пока не найдет нужную (x = 4), после чего, поднимает блокировку до X и производит запись. И, что важно, эта блокировка уже не снимается, а висит до конца транзакции.

T2 делает тоже самое. Она начинает перебирать записи, ставя и снимая блокировки, пока не находит нужную (x = 2). После этого она выполняет те же самые действия, что и первая транзакция - конвертацию блокировки в X, а затем запись. Опять-таки, эта блокировка (X) (и только эта) удерживается до фиксации или отмены T2. После этого перебор записей продолжается, так как не известно, все ли подходящие записи выбраны. Рано или поздно T2 натыкается на запись, уже заблокированную T1 (x=4), и вынуждена ждать либо фиксации, либо отмены T1.

Стартует второй оператор T1, со своим перебором, и натыкается на запись, уже заблокированную эксклюзивно (X) транзакцией T2 (x = 2).

Таким образом, T1 ждет T2, которая ждет T1 – взаимоблокировка.

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

Убедиться в этом можно, поменяв UPDATE в T2 таким образом:

и запустив заново скрипты. Перебирая записи по очереди, T2 раньше доберется до x=4, чем до x=10, и не сможет заблокировать x=10, а будет ждать, пока освободится x=4.

С другой стороны, если и T1 и T2 нашли нужную запись и успешно сконвертировали блокировку, то, что найдет раньше второй оператор в T1, уже значения не имеет. Он все равно вынужден перебрать все записи, и рано или поздно вынужден будет ожидать T2, которая уже ждет T1.

Способы устранения

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

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

С помощью специальной подсказки (hint) указать оптимизатору, что при обновлении записи блокировка должна производиться не по записям, а потаблично. Эффект будет тем же самым, что и при повышении уровня изоляции до SERIALIZABLE. T1 при первом же обращении заблокирует всю таблицу и будет удерживать блокировку до фиксации или отмены, а T2 не сможет захватить ни одну запись до тех пор, пока не отработает T1.

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

Очевидно, что третий вариант в подавляющем большинстве случаев предпочтительнее с точки зрения производительности.

Распределенная взаимоблокировка

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

1. Часть графа ожидания находится в клиентском приложении. Предположим, что группе клиентских потоков необходимо синхронизировать доступ к какому-либо ресурсу помимо СУБД. Один поток может захватить клиентский объект и ожидать снятия блокировки в БД. В это время другой поток, захвативший объект БД, необходимый первому потоку, может ожидать, пока первый поток освободит клиентский объект. Главная неприятность подобной взаимоблокировки в том, что она в принципе не детектируется, и приложение повисает намертво, если время ожидания блокировки не выставлено в разумных пределах. Можно порекомендовать следующие методы борьбы:

Использовать одно подключение к базе для всех потоков. В этом случае потоки на сервере не будут блокировать друг друга.

Microsoft SQL Server поддерживает механизм «связанных подключений» (BoundConnections), когда несколько подключений на клиенте «связываются» вместе и воспринимаются сервером как одно подключение. Эффект тот же самый, что и в предыдущем случае – потоки не блокируют друг друга при доступе к объектам СУБД.

Для синхронизации доступа к клиентскому объекту использовать механизм блокировок сервера. Некоторые серверы, в том числе и Microsoft SQL Server, имеют возможность предоставить свой менеджер блокировок для нужд внешних приложений. В этом случае весь граф ожидания находится на сервере, и определить взаимоблокировку не составляет никакого труда.

2. Часть графа ожидания находится на другом сервере баз данных. Тут, как ни странно, все еще сложнее. Для начала можно вспомнить, что не все серверы используют блокировки для синхронизации доступа. Тем не менее, даже если все участники транзакции – серверы, использующие блокировки, но разных производителей, все равно не обойтись без стандартного представления графа ожидания, который понимали бы все СУБД. Такового на данный момент не существует. И, наконец, даже если речь идёт только об одном сервере, то объём информации о графах ожидания, который нужно передавать по сети, может быть довольно значительным, хотя теоретически, в этом случае обнаружить взаимоблокировку можно. Можно было бы также построить механизм борьбы с распределенными взаимоблокировками на основе временных меток. Тогда объем информации, необходимый для предотвращения взаимоблокировки, был бы значительно меньше, но в случае большого числа откатов этот способ малоприменим. На данный момент Microsoft SQL Server не поддерживает определение распределенных взаимоблокировок между различными серверами.

Общие рекомендации

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

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

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

Очень часто в различных performance tips рекомендуют везде, где только можно, устанавливать уровень изоляции в READ UNCOMMITED. Я бы хотел предостеречь от этого шага. Вероятность мертвой блокировки при использовании этого уровня изоляции, конечно, понизится, но риск привести базу в несогласованное состояние при этом возрастает многократно. Бороться с последствиями этого эффекта гораздо сложнее, чем с последствиями возникновения взаимоблокировки. В подавляющем большинстве случаев можно найти выход из ситуации, не используя этот уровень изоляции. Как правило, необходимость его использования является следствием ошибок проектирования.

Довольно часто рекомендуется использовать наиболее низкий уровень изоляции. По сути своей совет правильный, так как при этом уменьшается число ожидающих на блокировках транзакций, уменьшается время удерживания блокировок и, как следствие, уменьшается вероятность того, что различные транзакции схлестнутся в борьбе за ресурсы. Но, как было показано в предыдущем примере, возможны и исключения. Там взаимоблокировка произойдет при уровнях изоляции READ COMMITED и REPEATABLE READ, а при уровне изоляции SERIALIZABLE ее уже не случится. То же самое относится и к рекомендации блокировать как можно меньший объем. В большинстве случаев это действительно помогает, по тем же самым причинам: потенциально опасные транзакции с меньшей вероятностью захватят общие ресурсы, но опять-таки возможны исключения.

Вообще же тут все зависит от конкретной ситуации. Для поиска причин необходимо анализировать errorlog и данные Profler’а, смотреть, на каких ресурсах произошла взаимоблокировка, какие операции «передрались» между собой. Даже если истинная причина не будет найдена, или из-за какой-либо особенности приложения полностью устранить подобную ситуацию будет невозможно, тщательный анализ поможет найти способ существенно снизить возможность возникновения взаимоблокировки. Исходить нужно из того, что любая взаимоблокировка не является таинственным природным феноменом, а имеет свою причину. Эту причину необходимо найти и попробовать устранить. И только если окажется, что причина непонятна, трудно устранима или взаимоблокировка случается крайне редко, можно рассматривать повторное выполнение отмененной транзакции как окончательный вариант.

Список литературы

[1] Системы Баз Данных, полный курс. Г. Гарсиа-Молино, Дж. Ульман, Дж. Уидом.

[2] Concurrency control and recovery in database systems. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman.

[3] Введение в системы баз данных. К. Дж. Дейт

[4] Inside Microsoft SQL Server 2000. Kalen Delaney

[5] Microsoft Books OnLine (Документацияк Microsoft SQL Server)

[6] Форумы на RSDN.RU и группа конференций FIDO su.dbms.*