Детерминированное выполнение транзакций
Как видно из материала предыдущих пунктов, в H-Store имеются две основные проблемы, обе связанные с поддержкой многораздельных транзакций: отображение результатов транзакции в репликах базы данных и двухфазная фиксация. В полагается, что эти проблемы можно решить путем перехода к полностью детерминированной схеме выполнения транзакций. (Замечу, что при этом описываемое исследование выполнено не в контексте общей архитектуры H-Store, хотя имеет явное отношение к этому проекту. –С.К.) Связанное с поддержкой свойств ACID требование сериализации транзакций, по мнению авторов , традиционно формулируется слишком слабо, поскольку требуется эквивалентность плана выполнения смеси транзакций какому-либо плану их последовательного выполнения, что оставляет простор для недетерминизма. При детерминированной сериализации смеси транзакций {T1, T2, ..., Tn} требуется эквивалентность плана выполнения этих транзакций некоторому предопределенному последовательному плану их выполнения (Ti1, Ti2, ..., Tin).
Простейшим способом детерминированного выполнения смеси транзакций, гарантирующим эквивалентность предопределенному последовательному плану было бы последовательное выполнение транзакций в порядке этого плана без какого-либо параллелизма. Однако в большинстве случаев это привело бы к неоптимальному использованию компьютерных ресурсов и, тем самым, к плохой производительности системы. Поэтому авторы предлагают использовать синхронизационные блокировки, но при соблюдении следующих ограничений, гарантирующих эквивалентность получаемого сериального плана предопределенному плану:
-
Если двум транзакции Ti и Tj требуются блокировки одной и той же записи r, и в предопределенном плане Ti находится раньше, чем Tj, то Ti должна запросить блокировку r раньше, чем Tj (т.е. должна использоваться схема упорядоченного запроса блокировок – помимо прочего, легко видеть, что при использовании такой схемы невозможно возникновение синхронизационных тупиков).
Каждая транзакция, не ожидающая удовлетворения запроса блокировки, должна продолжать выполняться до тех пор, пока не зафиксируется или не будет аварийно завершена детерминированным образом (т.е.
в соответствии с логикой приложения). Если выполнение какой-либо транзакции задерживается (например, из-за какого-то сбоя в системе), то система должна поддерживать эту транзакцию активной, пока она не завершится, или пока не будет ликвидирована сама система.
Эксперименты авторов показывают, что если возможны длительные задержки при выполнении какой-либо транзакции, то детерминированная схема приводит к быстрому "загромождению" системы блокированными транзакциями и резкому падению производительности. Поэтому, в частности, детерминированная схема непригодна для СУБД, работающих с базами данных в дисковой памяти. Однако в системах, обрабатывающих данные исключительно в основной памяти, ситуация меняется. В ряде случаев детерминизм позволяет повысить производительность систем, упрощая при этом репликацию и избавляя от потребности в двухфазном протоколе фиксации распределенных транзакций.
Рис. 3. Детерминированная система.
Возможная архитектура детерминированной реплицированной СУБД показана на рис. 3. Запросы на образование транзакций (как и раньше, транзакции являются заранее определенными и сохраняемыми в виде хранимых процедур) от пользовательских приложений поступают в препроцессор, являющий границей детерминированной системы. Препроцессор выполняет всю необходимую недетерминированную подготовительную работу (например, параметризует транзакции в соответствии с указаниями пользователей) и упорядочивает транзакции. После этого транзакции объединяются в пакет и надежно сохраняются. С этого момента система обязуется выполнить все поступившие транзакции, и все выполнение далее производится в соответствии с установленным в пакете порядком выполнения транзакций. Наконец, пакет транзакций надежным образом отсылается во все системы, содержащие реплики базы данных (в этой работе неявно полагается, что базы данных реплицируются целиком, так что любую транзакцию можно полностью выполнить в любой реплике).
От каждой системы-реплики требуется только то, чтобы в ней была реализована некоторая модель выполнения, гарантирующая отсутствие синхронизационных тупиков и эквивалентность порядку выполнения транзакций, установленному препроцессором.
Все системы реплики работают полностью независимо (по всей видимости, сообщая препроцессору о завершении обработки полученного пакета транзакций – С.К.). В случае отказа какой-либо системы реплики ее восстановление производится на основе реплик, сохранивших работоспособность (кстати, в контексте это не очень важно, поскольку эксперименты производились на прототипе, не поддерживающем репликацию, – С.К.).
Для поддержки упорядоченности запросов блокировок в предлагается запрашивать все блокировки, требуемые для каждой транзакции, перед началом ее выполнения (заметим, что если, как в предыдущем пункте, для каждого раздела базы данных используется только один поток управления, то, как и раньше, до появления первой многораздельной транзакции все предшествующие однораздельные транзакции можно выполнять без синхронизационных блокировок – С.К.). Если это возможно, то после этого транзакция выполняется вплоть до своего завершения (над данным разделом), не освобождая блокировок. Однако не для всех транзакций заранее известно, какие записи в них будут читаться и изменяться. Например, возможна следующая транзакция:
T(x): y := read(x) write(y)
Здесь параметр x указывает на некоторую запись, содержащую значение первичного ключа той записи, которую требуется обновить. В этом случае невозможно сразу запросить синхронизационную блокировку второй записи, поскольку значение ее первичного ключа неизвестно до выполнения первой операции чтения. Такие транзакции в называются зависимыми. В предлагаемой схеме зависимые транзакции разбиваются на несколько транзакций, из которых все транзакции, кроме последней, занимаются исключительно выяснением состава наборов чтения и записи, а последняя транзакция начинает свое выполнение при наличии полного знания наборов записей, которые она будет читать и изменять. Например, транзакцию T можно разбить на следующие транзакции T1 и T2:
T1(x): y := read(x) запрос_следующей_транзакции(T2(x, y))
T2(x, y): y´ := read(x) if (y´ ≠ y) запрос_следующей_транзакции(T2(x, y)) abort() else write(y)
Препроцессор не включает транзакцию T2 в пакеты транзакций, пока не получит результат транзакции T1. При начале выполнения T2 блокируются записи с ключами, содержащимися в x и y, а затем проверяется, что за время, прошедшее между завершением T1 и началом T2 не изменилось содержимое записи, на которую указывает x. Если эта проверка оказывается успешной, выполнение T2 продолжается. В противном случае T2 аварийно завершается с освобождением своих блокировок. Об этом оповещается препроцессор, который снова включает T2 в следующий пакет транзакций. Все действия по аварийному завершению транзакций и выполнению новых попыток детерминированы; они одинаковым образом выполняются во всех системах-репликах.
В этом примере для разбиения транзакции T требуется только одна дополнительная транзакция (в T имеется зависимость первого порядка. По наблюдениям авторов , такие транзакции часто встречаются в реальных рабочих нагрузках OLTP. Транзакции с зависимостями более высокого порядка встречаются реже, но теоретически с ними можно справиться с помощью того же приема. Эксперименты и аналитическое моделирование показали, что наличие в рабочей нагрузке OLTP транзакций с зависимостями первого порядка не может служить основанием для отказа от детерминированной схемы выполнения транзакций.
Наиболее интересен детерминизм при выполнении многораздельных транзакций. Общая схема выполнения многораздельной транзакции в не описывается, но идея состоит в том, что препроцессор разбивает каждую многораздельную транзакцию на фрагменты, каждый из которых затрагивает данные только одного раздела. Для каждого фрагмента обеспечивается информация о том, какие сообщения могут поступить от других фрагментов (включая сообщения, содержащие данные, и сообщения о детерминированном аварийном завершении). Фрагмент, получивший сообщение об аварийном завершении, освобождает свои синхронизационные блокировки и завершается. Фрагмент, получивший от других фрагментов все требуемые данные, выполняется до своего логического конца и освобождает синхронизационные блокировки.
Не требуется использование какого- либо протокола фиксации транзакции, поскольку отказ любого узла означает отказ данной системы-реплики. Транзакция зафиксируется в какой-либо другой реплике, и на ее основе будет восстановлена отказавшая система.
Еще раз подчеркну, что это только идея. Думаю, что авторы сами до конца не продумали эту схему, которая в общем случае может оказаться очень нетривиальной. В своих экспериментах, демонстрирующих преимущество детерминированного выполнения многораздельных транзакций они использовали очень простые транзакции из тестового набора TPC-C, а на общий случай пока не замахивались. В этой статье я не берусь разобраться со всеми возникающими сложностями, но нельзя не согласиться, что переспектива обойтись без двухфазного протокола фиксаций за счет детерминированного выполнения транзакций кажется очень привлекательной и потенциально достижимой. Как бы только не оказалось, что для этого требуется еще более сложный статический анализ транзакций, чем тот, который упоминался ранее в этом подразделе.
