Часть четвертая
Журнал «Открытые системы» продолжает публикацию обзорных статей, посвященных состоянию технологий управления транзакциями в системах баз данных.
В Части 1, которая была опубликована в апрельском выпуске журнала за 2002 год, содержались формальное и неформальное определение транзакции, а также рассматривались менеджер транзакций и журнал транзакций. В Части 2 (Открытые системы, 2002, №5) речь шла об обработке сервером баз данных отказов информационной системы, а также о поддержке свойств атомарности, сохранности и непротиворечивости. В Части 3 (Открытые системы, 2002, №11) рассматривалась проблема изолированности транзакций, а также подробно описывались техники блокирования и многоверсионности для обеспечения изолированности.
Стратегии обработки транзакций
При параллельной работе транзакции конфликтуют за объекты данных, к которым они обращаются. В предыдущих частях были рассмотрены зависимости транзакций и порождаемые ими феномены. Наличие зависимостей транзакций D0, D1, D2 в истории транзакций свидетельствует о конфликте этих транзакций.
На данный момент широко известны следующие стратегии обнаружения и разрешения конфликтов при параллельной работе транзакций.
Оптимистическая стратегия. Основным предположением является то, что любая транзакция T, как правило, работает «одна» и никакая другая транзакция T? не изменяет ни множество чтения, ни множество записи транзакции T до момента ее фиксации. Все конфликты чтения/записи, ограничения целостности проверяются в момент фиксации транзакции T. Транзакция T фиксируется в том и только в том случае, когда от момента ее старта и до момента ее фиксации отсутствовали описанные выше конфликты с любой другой параллельной транзакцией T?. Во всех остальных случаях транзакция T откатывается.
При таком протоколе работы транзакция T не блокирует каким-либо образом объекты данных, к которым она обращается.
Особенности этого протокола — долгая фиксация (проверки ограничений целостности и наличия конфликтов, перенос данных в базу данных) и быстрая работа при выполнении действий над данными в течение работы транзакции (ничто не блокируется, ничто не проверяется).
Такой протокол работает плохо, когда множества чтения и записи коротких и длинных транзакций пересекаются: длинные транзакции фиксируются относительно редко, а для коротких транзакций велик процент откатов по причине разрешения конфликтов только на стадии фиксации. В этом состоит существенный недостаток позднего обнаружения конфликтов. Однако если прикладные задачи построены так, что множества чтения и записи разных транзакций пересекаются редко, то оптимистическая стратегия дает существенный выигрыш в производительности за счет отсутствия проверок взаимодействий с другими транзакциями в процессе работы транзакции.
Пессимистическая стратегия. Основное предположение состоит в том, что T работает параллельно с другими транзакциями, и они ей «мешают». Другими словами, как правило, найдется хотя бы одна транзакция T?, которая изменяет множество чтения и (или) множество записи транзакции T до момента ее фиксации. Все конфликты чтения/записи, ограничения целостности проверяются в процессе работы транзакции T.
При таком протоколе работы транзакция T каким-либо образом блокирует объекты данных, к которым она обращается, предотвращая тем самым запись другими транзакциями объектов, блокированных на чтение и любых действий других транзакций над объектами, блокированными на запись.
Особенности этого протокола — быстрая фиксация (проверки ограничений целостности и наличия конфликтов при выполнении операции COMMIT отсутствуют) и медленная работа при выполнении действий над данными в течение работы транзакции (в процессе работы объекты блокируются, проверяются все ограничения).
Такой протокол требует наличия механизма блокировок, которые накладываются на объекты данных перед выполнением операции и удерживаются или не удерживаются до стадии фиксации транзакции. Для хранения блокировок требуются дополнительные ресурсы, но наиболее дорогой составляющей частью механизма является проверка блокировок — не заблокирован ли уже тот объект, который собирается блокировать транзакция в данный момент времени. Также необходим компонент обнаружения и разрешения взаимных блокировок (deadlock).
Протокол хорошо работает, когда множества чтения и записи коротких и длинных транзакций пересекаются: длинные транзакции фиксируются и вынуждены ожидать только фиксации коротких транзакций. При разрешении конфликтов по факту их возникновения процент откатов коротких транзакций будет гораздо ниже, чем при использовании оптимистической стратегии («дешевле ждать, чем откатываться»). В этом состоит существенное преимущество раннего обнаружения конфликтов; откаты же возможны только при возникновении взаимных блокировок. Но если прикладные задачи построены так, что множества чтения и записи разных транзакций пересекаются редко, то протокол не дает существенного выигрыша в производительности из-за присутствия проверок взаимодействий с другими транзакциями в процессе работы транзакции.
Спекулятивная стратегия. Основное предположение состоит в том, что транзакция Т работает параллельно с другими транзакциями, потенциальные конфликты распознаются в процессе работы, как только они возникают, но обнаружение таких конфликтов не влечет ни задержку выполнения таких транзакций (как при пессимистической стратегии) ни откат (как при оптимистической стратегии).
Операции записи объекта данных х никогда не производятся «вслепую», т. е. без предварительного чтения объекта х. Операция записи происходит над локальной копией объекта х в рабочем пространстве транзакции Т, и результат операции становится видимым для других транзакций только после фиксации Т.
Если какая-либо транзакция T?, выполняющаяся параллельно с T, читает объект х, то образуется теневая копия транзакции T? — T??. Транзакция T? продолжает выполняться в предположении, что она успеет зафиксироваться раньше, чем транзакция Т. В этом случае нет смысла откатывать Т, как это было бы сделано при оптимистической стратегии (T? отработала так, как если бы она полностью завершилась до начала T).
Если же транзакция Т фиксируется раньше Т?, то вместо выполнения полного отката T?, эта транзакция заменяется своей «тенью» T??, а выполнение транзакции продолжается этой тенью в точности так, как если бы транзакция Т стартовала и зафиксировалась бы перед стартом T?.
В этом и состоит «спекулятивный порядок сериализации» (Speculated Order of Serialisation). Основная идея спекулятивного протокола — поддерживать достаточное число теней, чтобы обеспечить возможность продолжения любой транзакции с момента образования ее теневой копии, а не производить ее полный рестарт.
Опишем один из вариантов реализации спекулятивной стратегии — с использованием k теней транзакций. У транзакции T есть k теней: одна оптимистическая тень T0, которая выполняется в предположении, что T фиксируется раньше всех транзакций, с которыми она конфликтует, и несколько спекулятивных теней Ts, s = 1, ..., k-1. Спекулятивная тень Ts выполняется в предположении, что она фиксируется раньше всех транзакций, конфликтующих с T, кроме некоторой одной транзакции Tu, которая «спекулирует» на том, что зафиксируется раньше T.
Ts задерживается на чтении объекта х, который изменила Tu, до тех пор пока Tu не фиксируется, только после этого Ts считывает x. Если «спекуляция» транзакции Tu оправдывается (она фиксируется раньше Т), то оптимистическая тень To транзакции T прерывается и заменяется на спекулятивную тень Ts, которая становится новой оптимистической тенью.
При таком протоколе работы транзакция T не блокирует каким-либо образом объекты данных, к которым она обращается, она всего лишь порождает много своих теней. Каждая тень соответствует потенциальному конфликту и начинает работать только тогда, когда конфликт произошел. Потенциальные конфликты, возникающие при выполнении транзакций, задержек не вызывают. Обеспечивается автоматический рестарт транзакции не сначала, а с момента реального возникновения конфликта, что дешевле, чем при использовании оптимистической стратегии.
Такой протокол используется для систем реального времени. Различные варианты реализации предполагают образование не больше чем n теней, ограничивая тем самым объем ресурсов, требуемых для выполнения транзакции.
Особенности реализации
В большинстве реализаций СУБД поддерживается только один протокол обработки транзакций. Распространены реализации пессимистической и оптимистической стратегий. Реализации спекулятивной стратегии не распространены, хотя системы реального времени достаточно актуальны.
В реализациях оптимистической стратегии для разрешения конфликтов транзакций, как правило, используется техника многоверсионности: фиксируется первая из конфликтующих транзакций, а остальные откатываются. В реализациях пессимистической стратегии для разрешения конфликтов транзакций, как правило, используется техника блокирования: конфликты распознаются и предотвращаются в течение жизни транзакции, а в случае возникновения взаимных блокировок выбирается транзакция-«жертва», которая откатывается принудительно.
Но это совсем не означает, что невозможна реализация пессимистического протокола при использовании техники многоверсионности, или что невозможна реализация оптимистического протокола при использовании техники блокирования. В некоторых реализациях используются смешанные подходы. Например, в СУБД Oracle одновременно используется техника многоверсионности страниц и техника блокирования. Имеются системы, в которых уровни изолированности для только читающих транзакций реализованы с элементами многоверсионности, а все остальные уровни изолированности основываются на технике блокирования.
Уровни изолированности: ANSI и коммерческие реализации
В ANSI SQL-92 вводятся четыре уровня изолированности транзакций.
- Незафиксированное чтение (READ UNCOMMITED).
- Зафиксированное чтение (READ COMMITED).
- Повторяемое чтение (REPEATABLE READ).
- Сериализуемость (SERIALIZABLE).
Эти четыре уровня изолированности вводятся на основе классического определения сериализуемости и трех феноменов — «грязное чтение», «неповторяемое чтение», «фантом».
Сериализуемость определяется как режим выполнения операций конкурирующих транзакций, дающий в точности тот же результат, что и последовательное выполнение этих транзакций в некотором порядке.
К сожалению, в стандарте отсутствует четкое определение феномена. Говорится лишь, что это некая последовательность операций, обладающая аномальным (возможно несериализуемым) поведением. Феномены определяются словесно.
- P1 ("грязное чтение"): SQL-транзакция T1 модифицирует запись. SQL-транзакция T2 считывает эту запись перед тем, как T1 выполняет COMMIT. Если T1 выполняет ROLLBACK, то T2 считает запись, которая никогда не была зафиксирована.
- P2 ("неповторяемое чтение"): SQL-транзакция T1 считывает запись. SQL-транзакция T2 затем модифицирует или удаляет эту запись и выполняет COMMIT. Если T1 повторно считает данную запись, она может получить измененное значение записи или обнаружить, что запись удалена.
- P3 ("фантом"): SQL-транзакция T1 считывает множество записей N, которые удовлетворяют некоторому условию поиска . После этого SQL-транзакция T2 выполняет SQL-оператор, который заносит в базу данных одну или более записей, удовлетворяющих условию , которое использовала SQL-транзакция T1. Если SQL-транзакция T1 затем повторит первоначальную операцию чтения с тем же условием поиска, она получит другое множество записей.
Следующая таблица определяет уровни изолированности через запрет (Not Possible) и/или разрешение (Possible) каждого из этих феноменов.
Определения всех трех феноменов P1, P2, P3 неточны. Они не исключают некоторые аномальные последовательности операций в историях выполнения транзакций. Определения феноменов в стандарте ANSI SQL запрещают только явные аномалии, но не потенциальные аномалии. Поэтому уровень SERIALIZABLE в стандарте ANSI не гарантирует сериализуемости. В частности, если использовать определения ANSI феноменов P2 и P3, то допускаются примеры, приведенные во второй части данного обзора в разделе «Формальное определение феноменов через зависимости транзакций» и иллюстрирующие аномальное поведение феноменов «неповторяемое чтение» и «фантом». В соответствующих историях выполнения транзакций имеются аномалии рассогласования данных. Тем самым, эти истории несериализуемы, хотя и подпадают под определение уровня изолированности SERIALIZABLE.
Детальное рассмотрение уровней изолированности ANSI приводит к следующим выводам.
- Множество феноменов ANSI не является полным, по крайней мере, отсутствует феномен "потерянные обновления".
- Определения феноменов ANSI допускают различную трактовку, и запрещение всех трех феноменов не обеспечивает сериализуемости истории транзакций.
- Уровни изолированности, реализуемые с помощью механизма блокировок, по своим характеристикам отличаются от уровней изолированности ANSI (а в большинстве коммерческих реализаций для обеспечения изолированности СУБД используется техника блокирования).
- Уровни изолированности, реализуемые с помощью механизма многоверсионности, по своим характеристикам отличаются от уровней изолированности ANSI, а уровень "изолированность образа" (реализованный, например, в Interbase) вообще не имеет эквивалента в ANSI.
- В феноменах ANSI не различаются типы поведения, возможные на каждом уровне изолированности, а эти типы поддерживаются в коммерческих системах.
- Уровень изолированности REPEATABLE READ, реализованный в IBM DB2 гораздо раньше появления стандарта, по своим характеристикам не совпадает с соответствующим уровнем изолированности ANSI.
Особенности одноверсионных и многоверсионных систем
Феномены, возникающие только при многоверсионности
Часто бывает так, что два объекта данных связаны некоторым условием C, нарушение которого означает рассогласование данных. При многопользовательском доступе можно столкнуться с чтением и записью неактуальных данных, когда связанные условием C объекты данных невозможно считать с помощью одного оператора SQL или оба объекта данных считываются по каким-то причинам разными предложениями SQL. Опишем два феномена, связанные с неактуальностью данных, а также предложим методики, позволяющие избежать подобных аномалий.
Проверка наличия искажения чтения (read skew). Феномен неповторяемого чтения является частным случаем феномена искажения чтения. Пусть объекты x и y связаны условием C. Рассмотрим следующую историю выполнения транзакций:
С одной стороны это нельзя назвать феноменом неповторяемого чтения, поскольку объект y до его модификации не считывался. С другой стороны содержится явная аномалия, так как T1 потенциально может основываться на рассогласованных данных.
Покажем, как может проявиться такой феномен. Допустим, мы имеем дело с таблицей rs1, определенной и заполненной следующим образом:
create table rs1 ( i int, j int references rs1(i), name char(2)); insert into rs1 values (1, NULL, 'fi'); insert into rs1 values (2, 1, 'se'); insert into rs1 values (10, NULL, 'th'); insert into rs1 values (11, 10, 'fo'); commit;
Введено ограничение ссылочной целостности, запрещающее удаление или модификацию данных, для которых есть хотя бы один потомок (значение атрибута i данной записи совпадает со значением атрибута j некоторой другой записи; значение NULL атрибута j характеризует вершину иерархии).
Приведем пример неконтролируемой «подмены» родителя:
App2: select i,j from rs1 where i=1; (0) App1: update rs1 set j=10 where j=1; (1) App1: commit; (2) App2: select i,j from rs1 where j=1; (3)
В данном случае осуществлена неконтролируемая подмена родителя (она может и не принести фатальных последствий), хотя к моменту старта транзакции приложения App2 потомок у считанной записи имелся. Такие феномены появления и исчезновения частей иерархий могут часто встречаться при попытках сканировать иерархии, если такое сканирование не поддерживается специальными операторами.
Если изолированность транзакций основана на многоверсионности, то действие (3) на высоких уровнях изолированности обеспечит отсутствие искажения чтения, так как будет считываться просто снимок объектов данных на момент старта транзакции.
В случае реализации изолированности посредством блокировок, если на сервере не блокируются сразу все объекты, удовлетворяющие условию C, то можно лишь предотвратить последствия искажения чтения, но не исключить сам феномен. Для этого приложение должно выполнить повторное чтение объекта данных, например, так:
В этом случае приложение само должно проверить, согласованы ли данные в момент (!!!) и, если они не согласованы, повторно считать объект x, тем самым его актуализировав, что возможно только на уровне изолированности, допускающем неповторяемое чтение, или откатить транзакцию во избежание рассогласования данных. Эта методика позволяет опознать рассогласование данных read skew. Транзакция T1 «провоцируется» на конфликт, и в момент (!!!) рассогласование данных может быть опознано и исправлено. Ситуация иллюстрирует тот неочевидный момент, что для одноверсионных систем (реализующих изолированность посредством блокирования) понижение уровня изолированности может позволить избежать некоторых видов трудно контролируемых аномалий.
Если же выбранная СУБД реализует изолированность посредством многоверсионности, то, чтобы избежать искажения чтения, следует наоборот повысить уровень изолированности — требуется, чтобы транзакция работала только с теми данными, которые были зафиксированы на момент старта данной транзакции или раньше.
Проверка наличия write skew
Пусть объекты x и y связаны условием C. Рассмотрим следующую историю выполнения транзакций:
После фиксации обеих транзакций условие C может перестать выполняться. Такая аномалия может возникать, если изолированность реализована посредством многоверсионности.
Покажем, когда можно столкнуться с наличием подобного феномена. Пусть мы имеем дело с таблицей ws1, определенной и заполненной следующим образом:
create table ws1 ( i int, j real); insert into ws1 values (1,0.); insert into ws1 values (2,0.6); commit;
Введено ограничение целостности sum(j)<=1.
Приведем пример, когда может быть осуществлено неконтролируемое изменение суммы, и фиксация обеих транзакции в совокупности приводит к нарушению ограничения.
App1: select i,j from ws1; (0) App2: select i,j from ws1; (1) App1: update ws1 set j=1. where i=2; (3) App2: update ws1 set j=0.4 where i=1; (2) App1: commit; (4) App2: commit; (5)
В данном случае после завершения обеих транзакций значением суммы стало 1,4, в то время как каждая из транзакций изменила значение суммы, не нарушая ограничения. При последовательной истории это бы не произошло.
Отметим, что такая аномалия на высоких уровнях изолированности характерна для многоверсионности. Отката какой-либо из транзакций не произойдет. Единственное радикальное решение проблемы — описать условие в виде ограничения целостности с обязательной проверкой при фиксации каждой транзакции. Аномалии такого вида очень сложно локализовать при тестировании приложений.
Особенности поведения приложений
Следует отметить, что способы построения транзакций для сервера, у которого изолированность реализована с использованием блокирования, и для сервера, у которого изолированность реализована с использованием многоверсионности, существенно различаются.
При реализации изолированности с использованием техники блокирования у пользователя возникает иллюзия слишком сильной жесткости предоставляемого протокола. В самом деле, если пользователь считывает из таблицы записи, удовлетворяющие некоторому условию P, то почему на высоких уровнях изолированности блокируются все записи, которые запрашивались в процессе обработки условия? Кажется, что это не требуется. Но все дело в том, что при блокировании предотвращаются как реальные конфликты — обращение на чтение или запись к захваченным данным, так и потенциальные конфликты — захват на чтение тех данных, которые сканировались при обработке условий выборок. Второй тип захватов предотвращает потенциальные конфликты.
Потенциальные конфликты реализуются далеко не во всех историях. Так, если транзакция единственный раз выполнила выборку и работает в высоком уровне изолированности SERIALIZABLE, то блокировки по чтению будут сняты только на стадии фиксации транзакции. Тем не менее, сервер не может предсказать дальнейшее поведение транзакции, поскольку в момент ее старта не известен весь набор выполняемых операций. Протокол же предполагает наличие конфликтов (конфликты существуют — вот основное предположение) и поэтому предотвращает их в течение работы транзакции независимо от того, реализуются они или нет. Это надо учитывать при написании приложений.
Например, можно делать транзакции пакетными: чем быстрее отработает транзакция и чем меньше будет пауза между выдачей результата одного запроса и посылкой следующего запроса, тем меньше вероятность конфликта на блокировках. Это не означает, что, используя только такой метод, эту вероятность можно свести к нулю.
Примером «плохого» приложения, которое (1) запрашивает данные на чтение, долгое время не выполняет никаких действий (например оператор заполняет форму) с данными, потом (2) подает запрос на модификацию блокированных ранее данных, потом (3) через некоторое время фиксируется.
Очевидно, что при параллельной работе нескольких таких приложений с большой вероятностью может получиться следующее: несколько приложений выполнили действие (1) — всем им разрешено блокировать данные на чтение. Потом одно предложение пытается выполнить действие (2). Тогда будет обнаружено, что данные заблокированы на чтение и другими приложениями, и поэтому данное приложение будет ждать освобождения объекта. И так далее. В конце концов несколько приложений попадают во взаимную блокировку (они «повисли» на блокировках). Такая ситуация будет разрешена откатом одной или нескольких конфликтующих транзакций в зависимости от того, сколько транзакций участвуют во взаимной блокировке.
Очевидно, что транзакции такого типа будут повторены после отката — данные должны быть отредактированы. Это означает повторение в точности такой же транзакции, а, кроме того, и повторение действий пользователя. Очевидно, что производительность такой системы будет низкой, а данное приложение будет непривлекательно для пользователей, так как пользователи достаточно болезненно относятся к тем ситуациям, когда они ощущают влияние на свою работу других пользователей.
Как ни странно, ситуация исправляется не ослаблением блокирования, а его усилением. При захвате объекта данных на чтение указывается, что эти данные будут редактироваться: накладывается блокировка for update (в большинстве реализаций такие блокировки при выполнении оператора SELECT ... FOR UPDATE). В режиме записи будет блокировано только целевое множество выборки. В этом случае приложения получат уведомление о конфликте раньше — как только попытаются захватить данные в режиме записи. Тогда одно из приложений будет либо ждать (что для пользовательских приложений нежелательно), либо сразу получит код ошибки о блокировании объекта (как правило, в реализациях это указывается с помощью задания опции NO WAIT) — такое поведение приложения предпочтительно. И сообщение, что именно эту запись в данный момент редактирует другой оператор, более понятно оператору. Кроме того, его избавили от лишней работы по вводу и повторному вводу данных в случае конфликта.
Оптимистический протокол работы реагирует только на реализовавшиеся конфликты транзакций, но имеет один существенный недостаток: конфликт опознается слишком поздно.
Поэтому в рассмотренном выше случае оптимистический протокол менее выгоден, так как конфликт транзакций (возникающий из-за того, что два пользователя пытаются редактировать одни и те же данные) будет опознан слишком поздно, на стадии фиксации транзакции. В этом случае протокол работы «выигрывает тот, кто первым фиксируется» не является предпочтительным.
Операции чтения и операции записи не конфликтуют, но пользователь рискует получить уведомление, о том, что его действия ошибочны, после того, как он полностью заполнил большую форму и подтвердил ввод. Если вероятность конфликта высока, то раздражение пользователя практически гарантировано. Но если заранее известно, что система характеризуется низким количеством таких конфликтов, то в этом случае оптимистические протоколы выигрывают, так как все проверки откладываются на конец транзакции и сама транзакция может отработать быстрее.
Кроме того, оптимистические протоколы выигрывают по производительности при массовой загрузке данных: данные сначала загружаются в систему, а только потом обрабатываются. Поэтому, если используются оптимистические стратегии, при написании пользовательских приложений следует внимательно оценивать вероятность конфликтов.
Блокирование или многоверсионность
Использование многоверсионности для обеспечения изолированности транзакций дает существенное преимущество: операции чтения и записи объектов данных никогда не конфликтуют. Но и цена отсутствия этих конфликтов достаточно высока. Накладные расходы складываются из следующих составляющих:
- хранение версий объектов данных;
- очистка устаревших версий объектов данных;
- затраты по актуализации запрашиваемых данных на чтение;
- принудительный откат транзакций в случае неактуальности считанных данных.
Кроме того, вводится ограничение на операции записи данных: для каждого объекта данных в каждый момент времени может существовать только одна нефиксированная версия. Порождение конкурирующей транзакцией второй нефиксированной версии запрещено. Это связано с тем, что разрешение порождать две нефиксированные версии объекта данных с последующей фиксацией соответствующих транзакций влечет проявление феномена LOST UPDATE. Разрешение порождения двух нефиксированных версий одного объекта данных влечет откат одной из конкурирующих транзакций, а именно той, которая подает операцию СOMMIT второй. Допускать фиксацию обеих транзакций нельзя, поскольку это привело бы систему к рассогласованию данных.
Если при использовании техники блокирования основным регулятором взаимодействия транзакций является синхронизационный захват объектов данных и запрет/разрешение доступа к данным, то при использовании техники многоверсионности основным регулятором является предоставление копии объекта данных и хранение копии объекта данных до тех пор, пока она может быть востребована хотя бы одной транзакцией.
