45888 (Deadlocks), страница 2
Описание файла
Документ из архива "Deadlocks", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "45888"
Текст 2 страницы из документа "45888"
Понятно, что доводить до бесконечного ожидания не стоит, и, как правило, в СУБД, в той или иной степени подверженной взаимоблокировкам, присутствуют механизмы определения подобных тупиковых ситуаций и их устранения.
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 используется механизм устранения взаимоблокировок на основе графа ожидания. Граф строится при каждом запросе блокировки. По истечении некоего тайм-аута просыпается монитор блокировок, и если он обнаруживает, что какая-то транзакция ждет слишком долго, инициируется процесс нахождения замкнутого цикла в графе ожидания. В случае обнаружения мертвой блокировки происходит откат одной из транзакций, участвующих в цикле. «Жертва» вычисляется в зависимости от объема проделанной работы, которая в свою очередь определяется по количеству записей в журнале транзакций, которые необходимо откатить. Однако есть возможность указать серверу, какую транзакцию предпочтительнее видеть в качестве «жертвы», с помощью команды:
| SET DEADLOCK_PRIORITY { LOW | NORMAL | @deadlock_var } |
Здесь @deadlock_var – переменная в диапазоне от 1 до 12, чем меньше число, тем ниже приоритет; LOW соответствует 3, а NORMAL – 6.
Но как бы сервер не старался, все, что он сможет сделать по своей инициативе – это отменить одну из транзакций. Самостоятельно Microsoft SQL Server отмененную транзакцию заново не запускает, а возвращает сообщение об ошибке. Поэтому в клиентском приложении необходимо предусмотреть обработку данной ситуации и, возможно, перезапуск отмененной транзакции. Однако по ряду причин целиком полагаться на обработку подобных ошибок в приложении не следует, это последний рубеж обороны по защите нервов конечного пользователя. Недостатки от перекладывания всей ответственности на клиента в данном случае таковы:
Возрастает нагрузка на журнал транзакций, так как каждая неудачная попытка тоже будет приводить к записи в журнале, включая запись об откате. Для интенсивно работающей системы это может быть критично, ввиду того, что самым узким местом в таких случаях часто оказывается именно журнал транзакций.
Монитор, отслеживающий замкнутые циклы в графе ожидания, не работает непрерывно, таким образом, взаимоблокировка не обнаруживается мгновенно. Это снижает производительность системы в целом из-за того, что ни в чем неповинные транзакции вынуждены ждать, пока менеджер не отменит одну из намертво заблокированных.
Подобное решение в общем случае отвратительно масштабируется, так как исходная причина не устранена, и с увеличением нагрузки число взаимоблокировок будет возрастать, причем не линейно. А следовательно, будет расти и количество ожидающих транзакций, что в итоге может привести к полной неработоспособности системы.
Возможные причины возникновения взаимоблокировок
В свете всего вышеописанного почетной обязанностью разработчика является сведение вероятности мертвой блокировки к минимуму, а в идеале – к нулю, что является достаточно сложной, но вполне разрешимой задачей.
Строго говоря, все случаи взаимоблокировки сводятся к нарушению порядка доступа к объектам. Далее разберем несколько примеров транзакций, потенциально способных привести к тупиковой ситуации. Но перед этим, чтобы примеры были более наглядными, надо выбрать базу для экспериментов (например стандартную Northwind) и создать в ней табличку для дальнейших опытов. Для этого достаточно выполнить в Query Analyzer’е вот такой скрипт:
| --- Выбор тестовой базы USE Northwind GO --- Создание таблицы if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[Tbl]') and OBJECTPROPERTY(id, N'IsUserTable') = 1) drop table [dbo].[Tbl] GO CREATE TABLE [dbo].[Tbl] ( [X] [int] NULL, [Y] [int] NULL, [value] [varchar] (50)) GO --- Заполнение тестовыми данными insert into Tbl(X, Y, Value) VALUES (1, 10, 'Алма-Ата') insert into Tbl(X, Y, Value) VALUES (2, 9, 'Алушта') insert into Tbl(X, Y, Value) VALUES (3, 8, 'Алупка') insert into Tbl(X, Y, Value) VALUES (4, 7, 'Анкара') insert into Tbl(X, Y, Value) VALUES (5, 6, 'Агра') insert into Tbl(X, Y, Value) VALUES (6, 5, 'Анапа') insert into Tbl(X, Y, Value) VALUES (7, 4, 'Альбукерке') insert into Tbl(X, Y, Value) VALUES (8, 3, 'Алансон') insert into Tbl(X, Y, Value) VALUES (9, 2, 'Авиньен') insert into Tbl(X, Y, Value) VALUES (10, 1, 'Абакан') |
Первый пример
Самый тривиальный случай, нарушение порядка доступа в чистом виде, представляют собой две транзакции примерно следующего содержания:
Первая транзакция - T1.
| BEGIN TRAN UPDATE Tbl SET X = 1 WHERE X = 1 UPDATE Tbl SET X = 3 WHERE X = 3 COMMIT TRAN |
Вторая транзакция - T2.
| BEGIN TRAN UPDATE Tbl SET X = 3 WHERE X = 3 UPDATE Tbl SET X = 1 WHERE X = 1 COMMIT TRAN |
Если эти транзакции стартуют одновременно, то произойдет взаимоблокировка по причине очевидного нарушения порядка доступа. 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 и он становится цикличным. Ну а поскольку подобная ситуация без грубого вмешательства неразрешима, то одна из транзакций будет отменена, другая же, пользуясь тем, что блокировка исчезла, спокойно завершит свою работу.
Способы лечения здесь также очевидны, достаточно просто поменять порядок операторов в одной из транзакций. В общем случае необходимо добиться того, чтобы все транзакции обращались к объектам в одном и том же порядке.
Второй пример
Следующие примеры я постараюсь разобрать более подробно, эмулируя поведение сервера в реальной ситуации.
Очень часто встречается примерно такая последовательность операторов в одной транзакции:
| SET TRANSACTION ISOLATION LEVEL REPEATABLE READ BEGIN TRAN SELECT @Var = Y FROM Tbl WHERE X = 2 --- --- здесь выполняются какие-нибудь вычисления над @Var. --- UPDATE Tbl SET Y = @Var WHERE X = 2 COMMIT TRAN |
Если два экземпляра такой транзакции запустить одновременно из двух разных потоков, то с очень большой вероятностью все закончится взаимоблокировкой.
Выполним вышеприведенный T-SQL-код из транзакций T1 и T2. Чтобы имитировать возможное развитие событий при параллельной работе будем выполнять транзакции по частям. Сначала половину T1, затем целиком T2, а потом оставшуюся часть T1. Эффект будет точно таким же, как если бы в реальном приложении между двумя операторами T1 успела бы пролезть транзакция T2. На самом деле для получения взаимоблокировки достаточно, чтобы между двумя операторами T1 успел втиснуться только первый оператор T2, дальнейший порядок операций уже не важен.
Итак, выполним первую часть T1 в одном из окон Query Analyser’а:
| --- установим необходимый уровень изоляции SET ISOLATION LEVEL REPEATABLE READ BEGIN TRANSACTION SELECT * FROM Tbl WHERE X = 2 |
Все выполнилось успешно, но транзакция все еще считается активной, мы ее не отменили и не зафиксировали. Если в этот момент посмотреть на блокировки, наложенные на таблицу Tbl, можно увидеть примерно следующую картину, с точностью до констант:
| spid dbid ObjId ObjName IndId Type Resource Mode Status ------ ------ ---------- ------- ----- ---- --------- ----- ------ 54 6 2034106287 Tbl 0 PAG 1:17495 IS GRANT 54 6 2034106287 Tbl 0 RID 1:17495:1 S GRANT 54 6 2034106287 Tbl 0 TAB IS GRANT |
Иными словами, мы наложили коллективную блокировку (S) на конкретную запись (RID 1:17495:1), и две коллективные блокировки намерения (IS) выше по иерархии, на страницу и таблицу. Откроем новое соединение с той же базой в новом окне QA и попытаемся выполнить эту же транзакцию целиком:
| --- установим необходимый уровень изоляции SET ISOLATION LEVEL REPEATABLE READ BEGIN TRAN SELECT * FROM Tbl WHERE X = 2 UPDATE Tbl SET Y = 3 WHERE X = 2 COMMIT TRAN |
Блокировок, естественно, добавилось:
| spid dbid ObjId ObjName IndId Type Resource Mode Status ------ ------ ----------- ------- ------ ---- ---------- ----- ------- 54 6 2034106287 Tbl 0 PAG 1:17495 IS GRANT 54 6 2034106287 Tbl 0 RID 1:17495:1 S GRANT 54 6 2034106287 Tbl 0 TAB IS GRANT 61 6 2034106287 Tbl 0 PAG 1:17495 IX GRANT 61 6 2034106287 Tbl 0 RID 1:17495:1 X CNVT 61 6 2034106287 Tbl 0 TAB IX GRANT |
Те, что (в моем случае) от spid 54 – это наложенные ранее, от первой транзакции, а те, у которых spid 61 - от второй. С блокировками намерения все то же самое, они запрошены и успешно получены. А вот с эксклюзивными ситуация такая: сначала, выполняя SELECT, мы получили разделяемую блокировку на ту же запись (RID 1:17495:1), что и первая транзакция. Затем нам понадобилось туда же записать, а для этого надо сконвертировать коллективную блокировку S до X. Однако сделать это не получается, так как мешает S-блокировка на ту же запись от первой транзакции. Что мы и видим в третьей снизу строчке, статус эксклюзивной блокировки (X) CNVT – конвертирование. То есть SELECT выполнился, но до UPDATE дело не дошло, T2 ждет, пока T1 освободит запись X=2, чтобы наложить эксклюзивную блокировку.
