Конец архитектурной эпохи

         

Управление транзакциями, репликация и восстановление


Поскольку в 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, руководствуясь следующими соображениями:



  1. Транзакции являются очень короткими. Отсутствуют задержки по вине пользователей и из-за обменов с дисками.


    Поэтому транзакции существуют в течение очень коротких временных промежутков. Это говорит в пользу оптимистических методов управления параллелизмом в противовес пессимистическим методам, подобным методу динамических блокировок. Другие исследователи и разработчики, в частности, разработчики языка программирования, использующие транзакциями при работе с моделями памяти [HM93], пришли к таким же выводам.
  2. Каждая транзакция разбивается на наборы подкоманд, являющихся локальными для некоторого узла. Как отмечалось ранее, этот набор подкоманд выполняется в каждом узле в однопотоковом режиме. Следует снова заметить, что это приводит к отсутствию ожиданий в связи с использованием «защелок» (latch), сокращению общего времени выполнения и опять является доводом в пользу использования более оптимистических методов.
  3. Авторы статьи предполагают заранее получать весь набор классов транзакций. Эту информацию можно использовать для сокращения накладных расходов на управление параллелизмом, как это делалось в системах, подобных SDD-1 [BSR80], еще в 1970-е гг.
  4. В правильно спроектированной системе имеется очень мало коллизий транзакций и тупиковых ситуаций. Такие ситуации приводят к деградации производительности, и для их устранения разработчики всегда модифицируют приложения. Поэтому скорее следует производить разработку, в которой будут отсутствовать коллизии, чем использовать пессимистические методы.




В 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.


Содержание раздела