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

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

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

Таблица 1.

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

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

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

Таблица 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.

Таблица 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) из курсора имеет метку, снимаемый в момент открытия курсора.)

Таблица 4.

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

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

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

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