Теория транзакций с примерами из Microsoft SQL Server

Думаю, многие из вас работали с транзакциями и представляют, как применить к базе данных консистентную последовательность операций. Сегодня мы узнаем, что происходит с транзакцией, когда мы отправляем ее в СУБД. Мы познакомимся с классической теорией транзакций и тем, какие существуют подходы для формирования корректных расписаний. Кроме того, постараемся связать эту теорию с практикой на примере известной СУБД Microsoft SQL Server. (Сегодня будет много информации, приготовьтесь!)

Сериализуемые расписания

Транзакции

Начнем с определения того, что такое транзакция:

Транзакция - это совокупность операций, выполняемых прикладной программой, которые переводят согласованное состояние базы данных в согласованное, если:

• отсутствуют помехи со стороны других приложений;
• транзакция выполнена полностью.

В MS SQL Server существует 2 типа транзакций:

1. Неявные - отдельные операции INSERT, UPDATE или DELETE.
2. Явные - набор операций языка T-SQL, начинающийся с инструкции BEGIN TRANSACTION и заканчивающийся COMMIT или ROLLBACK.

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

BEGIN TRANSACTION
UPDATE tbl1
    SET x = 10
    WHERE y = 1
    IF @@ERROR <> 0
        ROLLBACK
UPDATE tbl2
    SET x = 10
    WHERE y = 1
    IF @@ERROR <> 0
        ROLLBACK
COMMIT

Аномалии транзакций

При параллельном выполнении транзакций возникают различные проблемы, связанные с логикой работы с операциями. Рассмотрим наиболее распространенные из них на примерах из SQL сервера:

1) Потерянное обновление. При обновлении поля двумя транзакциями одно из изменений теряется.

2) Грязное чтение. Чтение данных, полученных в результате действия транзакции, которая после этого откатится.

3) Неповторяющееся чтение. Возникает, когда в течение одной транзакции при повторном чтении данные оказываются перезаписанными.

4) Фантомное чтение. Отличие от предыдущей аномалии в том, что при повторном чтении одна и та же выборка дает разные множества строк.

Вычислительная модель

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

1. Элементарные операции, определенные над объектами данных.
2. Транзакции: последовательности или частично упорядоченные множества элементарных операций.
3. Расписания (или истории), описывающие конкурентное выполнение транзакций.
4. Критерии корректности расписаний (историй).
5. Алгоритмы управления транзакциями, обеспечивающие получение корректных расписаний.

Сегодня мы будем рассматривать транзакции в контексте страничной модели. В этой модели база данных представляется как набор независимых страниц ` (x, y, z) `, над которыми возможны две атомарные операции: read и write с полным или частичным порядком внутри транзакции.

Критерии корректности

Первоначально определим понятие истории. История - упорядоченная совокупность операций нескольких транзакций, включая операции завершения транзакции (commit, abort). Расписанием называется префикс истории. Пример (индексы соответствуют транзакциям): ` r_1(x) r_2(x) w_1(x) w_2(x) c_1 c_2 `

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

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

Семантика Эрбрана

С помощью этого понятия определяются последующие сериализуемости. Семантика Эрбрана основывается на двух предположениях:

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

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

Сериализуемость по конечному состоянию

Расписания эквивалентны по конечному состоянию, если:

• равны множества операций
• семантики Эрбрана равны для всех элементов данных

Расписание называется сериализуемым по конечному расписанию (FSR), если оно эквивалентно серийному по конечному состоянию. Пример неэквивалентных расписаний:

Этот тип сериализуемости решает проблему потери обновления, но с другими аномалиями справиться он не в силах.

Сериализуемость по видимому состоянию

В дополнение к условиям предыдущей эквивалентности для эквивалентности по видимому состоянию требуется, чтобы все операции чтения в расписаниях следовали после одинаковых операций записи. Пример расписания, сериализуемого по видимому (VSR), но не по конечному состоянию: ` w_1(x) r_2(x) r_2(y) w_1(y) c_1 c_2 `

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

Сериализуемость по конфликтам

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

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

1. Перестановка соседних операций чтения
2. Перестановка соседних операций над разными элементами

Диспетчеры и протоколы

Функционирование диспетчера

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

В MS SQL Server, так же как и во многих других СУБД есть два вида конкурентного доступа (протоколов):

1. Пессимистичные. Для предотвращения нарушения сериализуемости двумя транзакциями применяются блокировки.
2. Оптимистичные. Протокол основывается на предположении маловероятности одновременного изменения данных двумя транзакциями. В случае нарушения сериализуемости транзакция обрывается.

Протокол Two Phase Locking

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

В SQL сервере используется модификация 2PL, именуемая SS2PL. К правилу, использующемуся в базовом протоколе добавляется strict - все полученные замки на запись сохраняются до завершения транзакции и strong - все замки удерживаются до завершения транзакции. При этом, в СУБД есть несколько режимов блокировок. Выбор режима зависит от типа ресурса, который требуется заблокировать. На уровне строки или страницы можно применить блокировки следующих режимов:

1. Разделяемая. Блокировка занимает ресурс только для чтения. Несколько транзакций могут блокировать этот ресурс таким образом и читать из него данные, но ни один процесс не сможет в него что-либо записать.
2. Монопольная. Резервирует ресурс для выполнения операций INSERT, UPDATE, DELETE. На ресурс может быть установлена только одна блокировка такого типа, причем блокировки других режимов также не могут быть установлены вместе с ней.
3. Обновления. Блокировка такого типа может быть установлена на ресурс, только если на нем еще не установлена другая обновляющая или монопольная блокировка. В случае установки ее на ресурс с разделяемой блокировкой, она накладывает на ресурс еще одну разделяемую блокировку. При этом, если модифицирующая объект транзакция подтверждается, то она преобразовывается в монопольную.

Для таблиц помимо разделяемой и монопольной можно также использовать три других типа блокировок:

1. Разделяемая с намерением. Защищает запрошенные или полученные разделяемые блокировки на некоторых ресурсах на более низком уровне иерархии.
2. Монопольная с намерением. Защищает запрошенные или полученные монопольные блокировки на некоторых ресурсах на более низком уровне иерархии.
3. Разделяемая с монопольным намерением. Защищает запрошенные или полученные совмещаемые блокировки на всех ресурсах более низкого уровня иерархии, а также блокировки с намерением на некоторых ресурсах более низкого уровня.

Проблемы 2PL

Одной из главных проблем блокирующих протоколов является возникновение тупиков (взаимоблокировок). Под тупиками понимаются ситуации, когда две транзакции блокируют друг друга. Небольшой пример:

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

При этом может возникнуть новая проблема - голодание. Этим термином описывается ситуация, когда одна и та же транзакция становится жертвой разрешения тупика при каждом новом запуске. Для предотвращения этой проблемы можно использовать первоначальные отметки времени поступления транзакции при выборе жертвы. В SQL сервере вы можете присвоить параметру DEADLOCK_PRIORITY одно из 21 значений (от -10 до 10) для выбора разных уровней приоритета взаимоблокировки.

Кроме того, существует еще один способ борьбы с тупиками. Для преждевременного завершения транзакции можно установить ограничение по времени. Если время ожидания блокировки превышает это ограничение, транзакция обрывается. В SQL сервере используется следующий синтаксис: SET LOCK_TIMEOUT 4000

Snapshot Isolation

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

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

Уровни изоляции в MS SQL Server

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

Read Uncommitted

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

Read Committed

Существует две формы уровня изоляции Read Committed - для пессимистичной и оптимистичной моделей выполнения. В этом подразделе описывается пессимистичный вариант, оптимистичному соответствует уровень Read Committed Snapshot.

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

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

Repeatable Read

В отличие от предыдущего уровня изоляции, Repeatable Read вешает разделяемые блокировки на все считываемые данные и удерживает их до тех пор, пока транзакция не будет подтверждена или отменена. Поэтому в этом случае многократное выполнение запроса внутри транзакции всегда будет возвращать один и тот же результат. Недостатком этого уровня изоляции является дальнейшее ухудшение одновременного конкурентного доступа, поскольку период времени, в течение которого другие транзакции не могут обновлять те же самые данные, значительно дольше, чем в случае уровня Read Committed.

Тем не менее, этот уровень изоляции не препятствует другим инструкциям вставлять новые строки, которые включаются в последующие операции чтения, вследствие чего могут появляться фантомы.

Serializable

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

Read Committed Snapshot

Последние два уровня используются в оптимистичном контексте. Read Committed Snapshot применяется на уровне инструкции, что означает, что что любая другая транзакция будет читать зафиксированные значения в том виде, в каком они существуют на момент начала этой инструкции. Для выборки строк для обновлений этот уровень изоляции возвращает версии строк в фактические данные и устанавливает на выбранных строках блокировки обновлений. Реальные строки данных, которые требуется изменить, получают монопольные блокировки.

Snapshot

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

Заключение

Сегодня мы познакомились с самыми основами теории транзакций и посмотрели, какие из них нашли свое применение в промышленной СУБД. Пост основывался на материалах лекций Новикова Б. А. и книге Душана Петковича Microsoft SQL Server 2012.