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

       

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


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

После того как координатор фиксирует A, он анализирует результаты C. Поскольку C зависит от A, и A зафиксирована, спекулятивные результаты являются корректными, и C можно зафиксировать. Если бы A завершилась аварийным образом, координатор послал бы сообщение об аварийном завершении A процессам разделов P1 и P2, а затем отбросил бы некорректные результаты, полученные по поводу 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. Чтобы система могла получить пользу от этой оптимизации при применении нескольких координаторов, каждый координатор должен распределять транзакции по пакетам. Это может приводить к задержке выполнения транзакций и требует настройки числа координаторов в соответствии с особенностями рабочей нагрузки.

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


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