Data Base Management Systems: #2/96

Системы Управления Базами Данных # 2/96 стр. 45-60

Критика уровней изолированности в стандарте ANSI SQL*)

Х. Беренсон, Ф. Бернштейн, Д. Грэй, Д. Мелтон, Э. О'Нил, П. О'Нил
1. Введение
2. Определение изолированности
    2.1. Концепция сериализуемости
    2.2. Уровни изолированности в ANSI SQL
    2.3. Механизм блокировок
3. Анализ Уровней Изолированности ANSI SQL
4. Другие типы изолированности
    4.1. Устойчивость курсора
    4.2. Изолированность Образа
    4.3. Другие многоверсионные системы
Резюме и Выводы
Благодарности
Литература

В ANSI SQL-92 [MS, ANSI] Уровни Изолированности (Isolation Levels) определяются в терминах феноменов (phenomena): Грязное Чтение (Dirty Read), Неповторимое Чтение (Non-repeatable Read) и Фантом (Phantom). В статье показывается недостаточность феноменов и определений ANSI SQL для полного корректного описания некоторых популярных уровней изолированности, включая стандартные блокировочные реализации рассматриваемых уровней. Исследуется неоднозначность определений феноменов и дается более точное формальное определение феномена. Приводятся новые феномены, которые лучше характеризуют типы изолированности. Определяется новый тип многоверсионной изолированности называемый Изолированностью Образа (Snapshot Isolation).

1. Введение

Возможность параллельного выполнения конкурирующих транзакций на различных уровнях изолированности позволяет разработчикам приложений повысить количество одновременно выполняющихся транзакций, сохраняя их корректность. Нижние уровни изолированности дают возможность увеличить количество одновременно выполняющихся транзакций за счет риска получения размытого или несогласованного состояния данных. Замечательно, что в то время, когда некоторые транзакции выполняются на высшем уровне изолированности (чистая сериализуемость), совместно выполняющиеся транзакции на нижних уровнях изолированности выполняются параллельно и могут работать с незафиксированными или устаревшими, прочитанными транзакцией ранее, данными [GLPT]. Конечно, транзакции, выполняющиеся на нижних уровнях изолированности, могут произвести в результате работы неправильные данные. Разработчики приложений должны остерегаться распространения таких ошибок при использовании некорректных данных транзакциями высоких уровней изолированности.

В стандарте ANSI SQL-92 [MS, ANSI] определяются четыре уровня изолированности.

    1) Незафиксированное Чтение (READ UN-COMMITED).
    2) Зафиксированное Чтение (READ COMMITED).
    3) Повторимое Чтение (REPEATABLE READ).
    4) Сериализуемость (SERIALIZABLE).

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

Уровни изолированности ANSI родственны по поведению планировщику блокировок. Некоторые планировщики блокировок позволяют транзакциям варьировать границы и продолжительность устанавливаемых ими запросов блокировок, таким образом отступая от чистой двухфазной блокировки. Эта идея была предложена в [GLPT], где степени согласованности определяются тремя способами: механизмом блокировок, графом потоков данных и аномалиями. В стандарте ANSI SQL определение уровней изолированности дается в терминах феноменов (аномалий) для того, чтобы такое определение уровней изолированности позволяло не только реализации стандарта SQL, основанные на механизме блокировок.

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

Во втором разделе вводится основная терминология, связанная с уровнями изолированности. Определяются ANSI SQL и блокировочные уровни изолированности.

В третьем разделе исследуются недостатки уровней изолированности в ANSI SQL и предлагается к рассмотрению новый феномен. Также даны определения других популярных уровней изолированности. Проводятся сравнительные параллели между уровнями изолированности в ANSI SQL и степенями согласованности, определенными в [GLPT] в 1977 году. Они также охватывают определения устойчивости курсора и повторимого чтения, данные Крисом Дейтом в [DAT]. Рассуждая об уровнях изолированности с помощью однородной общеупотребительной терминологии, мы стараемся избежать непонимания, возможного от употребления своей независимой терминологии.

В четвертом разделе описан механизм контроля многоверсионного параллельного выполнения транзакций. Он назван Изолированность Образа. Он позволяет избежать употребления феноменов ANSI SQL, но не является сериализуемым. Изолированность Образа интересна тем, что обеспечивает промежуточный уровень изолированности, лежащий между уровнями Зафиксированного Чтения и Повторимого Чтения. Новый формализм (описанный в более полной версии этой статьи [OOBBGM]) соединяет в себе промежуточный уровень изолированности для многоверсионных данных и классическую одноверсионную теорию блокировочной сериализуемости.

В пятом разделе исследуются несколько новых аномалий. Они позволяют выделить различия между уровнями изолированности, введенными в третьем и четвертом разделах. Дополнительные ANSI SQL-феномены, приводимые здесь, позволяют точно определить Изолированность Образа и Устойчивость Курсора. В шестом разделе представлено краткое Резюме и сделаны Выводы.

2. Определение изолированности

2.1. Концепция сериализуемости

Концепции транзакции и механизма блокировок хорошо документированы в литературе [BHG, PAP, PON, GR]. В следующих нескольких абзацах делается обзор терминологии, используемой в этой области.

Транзакцией называют упорядоченное множество операций, переводящих базу данных из одного непротиворечивого состояния в другое. История моделирует перекрывающееся выполнение множества транзакций в виде линейных последовательностей их операций Чтения и Записи (Вставки, Обновления, Удаления) определенных элементов данных. Говорят, что две операции в истории конфликтуют, если они осуществляются различными транзакциями над одним элементом данных и хотя бы одна из них выполняет операцию Записи. Согласно [EGLT], это определение можно широко интерпретировать в зависимости от того, что понимать под "элементом данных". Это может быть строка таблицы, конкретное поле на странице, целая таблица или коммуникационный объект, такой например как сообщение в очереди. Конфликтующие операции могут возникать не только на отдельных элементах данных, но и на множествах элементов данных, которые задаются с помощью предикатов.

Отдельные истории составляют граф зависимостей (dependency graph), определяющий потоки временных данных, передаваемых между транзакциями. Операции зафиксированных транзакций представляются вершинами графа. Если в истории операция op1 транзакции T1 конфликтует с предшествующей операцией op2 транзакции T2, то пара <op1, op2> становится ребром графа зависимостей. Две истории считаются эквивалентными, если они имеют одинаковые зафиксированные транзакции и одинаковые графы зависимостей. История называется сериализуемой, если она эквивалентна последовательной истории. Другими словами, если она имеет такой же граф зависимостей (межтранзакционный поток временных данных), как если бы все транзакции в ней выполнялись последовательно (поочередно).

2.2. Уровни изолированности в ANSI SQL

Разработчики ANSI SQL дали такое определение изолированности, которое допускает широкий спектр механизмов реализации, не только механизм блокировки. Они определили изолированность с помощью следующих трех феноменов (phenomena):

P1 (Грязное Чтение) (Dirty Read)

Транзакция T1 модифицировала содержимое элемента данных. После этого другая транзакция T2 прочитала содержимое этого элемента данных, до того как транзакция T1 выполнила операцию COMMIT (зафиксировалась) или ROLLBACK (откатилась). Если T1 завершается операцией ROLLBACK, то получается, что транзакция T2 прочитала реально не существующие данные.

P2 (Неповторимое или Размытое Чтение)
(Non-repeatable or Fuzzy Read)

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

P3 (Фантом) (Phantom):

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

Ни один из этих феноменов не может произойти в последовательной истории. Поэтому, по теореме о сериализуемости, они не могут произойти и в сериализуемой истории [EGLT, BHG Теорема 3.6, GR Раздел 7.5.8.2, PON Теорема 9.4.2].

Истории, состоящие из операций Чтения, Записи, Фиксации и Отката, могут быть записаны в сокращенной нотации: "w1[x]" обозначает операцию записи транзакции 1 в ячейку x (таким образом данные модифицируются)" "r2[x]" представляет операцию чтения из x транзакцией 2. Операции чтения и записи множества записей, удовлетворяющих предикату P, в транзакции 1 обозначаются соответственно r1[P] и w1[P]. Фиксация (COMMIT) и Откат (ROLLBACK) транзакции 1 соответственно обозначаются "c1" и "a1".

Феномен P1 может быть представлен как запрещение на следующую последовательность операций:

(2.1)  w1[x]...r2[x]... (a1 и c2 в любом порядке)

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

(2.2)  w1[x]...r2[x]... ((c1 или a1) и (c2 или a2) в любом порядке)

Запретив P1 в варианте (2.2), мы запретим любую историю следующего вида: T1 модифицирует содержимое элемента данных x. Затем T2 читает содержимое x, до того как T1 зафиксируется или откатится. Определение не настаивает на том, чтобы T1 откатилась или T2 зафиксировалась.

Определение (2.2) является более свободной интерпретацией P1, чем (2.1). Оно запрещает все четыре возможных варианта пар завершение-откат транзакций T1 и T2, когда в (2.1) запрещаются только две пары из четырех. Интерпретация (2.2) феномена P1 запрещает все варианты последовательности выполнения, даже те, в которых что-то аномальное может произойти в будущем. Мы называем интерпретацию (2.2)- свободной интерпретацией P1, а (2.1)- строгой интерпретацией P1. Интерпретация (2.2) определяет феномен, который может быть аномальным, а (2.1) - который заведомо аномален. Обозначим их соответственно P1 и A1:

P1: w1[x]...r2[x]... ((c1 или a1) и (c2 или a2) в любом порядке)
A1: w1[x]...r2[x]... ((a1 и c2) в любом порядке)

Аналогично, словарные определения феноменов P2 и P3 тоже имеют свободную и строгую интерпретации. Обозначим свободные интерпретации через P2 и P3, а строгие через A2 и A3:

P2: r1[x]...w2[x]... ((c1 или a1) и (c2 или a2) в любом порядке)
A2: r1[x]...w2[x]...c2...r1[x]...c1
P3: r1[P]...w2[y in P]... ((c1 или a1) и (c2 или a2) в любом порядке)
A3: r1[P]...w2[y in P] ...c2...r1[P]...c1

В третьем разделе все варианты интерпретаций феноменов рассматриваются более подробно. Аргументируется необходимость выбора свободных интерпретаций. Заметим, что в словесном ANSI SQL определении феномена P3 после чтения по предикату запрещается только вставлять данные, которые попадают в область действия предиката, а в определении P3, которое было приведено выше, запрещается производить любую операцию записи (вставка, обновление, удаление), влияющую на кортеж, удовлетворяющий предикату.

Далее в статье рассматривается концепция многозначной истории (multi-valued history) (сокращенно МВ-история, см. [BHG], Глава 5). Не вдаваясь в детали сейчас, многоверсионная система отличается тем, что может одновременно содержать несколько версий одного элемента данных. При выполнении операции чтения должно быть совершенно ясно, какую версию данных необходимо использовать. Здесь делаются попытки сопоставить определение условной изолированности ANSI с многоверсионными системами и более распространенными одноверсионными системами (single-version) (ОВ-истории) стандартного планировщика блокировок. Словесные определения феноменов P1, P2 и P3 подразумевают одноверсионные истории. В следующем разделе видно, как мы их интерпретируем.

В Таблице 1 приводятся четыре уровня изолированности определенные в ANSI SQL. Каждый уровень изолированности характеризуется возможностью происхождения феноменов (в строгой или свободной интерпретации). Однако сериализуемый уровень изолированности в ANSI SQL не определяется только в терминах феноменов. В работе [ANSI], подпункте 4.28 "SQL-транзакции", отмечается, что на уровне изолированности СЕРИАЛИЗУЕМОСТЬ должно обеспечиваться поведением, которое "хорошо известно как полностью сериализуемое выполнение". Анализируя верхнюю часть таблицы и принимая во внимание эту оговорку, обычно приходят к распространенному заблуждению, что запрещение всех трех феноменов приведет к сериализуемости. Истории, исключающие три указанных феномена, называют Аномально Сериализуемыми (ANOMALY SERIALIZABLE) (см. Таблицу 1).

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

Было бы проще в [ANSI] оставить P3 и использовать подпункт 4.28 для определения ANSI СЕРИАЛИЗУЕМОСТЬ. В Таблице 1 представлен только промежуточный результат, окончательный результат будет представлен в Таблице 3.

2.3. Механизм блокировок

В большинстве SQL-продуктов изолированность реализована на основе механизма блокировок. Поэтому полезно описать уровни изолированности ANSI SQL в терминах блокировок.

Выполнение транзакций происходит под управлением планировщика блокировок. Перед выполнением операции Чтения или Записи с одним или несколькими элементами данных транзакция делает запрос планировщику блокировок на установление блокировки по Чтению (Share) или по Записи (Exclusive) на те элементы данных, к которым она обращается. Две блокировки, поставленные различными транзакциями на одни и те же элементы данных, конфликтуют, если хотя бы одна из них является блокировкой по Записи.

Предикативная блокировка по Чтению (по Записи) множества элементов данных, определяющихся с помощью предиката <search condition>, блокирует все элементы данных, удовлетворяющие этому предикату. Это множество элементов данных теоретически является бесконечным, потому что в него попадают все элементы, уже присутствующие в базе данных и удовлетворяющие предикату <search condition>, и так же все фантомные элементы данных, которых еще нет в базе данных, но которые будут удовлетворять предикату <search condition>, если попадут туда вследствие выполнения операции Вставки или Обновления. В терминах SQL предикативная блокировка закрывает все присутствующие в базе данных элементы, которые удовлетворяют предикату, и любые другие удовлетворяющие предикату блокировки элементы, которые могут быть внесены в базу данных с помощью операций Вставки, Обновления или Удаления. Две предикативных блокировки различных транзакций конфликтуют, если одна является блокировкой по Записи и если есть (возможно, фантомные) элементы данных, закрытые обеими блокировками. Блокировка элемента данных (блокировка записи) является предикативной блокировкой, у которой в предикате указано имя данной записи.

Транзакция имеет хорошо сформированные (well-formed writes) операции Записи (Чтения), если она запрашивает блокировку по Записи (по Чтению) на каждый элемент данных или предикат перед выполнением операции Записи (Чтения) над этим элементом данных или множеством элементов данных, определенных с помощью предиката. Транзакция называется хорошо сформированной (well-formed), если все ее операции Записи и Чтения хорошо сформированные. Транзакция имеет двухфазные (two-phase writes) операции Записи (Чтения), если она не устанавливает новую блокировку по Записи (Чтению) на элементы данных после снятия с них блокировки по Записи (Чтению). Транзакция осуществляет двухфазную блокировку (two-phase locking), если она не запрашивает новой блокировки (по Записи или по Чтению) после снятия какой-то блокировки.

Блокировка, запрашиваемая транзакцией, называется долговременной (long duration), если она не снимается до конца выполнения транзакции (когда она зафиксируется или откатится). В противном случае блокировка называется кратковременной (short duration). На практике кратковременные блокировки обычно снимаются сразу же после завершения операции.

Уровень изолированности | Р1 (или А1) Грязное чтение (Dirty Read) | Р2 (или А2) Размытое чтение (Fuzzy Read) | Р3 (или А3) Фантом (Phantom)
ANSI НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (ANSI READ UNCOMMITTED) | возможен | возможен | возможен
ANSI НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (ANSI READ UNCOMMITTED) | невозможен | возможен | возможен
ANSI ПОВТОРИМОЕ ЧТЕНИЕ (ANSI REPEATABLE READ) | невозможен | невозможен | возможен
АНОМАЛЬНАЯ СЕРИАЛИЗУЕМОСТЬ (ANOMALY SERIALIZABLE) | невозможен | невозможен | невозможен

Таблица 1.

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

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

Для того чтобы показать эквивалентность механизма блокировок, зависимостей и механизмов, основанных на аномалиях, в статье [GLPT] определяются четыре степени согласованности (degrees of consistency). Определения аномалий (см. Определение 1) были даны очень расплывчато. Авторы продолжают критиковать определения в этом аспекте (см. также [GR]). Со временем остались только математически точные определения в терминах историй и графов зависимостей или блокировок.

Степень согласованности = Блокировочный уровень изолированности | Блокировка по Чтению на Элементах Данных и Предикатах (одинаковы если нет замечаний) | Блокировка по Записи на Элементах Данных и Предикатах (везде одинаковы)
Степень 0 | ничего не требуется | Хорошо сформированные Записи
Степень 1=Блокировочное Незафиксированное Чтение | ничего не требуется | Хорошо сформированные Записи Долговременные блокировки по Записи
Степень 2=Блокировочное Зафиксированное Чтение | Хорошо сформированные Чтения Кратковременные блокировки по Чтению (обе) | Хорошо сформированные Записи Долговременные блокировки по Записи
Устойчивость Курсора (см. Раздел 4.1) | Хорошо сформированные Чтения Блокировка по Чтению устанавливается на текущем элементе курсора Кратковременные блокировки по Чтению на Предикатах | Хорошо сформированные Записи Долговременные блокировки по Записи
Блокировочное Повторимое Чтение | Хорошо сформированные Чтения Долговременные блокировки по Чтениюна элементах данных Кратковременные блокировки по Чтению на Предикатах | Хорошо сформированные Записи Долговременные блокировки по Записи
Степень 3=Блокировочная СЕРИАЛИЗУЕМОСТЬ | Хорошо сформированные Чтения Долговременные блокировки по Чтению(обе) | Хорошо сформированные Записи Долговременные блокировки по Записи

Таблица 2.

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

    Блокировочное НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ UNCOMMITTED),
    Блокировочное ЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ COMMITTED),
    Блокировочное ПОВТОРИМОЕ ЧТЕНИЕ (Locking REPEATABLE READ),
    Блокировочная СЕРИАЛИЗУЕМОСТЬ (Locking SERIALIZABLE),

являются блокировочными аналогами уровней изолированности ANSI SQL, но, как показывается дальше, они существенно отличаются друг от друга (см. Таблицы 1 и 2). Поэтому необходимо различать уровни изолированности, определенные в терминах блокировок, и уровни изолированности, определенные с помощью феноменов. Для достижения такого различия уровни изолированности, определенные во второй Таблице, имеют префикс "Блокировочные", а определенные в первой Таблице - "ANSI".

[GLPT] определяет согласованность Степени 0, на которой разрешаются операции Грязного Чтения и Записи (Dirty Reads and Writes). Требуется только атомарность операций. Степени 1, 2 и 3 относятся, соответственно, к блокировочным уровням изолированности: Блокировочное НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ UNCOMMITTED), Блокировочное ЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ COMMITTED), Блокировочная СЕРИАЛИЗУЕМОСТЬ (Locking SERIALIZABLE). Ни одна степень согласованности не соответствует уровню изолированности Блокировочное ПОВТОРИМОЕ ЧТЕНИЕ (Locking REPEATABLE READ).

Дэйт и IBM сначала использовали термин "Повторимое Чтение" [DAT, DB2] для обозначения сериализуемости или блокировочной сериализуемости. Этот термин кажется более понятным, чем термин [GLPT] "третья степень изолированности", хотя по значению они идентичны. Такая терминология неудачна, так как значение термина ANSI SQL ПОВТОРИМОЕ ЧТЕНИЕ отличается от оригинального определения, данного Дэйтом. Аномалия P3 специально не исключается на уровне изолированности ANSI SQL ПОВТОРИМОЕ ЧТЕНИЕ, но из определения P3 ясно, что чтение НЕ повторимое! Во второй Таблице мы продолжаем употреблять термин Блокировочное ПОВТОРИМОЕ ЧТЕНИЕ в параллель с ANSI-определением, хотя это и неправильно. Аналогично Дэйт ввел термин Устойчивость Курсора как более подходящее название для второй степени изолированности с добавленной защитой от потери при обновлении курсора, как объясняется в разделе 4.1 ниже.

Определение. Уровень изолированности L1 слабее (weaker), чем уровень изолированности L2 (или L2 сильнее (stronger), чем L1), обозначим как L1 << L2, если все не сериализуемые истории, удовлетворяющие критериям уровня L2, также удовлетворяют критериям уровня L1 и существует хотя бы одна несериализуемая история, принадлежащая уровню L1 и невозможная на уровне L2. Два уровня изолированности L1 и L2 эквивалентны (equivalent), обозначаются как L1 == L2, если множества допустимых несериализуемых историй на L1 и L2 идентичны. L1 не сильнее (no stronger), чем L2, обозначаются как L1 <= L2, если или L1 << L2, или L1 == L2. Два уровня изолированности несравнимы (incomparable), обозначается как L1 >><< L2, когда каждый уровень изолированности допускает несериализуемую историю, недопустимую на другом уровне.

Сравнивая уровни изолированности, мы различаем их только по несериализуемым историям, которые могут произойти на одном уровне и невозможны на другом. Два уровня изолированности могут также различаться по тем сериализуемым историям, которые они допускают, но мы подразумеваем, что Блокировочная СЕРИАЛИЗУЕМОСТЬ == СЕРИАЛИЗУЕМОСТИ, даже при том, что хорошо известно, - что планировщики блокировок не допускают всевозможные сериализуемые истории. Возможно, такие уровни изолированности будут немного непрактичны, ввиду того, что они не допускают слишком много сериализуемых историй, но мы здесь этот вопрос не рассматриваем.

Следующее замечание и определения, приведенные выше, показывают полезность введенного отношения <=.

Замечание 1.
Блокировочное НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ UNCOMMITTED)
<< Блокировочное ЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ COMMITTED)
<< Блокировочное ПОВТОРИМОЕ ЧТЕНИЕ (Locking REPEATABLE READ)
<< Блокировочная СЕРИАЛИЗУЕМОСТЬ (Locking SERIALIZABLE)

В следующем разделе мы сравним блокировочные системы с определениями ANSI.

3. Анализ Уровней Изолированности ANSI SQL

Сначала сделаем позитивное замечание с том, что блокировочные уровни изолированности удовлетворяют требованиям ANSI SQL.

Замечание 2. Блокировочные протоколы во второй Таблице определяют блокировочные уровни изолированности, которые, как минимум, сильны настолько же, как и соответствующие, основанные на феноменах, уровни изолированности в Таблице 1. Доказательство этого утверждения приводится в [OOBBGH].

Поэтому блокировочные уровни изолированности как минимум на столько же изолированные, как и одноименные ANSI-уровни. Могут ли они быть более изолированными? Ответ - да, даже на самом нижнем уровне. Для того чтобы устранить феномен, который мы называем "Грязная Запись" (Dirty Write), на уровне Блокировочное НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (Locking READ UNCOMMITTED) по Записи производится долговременная блокировка, когда в определениях ANSI SQL, основанных на аномалиях, не исключается такое аномальное поведение. Например, на ANSI СЕРИАЛИЗУЕМОСТЬ (ANSI SERIALIZABLE).

P0 (Грязная Запись):

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

P0: w1[x]...w2[x]... ((c1 или a1) и (c2 или a2) в любом порядке)

Одним из доводов, почему плох феномен Грязной Записи, является то, что он может нарушить согласованность базы данных. Предположим, что существует ограничение на значения x и y (например x=y). Обе транзакции, и T1, и T2, сохраняют ограничение если выполняются порознь. Однако ограничение легко нарушается, если транзакции одновременно производят операции Записи в x и y в различном порядке. Это может произойти, если не исключены Грязные Записи. Например, если история будет: w1[x]...w2[x]...w2[y]...c2...w1[y]...c1, то "выживают" изменения, сделанные T1 в x, и изменения, сделанные T2 в x. Если T1 записывает 1 в обе ячейки x и y, а T2 записывает 2, то результатом будет x=2, y=1. Что нарушает ограничение x=y.

В работах [GLPT, BHG] и многих других рассматривается необходимость защиты от феномена P0 для возможности автоматического отката транзакций. Без защиты от P0 система не сможет аннулировать изменения, просто восстановив предыдущие значения. Рассмотрим историю: w1[x]...w2[x]...a1. Аннулирование w1[x] и восстановление предыдущего значения x вас не удовлетворит, потому что в результате такого восстановления уничтожится и модификация x, сделанная второй транзакцией w2[x]. В противном случае, если вы не восстанавливаете предыдущие значения x и вторая транзакция тоже выполняет откат, то вы также не можете аннулировать w2[x], просто восстановив значение x, которое было до выполнения этой операции Записи! Вот поэтому даже самые слабые системы блокировки по операции записи производят долговременную блокировку. В противном случае их механизмы восстановления не смогли бы работать.

Замечание 3. Уровни изолированности в ANSI SQL должны быть модифицированы так, чтобы исключить P0 на всех уровнях изолированности.

Теперь мы аргументируем, почему необходимы именно свободные интерпретации для всех трех ANSI-феноменов. Возвратимся и рассмотрим строгие интерпретации:

A1: w1[x]...r2[x]... ((a1 и c2) в любом порядке) (Грязное Чтение)
A2: r1[x]...w2[x]...c2...r1[x]...c1 (Размытое или Неповторимое Чтение)
A3: r1[P]...w2[y in P] ...c2...r1[P]...c1 (Фантом)

Согласно Таблице 1, на уровне изолированности ЗАФИКСИРОВАННОЕ ЧТЕНИЕ исключаются аномалии A1, на уровне ПОВТОРИМОЕ ЧТЕНИЕ исключены аномалии A1 и A2, и на уровне СЕРИАЛИЗУЕМОСТЬ исключаются аномалии A1, и A2, и A3. Рассмотрим историю H1, выполняющую перевод 40 долларов между строками x и y в банковском балансе:

H1: r1[x=50] w1[x=10] r2[x=10] r2[y=50] c2 r1[y=50] w1[y=90] c1

H1 не сериализуема, возникает классическая проблема анализа несогласованности (inconsistent analysis), когда транзакция T1 переводит 40 долларов с x на y, сохраняя размер общей суммы баланса, равный 100. Но транзакция T2 производит операцию Чтения в тот момент, когда баланс находится в несогласованном состоянии при общей сумме равной 60. История H1 не подходит ни под одну из аномалий A1, A2 и A3. В случае A1 одна из транзакций должна выполнить откат. Для A2 элемент данных должен быть прочитан транзакцией повторно. В A3 требуется нарушение какого-нибудь соотношения. Ни что из этого не происходит в H1. Рассмотрим свободную интерпретацию A1, феномен P1:

P1: w1[x]...r2[x]... ((c1 или a1) и (c2 или a2) в любом порядке)

H1 действительно нарушает P1. Поэтому мы должны брать интерпретацию P1, а не A1, как выражение идеи, заключенной в словесном определении ANSI первого феномена. Свободная интерпретация является единственной корректной интерпретацией.

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

H2: r1[x=50] r2[x=50] w2[x=10] r2[y=50] w2[y=90] c2 r1[y=90] c1

H2 не сериализуема - еще одна проблема анализа несогласованности, где T1 видит общий баланс, равный 140. В этой истории ни одна транзакция не читает грязные (т.е. незафиксированные) данные. Таким образом, история не противоречит P1. Также ни один элемент данных не читается дважды и нет нарушающегося предикативного условия. Проблема с H2 состоит в том, что T1 читает значение y, когда значение x уже устарело. Если бы T1 прочитала значение x снова, то оно бы обновилось, но она этого не делает, и A2 к этому случаю не подходит. Заменяя A2 на P2, т.е. свободную интерпретацию, мы решаем эту проблему:

P2: r1[x]...w2[x]... ((c1 или a1) и (c2 или a2) в любом порядке)

H2 будет устранена при попытке второй транзакции w2[x=10] переписать значение переменной, прочитанной до этого первой транзакцией r1[x=50]. Теперь она подходит под определение (P2). И наконец, рассмотрим A3 и историю H3:

A3: r1[P]...w2[y in P] ...c2...r1[P]...c1 (Фантом)
H3: r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1

T1 осуществляет поиск по условию P=<условие поиска> для получения списка служащих. Потом T2 производит вставку нового служащего и потом обновляет z, счетчик служащих в компании. Затем T1 читает значение счетчика служащих, проверяет и находит рассогласование. Ясно, что эта история несериализуема, но она допустима, т.к. не подходит под A3. Не происходит второе чтение по предикату. Снова только свободная интерпретация решает проблему:

P3: r1[P]...w2[y in P]... ((c1 или a1) и (c2 или a2) в любом порядке)

Если запретить P3, то история H3 тоже будет устранена. Ясно, что имели в виду в комитете ANSI, когда составляли спецификацию. Дальнейшая дискуссия направлена на то, чтобы продемонстрировать полученные результаты.

Замечание 4. Строгие интерпретации A1, A2 и A3 имеют существенные недостатки. Правильными являются свободные интерпретации. Определяя P1, P2 и P3, мы пытаемся следовать тому, что имели в виду в ANSI.

Замечание 5. Множество феноменов ANSI SQL неполно. Можно привести примеры нескольких аномалий, которые еще могут возникнуть. Для того чтобы сделать определение блокировки полным, необходимо ввести новые феномены. Определение P3 должно быть пересмотрено. В следующих определениях мы опустили пары (c2 или a2), что не ограничивает возможных историй.

P0: w1[x]...w2[x]... (c1 или a1) (Dirty Write) (Грязная Запись)
P1: w1[x]...r2[x]... (c1 или a1) (Dirty Read) (Грязное Чтение)
P2: r1[x]...w2[x]... (c1 или a1) (Fuzzy or Non-Repeatable Read) (Размытое или Неповторимое Чтение)
P3: r1[P]...w2[y in P]... (c1 или a1) (Phantom) (Фантом)

Заметим, что определение P3, приведенное выше, отличается от определения P3 в ANSI SQL. Определение P3 в ANSI SQL запрещает только операции вставки (и модификации в соответствии с некоторыми интерпретациями), попадающие под область действия предиката, когда определение P3, приведенное выше, запрещает любую операцию записи (вставки, модификации, удаления), попадающую под предикат, по которому была произведена операция чтения.

Предполагаемые определения уровней изолированности ANSI в терминах этих феноменов даны в Таблице 3.

Уровень изолированности | Р0 Грязная запись (Dirty Write) | Р1 Грязное чтение (Dirty Read) | Р2 Размытое чтение (Fuzzy Read) | Р3 Фантом (Phantom)
НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ (READ UNCOMMITTED) | невозможен | невозможен | невозможен | невозможен
ЗАФИКСИРОВАННОЕ ЧТЕНИЕ (READ COMMITTED) | невозможен | невозможен | невозможен | невозможен
ПОВТОРИМОЕ ЧТЕНИЕ (REPEATABLE READ) | невозможен | невозможен | невозможен | невозможен
СЕРИАЛИЗУЕМОСТЬ (SERIALIZABLE) | невозможен | невозможен | невозможен | невозможен

Таблица 3.

В одноверсионных историях оказывается, что P0-, P1-, P2- и P3-феномены являются замаскированными блокировочными версиями. Например, запрещая P0, мы устраняем возможность выполнения операции записи второй транзакцией над элементами, до этого записанными первой транзакцией. Это эквивалентно долговременной блокировке по Записи на элементах данных или предикате. Таким образом, Грязная Запись невозможна на всех уровнях. Подобно этому, запрещение P1 эквивалентно хорошо сформированным чтениям на элементах данных. Запрещение P2 означает долговременную блокировку по Чтению элементов данных. И наконец, запрещение P3 эквивалентно долговременной предикативной блокировке по Чтению. Таким образом, уровни изолированности, определенные в Таблице 3 с помощью феноменов, имеют такое же поведение, как и Блокировочные уровни изолированности, определенные во второй Таблице.

Замечание 6. Определения блокировочных уровней изолированности во второй Таблице эквивалентны феноменологическим определениям в третьей Таблице. Другими словами, P0, P1, P2 и P3 являются скрытыми определениями Блокировочного поведения.

В дальнейшем мы ссылаемся на уровни изолированности, перечисленные в третьей Таблице по их именам из этой таблицы, подразумевая их эквивалентность блокировочным уровням изолированности из второй Таблицы. Когда мы употребляем ANSI НЕЗАФИКСИРОВАННОЕ ЧТЕНИЕ, ANSI ЗАФИКСИРОВАННОЕ ЧТЕНИЕ, ANSI ПОВТОРИМОЕ ЧТЕНИЕ, АНОМАЛЬНАЯ СЕРИАЛИЗУЕМОСТЬ, то имеем в виду определения ANSI из первой Таблицы. (неадекватно, т.к. не включает P0)

В следующем разделе показывается, что большинство коммерческих реализаций изолированности имеют имеют уровни изолированности, которые по нашей классификации попадут между уровнями ЗАФИКСИРОВАННОЕ ЧТЕНИЕ и ПОВТОРИМОЕ ЧТЕНИЕ. Для того чтобы получить четкие уровни изолированности, на которых стали бы видны отличия в этих реализациях, мы предполагаем, что P0 и P1 являются базисом, и добавляем новые феномены по мере необходимости.

4. Другие типы изолированности

4.1. Устойчивость курсора

Устойчивость курсора была разработана для того, чтобы предотвратить феномен потерянной модификации (Lost Update).

P4 (Потерянная Модификация) (Lost Update) Аномалия потерянной модификации происходит в случае, когда транзакция T1 прочитала элементы данных, после нее T2 их модифицировала (возможно, исходя из предыдущего чтения), после чего T1 (основываясь на ранее прочитанном ею значении) модифицирует содержимое элемента данных и фиксируется. В терминах историй это будет:

P4: r1[x]...w2[x]...w1[x]...c1 (Потерянная Модификация) (Lost Update)

Проблема, как показывается в истории H4, заключается в том, что, даже если T2 зафиксируется, сделанная ею модификация элементов данных будет потеряна.

H4: r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1

Конечное значение переменной x равно 130. Его записала транзакция T1. P4 возможен на уровне изолированности ЗАФИКСИРОВАННОЕ ЧТЕНИЕ. Так, H4 допустима, когда запрещен P0 (операция фиксации транзакции, осуществляющей первую операцию записи, происходит до операции записи второй транзакции) или P1 (который требует чтения после записи). Конечно, запрещение P2 устранит P4, так как w2[x] происходит после r1[x] и перед фиксацией или откатом T1. Поэтому аномалия P4 полезна для различия промежуточных уровней изолированности между уровнями: ЗАФИКСИРОВАННОЕ ЧТЕНИЕ и ПОВТОРИМОЕ ЧТЕНИЕ.

Уровень изолированности УСТОЙЧИВОСТЬ КУРСОРА расширяет блокировочное поведение уровня ЗАФИКСИРОВАННОЕ ЧТЕНИЕ для SQL-курсоров, добавляя новую операцию чтения для выборки (Fetch) из курсора rc (означает read cursor, т.е. курсор для чтения) и требуя, чтобы на текущий элемент в курсоре была поставлена блокировка. Блокировка удерживается, пока курсор не будет перемещен или закрыт, возможно операцией фиксации. Реально, выбирающая (Fetching) данные транзакция может модифицировать строку (wc), и в этом случае блокировка по записи на строке будет сохраняться до тех пор, пока транзакция не зафиксируется, даже после передвижения курсора с последующей выборкой (Fetch). Операция rc1[x] и последующая wc1[x] имеют промежуточную операцию w2[x]. Поэтому феномен P4, для этого случая несколько измененный и переименованный в P4C, представлен в следующем виде:

P4C: rc1[x]...w2[x]...wc1[x]...c1 (Lost Update) (Потерянная Модификация)

Замечание 7.
ЗАФИКСИРОВАННОЕ ЧТЕНИЕ <<
УСТОЙЧИВОСТЬ КУРСОРА <<
ПОВТОРИМОЕ ЧТЕНИЕ.

УСТОЙЧИВОСТЬ КУРСОРА широко применяется в SQL-системах для предотвращения потери модификаций строк, читаемых через курсор. В некоторых системах ЗАФИКСИРОВАННОЕ ЧТЕНИЕ реально более сильный уровень, чем УСТОЙЧИВОСТЬ КУРСОРА. Стандарт ANSI это позволяет.

Техника установки курсора на элементы данных, для того чтобы сохранить их в неизменном виде, может быть использована для множества элементов за счет применения множества курсоров. Таким образом, программист может надеяться, что УСТОЙЧИВОСТЬ КУРСОРА даст такой же эффект изолированности, как и у Блокировочного ПОВТОРИМОГО ЧТЕНИЯ на любых транзакциях, оперирующих с небольшим, фиксированным числом элементов данных. Однако этот метод не является общеупотребительным и не всегда работает. Поэтому всегда существуют истории, удовлетворяющие феномену P4 (и, конечно, более общему P2) и не устранимые на уровне УСТОЙЧИВОСТЬ КУРСОРА.

4.2. Изолированность Образа

Транзакция, выполняющаяся на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА, всегда читает данные из образа (зафиксированных) данных, какими они были в момент начала транзакции, называемого Временной Меткой Старта. Он может быть сделан в любое время до первой операции чтения транзакции. Выполнение транзакции на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА никогда не блокируется при попытке выполнить операцию Чтения до тех пор, пока возможно использование данных из Временной Метки Старта. Все операции Записи (модификация, вставка и удаление), выполняемые транзакцией, будут отражаться в этой метке, если транзакция будет обращаться к данным (читать или модифицировать) вторично. После того как для транзакции T снята Временная Метка Старта, все модификации данных, производимые другими транзакциями, становятся для нее невидимыми.

Уровень ИЗОЛИРОВАННОСТЬ ОБРАЗА является разновидностью контроля многоверсионной конкурентности (multiversion concurrency control). Он расширяет Многоверсионный Смешанный Метод, описанный в [BHG], который допускает чтение данных из метка только для читающих транзакций.

Когда транзакция T1 готова к фиксации, она получает Временную Метку Фиксации. Она больше любой существующей Временной Метки Старта или Временной Метки Фиксации. Выполнение транзакции T1 успешно фиксируется только в том случае, если нет ни одной другой транзакции T2, которая имеет Временную Метку Фиксации, попадающий в интервал [Временная Метка Старта, Временная Метка Фиксации] транзакции T1, и пишет в те же элементы данных, что и T1. В противном случае T1 откатывается. Этот способ назван "Выигрывает Первый Зафиксированный" (First-committer-wins). Он устраняет феномен P4 потерянной модификации. Когда транзакция T1 зафиксировалась, то изменения данных, сделанные ею, становятся видны всем транзакциям, у которых Временная Метка Старта больше, чем Временная Метка Фиксации транзакции T1.

Метод Изолированности Образа является многоверсионным (многозначным) (МВ) методом. Он применим там, где одноверсионные (однозначные) (ОВ) истории не смогут однозначно отобразить временные последовательности операций. В любое время каждый элемент данных может иметь несколько своих версий, созданных активными или зафиксированными транзакциями. Операции чтения, выполняемые транзакциями, должны выбирать подходящую версию. Рассмотрим историю H1, приведенную в третьем разделе, которая показывает необходимость P1 при одноверсионном выполнении. При Изолированности Образа та же последовательность операций переносится на многозначную историю:

H1.SI: r1[x0=50] w1[x1=10] r2[x0=50] r2[y0=50] c2 r1[y0=50] w1[y1=90] c1

H1.SI имеет потоки данных сериализуемого выполнения. В [OOBBGM] мы показываем, что все истории с уровня ИЗОЛИРОВАННОСТЬ ОБРАЗА могут быть отображены о однозначные истории с сохранением зависимостей между потоками данных. Говорят, что МВ-истории Эквивалентны по Представлениям (View Equivalent) ОВ-историям. Этот подход описывается в [BHG], Глава 5. Например, МВ-история H1.SI может быть отображена в сериализуемую ОВ-историю.

H1.SI.SV: r1[x=50] r1[y=50] r2[x=50] r2[y=50] c2 w1[x=10] w1[y=90] c1

Отображение МВ-историй в ОВ-истории является единственным существенным основанием, благодаря которому мы должны разместить ИЗОЛИРОВАННОСТЬ ОБРАЗА в Иерархии Изолированности.

ИЗОЛИРОВАННОСТЬ ОБРАЗА не является сериализуемой, потому что операции чтения транзакции выполняются над одним экземпляром данных, а операции записи над другим. Для примера рассмотрим следующую однозначную историю:

H5: r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=-40] w2[x=-40] c1 c2

H5 не является сериализуемой и имеет такие же межтранзакционные потоки данных, которые могут произойти на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА (нет выбора версии, читаемой транзакциями). Предполагается, что обе транзакции, модифицирующие значения x и y, сохраняют ограничение, что сумма x+y всегда должна быть положительна. При полной изолированности обе транзакции сохраняют ограничение, а в примере H5 при одновременном выполнении нарушают его.

Нарушение ограничения (constrant violation) является характерным и основным типом аномалий, возникающих при конкурентном выполнении транзакций. Индивидуальные базы данных удовлетворяют ограничениям, заданным на множествах элементов данных (например уникальность ключей, целостность ссылок, репликация ссылок в двух таблицах и т.д.). Все вместе они формируют инвариантный ограничительный предикат базы данных C(DB). Предикат принимает значение Истина, если состояние базы данных DB не противоречит ограничениям, Ложь в противном случае. Для сохранения согласованности базы данных транзакции должны удовлетворять ограничительному предикату: если состояние базы данных непротиворечиво до начала транзакции, то оно должно остаться непротиворечивым и после ее фиксации. Если транзакция читает содержимое базы данных, находящейся в противоречивом состоянии, то в результате ее выполнения получится аномалия нарушения ограничения. Подобные нарушения ограничений называются противоречивый анализ (inconsistent analysis) [DAT].

A5 (Нарушение ограничения на элементах данных) Предположим, что C() - ограничение между двумя элементами базы данных x и y. Ниже приводятся две аномалии, возникающие при нарушении ограничения.

A5A Искажение Чтения (Read Skew). Предположим, что транзакция T1 читает значение x. Затем другая транзакция T2 модифицирует значения x и y и фиксируется. Если теперь T1 прочитает значение y снова, она может обнаружить нарушение целостности, и поэтому результат ее работы тоже будет содержать нарушение. В терминах историй мы имеем аномалию:

A5A: r1[x]...w2[x]...w2[y]... c2...r1[y]...(c1 или a1) (Искажение Чтения) (Read Skew)

A5B Искажение Записи (Write Skew). Предположим, что транзакция T1 читает значения x и y, которые согласованы с предикатом C(). Затем другая транзакция T2 читает значения x и y, модифицирует x и фиксируется. После этого T1 модифицирует значение y. Если на x и y было какое-нибудь ограничение, то оно может нарушиться. В терминах историй:

A5B: r1[x]...r2[y]...w1[y]... w2[x]...(c1 или c2) (Искажение Записи) (Write Skew)

Феномен размытого чтения (P2) является частным случаем Искажения Чтения, где x=y. Обычно транзакция читает два различных, но взаимозависимых элемента (например целостность ссылок). Искажение Записи (Write Skew) (A5B) может возникнуть из ограничения целостности в банковском примере. Предположим, что балансам счетов разрешается быть отрицательными, пока их общая сумма положительна. Здесь возникает аномалия, похожая на историю H5.

Если исключена аномалия P2, то становится невозможным появление в историях ситуаций, похожих на A5A и A5B, т.к. обе ситуации имеют операцию записи транзакции T2 в элемент данных, предварительно прочитанный незафиксированной транзакцией T1. Поэтому феномены A5A и A5B полезны только для классификации уровней изолированности, которые по уровню изолированности не сильнее уровня ПОВТОРИМОЕ ЧТЕНИЕ.

ANSI SQL определение уровня ПОВТОРИМОЕ ЧТЕНИЕ в строгой интерпретации осуществляет защиту от нарушения строковых ограничений только в частных примитивных случаях и не осуществляет таковой в общем виде. Конкретно, Блокировочное ПОВТОРИМОЕ ЧТЕНИЕ, определенное в Таблице 2, осуществляет защиту от нарушений строковых ограничений (row constraint violations), а ANSI SQL-определение из Таблицы 1, запрещая аномалии A1 и A2, - нет.

Возвращаясь к рассмотрению уровня ИЗОЛИРОВАННОСТЬ ОБРАЗА, можно заметить, что по изолированности он удивительно силен. Сильнее, даже чем ЗАФИКСИРОВАННОЕ ЧТЕНИЕ.

Замечание 8.
ЗАФИКСИРОВАННОЕ ЧТЕНИЕ << ИЗОЛИРОВАННОСТЬ ОБРАЗА

Доказательство. На уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА механизм "Выигрывает-Первый-Зафиксированный" устраняет феномен P0 (Грязная Запись), а механизм снятия меток не допускает P1 (Грязное Чтение). Отсюда следует, что ИЗОЛИРОВАННОСТЬ ОБРАЗА не слабее, чем ЗАФИКСИРОВАННОЕ ЧТЕНИЕ. Так как феномен A5A возможен на уровне ЗАФИКСИРОВАННОЕ ЧТЕНИЕ, но невозможен на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА за счет работы механизма снятия отпечатков, то ЗАФИКСИРОВАННОЕ ЧТЕНИЕ << ИЗОЛИРОВАННОСТЬ ОБРАЗА.

Заметим, что в однозначной интерпретации сложно показать, как на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА будут устраняться истории с феноменом P2. Аномалия A2 на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА произойти не может, так как транзакции на этом уровне даже в случае промежуточной модификации, сделанной другой транзакцией, будут читать одно и то же значение элемента данных. Очевидно, что на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА может произойти феномен Искажение Записи (A5B) (например в истории H5), а в простых однозначных реализациях историй запрещение феномена P2 устраняет A5B. Поэтому на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА допускаются истории с аномалиями, которые не допустимы на уровне ПОВТОРИМОЕ ЧТЕНИЕ.

Аномалия A3 не применима к случаю ИЗОЛИРОВАННОСТИ ОБРАЗА. Повторное чтение транзакции по предикату после модификации данных другой транзакцией будет всегда во всех случаях давать старый набор данных. Аномалии вида A3 применимы к уровню ПОВТОРИМОЕ ЧТЕНИЕ. ИЗОЛИРОВАННОСТЬ ОБРАЗА не допускает историй, содержащих феномен A3, но допускает с феноменом A5B, а у ПОВТОРИМОГО ЧТЕНИЯ все наоборот.

Замечание 9.
ПОВТОРИМОЕ ЧТЕНИЕ >> << ИЗОЛИРОВАННОСТЬ ОБРАЗА

Однако ИЗОЛИРОВАННОСТЬ ОБРАЗА не устраняет P3. Рассмотрим следующее ограничение: множество задач, определенное с помощью предиката, не могут иметь общую сумму часов, большую 8. T1 читает по предикату, определяет, что сумма равна 7 часам и добавляет новую задачу продолжительностью 1 час. Конкурирующая транзакция T2 делает то же самое. Это произошло потому, что транзакции манипулируют с различными экземплярами одних элементов данных (и так же с различными индексными полями). Такой сценарий может произойти на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА и не устраним с помощью механизма "Выигрывает-Первый-Зафиксированный". В любой эквивалентной последовательной истории такой сценарий приводит к возникновению феномена P3.

Возможно, наиболее впечатляюще то, что на уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА нет фантомов (в строгой интерпретации A3 определения ANSI). Каждая транзакция никогда не видит модификаций, производимых конкурирующими транзакциями. Таким образом, без дополнительных ограничений в подсекции 4.28 в [ANSI] можно сформулировать следующее: (напомним, что определенная в Таблице 1 АНОМАЛЬНАЯ СЕРИАЛИЗУЕМОСТЬ соответствует ANSI SQL определению СЕРИАЛИЗУЕМОСТЬ).

Замечание 10.
На уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА устраняются аномалии A1, A2 и A3. Поэтому для него выполняется следующее утверждение: АНОМАЛЬНАЯ СЕРИАЛИЗУЕМОСТЬ << ИЗОЛИРОВАННОСТЬ ОБРАЗА.

На уровне ИЗОЛИРОВАННОСТЬ ОБРАЗА разрешается выполняться транзакциям с очень старыми метками. Это позволяет им иметь достаточно продолжительное время выполнения, благодаря чему имеется возможность наблюдать эволюцию базы данных. Конечно, если транзакция модифицирует данные и имеет очень старые метки, то при попытке модификации данных, уже модифицированных другими транзакциями, ее выполнение будет откачено назад.

Достаточно простая реализация уровня ИЗОЛИРОВАННОСТЬ ОБРАЗА была предложена Ридом (Reed) в [REE]. Существует несколько коммерческих реализаций такой много-версионной модели базы данных. InterBase 4 фирмы Borland [THA] и ядро, лежащее в основе Exchange System фирмы Microsoft, оба реализуют ИЗОЛИРОВАННОСТЬ ОБРАЗА с механизмом "Выигрывает-Первый-Зафиксированный". Этот механизм заставляет систему запоминать все модификации (блокировки по записи), принадлежащие каждой транзакции, которая фиксируется после снятия Временной Метки Старта для каждой активной транзакции. Он откатывает выполнение транзакции, если сделанные ею модификации конфликтуют с заполненными модификациями, сделанными другими транзакциями.

Совершенно ясно, что "оптимистический" подход ИЗОЛИРОВАННОСТИ ОБРАЗА контроля конкурентного выполнения транзакций имеет преимущество для только читающих транзакций, но его преимущества для модифицирующих транзакций до сих пор обсуждаются. Возможно, этот метод плох для долговременных модифицирующих данные транзакций, выполняющихся одновременно с кратковременными. Кратковременные транзакции будут фиксировать свои модификации быстрее, следовательно, поскольку "Выигрывает-Первый-Зафиксировавшийся", долговременные транзакции, вероятнее всего, будут постоянно откатываться. (Заметим, что такой сценарий также проблематичен и в блокировочных реализациях, и если принять решение не использовать долговременные модифицирующие транзакции, то ИЗОЛИРОВАННОСТЬ ОБРАЗА тоже будет применима.) Конечно, в случае, когда кратковременные транзакции конфликтуют минимально, а долговременные только читают данные, ИЗОЛИРОВАННОСТЬ ОБРАЗА должна дать хорошие результаты. В случае сильной конкуренции между транзакциями сопоставимой длины ИЗОЛИРОВАННОСТЬ ОБРАЗА предлагает классический оптимистический подход. Мнения относительно его эффективности расходятся.

4.3. Другие многоверсионные системы

Существуют другие модели многоверсионности. Некоторые коммерческие продукты поддерживают версии объектов, но ограничивают применение метода ИЗОЛИРОВАННОСТЬ ОБРАЗА только для читающих транзакций. (Например, SQL-92, Rdb, SET TRANSACTION READ ONLY в некоторых других базах данных [MS, HOB, DRA]; Postgress и Illustra [STO, ILL] поддерживают долговременный тип таких версий (long-term) и предоставляют мигрирующие во времени (time-travel) запросы.) Другие реализации допускают модифицирующие транзакции, но не поддерживают защиту "Выигрывает-Первый-Зафиксировавшийся". (Например, уровень изолированности НЕПРОТИВОРЕЧИВОСТЬ ЧТЕНИЯ (READ CONSISTENCY) в Oracle [ORA].)

На уровне НЕПРОТИВОРЕЧИВОСТЬ ЧТЕНИЯ в Oracle каждому SQL-оператору перед началом его выполнения дается самое свежее зафиксированное состояние базы данных. Это похоже на то, как если бы Временная Метка Старта транзакции снимался бы для каждого оператора. Элементы курсора имеют значения, которые они имели в момент открытия курсора. Описанный ниже механизм перевычисляет подходящие версии строк и операторных отпечатков. Операции Вставки, Модификации и Удаления строк защищаются блокировкой по Записи для того, чтобы работал механизм "Выигрывает-Первый-Записавший", отличающийся от механизма "Выигрывает-Первый-Зафиксировавшийся". НЕПРОТИВОРЕЧИВОСТЬ ЧТЕНИЯ сильнее, чем ЗАФИКСИРОВАННОЕ ЧТЕНИЕ (она исключает потерю модификации курсора (P4C)), но допускает неповторимое чтение (P3), потерю модификации в общем случае (P4) и искажение чтения (A5A). ИЗОЛИРОВАННОСТЬ ОБРАЗА не допускает P4 или A5A.

Если пристально посмотреть на стандарт SQL, то можно сказать, что он трактует каждый оператор как атомарный. В начале каждого оператора имеется сериализуемая подтранзакция (или отпечаток). Можно представить иерархию уровней изолированности, определяемых различными вариантами комбинации оператора и присоединенного к нему оператора. (Например, в Oracle, операция выборки (fetch) из курсора имеет метку, снимаемый в момент открытия курсора.)

Уровень изолированности | Р0 Грязная Запись (Dirty Write) | Р1 Грязное Чтение (Dirty Read) | Р4С Потерянная Модификация Курсора (Cursor Lost Update) | P4 Потерянная Модификация (Lost Update) | Р2 Размытое Чтение (Fuzzy Read) | Р3 Фантом (Phantom) (Read Skew) | A5A Искажение Чтения (Write Skew) | A5B Искажение Записи
НЕЗАФИКСИ- РОВАННОЕ ЧТЕНИЕ (READ UNCOMMITTED) ==Степень 1 | невозможен | возможен | возможен | возможен | возможен | возможен | возможен | возможен
ЗАФИКСИ- РОВАННОЕ ЧТЕНИЕ (READ COMMITTED) ==Степень 2 | невозможен | невозможен | возможен | возможен | возможен | возможен | возможен | возможен
УСТОЙЧИВОСТЬ КУРСОРА (CURSOR STABILITY) | невозможен | невозможен | невозможен | иногда возможен | иногда возможен | возможен | возможен | иногда возможен
ПОВТОРИМОЕ ЧТЕНИЕ (REPEATABLE READ) | невозможен | невозможен | невозможен | невозможен | невозможен | невозможен | невозможен | невозможен
ИЗОЛИРО- ВАННОСТЬ ОБРАЗА (SNAPSHOT ISOLATION) | невозможен | невозможен | невозможен | невозможен | невозможен | иногда возможен | невозможен | возможен
ANSI SQL СЕРИАЛИЗУ- ЕМОСТЬ (SERIALIZABLE) ==Степень 3 ==Повторимое Чтение Дэйт, IBM, Tandem,... | невозможен | невозможен | невозможен | невозможен | невозможен | невозможен | невозможен | невозможен

Таблица 4.

Резюме и Выводы

Подводя итоги, можно сказать, что оригинальные ANSI SQL-определения уровней изолированности имеют серьезные недостатки (как показывается в третьем разделе). Словесные определения противоречивы и неполны. Не исключается феномен Грязной Записи (P0). В Замечании 5 мы даем рекомендации по тому, как модифицировать определения уровней изолированности ANSI SQL, чтобы сделать их эквивалентными Блокировочным уровням изолированности в [GLPT].

В ANSI SQL уровень изолированности ПОВТОРИМОЕ ЧТЕНИЕ мыслился как уровень, на котором исключаются все аномалии, кроме ФАНТОМА. Определение, данное в терминах аномалий в Таблице 1, не достигает этой цели, в отличие от блокировочного определения из второй Таблицы. Выбор ANSI-термина ПОВТОРИМОЕ ЧТЕНИЕ является крайне неудачным: (1) повторимые операции чтения не дают повторимых результатов" (2) в индустрии этот термин уже занят и обозначает следующее: в некоторых продуктах повторимое чтение означает сериализуемость. Мы рекомендуем найти для этого уровня новое название.

Некоторые коммерчески популярные уровни изолированности, по степени изолированности попадающие в интервал между уровнями ПОВТОРИМОЕ ЧТЕНИЕ и СЕРИАЛИЗУЕМОСТЬ из Таблицы 3, справляются с некоторыми новыми феноменами и аномалиями в четвертом Разделе. Все уровни изолированности, о которых упоминается в этой статье, можно классифицировать, как показано на Рисунке 1 и в Таблице 4. Чем выше на Рисунке расположен уровень, тем выше на нем степень изолированности (см. Определение в начале Раздела 4.1). Уровни классифицируются с помощью линий между ними с надписанными феноменами или аномалиями.

Рисунок 1.

Заметим, что, несмотря на то, что уровни ограниченной изолированности для многоверсионных систем реализованы во многих продуктах, не существует работ по их классификации. Во многих приложениях борьба между блокировками устраняется введением уровней изолированности типа УСТОЙЧИВОСТИ КУРСОРА или НЕПРОТИВОРЕЧИВОСТИ ЧТЕНИЯ в Oracle. ИЗОЛИРОВАННОСТЬ ОБРАЗА имеет лучшие характеристики, чем любой из таких уровней: исключаются аномалия потерянной модификации, некоторые фантомные аномалии (например описанная в ANSI SQL), никогда не блокируются только читающие транзакции и читающие транзакции никогда не блокируют модифицирующих.

Благодарности

Мы выражаем благодарность Крису Ларсону (Chris Larson) из Microsoft, Алану Рейтеру (Alan Reiter), которые нашли несколько новых аномалий в ИЗОЛИРОВАННОСТИ ОБРАЗА, Франко Путзолу (Franco Putzolu) и Анил Нори (Anil Nori) из Oracle, Майку Убеллу (Mike Ubell) из компании Illustra и всем анонимным рефери из SIGMOD за ценные предложения, которые улучшили эту статью. Сашил Джодиа (Sushil Jajodia), V.Atluri и E.Bertino, которые прислали нам черновой вариант своей работы [ABJ], касающейся уровней ограниченной изолированности для многозначных историй.

Литература

[ANSI] ANSI X3.135-1992, American National Standart for Information Systems - Database Language - SQL, November, 1992.

[ABJ] V.Atluri, E.Bertino, S.Jajodia, "A Theoretical Formuation for Degrees of Isolation in Databases", Technical Report, George Mason Iniversity, Fairfax, VA, 1995.

[BHG] P.A. Bernstein, V. Hadzilacos, N. Goodman, "Concurrency Control and Recovery in Database Systems", Addison-Wesley, 1987.

[DAT] C.J. Date, "An Introduction to Database Systems", Fifth Edition, Addison-Wesley, 1990.

[DB2] C.J. Date and C.J. White, "A Guide to DB2", Third Edition, Addison-Wesley, 1989.

[EGLT] K.P. Eswaran, J. Gray, R. Lorie, I. Traiger, "The Notions of Consistency and Predicate Locks in a Database System", CACM V 19.11, pp. 624-633, Nov. 1978.

[GLPT] J. Gray, R. Lorie, G. Putzolu and, I. Traiger, "Granularity of Locks and Degrees of Consistency in a Shared Data Base", in Readings in Database Systems, Second Edition, Chapter 3, Michael Stonebraker, Ed., Morgan Kaufmann 1994 (ordinally published in 1997).

[GR] J. Gray and A. Reuter, "Transaction Processing: Concepts and Techniques", Corrected Second Printing, Morgan Kaufmann 1993, Section 7.6 and following.

[HOB] L Hobbs and K. England, "Rdb/VMS, A Comprehensive Guide", Digital Press, 1991.

[ILL] Illustra Information Technologies, "Illustra User"s Guide", Illustra Information Technologies, Oakland, CA. 1994.

[MS] J. Meiton and A.R. Simon, "Understanding The New SQL: A Comlete Guide", Morgan Kaufmann, 1993.

[OOBBGM] P. O'Neil, E. O'Neil, H. Berenson, P. Bernstein, J. Gray, J. Melton, "An Investigation of Transactional Isolation Levels", UMass/Boston Dept. of Math &" C.S. Preprint.

[ORA] "PL/SQL User's Guide and Reference, Version 1.0", Part. 800-V1.0, Oracle Corp., 1989.

[PAR] C. Papadimitriou, "The Theory of Database Concurrency Control", Computer Science Press, 1986.

[PON] P. O'Neil, "Database: Principles, Programming, Performance", Morgan Kaufmann, 1994, Section 9.5.

[REE] D. Reed, "Implementing Atomic Actions On Decentralized Data", ACM TOCS 1.1, 1981, pp. 3-23.

[STO] M.J. Stonebraker, "The Design of the POSTGRES Storage System", 13th VLDB, 1987, reprinted in Readings in Database Systems, Second Edition, M.J. Stonebraker, Ed., Morgan Kaufmann, 1994.

[THA] M. Thakur, "Transaction Models in InterBase 4", Proceedings of the Borland International Conference, June, 1994.

Hal Berenson, Microsoft Corp. haroldb@microsoft.com
Phil Bernstein, Microsoft Corp. philbe@microsoft.com
Jim Gray, U.C. Berkeley gray@crl.com
Jim Melton, Sybase Corp. jim.melton@sybase.com
Elizabeth O'Neil, UMass/Boston eoneil@cs.umb.edu
Patrick O'Neil, UMass/Boston poneil@cs.umb.edu

*)Переведено из Proceeding of the ACM SIGMOO International Conference, May, 1995, с разрешения ACM 1996 (с) ACM, Inc

Системы Управления Базами Данных # 2/96
Bottom Line