Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти

Эван Джонс, Дэниэль Абади и Сэмуэль Мэдден
Перевод: Сергей Кузнецов

Назад Содержание Вперёд

4. Схемы управления параллелизмом

4.1. Блокирование

Простейшая схема управления многораздельными транзакциями состоит в том, что до завершения активных транзакций прием на обработку других транзакций блокируется. Когда процесс некоторого раздела получает первый фрагмент некоторой многораздельной транзакции, он выполняет его и возвращает результаты. Все другие транзакции ставятся в очередь. При получении последующих фрагментов активной транзакции процесс обрабатывает их по порядку. После того как данная транзакция фиксируется или откатывается, обрабатываются транзакции, ранее поставленные в очередь. По сути, система предполагает, что все транзакции конфликтуют, и поэтому их можно выполнять только по одной. На рис. 2 показан псевдокод, соответствующий этому подходу.

Transaction Fragment Arrives
if no active transactions:
   if single partition:
     execute fragment without undo buffer
     commit
   else:
     execute fragment with undo buffer
else if fragment continues active multi-partition transaction:
   continue transaction with fragment
else:
   queue fragment

Commit/Abort Decision Arrives
if abort:
   undo aborted transaction
execute queued transactions

Рис. 2. Псевдокод блокирования

4.2. Спекулятивное выполнение

При применении этой схемы управления параллелизмом транзакции из очереди выполняются спекулятивным образом в то время, когда применение блокирующей схемы привело бы к простою. Более точно, после выполнения последнего фрагмента многораздельной транзакции процесс раздела должен ждать, чтобы узнать фиксируется транзакция или же откатывается. В большинстве случаев она будет фиксироваться. Поэтому при использовании спекулятивной схемы во время ожидания завершения 2PC выполняются транзакции из очереди. Результаты этих спекулятивно выполненных транзакций нельзя пересылать за пределы базы данных, поскольку если первая транзакция откатится, результаты спекулятивно выполненных транзакций могут оказаться некорректными. Для спекулятивных транзакций должна накапливаться информация, позволяющая в случае необходимости их откатить. Если первая транзакция фиксируется, все спекулятивно выполненные транзакции немедленно фиксируются. Таким образом, спекулятивный подход позволяет скрыть задержку, порождаемую 2PC, путем выполнения во время ожидания полезной работы.

Спекулятивная схема приводит к сериализуемому плану выполнения транзакций, поскольку, когда транзакция t завершает выполнение всех своих операций чтения и записи, и процесс раздела просто ожидает, чтобы узнать, фиксируется t или откатывается, мы можем быть уверены, что любая транзакция t^*, использующая результаты t в разделе p, окажется в сериальном плане раздела p после t. Однако t^* может читать данные, записанные t, так что, если откатывается t, придется откатить и t^*, чтобы избежать проявления "грязных" (откаченных) данных t.

Простейшая форма спекулятивной схемы применяется в случае, когда все выполняемые транзакции являются однораздельными, так что сначала мы рассмотрим именно этот случай.

4.2.1. Спекулятивная обработка однораздельных транзакций

Для каждого раздела поддерживается очередь невыполненных транзакций и очередь незафиксированных тразакций. В начале очереди незафиксированных транзакций всегда находится некоторая не спекулятивная транзакция. После того, как в разделе выполняется последний фрагмент некоторой многораздельной транзакции, в нем спекулятивным образом выполняются дополнительные транзакции, взятые из очереди невыполненных транзакций. Для каждой такой транзакции поддерживается буфер отката. Если не спекулятивная транзакция откатывается, выбирается каждая транзакция из оставшейся части очереди незафиксированных транзакций, откатывается, а затем добавляется в начало очереди невыполненных транзакций для повторного исполнения. Если не спекулятивная транзакция фиксируется, то выбираются транзакции из очереди незафиксированных транзакций, и результаты их выполнения посылаются в приложение. Когда очередь незафиксированных транзакций опустошается, система возобновляет выполнение транзакций в не спекулятивном режиме (для транзакций, которые не могут завершиться аварийным образом, выполнение происходит без накладных расходов, связанных с сохранением информации, которая требуется для отката).

В качестве примера рассмотрим двухраздельную базу данных (с разделами P₁ и P₂), содержащую две целочисленных записи – x в P₁ и y в P₂. Пусть сначала x = 5, и y = 17. Предположим, что в системе выполяются три транзакции: A, B₁ и B₂ (в таком порядке). A – это многораздельная транзакция, переставляющая значения в записях x и y. Транзакции B₁ и B₂ – это однораздельные транзакции над разделом P₁, увеличивающие значение x на единицу и возвращающие полученное значение.

Процессы обоих разделов начинают выполнение первых фрагментов транзакции A, в которых читаются x и y. Процессы разделов P₁ и P₂ выполняют эти фрагменты и возвращают значения координатору. Поскольку транзакция A не заканчивается, нельзя начать спекулятивное выполнение B₁ и B₂. Если бы это позволить, то результатом транзакции B₁ было бы x = 6, что неправильно. Координатор посылает процессам разделов заключительные фрагменты, в которых в разделе P₁ в x записывается значение 17, а в разделе P₂ в y – 5. После завершения выполнения этих фрагментов процессы разделов посылают координатору свои подтверждения "готов к фиксации" ("ready to commit") и ожидают его решения. Поскольку транзакция A закончилась, можно начинать спекулятивное выполнение транзакций. Транзакции B₁ и B₂ выполняются с заполнением буферов отката, и их результаты ставятся в очередь. Если бы в это время транзакции A пришлось откатиться, то B₁ и B₂ также были бы откачены и выполнены повторно. Если же процессу раздела P₁ становится известно, что транзакция A зафиксирована, то он посылает результаты транзакций B₁ и B₂ клиентам и освобождает буфера отката.

Выше описывалось схема чисто локального спекулятивного выполнения, когда спекулятивные результаты буферизуются внутри раздела и не демонстрируются за его пределами до тех пор, пока не станет известно, что они корректны. При такой схеме можно спекулятивно выполнить только первый фрагмент многораздельной транзакции, поскольку результаты, которые могут быть откачены, нельзя делать доступными вне локального раздела. Однако, как описывается в следующем пункте, можно допустить спекулятивное выполнение многих многораздельных транзакций, если о спекулятивном выполнении знает координатор.

4.2.1. Спекулятивная обработка многораздельных транзакций

Рассмотрим похожий пример, в котором система выполняет транзакции A, B₁, потом новую многораздельную транзакцию C, увеличивающую на единицу значения и x, и y, и, наконец, транзакцию B₂. Система выполняет транзакцию A так же, как и раньше, и в разделе P₁ спекулятивным образом выполняется транзакция B₁. В разделе P₂ спекулятивным образом может выполняться соответствующий фрагмент C, вычисляющий y = 6. При использовании описанной выше локальной схемы спекулятивного выполнения транзакций процесс этого раздела должен ждать фиксации A до возврата этого результата координатору, потому что, если A завершится аварийным образом, этот результат будет некорректным. Однако поскольку у A и C имеется один и тот же координатор, процесс раздела P₂ может возвратить координатору результат своего фрагмента транзакции C с дополнительным указанием того, что он зависит от транзакции A. Аналогично, в разделе B₁ может спекулятивно выполняться его фрагмент транзакции C, вычисляющий и возвращающий x = 17 вместе с указанием, что этот результат зависит от A. В этом разделе также спекулятивно выполняется транзакция B₂, вычисляющая x = 18. Однако процесс раздела не может послать этот результат, поскольку он направлялся бы прямо к клиенту, который ничего не знает про предыдущие транзакции, поскольку однораздельные транзакции не проходят через центральный координатор. Когда многораздельные транзакции зафиксируются, и очередь незафиксированных транзакций станет пустой, процессы разделов смогут возобновить не спекулятивное выполнение транзакций.

После того как координатор фиксирует A, он анализирует результаты C. Поскольку C зависит от A, и A зафиксирована, спекулятивные результаты являются корректными, и C можно зафиксировать. Если бы A завершилась аварийным образом, координатор послал бы сообщение об аварийном завершении A процессам разделов P₁ и P₂, а затем отбросил бы некорректные результаты, полученные по поводу C. Как и раньше, сообщение об аварийном завершении привело бы к откату процессами разделов всех транзакций, находящихся в очереди незафиксированных транзакций. Транзакция A была бы аварийно завершена, но другие транзакции были бы перемещены в очередь невыполненных транзакций и повторно выполнены в том же порядке. Псевдокод для этой схемы показан на рис. 3.

Transaction Fragment Arrives
if no active transaction:
   if single partition:
     execute fragment without undo buffer
     commit
   else:
     execute fragment with undo buffer
else if fragment continues active multi-partition transaction:
   continue transaction by executing fragment
   if transaction is finished locally:
     speculate queued transactions
else if tail transaction in uncommitted queue is finished locally:
   execute fragment with undo buffer
   same_coordinator ← false
   if all txns in uncommitted queue have same coordinator:
     same_coordinator ← true
   if transaction is multi-partition and same coordinator:
     record dependency on previous multi-partition transaction
     send speculative results
else if:
   queue fragment

Commit/Abort Decision Arrives
if abort:
   undo and re-queue all speculative transactions
   undo aborted transaction
else:
   while next speculative transaction is not multi-partition:
     commit speculative transaction
     send results
execute/speculate queued transactions

Рис. 3. Псевдокод спекулятивного выполнения транзакций

Эта схема позволяет без блокирования выполнять последовательность многораздельных транзакций, в каждой из которых имеется по одному фрагменту для каждого раздела, если все эти транзакции фиксируются. Мы называем такие транзакции простыми многораздельными транзакциями. Транзакции этого вида довольно распространены. Например, если имеется некоторая таблицы, над которой в основном выполняются операции чтения, то может оказаться полезно реплицировать ее по всем разделам. Тогда операции чтения могут выполняться локально, в составе какой-либо однораздельной тразакции. Случайные операции модификации этой таблицы выполяются в виде простой многораздельной транзакции над всеми разделами. Другой пример представляет таблица, разделенная по столбцу x, доступ к записям которой основывается на значении столбца y. Такой доступ может быть обеспечен за счет обращения ко всем разделам этой таблицы, что также является простой многораздельной транзакцией. Третий пример составляют распределенные транзакции из тестового набора TPC-C, которые все являются простыми многораздельными транзакциями [26]. Таким образом, эта оптимизация расширяет виды рабочих нагрузок, для которых полезно спекулятивное выполнение.

У спекулятивной схемы выполнения транзакций имеется несколько ограничений. Во-первых, поскольку спекулятивное выполнение может применяться только после выполнения последнего фрагмента транзакции, это подход менее эффективен при наличии транзакций с несколькими фрагментами над одним разделом.

Во-вторых, многораздельное спекулятивное выполнение транзакций можно применять только в тех случаях, когда многораздельные транзакции поступают от одного и того же координатора. Это требуется для того, чтобы координатор знал о виде завершения более ранних транзакций и мог при необходимости каскадно откатить несколько транзакций. Однако единственный координатор может стать узким местом системы, как это обсуждается в подразделе 3.3. Чтобы система могла получить пользу от этой оптимизации при применении нескольких координаторов, каждый координатор должен распределять транзакции по пакетам. Это может приводить к задержке выполнения транзакций и требует настройки числа координаторов в соответствии с особенностями рабочей нагрузки.

Преимуществом спекулятивной схемы является то, что в этом случае не требуются синхронизационные блокировки и отслеживание наборов чтения/записи. Кроме того, возникающие накладные расходы ниже, чем у традиционных схем управления параллелизмом. Недостатком является предположение, что все транзакции конфликтуют, из-за чего временами происходят ненужные откаты.

4.3. Синхронизационные блокировки

В схеме с синхронизационными блокировками транзакции при своем выполнении запрашивают синхронизационные блокировки элементов данных по чтению и записи, и выполнение транзакции, запросившей конфликтующую синхронизационную блокировку, приостанавливается. Транзакции должны сохранять информацию, требуемую для отката, чтобы иметь возможность откататься при возникновении синхронизационного тупика. Применение синхронизационных блокировок позволяет в одном разделе выполнять и фиксировать неконфликтующие транзакции во время сетевых задержек для многораздельных транзакций. Механизм синхронизационных блокировок гарантирует, что результаты будут эквивалентны результатам выполнения транзакций в некотором последовательном порядке. Недостатком является то, что транзакции выполняются с дополнительными накладными расходами, связанными с запросами блокировок и обнаружением тупиковых ситуаций.

По возможности мы избегаем этих накладных расходов. Если в системе, работающей с использованием синхронизационных блокировок, нет активных транзакций, и в ней появляется некоторая однораздельная блокировка, то эта транзакция может выполняться без блокировок и без сохранения информации, требуемой для отката, точно так же, как и при применении блокирующей или спекулятивной схемы. Так работать можно, поскольку нет активных транзакций, из-за которых могли бы возникнуть конфликты, и гарантируется полное выполнение транзакции вплоть до ее фиксации до того, как в данном разделе будет выполняться какая-либо другая транзакция. Таким образом, блокировки запрашиваются только тогда, когда имеются активные многораздельные транзакции.

В своей схеме синхронизационных блокировок мы следуем строгому двухфазному протоколу. Поскольку это гарантирует получение сериализуемого плана выполнения транзакций, клиенты посылают многораздельные транзакции прямо процессам разделов, не используя центральный координатор. Этот подход более эффективен при отсутствии конфликтующих синхронизационных блокировок, поскольку позволяет сократить сетевые задержки и удалить из системы один процесс. Однако при этом появляется возможность распределенного синхронизационного тупика. В нашей реализации для распознавания локальных тупиков используется выявление наличия циклов, а наличие распределенных тупиков устанавливается с использованием механизма таймаутов. При обнаружении цикла для его разрушения в жертву приносятся однораздельные транзакции, потому что их повторное выполнение обходится более дешево.

Поскольку наша система находится под влиянием идей систем H-Store [26] и DORA [20], в процессе каждого раздела имеется только один поток управления. Поэтому наша схема синхронизационных блокировок порождает намного меньшие накладные расходы, чем традиционные схемы блокировок, в которых приходится дополнительно синхронизоваться с помощью защелок для манипулирования структурами данных централизованного менеджера блокировок. В нашей системе можно установить синхронизационную блокировку на некоторый элемент данных, не беспокоясь о том, что в то же время некоторый другой поток управления мог бы пытаться блокировать тот же элемент данных. Единственным типом параллелизма, который мы пытаемся обеспечить, является логический параллелизм, означающий, что некоторая новая транзакция может выполняться только в то время, когда предыдущая транзакция вынуждена ожидать сообщения из сети, – физический параллелизм возникнуть просто не может.

Когда некоторая транзакция завершается и готова к фиксации, фрагменты этой транзакции посылаются в процессы резервных разделов. Вместе с ними посылаются все данные, полученные из других разделов, так что фрагменты, выполняемые в резервных разделах, не участвуют в распределенных транзакциях. Процессы резервных разделов выполняют транзакции последовательно в том порядке, в котором они получают их от процессов отновных разделов. При этом будет получен тот же самый результат, поскольку мы предполагаем, что транзакции являются детерминированными. При выполнении фрагментов в процессах резервных разделов синхронизационные блокировки не запрашиваются, поскольку они не нужны. В отличие от типичной пооператорной репликации, последовательное выполнение транзакций не порождает проблем производительности, поскольку процессы основных разделов также являются однопотоковыми. Как и при использовании схем, описанных выше, после получения процессом основного раздела подтверждений от всех процессов резервных разделов он считает, что результаты транзакции долговременно сохранены, и может вернуть результаты клиенту.

Назад Содержание Вперёд