Транзакционные параллельные СУБД: новая волна

Сергей Кузнецов

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

3.1.3 Спекулятивное выполнение транзакций

Как отмечалось выше, оптимистическая схема управления распределенными (не однораздельными) транзакциями, разработанная в начале проекта H-Store, не стала стратегической схемой этого проекта. Продолжались (и, по-видимому, продолжаются) исследования, направленные на поиск более эффективных схем. Результаты одного из перспективных исследований описываются в [27]. Идея заключается в том, чтобы постараться избежать простаивания потоков управления, когда выполняемые в них фрагменты распределенных транзакций вынуждаются ожидать поступления сетевых сообщений.

Рис. 2. Архитектура системы

В этом исследовании использовался прототип H-Store, архитектура которого показана на рис. 2. Для каждого раздела данных имеются один основной поток управления и k-1 резервных потоков управления (где k – это упоминавшийся в предыдущем пункте уровень надежности системы; у системы на рис. 2 k=2). В отличие от [22], в архитектуре на рис. 2 используется только один координатор распределенных транзакций (авторы объясняют это тем, что исследования способов полного упорядочивания транзакций при наличии нескольких координаторов, т.е. способов обеспечения уникальных и полностью упорядоченных временных меток транзакций, пока еще не завершены). Наличие единственного центрального координатора ограничивает число одновременно выполняемых распределенных транзакций, но этот вариант конфигурации системы является временным.

Каждая транзакция разбивается на фрагменты – части работы, каждую из которых можно выполнить над данными только одного раздела. Транзакции делятся на однораздельные и многораздельные (в [22] они назывались одноузловыми и многоузловыми соответственно; с моей точки зрения, новые термины являются более правильными, поскольку более точно характеризуют природу транзакций; тем не менее, в предыдущем пункте я решил следовать терминологии [22] – К.С.).

Однораздельной транзакцией называется такая транзакция, для полного выполнения которой достаточно данных некоторого одного раздела (т.е. однораздельная транзакция состоит из одного фрагмента). Как показывает рис. 2, однораздельные транзакции запускаются сразу в потоках управления соответствующих разделов, минуя центральный координатор. (В прототипе H-Store приписывание фрагментов транзакций к разделам делается вручную, хотя в перспективе это должен делать автоматический планировщик). Для обеспечения долговечности результатов транзакций используется протокол репликации. Поток управления основного раздела, получив заявку на выполнение транзакции, пересылает ее всем потокам управления резервных разделов. После этого в основном разделе выполняется транзакция, в конце которой поток управления убеждается в получении подтверждения от потоков резервных разделов. Фактически, если получено подтверждение хотя бы от одной реплики, транзакцию можно считать зафиксированной.

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

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

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

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

Тем самым, при выполнении многораздельных транзакций в потоках управления основных разделов могут возникать задержки из-за ожидания получения по сети сообщений от других потоков управления. Причем при использовании гигабитного Ethernet за время обмена сообщениями между двумя машинами по сети (40 миллисекунд) в потоке управления можно выполнить почти две одноузловые транзакции из тестового набора TPC-C. В [27] предлагаются и сравниваются методы, позволяющие системе выполнять полезную работу в то время, в которое она в противном случае простаивала бы.

Самый простой способ управления многоузловыми транзакциями заключается в том, что после получения первого фрагмента многораздельной транзакции поток управления основного раздела не обрабатывает фрагменты других многораздельных транзакций до тех пор, пока не обработает последний фрагмент данной транзакции. Фрагменты всех остальных транзакций ставятся в очередь, т.е. блокируются. Можно считать, что система расценивает все транзакции, затрагивающие один и тот же раздел, как конфликтующие, и выполняет их по очереди. Естественно, метод блокирования транзакций не позволяет системе выполнять полезную работу во время простоев из-за ожидания сетевых сообщений. В [27] этот метод используется в качестве отправной точки для выявления преимуществ и сравнения более развитых методов.

Оригинальным методом выполнения транзакций, предложенным в [27], является метод спекулятивного выполнения. Основная идея состоит в том, что когда в некотором потоке управления основного раздела возникает задержка из-за выполнения двухфазного протокола распределенной фиксации транзакций, этот поток не простаивает, а выполняет другие фрагменты транзакций из своей входной очереди. Это выполнение на фоне фиксации транзакции является спекулятивным (рискованным), потому что результаты выполненных таким образом транзакций будут некорректными, если транзакция, на фоне фиксации которой эти транзакции выполняются, не зафиксируется, а откатится. Поэтому все спекулятивно выполненные транзакции не фиксируются до тех пор, пока не будет зафиксирована первая транзакция, в случае ее отката – все тоже откатываются (тем самым, для всех спекулятивно выполняемых транзакций необходимо поддерживать журналы откатов). Очевидно, что спекулятивная схема обеспечивает сериальный план выполнения транзакций.

Достаточно проста схема спекулятивного выполнения однораздельных транзакций. Для каждого потока управления основного раздела поддерживаются две очереди: очередь невыполненных транзакций и очередь незафиксированных транзакций (при спекулятивном выполнении первой в этой очереди всегда будет многораздельная транзакция, на фоне фиксации которой происходит спекулятивное выполнение). Если многораздельная транзакция откатывается, то по очереди откатываются все спекулятивно выполненные однораздельные транзакции и ставятся в начало очереди невыполненных транзакций для повторного выполнения (в [27] по этому поводу ничего не сказано, но похоже, что в этом случае перед откатом каждого фрагмента требуется послать требования отката во все потоки управления соответствующих резервных разделов; нельзя ставить однораздельную транзакцию в очередь для повторного выполнения, пока не выполнен откат резервных разделов. – С.К.). Если многораздельная транзакция фиксируется, то окончательно фиксируются и все транзакции из очереди незафиксированных транзакций, т.е. они удаляются из этой очереди, и их результаты посылаются в приложение. После обработки всех спекулятивно выполненных незафиксированных транзакций система возобновляет выполнение транзакций в не спекулятивном режиме.

Что касается спекулятивного выполнения многораздельных транзакций, то в [27] предлагается поддержка такого выполнения только для простых многораздельных транзакций, т.е. для транзакций, в которых с каждым разделом базы данных работает не более чем один фрагмент. Отмечается распространенность таких транзакций в транзакционных рабочих нагрузках (например, все транзакции эталонного тестового набора TPC-C относятся к этой категории).

Пусть, например, в некотором потоке управления основного раздела на фоне выполнения двухфазного протокола фиксации многораздельной транзакции T₁ после спекулятивного выполнения транзакций T₂, ..., T_n-1 спекулятивно выполняется фрагмент другой многораздельной транзакции T_n. Тогда после завершения выполнения этого фрагмента координатору посылаются его результаты (вместе с подтверждением готовности к фиксации T_n), а также указывается, что эти результаты зависят от T₁.

Если координатор принимает решение зафиксировать T₁, то спекулятивные результаты T_n являются корректными, и координатор может учесть это при фиксации T_n. В этом случае окончательно фиксируются транзакции T₁, ..., T_n-1, а на фоне ожидания решения координатора о фиксации транзакции T_n продолжается спекулятивное выполнение транзакций из очереди необработанных транзакций потока управления.

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

Достоинством метода спекуляций является возможность избежать простоев в работе потоков управления основных разделов без использования синхронизационных блокировок и отслеживания наборов чтения и записи транзакций. Недостатками и ограничениями являются:

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

Наконец, последняя схема, рассматриваемая в [27], основывается на синхронизационных блокировках. Идейно эта схема очень близка к схеме применяемой в [15] (см. подраздел 3.2). Поскольку все фрагменты транзакций, адресуемые одному разделу базы данных, выполняются в одном потоке управления, нет потребности в менеджере блокировок, доступ к которому производился бы из разных потоков управления. Тем самым, нет потребности в какой-либо синхронизации доступа к структурам данных, разделяемым между несколькими потоками управления. Более того, если в некотором потоке управления отсутствуют активные (незафиксированные) многораздельные транзакции, то поступающие в него однораздельные транзакции могут выполняться без блокировок (и без журналов откатов, если в них невозможно аварийное завершение по инициативе пользователей). Но как только в этом потоке начинает обрабатываться многораздельная транзакция, все остальные транзакции должны выполняться с блокировками и с поддержкой журналов откатов (для разрушения возможных тупиковых ситуаций).

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

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

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

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

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

Авторы [27] выполнили ряд интересных и содержательных экспериментов, которые, в частности, показали, что:

• блокировочная схема почти всегда существенно уступает и спекулятивной схеме, и схеме с синхронизационными блокировками;
• спекулятивная схема работает значительно лучше двух других схем при наличии многораздельных транзакций с одним циклом коммуникаций транзакции с координатором (т.е. для простых многораздельных транзакций, в которых для каждого используемого раздела имеется один фрагмент) и небольшой доли аварийно завершающихся транзакций;
• схема с синхронизационными блокировками обеспечивает наилучшие результаты при наличии многих транзакций с несколькими циклами коммуникаций (для справедливости замечу, что спекулятивный способ выполнения таких транзакций настолько сложен и непонятен, что авторы его даже и не описывают – С.К.).

Общий вывод состоит в том, что в системе стоило бы вести статистику разновидностей транзакций во время выполнения и выбирать метод, следуя, например, модели, показанной в табл. 1.

Табл. 1. Наилучшие схемы управления параллелизмом для разных ситуаций.

		Редкие авар. заверш.		Частые авар. заверш.
		Мало конфл.	Много конфл.	Мало конфл.	Много конфл.
Мало транз. с нескол. циклами коммун.	Много многоразд. транз.	Спекул. выполн.	Спекул. выполн.	Синхр. блокир.	Синхр. блокир. и спекул. выполн.
	Мало многоразд. транз.	Спекул. выполн.	Спекул. выполн.	Блокир. выполн. или синхр. блокир.	Блокир. выполн.
Много транз. с нескол. циклами коммун.		Синхр. блокир.	Синхр. блокир.	Синхр. блокир.	Синхр. блокир.

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