Трудные классы транзакций
Не для всех транзакций можно запросить блокировки всех записей, к которым в ней будут происходить обращения, сразу после поступления транзакции в систему. Рассмотрим транзакцию
U(x): y ← read(x) write(y)
где x является первичным ключом записи, y – локальная переменная, и write(y) обновляет запись, первичный ключ которой содержится в y.
Очевидно, что для транзакций типа U невозможно запросить блокировки сразу после входа в систему (если только не заблокировать целиком таблицу, связанную с y), поскольку механизм исполнения никаким образом не может определить значение y, не выполнив до этого чтение записи x. Мы называем такие транзакции зависимыми транзакциями (dependent transactions). В нашей схеме проблема зависимых транзакций решается путем их разбиения на несколько транзакций, из которых все транзакции, кроме последней, работают с целью обнаружения полного набора чтения/записи, так что последняя транзакция может начать свое выполнение при наличии полного знания о том, к чему она будет обращаться. Например, транзакцию U можно разбить на транзакции:
U1(x): y ← read(x) newtxnrequest(U2(x, y))
и
U2(x, y): y' ← read(x) if (y' ≠ y) newtxnrequest(U2(x, y')) abort() else write(y)
U2 не включается в упорядоченные пакеты транзакций, направляемые препроцессором в системы, которые содержат реплики, до тех пор, пока в препроцессор не поступит результат U1 (в этот промежуток времени может выполняться произвольное число транзакций). В U2 имеется некоторая информация о том, что, вероятно, следует заблокировать, и соответствующие элементы данных немедленно блокируются. После этого U2 проверяет, что заблокированы корректные элементы данных (т.е. что никакая транзакция, выполнявшаяся в промежуток времени между завершением выполнения U1 и началом выполнения U2 не изменила зависимость). Если эта проверка удается, то выполнение U2 может продолжаться. Иначе U2 должна завершиться аварийным образом (и освободить свои блокировки).
Препроцессор оповещается об этом аварийном завершении и снова включает U2 в следующий пакет транзакций, направляемый в системы с репликами базы данных. Заметим, что все действия "аварийно завершить и сделать новую попытку" являются детерминированными (в промежутке времени между завершением выполнения U1 и началом выполнения U2 над всеми репликами будут выполняться одни и те же транзакции, и, поскольку повторная попытка выполнить U2 после ее аварийного завершения делается препроцессором, все последующие действия "аварийно завершить и сделать новую попытку" также являются детерминированными).
Поскольку для разбиения U требуется всего одна дополнительная транзакция, вычисляющая полный набор чтения/записи, мы называем U зависимой транзакцией первого порядка. Зависимые транзакции первого порядка часто встречаются в рабочих нагрузках OLTP в виде последовательности "индексный поиск – доступ к записи". Зависимые транзакции более высокого порядка, такие как следующая зависимая транзакция второго порядка:
V(x): y ← read(x) z ← read(y) write(z)
в реальных рабочих нагрузках встречаются гораздо реже, но тот же самый метод разбиения позволяет справиться с обработкой зависимых транзакций произвольного порядка.
Принцип работы этого метода похож на принцип оптимистического управления параллелизмом (optimistic concurrency control, OCC), и так же, как в в OCC, при выполнении декомпозированных зависимых транзакций имеется риск "зависания" (starvation), если их зависимости будут часто изменяться в промежутках между выполнением декомпозированных частей.
Чтобы лучше понять применимость и стоимость этого метода разбиения, мы выполнили ряд экспериментов и подкрепили их исследованиями на основе аналитической модели. Детали экспериментов и описание модели содержатся в приложении. Мы установили, что производительность при наличии рабочих нагрузок, насыщенных зависимыми транзакциями первого порядка, обратно пропорциональна интенсивности обновлений зависимостей декомпозированных транзакций.
Например, при наличии рабочей нагрузки, состоящей из транзакций Payment из тестового набора TPC-C (в которых вместо первичного ключа часто задается имя заказчика, что делает необходимым индексный поиск), пропускная способность заметным образом пострадает только в том случае, если имя каждого заказчика будет обновляться исключительно часто – сотни или даже тысячи раз в секунду. Накладные расходы, вызываемые добавлением читающей транзакции, которая устанавливает зависимость, почти совсем незаметны. Поскольку в реальных рабочих нагрузках OLTP редко встречаются зависимости по часто обновляемым данным (например, над изменчивыми данными обычно не создаются вторичные индексы), мы заключаем, что наличие рабочих нагрузок с большим числом зависимостей не может служить основанием для отказа от детерминированной схемы управления параллелизмом.
Эта схема также хорошо встраивается в среды систем баз данных, позволяющие пользователям регулировать уровни изоляции своих транзакций для повышения производительности. Возможна простая оптимизация, приводящая к тому, что зависимые чтения будут выполняться на уровне изоляции чтения зафиксированных данных (read-committed) (а не на уровне изоляции полной сериализуемости (serializable)). Тогда зависимая транзакция будет по-прежнему разбиваться на две транзакции, но во второй транзакции больше не потребуется проверять, что ранее прочитанные данные по-прежнему являются точными. Тем самым, эта проверка (и потенциальное аварийное завершение транзакции) устраняется. Заметим, что в системах баз данных, основанных на традиционной двухфазной блокировке, также приходится бороться с высокой интенсивностью конфликтов, которые свойственны рабочим нагрузкам, насыщенным долговременными запросами только на чтение, и что во многих таких системах уже поддерживается выполнение транзакций на более низких уровнях изоляции. Мы предвидим, что разработчикам приложений, предупрежденным о том, что производительность выполнения зависимых транзакций может быть повышена, если эти транзакции выполняются на более низком уровне изоляции, понадобится некоторый период времени для "выяснения отношений" с детерминированной системой баз данных.
В системах, основанных на поддержке версий (multiversion) и мгновенных снимков (snapshot), запросы только на чтение не порождают проблем, но этот подход ортогонален подходу, описываемому в данной статье, поскольку возможны версионные реализации детеминированных систем баз данных.
