Характеристики транзакций и схем
При использовании H-Store требуется заранее специфицировать рабочую нагрузку в виде набора классов транзакций. В каждом классе содержатся транзакции с одними и теми же операторами SQL и программной логикой, отличающиеся только значениями констант времени выполнения. Поскольку предполагается, что в системе OLTP не будут возникать непредвиденные (ad-hoc) транзакции, это требование не кажется неразумным. Такие классы транзакций должны заранее регистрироваться в H-Store, и не допускается, чтобы при их выполнении возникали задержки по вине пользователей (user stall) (задержки по другим причинам допускаются – например, они могут появиться в распределенной среде, когда одна машина ожидает, пока другая машина выполнит ее запрос). Аналогично, в H-Store предполагается, что заранее известным является и набор таблиц (логическая схема база данных), над которой будут выполняться транзакции.
Авторы обнаружили, что во многих базах данных OLTP у каждой таблицы, кроме одной, называемой корневой таблицей, имеется ровно один элемент соединения, представляющий собой связь n-к-1 со своим предком. Следовательно, схема является деревом связей 1-к-n. Такие схемы являются весьма распространенными. Например, клиенты производят заказы, в которых имеются позиции и графики выполнения. Для древовидных схем имеется очевидное горизонтальное разделение по узлам grid’а. Корневую таблицу можно разделить в соответствии с диапазонами значений первичного ключа или с использованием хеширования этих значений. Каждую таблицу-потомка можно разделить таким образом, что при выполнении любого эвкисоединения в каждом узле требуются данные, хранимые только в этом узле. Далее авторы более подробно обсуждают древовидные и не древовидные схемы.
Предположим, что при использовании древовидной схемы в каждом операторе каждой транзакции имеются предикаты сравнения по равенству с первичным ключом корневой таблицы (например, в приложениях электронной коммерции многие команды относятся к конкретному заказчику, и поэтому они будут содержать предикаты типа customer_id = 27).
Если использовать упомянутое выше горизонтальное разделение, то становится очевидно, что каждый оператор SQL в каждой транзакции будет являться локальным для одного узла. Если же, кроме того, каждый оператор каждой транзакции является локальным для одного и того же узла, то соответствующее приложение называется приложением над ограниченным деревом (constrained tree application, CTA). У CTA-приложений имеется то ценное свойство, что каждая транзакция может быть полностью выполнена в единственном узле. Как демонстрируется в , ценность таких одноузловых транзакций состоит в том, что транзакции могут выполняться без каких-либо задержек из-за коммуникаций с другими узлами grid’а (однако в некоторых случаях потребуется синхронизация реплик, чтобы транзакции над ними выполнялись в одном и том же порядке).
Если в каждой команде каждой транзакции CTA-приложения, кроме предиката сравнения по равенству с первичным ключом корневой таблицы, специфицируются предикаты сравнения по равенству с первичными ключами одной или нескольких таблиц, являющихся непосредственными потомками, то разделение древовидной схемы может быть иерархически расширено с включением в него этих таблиц-потомков. В этом случае, если это требуется, можно использовать более детальное разбиение.
CTA-приложения составляют важный класс одноузловых приложений, которые могут выполняться очень эффективно. Многолетний опыт авторов по разработке приложений баз данных для ведущих компаний позволяет заключить, что OLTP-приложения часто разрабатываются в точности в стиле CTA, а в других случаях часто возможна их декомпозиция для преобразования к CTA-приложениям [Hel07]. Помимо выяснения факта о распространенности CTA-приложений, авторов интересуют методы преобразования к одноузловым приложениям приложений, не относящихся к категории CTA. Интересной исследовательской проблемой является установление характеристик ситуаций, в которых это сделать можно. Здесь можно систематически применять два вида преобразований схем.
Во-первых, в схеме можно выделить все таблицы, которые являются только читаемыми, т.е. не изменяемыми ни одним классом транзакций. Эти таблицы можно реплицировать во всех узлах. Если приложение является CTA-приложением по отношению ко всем остальным таблицам, то после репликации только читаемых таблиц оно станет одноузловым.
Другой важный класс приложений составляют приложения с одноразовым использованием результатов (one-shot). Эти приложения обладают тем свойством, что все их транзакции можно выполнять параллельно без потребности в передаче промежуточных результатов между узлами. Более того, результаты предыдущих SQL-запросов никогда не требуются в последующих командах. В этом случае каждую транзакцию можно декомпозировать в некоторый набор одноузловых планов, каждый из которых можно выполнить в соответствующем узле.
Приложения часто можно сделать one-shot-приложениями путем вертикального разделения таблиц между узлами (необновляемые столбцы реплицируются). Например, так можно поступить с тестовым набором TPC-C (подробнее это обсуждается в разд. 5).
Некоторые классы транзакций являются двухфазными (two-phase) (или могут быть преобразованы к двухфазным). На первой фазе выполняется набор операций только чтения. На основании результатов этих запросов транзакция может быть аварийно завершена. Вторая фаза состоит из последовательности запросов и операций обновления, которые не могут нарушить какие-либо ограничения целостности. Использование свойства двухфазности в H-Store позволяет обойтись без журнала откатов. Авторы статьи установили, что многие транзакции, включая те, которые включены в TPC-C, являются двухфазными.
Класс транзакций является строго двухфазным (strongly two-phase), если он является двухфазным и, кроме того, обладает тем свойством, что операции первой фазы во всех узлах, участвующих в обработке данной транзакции, производят один и тот же результат по отношению к аварийному завершению или продолжению выполнения этой транзакции.
Кроме того, для каждого класса транзакций обнаруживаются все другие классы, транзакции которого являются коммутативными с транзакциями данного класса.Коммутативность определяется следующим образом:
Две параллельно выполняемые транзакции из одного и того же класса или из разных классов транзакций являются коммутативными, если при любом перекрытии их одноузловых подпланов образуется то же окончательное состояние базы данных, что и при любом другом перекрытии (в предположении, что обе транзакции фиксируются).
Класс транзакций, являющийся коммутативным со всеми другими классами транзакций (включая самого себя), называется стерильным (sterile).
В описываемых в алгоритмах H-Store используются свойства одноузлового выполнения, стерильности, двухфазности и строгой двухфазности. На основе своего опыта работы с ведущими коммерческими онлайновыми приложениями розничной торговли авторы установили уместность этих свойств, и они уверены, что подобные свойства будут обнаружены во многих других реальных приложениях баз данных.
