В этом разделе обсуждается, как в проекте H-Store используются ранее описанные свойства для реализации очень эффективной системы баз данных, ориентированной на OLTP.
H-Store выполняется в grid’е компьютеров. Все объекты разделяются между узлами grid’а. Подобно тому, как это делалось в C-Store [SAB+05], пользователь может указать желаемый уровень K-надежности (K – это число узлов, при одновременном отказе которых система может восстановить работоспособность без потери выполняемых транзакций в течение заданного времени t).
В каждом узле grid строки таблиц размещаются вплотную одна к другой с использованием традиционной индексации на основе B-деревьев. Размер блока B-дерева настраивается в соответствии с размером блока кэша второго уровня используемой машины. Хотя вместо традиционных B-деревьев можно было бы использовать более эффективные варианты, основанные на знании поведения кэша [RR99, RR00], авторы решили прибегнуть к этой оптимизации только в том случае, если код поддержки индексации окажется существенным узким местом для производительности системы.
Каждый узел H-Store является однопотоковым, и в нем полностью, без прерываний выполняется каждая поступающая на обработку команда SQL. Каждый узел разбивается на несколько логических узлов в соответствии с числом ядер в соответствующем процессоре. Каждый логический узел трактуется как независимый физический узел со своими собственными индексами и областью хранения кортежей. Основная память реального физического узла разделяется между логическими узлами. Таким образом, у каждого логического узла имеется выделенный ЦП и единственный поток управления.
В среде OLTP в большинстве приложений для сокращения числа двухсторонних коммуникаций между приложением и СУБД используются хранимые процедуры. Поэтому в H-Store поддерживается всего лишь одна возможность СУБД – возможность выполнения предопределенной транзакции (выполнение транзакции может инициироваться в любом узле): Execute transaction (parameter_list).
В текущем прототипе для написания хранимых процедур используется язык C++, хотя у авторов имеются соображения по поводу возможности применения более удобных языков (см. разд. 6). В данной реализации в одном и том же процессе сочетаются логика приложения и непосредственное манипулирование базой данных. Этот подход позволяет добиться адекватной производительности при выполнении всего приложения внутри одной хранимой процедуры, в которой вызовы SQL производятся как вызовы локальных процедур (не на основе ODBC/JDBC), а данные возвращаются через совместно используемые массивы данных (опять же не на основе ODBC/JDBC).
Так же, как и в C-Store, не поддерживается журнал повторного выполнения операций (redo), а журнал отката (undo) поддерживается только при необходимости (обсуждение см. в подразделе 4.4). Журнал отката (если он ведется) сохраняется только в основной памяти и ликвидируется при фиксации транзакции.
Планируется разработка традиционного оценочного (cost-based) оптимизатора запросов, производящего планы выполнения SQL-операторов, которые содержатся в классах транзакций, во время определения этих классов. Авторы полагают, что этот оптимизатор может быть сравнительно простым, поскольку в средах OLTP никогда не встречаются, например, запросы с шестью соединениями таблиц. В запросах с несколькими соединениями всегда идентифицируется некоторый уникальный кортеж, представляющий интерес, (например, номер заказа), и кортежи, которые должны быть соединены с этой записью (например, позиции заказа). Поэтому все выполнение запроса опирается на некоторый опорный кортеж (anchor tuple), над которым выполняется небольшое число соединений 1-к-n, формирующих кортежи результата запроса. В средах OLTP редко встречаются запросы с GROUP BY и агрегатными функциями. Конечным результатом является простой план выполнения запроса.
Планы выполнения всех команд некоторой транзакции могут относиться к одной из следующих категорий:
Общие: В общем случае будут иметься команды, для которых требуется передача результатов между узлами grid’а. Кроме того, могут иметься команды, параметры времени выполнения которых получаются в результате выполнения предыдущих команд. В этом случае требуется применение выполнения запросов в стиле системы Gamma с поддержкой диспетчера выполнения (execution supervisor) в узле, в котором транзакция была инициирована в системе, и этот диспетчер должен взаимодействовать с исполнителями (worker) в узлах, где располагаются данные.
Для транзакций общего вида вычисляется глубина (depth) класса транзакций как число межузловых сообщений, обмен которыми потребуется для выполнения соответствующего набора планов выполнения запросов.
4.3 Дизайнер баз данных
Для обеспечения функционирования без потребности в ручках управления в среде H-Store будет создано средство автоматического проектирования физических схем баз данных (дизайнер баз данных), которое будет определять горизонтальное разделение, реплицирование и индексные поля.
В отличие от C-Store, где предполагалась поддержка массы материализованных представлений, уместных в среде с большинством операций только чтения, в H-Store сохраняются таблицы, определенные пользователями, и для достижения высокого уровня доступности используется стандартная репликация этих таблиц. Большая часть таблиц будет горизонтально разделена между всеми узлами grid’а. Для достижения высокого уровня доступности для каждого такого фрагмента таблицы (table fragment) должны иметься один или несколько партнеров (buddy), которые содержат в точности ту же информацию с использованием, возможно, другого физического представления (например, с другим порядком сортировки).
Цель дизайнера баз данных состоит в том, чтобы сделать как можно большее число классов транзакций одноузловыми. Используемая стратегия аналогична той, которая применялась в C-Store [SAB+05]. В C-Store для использования в среде хранилищ данных автоматически конструировались вездесущие схемы «звезда» или «снежинка», а теперь эти алгоритмы обобщаются для построения схем, являющихся «почти снежинками». Кроме того, в H-Store будут автоматически строиться схемы для поддержки распространенных в среде OLTP CTA-приложений, и будет использоваться ранее упоминавшаяся стратегия разделения базы данных между узлами на основе значений первичного ключа корневой таблицы с распределением по узлам кортежей других таблиц на основе кортежей корневой таблицы, потомками которых они являются. Будет использоваться и некоторые расширения, такие как оптимизация для только читаемых таблиц и вертикальное разделение, упоминавшиеся в разд. 3. Исследовательская задача авторов состоит в том, чтобы понять, насколько далеко можно распространить этот подход, и насколько успешным он окажется.
В настоящее время горизонтальное разделение и варианты индексации определяются вручную знающими пользователями.
4.4. Управление транзакциями, репликация и восстановление
Поскольку в H-Store поддерживается не менее двух копий каждой таблицы, реплики должны быть транзакционно обновляемыми. Это достигается за счет того, что любой SQL-запрос адресуется к любой соответствующей реплике, а операции обновления выполняются надо всеми соответствующими репликами.
Кроме того, при входе в H-Store каждой транзакции назначается временная метка (timestamp), имеющая формат (site_id, local_unique_timestamp). Если поддерживать порядок на множестве узлов grid, то временные метки будут являться уникальными и полностью упорядоченными. Предполагается, что локальные часы, генерирующие локальные временные метки, взаимно синхронизируются с использованием какого-либо алгоритма типа NTP [Mil89].
Имеется несколько ситуаций, в которых технология H-Store позволяет упростить протоколы управления параллелизмом и фиксации.
Одноузловые (single-sited) транзакции / транзакции с одноразовым использованием результатов (one-shot): Если все классы транзакций являются одноузловыми или содержат только транзакции с одноразовым использованием результатов, то каждая индивидуальная транзакция может быть направлена для выполнения в узлы с нужными копиями данных и полностью там выполнена. Если не все классы транзакций являются стерильными, то каждый узел выполнения транзакций должен подождать в течение небольшого промежутка времени (для учета сетевых задержек) поступления транзакций от других инициаторов, чтобы выполнение транзакций происходило в порядке временных меток. За счет незначительного увеличения времени задержки все реплики будут обновляться в одном и том же порядке, а предельные значения задержек в локальной сети не будут превышать миллисекунды. Этот будет гарантировать идентичность состояния всех реплик. Следовательно, не может произойти рассогласование реплик. Кроме того, либо во всех репликах будут зафиксированы изменения от данной транзакции (если она заканчивается фиксацией), либо все они останутся неизменными (если транзакция заканчивается аварийно). Следовательно, любая транзакция может локально фиксироваться или аварийно завершаться с гарантией того, что у всех реплик останется одно и то же состояние. Не требуются журнал повторного выполнения операций (redo), управление параллелизмом и обработка распределенной фиксации.
Двухфазовые транзакции: Не требуется журнал откатов (undo). Для транзакций, которые обладают этим свойством совместно со свойствами, рассмотренными в предыдущем пункте, вообще не требуются системные средства поддержки.
Стерильные транзакции: Если все транзакции являются стерильными, то их выполнение обычно будет производиться без какого-либо управления параллелизмом. Более того, в этом случае исчезает потребность в назначении временных меток и выполнении транзакций в одном и том же порядке надо всеми репликами. Однако если в обработке транзакции принимает участие несколько узлов, то отсутствует гарантия того, что все узлы аварийно ее завершат, или все они продолжат ее выполнение. В этом случае исполнители в конце первой фазы должны посылать диспетчеру выполнения сообщения «аварийное завершение» или «продолжение выполнения», а диспетчер должен пересылать эту информацию в узлы исполнителей. Следовательно, в конце первой фазы требуется производить стандартную обработку фиксации. Этих дополнительных накладных расходов можно избежать, если транзакция является строго двухфазной.
Другие случаи: В других случаях (отсутствие стерильности, не одноузловые транзакции, транзакции не с одноразовым использованием результатов) приходится применять какую-либо схему управления параллелизмом. Во всех знакомых авторам статьи РСУБД для обеспечения согласованности транзакций используются динамические блокировки. При принятии решения об использовании этого подхода производители следовали пионерской работе [ACL87], в которой на основе моделирования было показано, что вариант с блокировками работает лучше других схем. Однако авторы полагают, что динамические блокировки плохо подходят для H-Store, руководствуясь следующими соображениями:
- Транзакции являются очень короткими. Отсутствуют задержки по вине пользователей и из-за обменов с дисками. Поэтому транзакции существуют в течение очень коротких временных промежутков. Это говорит в пользу оптимистических методов управления параллелизмом в противовес пессимистическим методам, подобным методу динамических блокировок. Другие исследователи и разработчики, в частности, разработчики языка программирования, использующие транзакциями при работе с моделями памяти [HM93], пришли к таким же выводам.
- Каждая транзакция разбивается на наборы подкоманд, являющихся локальными для некоторого узла. Как отмечалось ранее, этот набор подкоманд выполняется в каждом узле в однопотоковом режиме. Следует снова заметить, что это приводит к отсутствию ожиданий в связи с использованием «защелок» (latch), сокращению общего времени выполнения и опять является доводом в пользу использования более оптимистических методов.
- Авторы статьи предполагают заранее получать весь набор классов транзакций. Эту информацию можно использовать для сокращения накладных расходов на управление параллелизмом, как это делалось в системах, подобных SDD-1 [BSR80], еще в 1970-е гг.
- В правильно спроектированной системе имеется очень мало коллизий транзакций и тупиковых ситуаций. Такие ситуации приводят к деградации производительности, и для их устранения разработчики всегда модифицируют приложения. Поэтому скорее следует производить разработку, в которой будут отсутствовать коллизии, чем использовать пессимистические методы.
В H-Store из этих факторов извлекается польза.
Для каждого класса транзакций (с отсутствием стерильности, с не одноузловыми транзакциями и транзакциями с не одноразовым использованием результатов) обнаруживается набор классов транзакций, с которыми транзакции данного класса могут конфликтовать. Транзакция инициируется в некотором узле grid и взаимодействует с координатором транзакций в этом узле. Координатор транзакций действует как диспетчер транзакций в узле инициации транзакции и рассылает части подплана в различные узлы. Сайт-исполнитель получает подплан и выжидает упоминавшийся ранее небольшой промежуток времени на предмет поступления возможно конфликтующей транзакции с меньшим значением временной метки. После этого исполнитель делает следующее:
- Выполняет подплан, если в его узле отсутствуют незафиксированные, потенциально конфликтующие транзакции с меньшими значениями временных меток и затем посылает результирующие данные в запрашивающий их узел, который может являться промежуточным узлом или координатором транзакции.
- В противном случае посылает координатору сообщение «abort».
Если координатор получает сообщение «ok» от всех узлов, он продолжает выполнение транзакции путем рассылки следующего набора подпланов, возможно, со встроенной в них логикой на C++. Если подпланов больше нет, координатор фиксирует транзакцию. В противном случае транзакция завершается аварийно.
В представленном алгоритме заключается основная стратегия H-Store. В процессе выполнения транзакций монитор транзакций отслеживает процентное соотношение успешно завершившихся транзакций. Если возникает слишком много аварийных завершений, H-Store динамически переходит к использованию следующей более сложной стратегии.
До выполнения или отказа в выполнении подплана каждый исполнитель выжидает промежуток времени, приблизительно равный MaxD * average_round_trip_message_delay, в попытке дождаться поступления плана с меньшим значением временной метки. В таком случае исполнитель корректно упорядочивает подпланы, уменьшая вероятность аварийного завершения транзакций. В приведенной формуле MaxD является максимальной глубиной класса конфликтующих транзакций.
Эта промежуточная стратегия позволяет уменьшить вероятность аварийного завершения транзакций, но за это приходится платить несколькими дополнительными миллисекундами задержки. В настоящее время авторы статьи производят моделирование для выяснения условий, в которых эта стратегия приводит к повышению производительности.
При применении усложненной (advanced) стратегии в каждом узле отслеживаются наборы прочитанных данных (read set) и наборы измененных данных (write set) каждой транзакции. В этом случае исполнитель запускает любой подплан, а затем при необходимости аварийно прекращает его выполнение в соответствии со стандартными правилами оптимистического управления параллельностью. За счет дополнительных расходов на сбор дополнительной информации и дополнительной работы для обнаружения потребности в аварийном прекращении выполнения можно еще существеннее уменьшить вероятность аварийного завершения транзакций. В настоящее время производится моделирование с целью выявления ситуаций, в которых эта стратегия является выигрышной.
Таким образом, алгоритм управления параллелизмом в H-Store состоит в следующем:
- Запускать стерильные транзакции, одноузловые транзакции и транзакциями с одноразовым использованием результатов без какого-либо управления параллелизмом.
- Прочие транзакции запускать с использованием основной стратегии.
- Если возникает слишком много аварийных завершений транзакций, переходить к использованию промежуточной стратегии.
- Если все равно возникает слишком много аварийных завершений транзакций, переходить к использованию усложненной стратегии.
Следует заметить, что этот алгоритм представляет собой усовершенствованную схему оптимистического управления параллелизмом. Оптимистические методы активно исследовались ранее [KR81, ACL87]. В СУБД Ants [Ants07] свойство коммутативности используется для снижения расходов на блокировки. Поэтому методы, описанные в этом разделе, можно считать объединением ранее известных методов, ориентированным на достижение очень низкого уровня накладных расходов.
Авторы также отмечают, что они пока еще не использовали какие-либо усложненные методы планирования для снижения уровня конфликтности транзакций. Например, можно было бы запускать транзакции из всех возможных пар классов транзакций и фиксировать частоту возникновения конфликтов. После этого планировщик мог бы руководствоваться этой информацией и пытаться не запускать вместе транзакции с высокой вероятностью конфликтов.
В следующем разделе демонстрируется, как эти методы и реализация H-Store в целом работают при выполнении тестового набора TPC-C.
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
Виртуальные VPS серверы в РФ и ЕС
