[ «Boston • San Francisco • New York London • Toronto • Sydney • Tokyo • Singapore • Madrid Mexico City • Munich • Paris • Cape Town • Hong Kong • Montreal Введение в системы баз данных К. Дж. Дейт Москва • Санкт-Петербург ...»
Рис. 16.13. Матрица совместимости, расширенная с учетом намеченных блокировок Ниже приведена более точная формулировка определения протокола намеченной блокировки.
1. Прежде чем любая конкретная транзакция сможет приобрести блокировку S на указанном кортеже, она должна вначале приобрести блокировку IS или более сильную блокировку (как описано ниже) на переменную отношения, содержащую этот кортеж.
2. Прежде чем любая конкретная транзакция сможет приобрести блокировку X на указанном кортеже, она должна вначале приобрести блокировку IX или более сильную блокировку (как описано ниже) на переменную отношения, содержащую этот кортеж.
(Но следует отметить, что это — еще не полное определение. См. аннотацию к [16.10].) Термин сильная блокировка, применяемый в приведенном выше определении протокола, который полностью формулируется как относительно более сильная блокировка, можно объяснить следующим образом. Рассмотрим граф предшествования, приведенный на рис. 16.14. Принято считать, что блокировка типа L2 сильнее (т.е. находится выше в этом графе), чем блокировка типа L1 тогда и только тогда, когда при наличии обозначения "N" (конфликт) в столбце блокировки L1 в матрице совместимости для заданной строки имеется также обозначение "N" в столбце блокировки L2 для той же строки (см.
рис. 16.13). Следует отметить, что запрос на блокировку, оканчивающейся неудачей при использовании блокировки определенного типа, безусловно, также окончится неудачей при запросе блокировки более сильного типа (и из этого факта следует, что всегда безопасно использовать блокировки такого типа, который является более сильным по сравнению со строго необходимым). Заслуживает также внимания то, что ни блокировка S, ни блокировка IX не являются более сильными по сравнению с другими.
Рис. 16.14. Граф предшествования типов блокировок Необходимо также указать, что на практике блокировки переменных отношения, приобретаемые с помощью протокола намеченной блокировки, обычно приобретаются неявно. Например, если речь идет о транзакциях, предусматривающих только чтение, то система по всей вероятности должна неявно приобретать блокировки IS на всех переменных отношения, к которым получают доступ эти транзакции. А если речь идет о транзакциях обновления, то система вместо этого должна, по-видимому, приобретать блокировки IX. Но в системе, вероятно, должен быть предусмотрен явно заданный оператор LOCK определенного типа для того, чтобы была возможность приобретать в транзакциях 624 Часть IV. Управление транзакциями блокировки S, X или SIX на уровне переменной отношения, если они потребуются.
В частности, такой оператор поддерживается в СУБД DB2 (только для блокировок S и X, а не для блокировок SIX).
В завершение этого раздела отметим, что во многих системах предусмотрена возможность эскалации блокировок. Это средство представляет собой попытку достичь равновесия между конфликтующими требованиями повышения степени распараллеливания и снижения издержек на управление блокировками. Основная его идея состоит в том, что после достижения некоторого заранее заданного порогового значения система автоматически заменяет коллекцию блокировок с тонкой степенью детализации единственной блокировкой с более грубой детализацией, например, путем оценки мощности множества отдельных блокировок S уровня кортежа и преобразования в блокировку S той блокировки IS, которая установлена на переменной отношения, содержащей отдельных кортежи с блокировками S. Создается впечатление, что этот метод достаточно хорошо проявляет себя на практике [16.9].
16.10. КРИТИКА ПОДХОДА, ОСНОВАННОГО НА ИСПОЛЬЗОВАНИИ СВОЙСТВ ACID
Вначале напомним, что ACID — это сокращенное обозначение таких свойств транзакций, как неразрывность, правильность, изолированность и устойчивость (atomicitycorrectness-isolation-durability). Ниже эти свойства кратко описаны повторно.
Неразрывность. Любая конкретная транзакция действует по принципу "все или ничего".
Правильность (обычно именуемое в литературе как совместимость — consistency).
Любая конкретная транзакция преобразует правильное состояние базы данных в другое правильное состояние, притом что сохранение свойства правильности на всех промежуточных этапах этого преобразования не является обязательным.
Изолированность. Любые обновления, внесенные конкретной транзакцией, оста ются скрытыми от всех других транзакций до тех пор, пока не произойдет фикса ция данной транзакции.
Устойчивость. После фиксации любой конкретной транзакции внесенные ею об новления остаются в базе данных, даже если впоследствии произойдет аварийный останов системы.
Итак, на первый взгляд за сокращением ACID стоят весьма желаемые свойства, но так ли действительно выглядят представляемые ими понятия при более внимательном исследовании? В данном разделе приведены некоторые свидетельства, которые показывают, что в общем ответ на этот вопрос является отрицательным.
Немедленная проверка ограничений Начнем с того, что может показаться отступлением от основной темы, — с обоснования нашей позиции, впервые явно сформулированной в главе 9, о том, что все ограничения целостности должны проверяться немедленно (т.е. по окончании выполнения оператора), а не откладываться до конца транзакции. В основе этой позиции лежат по меньшей мере четыре причины, которые описаны ниже.
1. Как известно, любая база данных может рассматриваться как коллекция высказы ваний (которые в соответствии с принятым соглашением считаются истинными).
А если есть хоть какая-то вероятность, что эта коллекция будет включать любые несогласованные, противоречивые высказывания, то все эти предположения ста новятся бессмысленными. Мы не должны ни в коем случае доверять ответам, по лученным из противоречивой базы данных; фактически из подобной базы данных можно вообще получить абсолютно любой ответ (доказательство этого факта дано в аннотации к [9.16] в главе 9). Хотя свойство изолированности (или кратко свой ство "i" — isolation) транзакций может означать, что с любой конкретной несогла сованностью может столкнуться не больше чем одна транзакция, неоспоримым фактом остается то, что все равно с этой несогласованностью столкнется данная конкретная транзакция, поэтому может выработать неправильные ответы. Имен но поэтому прежде всего необходимо ввести в действие ограничения — не по той причине, что путем изоляции следует исключить возможность обнаруживать эти несогласованности больше чем в одной транзакции одновременно, а потому, что с несогласованностями вообще нельзя смириться.
2. Так или иначе, нельзя гарантировать, что любая конкретная несогласованность (при условии, что допускается их наличие в базе данных) будет обнаружена только одной транзакцией. Подлинной гарантией того, что транзакции остаются изоли рованными друг от друга, может стать только соблюдение в них определенных протоколов, причем эти протоколы не должны вводиться принудительно (а в дей ствительности их невозможно ввести принудительно). Например, если транзакция А обнаруживает противоречивое состояние базы данных и поэтому записывает не согласованные данные в некоторый файл F, после чего транзакция в считывает ту же информацию из файла F, то А и в фактически не являются изолированными друг от друга (независимо от того, выполняются ли они параллельно или в любом другом режиме)8. Иными словами, свойство "I" транзакций находится под сомне нием, если не сказать большего.
3. В предыдущем издании данной книги было указано, что ограничения переменной отношения проверяются немедленно, а ограничения базы данных проверяются в конце транзакции (с этой позицией соглашаются многие авторы, хотя они обычно используют другую терминологию). Но из принципа взаимозаменяемости (базовых и производных переменных отношения — см. главу 9) следует, что одно и то же практическое ограничение может стать ограничением переменной отноше ния в одном проекте базы данных и ограничением базы данных — в другом! По скольку вполне очевидно, что ограничения переменной отношения должны про веряться немедленно, из этого следует, что и ограничения базы данных также должны проверяться немедленно.
В действительности, эта проблема возникает, даже если транзакция А не обнаруживает несогласованного состояния базы данных; все еще остается возможность того, что транзакция А сама записала несогласованные данные в определенный файл, который впоследствии считывается транзакцией В.
626 Часть IV. Управление транзакциями 4. Для обеспечения возможности выполнять семантическую оптимизацию требуется, чтобы база данных была согласованной постоянно, а не только на границах транзакций.
Примечание. Семантическая оптимизация — это метод использования ограничений целостности для упрощения запросов в целях повышения производительности.
Очевидно, что если ограничения не удовлетворяются, то и результаты упрощений будут неправильными. Дополнительная информация по этой теме приведена в Безусловно, здравый смысл подсказывает, что проверку ограничений базы данных почти наверняка приходится откладывать на более позднее время. В качестве простейшего примера предположим, что на базу данных поставщиков и деталей распространяется ограничение "Поставщик si и деталь Р1 находятся в одном том же городе". Если поставщик S1 переезжает, скажем, из Лондона в Париж, то деталь Р1 также необходимо перевезти из Лондона в Париж. Обычно применяемое решение этой проблемы состоит в том, что оба обновления заключаются в одну транзакцию, как показано ниже.
BEGIN TRANSACTION ;
'Paris' } ;COMMIT ;
В этом обычном решении указанное ограничение проверяется при выполнении оператора COMMIT, а база данных на этапе между двумя операциями UPDATE остается несогласованной. В частности, следует отметить, что если бы в этой транзакции, где выполняются операторы UPDATE, был задан вопрос "Находятся ли поставщик S1 и деталь Р1 в одном и том же городе?" на этапе между выполнением этих двух операторов UPDATE, TO был бы получен отрицательный ответ.
Однако следует напомнить, что автор настаивает на необходимости поддержки операции множественного присваивания, которая позволяет выполнить сразу несколько присваиваний в виде одной операции (т.е. в одном операторе) без осуществления какойлибо проверки целостности до того, как будут произведены все рассматриваемые присваивания. Напомним также, что операции INSERT, DELETE и UPDATE являются просто сокращенными обозначениями некоторых операций присваивания. Поэтому в данном примере мы должны иметь возможность осуществлять желаемое обновление в одной операции следующим образом.
UPDATE S WHERE S# = S# ('S1') { CITY := 'Paris' }, UPDATE P WHERE P# = P# ('P1') { CITY := 'Paris' } ;
В таком случае никакие проверки целостности не выполняются до завершения обработки обоих операторов UPDATE (т.е., как принято условно обозначать эту ситуацию, "до достижения точки с запятой"). Следует также отметить, что в данном случае исключена вероятность того, что указанная транзакция обнаружит противоречивое состояние базы данных на этапе между выполнением двух операторов UPDATE, поскольку теперь понятие "этап работы между двумя операторами UPDATE" не имеет смысла.
Из этого примера следует, что если бы поддерживалась операция множественного присваивания, то не было бы необходимости осуществлять отложенную проверку в традиционном смысле этого термина (т.е. выполнять ее как проверку, которая отложена до конца транзакции).
Теперь перейдем к анализу свойств ACID как таковых. Но будет проще провести такой анализ, рассматривая данные свойства в последовательности C-I-D-A (Correctness— Integrity-Durability-Atomicity).
Правильность Автор уже изложил свои соображения (в главе 15) относительно того, почему он предпочитает использовать указанный здесь термин правильность вместо более общепринятого термина согласованность. Создается впечатление, что в литературе эти два понятия приравниваются. Например, ниже приведена цитата из глоссария к книге Грея (Gray) и Рейтера (Reuter) [15.12].
Согласованность. Правильность.
Кроме того, в той же книге дано приведенное ниже определение свойства согласованности транзакций.
Согласованность. Транзакция — это правильное преобразование состояния. С этим состоянием связаны действия, объединенные в группу, которые не нарушают какихлибо ограничений целостности. Для этого требуется, чтобы транзакция представляла собой правильную программу [именно так!].
Но если ограничения целостности всегда проверяются немедленно, то база данных всегда является согласованной (но не обязательно правильной!) и транзакции всегда заведомо преобразуют базу данных из одного согласованного состояния в другое согласованное состояние.
Поэтому, если буква С в аббревиатуре ACID обозначает согласованность (consistency), то смысл этого свойства является тривиальным9, а если оно обозначает правильность (correctness), то его нельзя достичь, принудительно вводя какие-либо протоколы (см. п. в подразделе "Немедленная проверка ограничений"). Поэтому, так или иначе, это свойство фактически является бессмысленным, по меньшей мере, с формальной точки зрения. Как уже было сказано, сам автор предпочитает рассматривать букву С как сокращенное обозначение свойства правильности, но тщательный анализ показывает, что так называемое свойство правильности фактически следует считать не свойством как таковым, а всего лишь благим пожеланием.
Изолированность Теперь рассмотрим свойство изолированности. Как уже было указано в данном разделе, в подразделе "Немедленная проверка ограничений", это свойство также является довольно сомнительным. Но, по крайней мере, нельзя отрицать того, что если каждая транзакция действует по такому же принципу, как если бы она была единственной транзакцией в системе, то безукоризненно действующий механизм управления параллельным выполнением гарантирует изолированность (и упорядочиваемость) транзакций. Тем не менее, для того чтобы транзакция могла действовать "как если бы она была единственной В действительности, он был бы тривиальным, даже если бы проверка ограничений не осуществлялась немедленно, поскольку все равно выполнялся бы откат транзакции, а это было бы равносильно тому, что она не выполнялась в случае нарушения какого-либо ограничения. Иными словами, все равно остается в силе такое условие, что транзакции оказывают долговременное воздействие на базу данных, только если они не нарушают никаких ограничений.
628 Часть ГУ. Управление транзакциями транзакцией в системе", она, кроме всего прочего, должна соответствовать перечисленным ниже требованиям.
Не предпринимать попыток (преднамеренных или иных) вступать во взаимодей ствие с другими транзакциями (выполняемыми параллельно или иными).
Не допускать даже возможности влияния того, что в системе могут существовать другие транзакции (задавая уровень изоляции меньше максимального).
Итак, в действительности свойство изолированности также в большей степени напоминает благие пожелания, чем абсолютную гарантию. Более того, в практически применяемых системах обычно предусмотрены явно заданные механизмы (а именно уровни изоляции меньше максимального), действие которых сводится именно к тому, что они нивелируют свойство изолированности.
Устойчивость Теперь рассмотрим свойство устойчивости. Это свойство является достижимым благодаря использованию механизма восстановления системы, при условии, что отсутствует вложенность транзакций. И действительно, до настоящего времени предполагалось, что это требование соблюдается. Но допустим, что поддерживается вложенность транзакций.
А именно: предположим, что транзакция в вложена в транзакцию А и происходит показанная ниже последовательность событий.
BEGIN TRANSACTION (транзакция А) ;
BEGIN TRANSACTION(транзакция В) ; транзакция В обновляет кортеж t ; COMMIT (транзакция ROLLBACK (транзакция А) ;
Если выполняется оператор ROLLBACK транзакции А, то фактически выполняется также откат транзакции в (поскольку в в действительности входит в состав А). Поэтому воздействие транзакции в на базу данных не является устойчивым; по сути, выполнение оператора ROLLBACK транзакции А вызывает восстановление того значения кортежа t, которое он имел до выполнения транзакции А. Иными словами, соблюдение свойства устойчивости больше нельзя гарантировать, по меньшей мере, для транзакций, подобных транзакции в, рассматриваемой в данном примере, которая вложена в некоторую другую транзакцию.
А теперь отметим, что многие авторы, начиная с Дэвиса (Davies) [15.8], фактически предложили предусмотреть возможность вкладывать транзакции в той форме, которая показана в приведенном выше примере. А в [15.15] утверждается, что такая поддержка желательна по меньшей мере по трем причинам: распараллеливание работы между транзакциями, управление восстановлением с учетом нескольких транзакций и повышение модульности системы. Но, как показывает данный пример, в системе с подобной поддержкой операторы COMMIT, выполненные во внутренней транзакции, фиксируют обновления, внесенные в этой транзакции, но только на следующем, более внешнем уровне. По сути, внешняя транзакция обладает правом вето на выполнение операторов COMMIT внутренними транзакциями, поскольку если внешняя транзакция выполняет откат, происходит также откат и внутренней транзакции. В данном примере оператор COMMIT транзакции в является таковым только для транзакции А, но не для внешнего мира, а фактически этот оператор COMMIT впоследствии отменяется (происходит его откат).
Примечание. Следует отметить, что вложенные транзакции могут рассматриваться как обобщение понятия точек сохранения. Точки сохранения позволяют структурировать транзакции как линейные последовательности действий, выполняемые одна за другой (и откат к началу любого предыдущего действия в данной последовательности может произойти в любое время). В отличие от этого, вложение позволяет структурировать транзакции рекурсивно, как иерархию действий, которые могут выполняться одновременно. Иными словами, являются справедливыми приведенные ниже утверждения.
Оператор BEGIN TRANSACTION расширяется с учетом поддержки субтранзакций (т.е., если оператор BEGIN TRANSACTION вызывается на выполнение, притом что уже функционирует некоторая транзакция, то он запускает дочернюю транзакцию).
Оператор COMMIT осуществляет фиксацию, но только в области определения роди тельской транзакции (если транзакция, в которой выполнен этот оператор, явля ется дочерней).
Оператор ROLLBACK отменяет выполненную работу, но только вплоть до начала данной конкретной транзакции (включая сами дочерние транзакции, дочерние транзакции этих дочерних транзакций и т.д., но не включая родительскую тран закцию, если она имеется).
Теперь, вернувшись к главной теме данного обсуждения, можно убедиться в том, что свойство устойчивости транзакций является применимым только на самом внешнем уровне (иными словами, применяется только к транзакциям, не вложенным в другие транзакции)10. Поэтому в общем мы убедились в том, что это свойство также не гарантируется на все 100%.
Неразрывность Наконец, рассмотрим свойство неразрывности. Как и свойство устойчивости, данное свойство гарантируется механизмом восстановления системы (даже во вложенных транзакциях). Наши возражения против использования этого свойства несколько отличаются от приведенных выше возражений. А именно: достаточно просто отметить, что если бы система поддерживала множественное присваивание, то не нужно было бы требовать от транзакций как таковых, чтобы они обладали свойством неразрывности; вместо этого, было бы достаточно требовать это только от операторов. Кроме того, все равно необходимо соблюдать условие, чтобы операторы также обладали свойством неразрывности, по причинам, уже подробно описанным в других стандартах11.
В [15.15] указано, что такое же утверждение является справедливым и по отношению к свойству согласованности, поскольку в этой статье, как и в большей части литературы, посвященной данной теме, предполагается, что самая внешняя транзакция вовсе не обязательно должна обеспечивать согласован ность на промежуточных этапах. Но мы не разделяем эту позицию по уже описанным выше причинам.
Кстати, следует отметить, что свойством неразрывности, в частности, обладают многие операто ры, описанные в стандарте SQL.
630 Часть IV. Управление транзакциями Заключительные замечания Мы можем подытожить этот раздел с помощью приведенных ниже довольно риторических вопросов.
Действительно ли транзакция является единицей работы? Да, но только если не поддерживается множественное присваивание.
Действительно ли она является единицей восстановления ? Тот же ответ.
Действительно ли она является единицей параллельности ?Тот же ответ. Действительно ли она является единицей целостности? Да, но только если не со блюдается требование, что "проверка всех ограничений должна осуществляться немедленно".
Примечание. Приведенные здесь ответы являются таковыми несмотря на многие замечания, сделанные в предыдущих главах (а также в предыдущих изданиях данной книги), которые в большей степени следовали здравому смыслу, накопленному в этой области знаний.
Поэтому в целом наш вывод состоит в том, что понятие транзакции является значимым в большей степени с практической точки зрения, чем с теоретической. Автор просит понять его правильно, что этот вывод не следует рассматривать как стремление перечеркнуть всю работу, сделанную в этой области! У него не вызывают ничего, кроме глубокого уважения, те многочисленные изящные и полезные результаты, которые получены в течение больше чем 25 лет исследований в области управления транзакциями. Он просто отмечает, что теперь мы обладаем гораздо лучшим пониманием некоторых предпосылок, на которых были основаны эти исследования, — в частности, лучшим пониманием важнейшей роли ограничений целостности, а также признанием того, что необходима поддержка множественного присваивания как примитивного оператора.
И действительно, было бы удивительно, если бы смена предпосылок не повлекла за собой пересмотр заключений, сделанных на их основании.
16.11. СРЕДСТВА ЯЗЫКА SQL В стандарте SQL не предусмотрены какие-либо явно заданные средства блокировки;
фактически в нем вообще не упоминается блокировка как таковая12. Но этот стандарт требует, чтобы в его реализации были предусмотрены обычные гарантии, касающиеся взаимного вмешательства (или, скорее, его отсутствия) между одновременно выполняемыми транзакциями. Что еще более важно, в этом стандарте требуется, чтобы обновления, внесенные любой конкретной транзакцией Т1, не становились бы доступными для любой другой транзакции Т2 до тех пор (или только после того), пока не произойдет фиксация транзакции Т1.
Примечание. Для соблюдения изложенных выше требований необходимо, чтобы все транзакции выполнялись на уровне изоляции READ COMMITTED, REPEATABLE READ или SERIALIZABLE (см. следующий абзац). К транзакциям, выполняемым на уровне Это упущение сделано преднамеренно — идея заключается в том, что разработчики системы должны быть вправе использовать любые механизмы управления параллельным выполнением, при условии, что эти механизмы позволяют реализовать желаемые функциональные возможности.
READ UNCOMMITTED, предъявляются особые требования, поскольку им, во-первых, разрешено выполнять грязное чтение, но, во-вторых, они обязательно должны относиться к типу READ ONLY (поскольку если бы было разрешено применять в этом случае транзакции типа READ WRITE, то восстанавливаемость больше нельзя было бы гарантировать).
Теперь напомним, что уровни изолированности SQL определяются в операторе START TRANSACTION (как было сказано в главе 15). Для этого предусмотрены четыре
ВОЗМОЖНОСТИ13— SERIALIZABLE, REPEATABLE READ, READ
COMMITTED И READ UNCOMMITTED. По умолчанию применяется значение SERIALIZABLE; если определена любая из трех других возможностей, то в конкретной реализации разрешено назначать некоторый более высокий уровень, где понятие более высокий определено в терминах упорядочения SERIALIZABLE > REPEATABLE READ >READ COMMITTED > READ UNCOMMITTED.
Если все транзакции выполняются на уровне изоляции SERIALIZABLE (применяемом по умолчанию), то гарантирована упорядочиваемость процедуры чередующегося выполнения любого множества параллельных транзакций. Но если любая транзакция выполняется на более низком уровне изоляции, то нарушение упорядочиваемости может произойти по самым различным причинам. В стандарте определено три вида нарушений: грязное чтение, неповторяемое чтение и фантомы (первые два из них описаны в разделе 16.2, а третий — в разделе 16.8), а различные уровни изоляции определены в терминах нарушений, которые в них допускаются'4.Итоговые сведения об этих нарушениях приведены в табл. 16.1 (здесь "Y" обозначает, что нарушение может возникнуть, a"N" — нет).
Таблица 16.1. Уровни изоляции SQL В завершение этого раздела напомним, что ключевое слово REPEATABLE READ, которое определено в стандарте SQL, и опция повторяемого чтения (Repeatable Read — RR), определенная в СУБД DB2, не являются одинаковыми. В действительности, опция RR В СУБД DB2 аналогична ключевому слову SERIALIZABLE этого стандарта.
16.12. РЕЗЮМЕ В этой главе были описаны способы управления параллельностью. Вначале рассматривались три проблемы, возникающие из-за отсутствия такого управления при чередующемся выполнении параллельных транзакций, а именно: проблема потерянного обновления, В данном случае ключевое слово SERIALIZABLE не совсем подходит, поскольку предполагается, что упорядочиваемыми должны быть графики, а не транзакции. Более подходящим термином был бы просто TWO PHASE, который означает, что транзакция подчиняется (или будет вынуждена подчиняться) протоколу двухфазной блокировки.
Однако см. [16.2] и [16.14].
632 Часть TV. Управление транзакциями проблема зависимости от незафиксированных результатов и проблема анализа несогласованности. Все эти проблемы возникают из-за того, что график запуска не является упорядочиваемым, т.е. он не эквивалентен некоторому последовательному графику запуска этих же транзакций.
Наиболее распространенным методом разрешения указанных проблем является использование механизма блокировки. Существует два основных типа блокировок: разделяемая (блокировка S) и исключительная (блокировка X). Если транзакция устанавливает блокировку S для некоторого объекта, то другие транзакции также смогут установить блокировку S для этого же объекта, однако установить для него блокировку X им не удастся. Если одна транзакция устанавливает блокировку X для некоторого объекта, то никакая другая транзакция не сможет установить для этого объекта никакой другой блокировки. Специальный протокол использования этих блокировок позволяет устранить упомянутую выше проблему потерянного обновления и другие возможные проблемы.
В соответствии с данным протоколом, блокировка S устанавливается для всех считываемых объектов, а блокировка X — для всех обновляемых объектов, причем все установленные блокировки сохраняются до окончания выполнения транзакции. С помощью этого протокола можно обеспечить упорядочиваемость графика выполнения транзакций.
Описанный протокол является строгой формой протокола двухфазной блокировки.
В теореме двухфазной блокировки утверждается, что если выполнение всех транзакций подчиняется этому протоколу, то любой из возможных графиков запуска будет упорядочиваемым. При построении такого графика запуска гарантируется, что если А и в являются двумя транзакциями данного графика, то либо транзакция А получит доступ к результатам выполнения транзакции в, либо транзакция в получит доступ к результатам выполнения транзакции А. К сожалению, применение протокола двухфазной блокировки может привести к возникновению взаимоблокировки, несмотря на то, что этот протокол гарантирует восстанавливаемость транзакций и обеспечивает создание графиков, которые не становятся причиной каскадных откатов. Для устранения взаимоблокировки следует выбрать одну из конфликтующих транзакций в качестве транзакции-жертвы и отменить с выполнением отката всех внесенных ею изменений (в результате чего происходит освобождение всех ее блокировок).
В общем случае нельзя гарантировать безопасность выполнения набора транзакций, если используемый график — не полностью упорядочиваемый. Однако в некоторых системах для повышения производительности и пропускной способности предусмотрена возможность чередующегося выполнения нескольких транзакций с некоторым установленным уровнем изоляции, что на самом деле является не совсем безопасным решением.
В этой главе был описан один такой небезопасный уровень, т.е. уровень стабильности курсора (с применением терминологии, принятой в СУБД DB2, хотя в стандарте языка SQL аналогичный уровень называется READ COMMITTED).
Далее вкратце было рассмотрено понятие степени детализации блокировок и связанная с ним идея намеченной блокировки. Предполагается, что перед установкой транзакцией блокировки определенного типа для некоторого объекта, например для кортежа базы данных, ей следует установить соответствующую намеченную блокировку, по меньшей мере, для родительского объекта (в случае кортежа — для переменной отношения, в которой содержится кортеж). На практике намеченные блокировки обычно устанавливаются неявно таким же образом, как блокировки S и X кортежей. Однако рекомендуется предусмотреть оператор типа LOCK для явной установки (в случае необходимости) блокировок, более сильных, чем те, которые устанавливаются системой неявно (хотя в стандарте SQL такой механизм не предусмотрен).
Затем в этой главе под новым углом зрения были проанализированы так называемые свойства ACID транзакций и сделан вывод, что, вопреки широко распространенному мнению, эти свойства являются не такими уж бесспорными. Наконец, в данной главе были кратко описаны средства управления параллельностью, предусмотренные в языке SQL. В стандарте языка SQL средства явной установки блокировки не предусмотрены вообще, однако в нем поддерживаются различные уровни изоляции (SERIALIZABLE,
REPEATABLE READ, READ COMMITTED, READ UNCOMMITTED),
которые в СУБД обычно реализуются неявно заданными средствами блокировки.
УПРАЖНЕНИЯ
16.1. Дайте определение понятияупорядочиваемости.16.2. Дайте полное определение:
а) протокола двухфазной блокировки; !
б) теоремы двухфазной блокировки.
Подробно опишите, каким образом с помощью двухфазной блокировки разрешаются конфликты RW, WR и WW.
16.3. Пусть даны транзакции Tl, T2 и ТЗ, которые выполняют следующие операции:
Т2 — удвоить значение А;
ТЗ — вывести значение А на экран, а затем поместить в А значение (здесь А — некоторый числовой элемент в базе данных).
а) Допустим, что разрешено параллельное выполнение транзакций Tl, T2 и ТЗ.
Перечислите все возможные результаты их выполнения, если начальное значе б) Допустим, что транзакции Tl, T2 и ТЗ имеют показанную ниже внутреннюю Сколько существует возможных графиков запуска, если эти транзакции выполняются без каких-либо блокировок?
в) Существуют ли какие-либо чередующиеся графики запуска, которые для заданного начального значения А (нуль) приводят к получению правильного результата, но не допускают упорядочения?
634 Часть IV. Управление транзакциями г) Существуют ли какие-либо графики запуска, которые действительно допускают упорядочение, но не могут быть реализованы, если все три транзакции подчиняются протоколу двухфазной блокировки?
16.4. Ниже приведена последовательность выполнения различных событий в графике запуска с транзакциями Т1, Т2,..., Т12 и объектами базы данныхА, в,..., Н.
время tO......
время tl (Tl) : RETRIEVE A ; время t2 (T2) : RETRIEVE... (Tl) : RETRIEVE С ;
... (T4) : RETRIEVE D ;
... (T5) : RETRIEVE A ;
... (T2) : RETRIEVE E ;
... (T2) : UPDATE E ;
... (T3) : RETRIEVE F ;
... (T2) : RETRIEVE F ;
... (T5) : UPDATE A ;
... (Tl) : COMMIT ;
... (T6) : RETRIEVE A ;
... (T5) : ROLLBACK ;
... (T6) : RETRIEVE С ;
... (T6) : UPDATE С ;
... (T7) : RETRIEVE G ;
... (T8) : RETRIEVE H ;
... (T9) : RETRIEVE G ;
... (T9) : UPDATE G ;
... (T8) : RETRIEVE E ;
... (T7) : COMMIT ;
... (T9) : RETRIEVE H ;
... (T3) : RETRIEVE G ;
... (T10) : RETRIEVE A ;
... (T9) : UPDATE H ;
... (T6) : COMMIT ;
... (T12) : RETRIEVE D ;
... (T12) : RETRIEVE С ;
... (T2) : UPDATE F ;
... (T1l) : UPDATE С ;
... (T12) : RETRIEVE A ;
... (T10) : UPDATE A ;
... (T12) : UPDATE D ;
... (T4) : RETRIEVE G ;
время t3 6......
Предположим, что для выполнения оператора RETRIEVE i (считать i) требуется (в случае успеха) установить блокировку S для объекта i, а для выполнения оператора UPDATE i (обновить i) требуется (в случае успеха) установить для объекта i блокировку X. Допустим, что все блокировки сохраняются до конца выполнения транзакции. Начертите граф ожидания (показав на нем, "кто кого ожидает"), который соответствует состоянию дел в момент времени t3 6. Возникнет ли к этому моменту ситуация взаимоблокировки?
16.5. Еще раз обратимся к проблемам параллельности, представленным на рис. 16.1Что произойдет в каждом из этих случаев, если все транзакции будут выпол няться на уровне изоляции стабильность курсора (CS), а не на уровне повторяемое Примечание. Здесь обозначения CS и RR относятся к уровням изоляции DB2, которые описаны в разделе 16.8.
16.6. Дайте формальные и неформальные определения пяти типов блокировок: X, S, IX, 16.7. Сформулируйте понятие относительной силы блокировок и нарисуйте соответст вующую диаграмму их предшествования.
16.8. Сформулируйте определение протокола намеченной блокировки, а также поясни те основное назначение этого протокола.
16.9. В стандарте языка SQL определяются три проблемы параллельности: грязное чте ние, неповторяемое чтение и фантомы. Как они соотносятся с тремя проблемами параллельности, описанными в разделе 16.2?
16.10. Кратко опишите возможный механизм реализации протокола управления парал лельностью на основе поддержки многих версий, который рассматривается в ан
СПИСОК ЛИТЕРАТУРЫ
В этом списке следовало бы также упомянуть работы [15.2], [15.10] и особенно [15.12] из главы 15.16.1. Bayer R., Heller M., Reiser A. Parallelism and Recovery in Database Systems // ACM Как уже говорилось в главе 15, новые прикладные области (например, проектирование и разработка программного и аппаратного обеспечения) часто выдвигают сложные требования к обработке данных, которые нельзя полностью удовлетворить с помощью классических схем управления выполнением транзакций, описанных в этой и предыдущей главах. Основная проблема заключается в том, что сложные транзакции в этих прикладных областях могут продолжаться в течение часов или даже суток вместо нескольких миллисекунд, что типично для большинства традиционных систем обработки данных. Это может привести к перечисленным ниже последствиям.
1. Полный откат транзакции к самому началу может вызвать потерю слишком большого объема уже проделанной работы, что совершенно неприемлемо.
2. Использование обычных блокировок может иметь следствием появление чрез мерных задержек, вызванных ожиданием снятия блокировок требуемых эле ментов, что также неприемлемо.
В этой работе описывается один из методов устранения подобных недостатков (см. также [16.8], [16.12], [16.15] и [16.20]), а именно— метод управления параллельностью, называемый параллельным выполнением с применением многих версий (multi-version locking); он известен также под названием чтения с применением 636 Часть IV. Управление транзакциями многих версий (multi-version read) и уже используется в нескольких коммерческих программных продуктах. Основное преимущество этого метода заключается в том, что операции чтения выполняются без вынужденного ожидания, т.е. любое количество операций чтения и одна операция записи могут выполняться для одного и того же объекта одновременно. Точнее говоря, выполняются приведенные ниже Операция чтения всегда выполняется без задержки (как только что говорилось).
Операции чтения никогда не задерживают выполнение операций обнсвления.
Откат транзакций, выполняющих только чтение, не имеет смысла и никогда не Ситуация взаимной блокировки может возникнуть только между транзакция Указанные преимущества особенно важны для распределенных систем (см. главу 21), в которых на выполнение обновления данных может потребоваться значительное время, поэтому может чрезмерно затянуться выполнение запросов, включающих только операции чтения (и наоборот). Основную идею данного метода можно сформулировать, как описано ниже.
Если транзакция в пытается выполнить операцию чтения объекта, для кото рого в данный момент выполняется обновление в пределах транзакции А, то транзакции в предоставляется доступ к предварительно зафиксированной версии этого объекта. Такая версия обычно хранится в каком-то особом месте систе мы (как правило, в журнале регистрации) и предназначается для восстановле Если транзакция в пытается выполнить операцию обновления объекта, кото рый в данный момент считывается транзакцией А, то транзакции в предостав ляется доступ к этому объекту, тогда как транзакции А предоставляется доступ к некоторой версии этого объекта (которая в действительности является его предыдущей версией).
Если транзакция в пытается выполнить операцию обновления объекта, который в данный момент обновляется транзакцией А, то транзакция в переходит в состояние ожидания15 (таким образом, как отмечалось выше, в системе может возникнуть ситуация взаимоблокировки, для устранения которой потребуется принудительный откат одной из транзакций).
Безусловно, этот метод предусматривает наличие соответствующих средств управления, необходимых для обеспечения того, что каждая транзакция всегда будет "иметь дело" с согласованным состоянием базы данных.
16.2. Berenson H. et al. A Critique of ANSI SQL Isolation Levels // Proc. 1995 ACM SIGMOD Int. Conf. on Management of Data. — San Jose, Calif. — May 1995.
Иначе говоря, конфликты WW все еще могут возникать, и здесь предполагается, что для их устранения используется механизм блокировки. Однако для устранения конфликтов, безусловно, могут использоваться и другие методы, например временные отметки [16.3].
В этой статье критически оценивается предпринятая в стандарте "ANSI SQL" попытка охарактеризовать уровни изоляции на основе нарушений упорядочиваемости (см. раздел 16.11). "[Эти] определения не способны должным образом охарактеризовать несколько широко распространенных уровней изоляции, включая стандартные способы реализации блокировок для упомянутых уровней". В частности, в этой статье подчеркивается, что данный стандарт не способен запретить грязную запись (си. раздел 16.2).
Похоже, что это действительно так, поскольку в данном стандарте грязная запись явно не запрещена. В нем фактически изложены приведенные ниже требования (здесь они немного перефразированы).
"Выполнение параллельных транзакций на уровне изоляции SERIALIZABLE гарантированно является упорядочиваемым". Иначе говоря, если все транзак ции выполняются на уровне изоляции SERIALIZABLE, в реализации требует ся запретить операции грязной записи, поскольку они, безусловно, будут нару шать упорядочиваемость.
"Четыре уровня изоляции гарантируют, что... никакие обновления не будут по теряны". Это утверждение на самом деле является лишь благим пожеланием, поскольку сами определения четырех уровней изоляции не дают подобных га рантий. Однако оно указывает на то, что разработчики стандарта действитель но стремились запретить операции грязной записи.
т "Изменения, выполненные одной транзакцией, не могут быть восприняты другими транзакциями [за исключением транзакций на уровне изоляции READ UNCOMMITTED] до тех пор, пока результаты выполнения первоначальной транзакции не будут зафиксированы". Что в данном контексте означает слово восприняты'! Может ли транзакция обновить часть грязных данных без их восприятия?
См. также [16.14].
16.3. Bernstein P.A., Goodman N. Timestamp-Based Algorithms for Concurrency Control in Distributed Database Systems // Proc. 6th Int. Conf. on Very Large Data Bases. — Montreal, Canada. — October 1980.
В работе рассматриваются некоторые методы управления параллельностью, в основу которых положены не блокировки, а временные отметки. Основная идея заключается в том, что если транзакция А начинает выполняться раньше транзакции в, то система ведет себя так, как будто выполнение транзакции А полностью завершилось еще до начала выполнения транзакции в (как это имеет место в классическом последовательном графике). Из этого следуют приведенные ниже выюды.
1. Для транзакции А не должны быть доступны любые обновления, выполняемые 2. Для транзакции А не должно быть разрешено обновлять объект, уже считанный Эти два требования могут быть выполнены следующим образом. Для каждого запроса к базе данных система сравнивает временную отметку транзакции этого запроса с временной отметкой транзакции, выполнившей последнюю выборку или обновление запрашиваемого кортежа. В случае конфликта транзакция запроса 638 Часть ГУ. Управление транзакциями может быть перезапущена с новой временной отметкой (так же, как и при использовании так называемых оптимистических методов [ 16.16]).
Как следует из заголовка этой работы, данная методика была изначально создана в контексте распределенной системы (где использование блокировки сопряжено с возникновением нежелательных издержек из-за отправки сообщений для проверки и установки блокировок). Однако такая методика почти наверняка не подходит для нераспределенных систем. Кроме того, существует достаточно скептическая оценка практичности ее использования даже для распределенных систем. Одной очевидной проблемой является то, что каждый кортеж должен содержать временную отметку последней транзакции, которая считывала данные этого кортежа (а также временную отметку последней транзакции, которая обновляла данные этого кортежа). В таком случае подразумевается, что каждая операция чтения становится операцией записи! Еще одна проблема состоит в том, что транзакция в не должна иметь доступ к каким-либо обновлениям транзакции А до тех пор, пока в последней не будет выполнена фиксация; из этого следует, что (по сути) на обновления транзакции А накладывается исключительная блокировка до фиксации каких-либо данных. Действительно, в [15.12] утверждается, что такая схема с применением временных отметок на самом деле является вырожденным случаем схем оптимистического метода управления параллельным выполнением [16.16], для которых, в свою очередь, характерны собственные проблемы.
Примечание. Одно из понятий, широко обсуждавшихся в литературе, — правило записи Томаса [16.22] — фактически представляет собой одно из усовершенствований описанной выше схемы; оно основано на той идее, что некоторые операции обновления можно пропустить, поскольку они уже являются устаревшими (запрос на уровне пользователя удовлетворяется, а физическое обновление не выполняется).
16.4. Blasgen M.W., Gray J.N., Mitoma M., Price T.G. The Convoy Phenomenon // ACM Operating Systems Review. — April 1979. — 13, № 2.
Проблема образования вереницы (convoy) возникает при использовании механизма блокировок для интенсивно применяемых элементов данных. Примером может служить установка блокировки перед выполнением операции записи в журнал регистрации в системах с приоритетным планированием.
Примечание. Здесь понятие планирования относится к проблеме распределения процессорного времени по выполняемым транзакциям, а не к чередованию операций, принадлежащих различным транзакциям, что обсуждалось ранее в настоящей главе.
Эта проблема может быть пояснена следующим образом. Пусть транзакция т устанавливает блокировку некоторых интенсивно используемых элементов данных, после чего выполнение этой транзакции прекращается системным планировщиком, т.е. транзакция переходит в состояние ожидания, например, из-за того, что время отведенное ей для выполнения, истекло. Такая ситуация способствует образованию вереницы транзакций, каждая из которых ожидает продолжения его выполнения и уже успела установить блокировку некоторых элементов интенсивно используемых данных. Когда транзакция Т выйдет из подобного состояния ожидания она должна будет завершить обработку и снять блокировку используемых ею элементов данных. Однако именно из-за того, что заблокированными являются интенсивно используемые данные, велика вероятность того, что транзакция Т выйдет из состояния ожидания слишком рано, еще до того, как иная транзакция завершит работу с другим требуемым транзакции т элементом данных. Поэтому транзакция т не сможет продолжить выполнение своих операций и уже по собственной инициативе переведет себя в состояние ожидания.
Суть проблемы заключается в том, что в большинстве случаев (но не во всех) планирование является частью функций базовой операционной системы, а не СУБД, поэтому оно организуется на основе совершенно других допущений. По наблюдениям авторов этой работы, однажды образовавшаяся вереница проявляет тенденцию к стабильности. В результате система оказывается в состоянии постоянной пробуксовки блокировок (lock thrashing) и основная часть процессорного времени расходуется на переключение с одного процесса на другой, а не на выполнение какой-либо полезной работы. В качестве возможного решения этой проблемы, помимо замены способа планирования, можно предложить установку блокировок в произвольном порядке, а не на основе схемы "первым поступил-первым обработан".
16.5. Blott S., Korth H.F. An Almost-Serial Protocol for Transaction Execution in MainMemory Database Systems // Proc. 28th Int. Conf. on Very Large Data Bases, Hong Kong. — August 2002.
В статье предложен механизм обеспечения упорядочиваемое™ для систем с оперативной памятью, который позволяет полностью избежать необходимости использования блокировок.
16.6. Eswaran K.P., Gray J.N., Lorie R.A., Traiger I.L. The Notions of Consistency and Predicate Locks in a Data Base System // CACM. — November 1976. — 19, № 11.
В этой работе впервые дано строгое теоретическое описание основ управления параллельностью.
16.7. Franaszek P., Robinson J.T. Limitations on Concurrency in Transaction Processing // ACM TODS. - March 1985. - 10, № 1.
См. аннотацию К [16.16].
16.8. Franaszek P., Robinson J.T., Thomasian A. Concurrency Control for High Contention Environments //ACM TODS. - June 1992. - 17, № 2.
В статье сделано заявление, что в будущем системы обработки транзакций, вероятно, будут обеспечивать гораздо большую степень параллельности, чем современные системы (по разным причинам). Поэтому в них будут гораздо чаще возникать конфликтные ситуации на уровне данных. Затем авторы представляют "несколько концепций управления параллельностью [без использования блокировки] и методов планирования транзакций, которые применимы к средам с большим количеством конфликтных ситуаций". Применимость такого подхода обоснована экспериментами с различными имитационными моделями и, по словам авторов, этот подход "может обеспечить значительные преимущества".
16.9. Gray J.N. Experience with the System R Lock Manager // IBM San Jose Research Laboratory internal memo, 1980.
640 Часть IV. Управление транзакциями Эта работа представляет собой набор заметок, а не законченную статью, причем они в настоящее время уже несколько устарели. Тем не менее, в ней содержится несколько интересных утверждений, включая приведенные ниже.
Использование блокировок связано с издержками в размере 10% при работе с транзакциями, выполняемыми в интерактивном режиме, и в размере 1% при работе с транзакциями в пакетном режиме.
Желательно поддерживать разные уровни детализации блокировок, На практике хорошо себя показали средства автоматической эскалации уровня Метод с использованием повторяемого чтения (RR) является более эффектив ным, а также более безопасным по сравнению с методом, основанным на ста Ситуации взаимоблокировки очень редко возникают на практике и никогда не включают более двух транзакций.
Почти все ситуации взаимоблокировки (97%) можно устранить с помощью блокировок U, что и предусмотрено в СУБД DB2, но не в системе System R.
Примечание. В этом определении предполагается, что блокировки U совместимы с блокировками S, но не с другими блокировками U и, безусловно, не с блокировками X. Более подробные сведения приводятся в [4.21].) 16.10. Gray J.N., Lorie R.A., Putzolu G.R. Granularity of Locks in a Large Shared Data Base// Proc. 1st Int. Conf. on Very Large Data Bases. — Framingham, Mass. — September В статье впервые описана концепция намеченной блокировки. Как объясняется в разделе 16.8, понятие степень детализации (granularity) относится к размеру блокируемых объектов. Поскольку очевидно, что разные транзакции имеют различные характеристики и требования, желательно, чтобы в системе существовал целый набор возможных степеней детализации блокировок (что, в принципе, реализовано во многих системах). В этой статье представлена методика воплощения нескольких степеней детализации блокировок на основе механизма намеченной блокировки в подобной системе.
Поскольку в данной главе было дано весьма упрощенное описание протокола намеченной блокировки, ниже он будет рассмотрен несколько подробнее. Во-первых, стоит отметить, что блокируемыми объектами могут быть не только переменные отношения и кортежи, как предполагалось прежде. Во-вторых, типы блокируемых объектов могут в общем случае не обладать строгой иерархической структурой.
Присутствие индексов или других структур доступа будет лишь означать, что систему объектов следует рассматривать как ориентированный ациклический граф. Например, база данных поставщиков и деталей может содержать как хранимую переменную отношения деталей Р, так и индекс, например ХР, построенный для атрибута р# этой переменной отношения. Для выборки кортежей переменной отношения Р следует открыть всю базу данных, а затем либо перейти непосредственно к этому отношению и выполнить последовательный поиск, либо использовать индекс ХР для прямого перехода к искомым кортежам переменной отношения Р. Таким образом, кортежи переменной отношения Р в этом графе имеют два родительских объекта, Р и ХР, для каждого из которых родительским объектом является база данных.
Теперь формулировку этого протокола можно представить в более обобщенной При установке блокировки X для данного объекта для всех его дочерних объек тов неявным образом устанавливается блокировка X.
При установке блокировки S или SIX для данного объекта для всех его дочерних объектов неявным образом устанавливается блокировка S.
Прежде чем транзакция сможет потребовать установить блокировку S или IS для заданного объекта, она должна установить блокировку IS (или более силь ную) по крайней мере для одного из его родительских объектов.
Прежде чем транзакция сможет потребовать установить блокировку X, IX или SIX для заданного объекта, она должна установить блокировку IX (или более сильную) для всех родительских объектов этого объекта.
Прежде чем транзакция получит право освободить блокировку данного объек та, она должна вначале освободить все блокировки, установленные ею для до черних объектов данного объекта.
На практике использование этого протокола не сопровождается слишком большими издержками, как это может показаться на первый взгляд, поскольку в любой заданный момент транзакция, весьма вероятно, уже будет обладать почти всеми необходимыми ей блокировками. Например, блокировка IX для всей базы данных, вероятно, будет установлена непосредственно во время инициализации программы и эта блокировка будет сохраняться для всех транзакций, выполняемых на протяжении всей работы данной программы.
16.11. Gray J.N., Lorie R.A., Putzolu G.R., Traiger I.L. Granularity of Locks and Degrees of Consistency in a Shared Data Base // Proc. IFIP TC-2 Working Conf. on Modeling in Data Base Management Systems (ed. G. M. Nijssen). — Amsterdam, Netherlands:
North-Holland/New York, N.Y.: Elsevier Science, 1976.
В статье впервые введено понятие уровней изоляции (под названием степени согласованности — degrees of consistency)16.
16.12. Harder Т., Rothermel К. Concurrency Control Issues in Nested Transactions // The VLDB Journal. — January 1993. — 2, № 1.
Как уже отмечалось в разделе "Список литературы" главы 15, несколькими различными авторами была предложена идея вложенных транзакций. В этой статье предлагается соответствующий набор протоколов блокировки для подобных транзакций.
16.13. Jordan J.R., Banerjee J., Batman R.B. Precision Locks // Proc. 1981 ACM SIGMOD Int. Conf. on Management of Data. — Ann Arbor, Mich. — April/May 1981.
Этот термин нельзя назвать очень удачным. Данные могут быть только согласованными или несогласованными. Таким образом, термин, который указывает на то, что могут быть "степени" согласованности, звучит так, как будто ставится под сомнение сам этот тезис. Создается впечатление, что теория, лежащая в основе понятия "степеней согласованности", была разработана еще до того, как удалось достичь четкого понимания фундаментальной важности понятия целостности данных (или их "согласованности").
642 Часть IV. Управление транзакциями Точная блокировка является схемой блокировки на уровне кортежей, которая гарантирует блокировку только нужных кортежей (для достижения упорядочиваемости), включая фантомы. На самом деле эта форма блокировки называется блокировкой предикатов (см. раздел 16.8, а также [16.6]). Она основана на следующих действиях. Во-первых, при проверке запросов на обновление система определяет, удовлетворяет ли вставляемый или удаляемый кортеж сделанному ранее запросу на выборку данных в некоторой параллельной транзакции. Во-вторых, при проверке запросов на выборку система определяет, удовлетворяет ли вставляемый или удаляемый в некоторой параллельной транзакции кортеж данному запросу на выборку. Эта схема не только изящна, но и, как заявляют ее авторы, обладает более высокой производительностью, чем обычные методы (в которых блокируется чрезмерно много объектов).
16.14. Kempster Т., Stirling С, Thanisch P. Diluting ACID // ACM SIGMOD Record.— Эту статью лучше было бы назвать не "Разведение", а "Концентрирование ACID" (если ACID рассматривается не как аббревиатура, а как одно слово — кислота)!
Кроме всего прочего, в ней утверждается, что обычные механизмы управления параллельным выполнением исключают возможность создания некоторых упорядочиваемых графиков (как сказано в статье, "изолированность фактически является достаточным, но не необходимым условием для упорядочиваемое™"). Как и в стандарте SQL и в [16.2], в этой статье уровни изоляции определены в терминах нарушений упорядочиваемости, но эти определения являются более точными и охватывают больше упорядочиваемых графиков по сравнению с предыдущими попытками. В данной статье также отмечена одна ошибка (касающаяся фантомов) 16.15. Korth H.F., Speegle G. Formal Aspects of Concurrency Control in Long-Duration Transaction Systems Using the NT/PV Model // ACM TODS. - September 1994.. - 19, Как уже отмечалось в литературе (см., например, [15.3], [15.9], [15.16] и [15.17]), упорядочиваемость часто рассматривается как чрезмерно строгое требование, которое накладывается на некоторые виды систем обработки транзакций, особенно в новых прикладных областях, включающих взаимодействие с людьми, а значит, и транзакции большой длительности. В данной статье представлена новая модель обработки транзакций NT/PV (Nested Transactions with Predicates and Views — вложенные транзакции с предикатами и представлениями), позволяющая решить эти проблемы. В статье также показано, что стандартная модель обработки транзакций с упорядочением является лишь частным случаем; после чего дается определение "новых и более полезных классов правильности". Здесь утверждается, что новая модель обеспечивает "необходимую основу для решения проблем, связанных с долговременными транзакциями".
16.16. Kung H.T., Robinson J.T. On Optimistic Methods for Concurrency Control // ACM TODS. -June 1981. -6, №2.
Схемы блокировки рассматриваются как пессимистические в случае, когда делается предположение (худшее из возможных) о том, что все данные, необходимые для заданной транзакции, могут также потребоваться для параллельно выполняемой транзакции и поэтому их следует заблокировать. В отличие от этого, в оптимистических схемах (называемых также схемами сертификации или подтверждения) делается противоположное допущение о том, что такие конфликтные ситуации весьма маловероятны. Поэтому в рассматриваемых схемах допускается беспрепятственное выполнение всех транзакций. И только во время фиксации проверяется наличие конфликтных ситуаций. Если такие конфликты имели место, то вызвавшие их транзакции просто перезапускаются. Никакие обновления не записываются в базу данных до успешного завершения процедуры фиксации, поэтому при повторном запуске транзакций не требуется отменять какие-либо операции обновления.
Позднее в [16.7] было показано, что при некоторых разумных предположениях оптимистические методы демонстрируют определенные присущие им преимущества по сравнению с традиционными методами блокировки для некоторого уровня параллельности (т.е. некоторого числа одновременно выполняемых транзакций), который они способны поддерживать. Предполагается, что оптимистические методы могут быть наиболее полезными в системах с большим количеством параллельных процессоров. (В [15.12], наоборот, утверждается, что оптимистические методы в общем случае на самом деле хуже методов блокировки в некоторых "горячих" ситуациях, т.е. в ситуациях, когда объект данных обновляется очень часто и несколькими различными транзакциями. Более подробную информацию о методах, эффективных при работе в подобных ситуациях, можно найти в [16.17].) 16.17. O'Neil P.E. The Escrow Transactional Method // ACM TODS. — December 1986. — Рассмотрим следующий весьма простой пример. Предположим, что в базе данных содержится объект данных тс, представляющий имеющуюся на руках наличность, и допустим, что почти каждая транзакция в системе обновляет данные в объекте ТС с некоторым уменьшением их значения (соответствующим некоторому списанию денежных средств со счета). Объект ТС представляет собой пример горячей точки, т.е. элемента базы данных, который используется большинством транзакций в системе. Образно говоря, при традиционной блокировке горячая точка может очень скоро превратиться в узкое место всей системы, поэтому в таких ситуациях было бы весьма неразумно использовать традиционную блокировку. Если начальное значение TC равно 10 млн. долл., а каждая отдельная транзакция приводит к его уменьшению в среднем на 10 долл., то в целом может быть выполнено около миллиона таких транзакций. Причем для этого потребовалось бы выполнить в произвольном порядке около миллиона операций вычитания. В таком случае действительно вовсе нет необходимости в использовании традиционной блокировки для ТС.
Вместо этого следует убедиться, что текущее значение достаточно велико для успешного выполнения данной операции вычитания, а затем выполнить обновление значения. (Если выполнение такой транзакции не будет успешно завершено, то последнюю операцию вычитания следует отменить.) Метод депонирования применяется в ситуациях, подобных описанной выше, т.е.
когда обновления имеют некоторую конкретную, а не произвольную форму. В такой системе должен быть определен особый вид оператора обновления (например, "уменьшить на х тогда и только тогда, когда текущее значение больше, чем у").
В этом случае обновление можно было бы выполнить, помещая уменьшенное 644 Часть TV. Управление транзакциями значение х в некоторый третий объект-депонент, для его извлечения оттуда в конце выполнения транзакции (это изменение фиксируется, если в конце транзакции выполняется оператор COMMIT, а если транзакция оканчивается оператором ROLLBACK, эта сумма снова добавляется к первоначальной).
В статье описывается несколько ситуаций, в которых можно использовать метод депонирования. Одним из примеров коммерческого продукта, в котором поддерживается данный метод, является информационная система IMS Fast Path фирмы IBM. Следует отметить, что этот метод может рассматриваться как частный случай оптимистического управления параллельностью [16.16]. Но заслуживает внимания то, что данный случай и должен рассматриваться как частный, поэтому для него крайне необходимо предусмотреть специальные операторы обновлгния.
16.18. Papadimitriou С. The Theory of Database Concurrency Control. — Rockville, Md.:
Computer Science Press, 1986.
Учебное пособие, в котором особое внимание уделяется формальной теории.
16.19. Rosencrantz D.J., Stearns R.E., Lewis II P.M. System Level Concurrency Control for Distributed Database Systems //ACM TODS. — June 1978. — 3, № 2.
16.20. Salem K., Garcia-Molina H., Shands J. Altruistic Locking // ACM TODS. — March В этой статье предлагается расширение протокола двухфазной блокировки, в соответствии с которым транзакция А, завершившая работу с заблокированным элементом данных (который не может быть разблокирован из-за ограничений протокола двухфазной блокировки), все же возвращает этот элемент системе, тем самым позволяя некоторой другой транзакции в установить для него блокировку. В этом случае говорят, что транзакция в идет вслед за транзакцией А. Здесь определены протоколы, например, позволяющие предотвратить получение некоторой транзакцией любых обновлений, внесенных той транзакцией, которая следовала за ней. Показано, что альтруистическая блокировка (происхождение этого термина связано с тем фактом, что возвращение данных приносит пользу другим транзакциям, а не транзакции, отдающей другим свои ресурсы) обеспечивает более высокую степень параллельности, чем обычный протокол двухфазной блокировки, особенно когда некоторые из транзакций продолжаются достаточно долго.
16.21. Silberschatz A., Korth H.F., Sudarshan S. Database System Concepts (4th ed.). — New York, N.Y.: McGraw-Hill, 2002.
' В этом учебнике по вопросам управления базой данных содержится формальное описание тематики управления транзакциями (с учетом требований восстановления и организации параллельной работы).
16.22. Thomas R.H. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases//ACM TODS. — June 1979. — 4, № 2.
См. аннотацию к [16.3].
16.23. Thomasian A.Concurrency Control: Methods, Performance, and Analysis // ACM Сотр. Surv. — March 1998. — 30, № 1.
Подробное исследование производительности различных алгоритмов управления параллельной работой.
ДОПОЛНИТЕЛЬНЫЕ ТЕМЫ
В части II этой книги было сказано, что реляционная модель является основой современной технологии баз данных, и это действительно так. Но это только основа, и, помимо описанной в части II реляционной модели, в технологии баз данных есть много других компонентов. Как студентам, так и профессионалам необходимо освоить множество дополнительных концепций и технологий, чтобы полностью овладеть этой областью знаний (последнее вполне очевидно из обсуждений в частях III и IV данной книги). Теперь нам предстоит сосредоточить внимание на ряде важных тем, которые будут рассматриваться в такой последовательности.Защита данных (глава 17).
Оптимизация (глава 18).
Отсутствующая информация (глава 19).
Наследование типов (глава 20).
Распределенные базы данных (глава 21).
Поддержка принятия решений (глава 22).
Хронологические базы данных (глава 23).
Логические системы управления базами данных (глава 24).
Выбранная последовательность глав носит несколько произвольный характер, однако при их написании предполагалось, что эти главы (может быть, не все) будут изучаться именно в таком порядке.
17.1. Введение 17.2 Избирательная схема управления доступом 17.3. Мандатная схема управления доступом 17.4. Статистические базы данных 17.5. Шифрование данны:
17.6. Средства языка SQL 17.7. Резюме Вопросы защиты данных часто рассматриваются вместе с вопросами поддержки целостности данных (по крайней мере, в неформальном контексте), хотя на самом деле это совершенно разные понятия. Термин защита (security) относится к защищенности данных от несанкционированного доступа, изменения или умышленного разрушения, а целостность— к точности или достоверности данных'. Эти термины можно определить, как показано ниже.
Под защитой данных подразумевается предотвращение доступа к ним со несанкционированных пользователей.
Под поддержкой целостности данных подразумевается предотвращение шения при доступе со стороны санкционированных пользователей (!).
Иначе говоря, защита данных означает получение гарантий, что пользователям разрешено выполнять те действия, которые они пытаются выполнить, а поддержка целостности означает получение гарантий, что действия, которые пользователи пытаются выполнить, будут допустимыми.
Как указано в главе 9, в данном контексте термин достоверность или, скорее, правильность, должен быть в действительности приведен в кавычках.
648 Часть V. Дополнительные темы Между этими понятиями есть, безусловно, некоторое сходство, поскольку как при обеспечении защиты данных, так и при обеспечении поддержки их целостности система вынуждена проверять, не нарушаются ли при выполняемых пользователем действиях некоторые установленные ограничения. Эти ограничения формулируются (обычно администратором базы данных) на некотором подходящем языке и сохраняются в системном каталоге. Причем в обоих случаях СУБД должна каким-то образом отслеживать все выполняемые пользователем действия и проверять их соответствие установленным ограничениям. В данной главе речь пойдет о защите данных, а вопросы целостности уже рассматривались в главе 9.
Примечание. Основная причина, по которой эти две темы обсуждаются раздельно, состоит в том, что целостность данных является фундаментальным понятием, тогда как защита данных — понятием вторичным, несмотря на его большую практическую важность (особенно в наши дни повсеместного распространения Internet, электронной коммерции и соответствующих средств доступа).
Ниже описаны многочисленные аспекты проблемы защиты данных.
Правовые, общественные и этические аспекты (например, имеет ли некоторое ли цо легальное основание запрашивать, скажем, информацию о выделенном клиен ту кредите).
Физические условия (например, запирается ли помещение с компьютерами или терминалами на замок либо оно охраняется другим способом).
Организационные вопросы (например, каким образом на предприятии, являю щемся владельцем системы, принимается решение о том, кому разрешено иметь доступ к тем или иным данным).
Вопросы управления (например, как в случае организации защиты системы от не санкционированного доступа по схеме паролей обеспечивается секретность ис пользуемых паролей и как часто они меняются).
Аппаратные средства защиты (например, имеет ли используемое вычислительное оборудование встроенные функции защиты, подобные ключам защиты хранимой информации или привилегированному режиму управления).
Возможности операционной системы (например, стирает ли используемая опера ционная система содержимое оперативной памяти и дисковых файлов после прекращения работы с ними, и каким образом обрабатывается журнал восста новления).
Аспекты, имеющие отношение непосредственно к самой СУБД (например, под держивает ли используемая СУБД концепцию владельца данных).
По очевидным причинам обсуждение этой обширной темы в данной главе будет ограничено в основном вопросами, относящимися к последнему пункту приведенного выше списка.
В современных СУБД обычно поддерживается один из двух широко распространенных методов организации защиты данных — избирательный (discretionary) или мандатный (mandatory), а иногда оба этих метода. В обоих случаях единица данных (или объект данных) для которой организуется защита, может выбираться из широкого диапазона, от всей базы данных до конкретных компонентов отдельных кортежей. Различия между двумя указанными методами кратко описаны ниже.
В случае избирательного контроля каждому пользователю обычно предоставляются различные права доступа (иначе называемые привилегиями, или полномочиями) к разным объектам. Более того, разные пользователи, как правило, обладают раз ными правами доступа к одному и тому же объекту. (Например, пользователю U может быть разрешен доступ к объекту А, но запрещен доступ к объекту в, тогда как пользователю U2 может быть разрешен доступ к объекту в, но запрещен доступ к объекту А.) Поэтому избирательные схемы характеризуются значительной гиб костью.
В случае мандатного контроля, наоборот, каждому объекту данных назначается не который классификационный уровень, а каждому пользователю присваивается не который уровень допуска. В результате право доступа к объекту данных получают только те пользователи, которые имеют соответствующий уровень допуска. Ман датные схемы обычно имеют иерархическую структуру и поэтому являются более жесткими. (Если пользователь U1 имеет доступ к объекту А, но не имеет доступа к объекту в, то в схеме защиты объект в должен будет располагаться на более высоком уровне, чем объект А, а значит, не может существовать никакого пользователя U2, который будет иметь доступ к объектув, но не будет иметь доступа к объекту А.) Избирательные схемы подробно обсуждаются ниже, в разделе 17.2, а мандатные схемы — в разделе 17.3.
Независимо от того, какая схема используется (избирательная или мандатная), все решения относительно предоставления пользователям прав на выполнение тех или иных операций с теми или иными объектами должны приниматься исключительно управленческим персоналом. Поэтому все эти вопросы выходят за пределы возможностей самой СУБД, и все, что она способна сделать в данной ситуации, — привести в действие решения, которые будут приняты на другом уровне. Исходя из этих соображений, можно определить приведенные ниже условия.
Принятые организационные решения должны быть доведены до сведения систе мы (т.е. представлены как ограничения защиты, выраженные с помощью некото рого языка описания требований защиты) и должны быть ей постоянно доступны (храниться в системном каталоге).
Очевидно, что в системе должны существовать определенные средства проверки поступающих запросов на получение доступа по отношению к установленным правилам защиты. (Здесь под понятием запрос на получение доступа подразумева ется конкретная комбинация запрашиваемой операции, запрашиваемого объекта и запрашивающего пользователя.) Обычно такая проверка выполняется подсистемой защиты СУБД, которую иногда называют также подсистемой авторизации.
Для принятия решения о том, какие именно установленные ограничения защиты применимы к данному запросу на получение доступа, система должна быть способна установить источник этого запроса, т.е. суметь опознать запрашивающего пользова теля. Поэтому при подключении к системе от пользователя обычно требуется вве сти не только свой идентификатор (чтобы указать, кто он такой), но и пароль (чтобы подтвердить, что он именно тот, за кого себя выдает). Предполагается, что пароль известен только системе и тем лицам, которые имеют право применять дан ный идентификатор пользователя. Процесс проверки пароля (т.е. проверки того, что пользователи являются теми, за какого себя выдают) называется аутентификацией, 650 Часть V. Дополнительные темы Примечание. Следует отметить, что в настоящее время существуют намного более сложные методы аутентификации по сравнению с простой проверкой паролей, в которых для аутентификации применяется целый ряд биометрических устройств:
приборы для чтения отпечатков пальцев, сканеры радужной оболочки, анализаторы геометрических характеристик ладони, приборы проверки голоса, устройства распознавания подписей и т.д. Все эти устройства могут эффективно использоваться для проверки "персональных характеристик, которые никто не может подделать" [17.6].
Кстати, в отношении идентификаторов пользователей следует заметить, что один и тот же идентификатор может совместно применяться для целого ряда разных пользователей, входящих в состав некоторой группы. Таким образом, система может поддерживать группы пользователей (называемые также ролями), обеспечивая одинаковые права доступа для всех ее членов, например, для всех работников бухгалтерского отдела. Кроме того, операции добавления новых пользователей в группу или их удаления из нее можно выполнять независимо от операций задания привилегий доступа для этой группы на те или иные объекты. В этой связи следует обратить внимание на работу [17.11], в которой описана система с вложенными пользовательскими группами. Приведем цитату из этой работы: "Способность классифицировать пользователей в виде иерархии групп представляет собой мощный инструмент администрирования больших систем с тысячами пользователей и объектов". Но следует отметить, что наиболее удобным местом для регистрации информации о том, какие пользователи относятся к тем или иным группам, является также системный каталог (или, возможно, сама база данных), причем и эта информация должна быть, безусловно, объектом применения подходящих средств защиты.
17.2. ИЗБИРАТЕЛЬНАЯ СХЕМА УПРАВЛЕНИЯ ДОСТУПОМ
Повторяя сказанное выше, следует еще раз отметить, что во многих СУБД поддерживается либо избирательная, либо мандатная схема управления доступом, либо оба типа доступа одновременно. Однако точнее все же будет сказать, что в действительности в большинстве СУБД поддерживается только избирательная схема доступа и лишь в некоторых — только мандатная. Поскольку на практике избирательная схема доступа встречается гораздо чаще, основное внимание в этой главе уделено именно ей.Как уже отмечалось, для определения избирательных ограничений защиты необходимо использовать некоторый язык. По вполне очевидным причинам гораздо легче указать то, что разрешается, чем то, что не разрешается. Поэтому в подобных языках обычно поддерживается определение не самих ограничений защиты, а полномочий, которые по своей сути противоположны ограничениям защиты (т.е. они разрешают какие-либо действия, а не запрещают их). Дадим краткое описание гипотетического языка определения полномочий2, воспользовавшись следующим примером.
«