ACID в распределенной среде задешево – от переводчика

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

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

Естественный интерес вызывают и возможности применения распределенных систем баз данных в приложениях, которые традиционно назывались транзакционными (on-line analytical processing, OLTP). Использование распределенных систем баз данных в таких приложениях, вообще говоря, позволяет повысить производительность этих приложений, а также способствует увеличению уровней их надежности и доступности. Общим приемом для повышения производительности, надежности и доступности является разделение (partitioning) базы данных по нескольким узлам кластера, а также репликация (replication) отдельных частей базы данных в нескольких узлах.

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

По моему мнению, наиболее интересные работы и публикации в области систем и приложений баз данных, выполненные под влиянием теоремы CAP, принадлежат Пэту Хелланду (Pat Helland) и Дональду Коссманну (Donald Kossmann). Здесь я не могу подробно остановиться на сути их работ, для этого требуется отдельная большая статья, которую я планирую написать. Для общего понимания стоит прочитать статьи:

;

и

.

Однако существует альтернативная точка зрения на проблему транзакционных разделенных систем баз данных и теорему CAP, четко выраженная в недавней заметке Майкла Стоунбрейкера (Michael Stonebraker) . В этой заметке Майкл утверждает, что случаи потери связности узлов в распределенных разделенных системах баз данных чрезвычайно редки, и что стремление к обеспечению высокого уровня доступности данных в ущерб их согласованности не является оправданным.

Эта заметка, с одной стороны, является вполне убедительной, а с другой стороны, как и все, что пишет Стоунбрейкер, она появилась совсем не случайно, поскольку именно в этом стиле действует новая компания Стоунбрейкера VoltDB, производящая одноименную распределенную СУБД с хранением данных в основной памяти. VoltDB в большой степени основана на университетском исследовательском проекте H-Store, о котором можно прочитать в статьях:

и

.

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

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

Аналитическая модель

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

Пусть база данных состоит из двух разделов P1 и P2, а работая нагрузка – из двух транзакций. Первая транзакция – однораздельная, обращающаяся к данным либо из P1, либо из P2, причем раздел выбирается случайным образом. Вторая транзакция – многораздельная, обращающаяся к данным из обоих разделов. Зависимости по данным отсутствуют, так что требуется только один цикл коммуникаций. Другими словами, координатор просто посылает в каждый из разделов по односу фрагменту транзакции, ожидает ответа, а затем посылает свое решение о фиксации или аварийном завершении. Каждая многораздельная транзакция обращается в каждом разделе к данным одного и того же объема, но общий объем данным, к которым она обращается, такой же, что и любой однораздельной транзакции. Чтобы обеспечить максимальные преимущества для схемы с синхронизационными блокировками, мы считаем, что транзакции никогда не конфликтуют. Нас интересует пропускная способности системы при росте доли f многораздельных транзакций в рабочей нагрузке.

Аннотация

Разделение базы данных позволяет повысить производительность распределенных систем баз данных OLTP, поскольку для "однораздельных" ("single partition") транзакций не требуется координация с другими разделами. Бытует мнение, что транзакции, пригодные к разделению, следует выполнять в каждом разделе последовательно, вообще без какого-либо параллелизма. Эта стратегия имеет смысл применительно к системам баз данных в основной памяти, в которых отсутствуют задержки из-за обменов с дисками или ожидания реакции пользователей, поскольку можно полностью использовать ресурсы процессора и избежать традиционных накладных расходов на управление параллелизмом, например, на поддержку двухфазного протокола блокировок. К сожалению, во многих приложениях OLTP имеются некоторые тразакции, которые производят доступ к данным из нескольких разделов. Это приводит к сетевым задержкам из-за потребности в координации транзакций, что ограничивает производительность системы баз данных и не допускает параллельного выполнения транзакций.

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

Аварийное завершение транзакций

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

Рис. 6. Микротестирование с аварийным завершением транзакций

Результаты этого эксперимента показаны на рис. 6. Стоимость аварийного завершения изменчива, в зависимости от того, сколько спекулятивно выполненных транзакций требуется выполнить заново. Однако расхождения находятся в пределах 5%, и для простоты мы их не учитываем. Поскольку при использовании блокирующей схемы и схемы с синхронизационными блокировками каскадное аварийное завершение отсутствует, частота аварийных завершений не оказывает существенного влияния, и мы показываем только результаты для вероятности 10%. Пропускная способность системы оказывается немного выше, чем в случае, когда вероятность равняется 0%, поскольку для аварийного завершения транзакций требуется меньше процессорного времени.

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

Благодарности

Эта работа поддерживалась грантами NFS IIS- 0845643 и IIS-0704424, а также канадским Советом по естественным и техническим наукам (Natural Sciences and Engineering Research Council). Все высказывания, оценки и рекомендации, высказанные в статье, отражают мнение авторов, которое не обязательно совпадает с точкой зрения National Science Foundation (NSF).

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

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

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

Начнем с анализа схемы блокирования. Пусть однораздельная транзакция выполняется в одном разделе tsp секунд, а многораздельная транзакция – tmp секунд в обоих разделах, включая время, требующееся на двухфазную фиксацию. Если выполняется всего N транзакций, то имеется N × f многораздельных транзакций и 1/2 × N × (1-f) однораздельных транзакций. Сомножитель 1/2 появляется из-за того, что однораздельные транзакции поровну распределены между двумя разделами. Поэтому время, требуемое для выполнения всех транзакций, и пропускная способность системы выражаются следующими формулами:

время = N × f × tmp + ((N × (1-f)) / 2) × tsp

пропускная способность = N / время = 2 / (2 × f × tmp + (1-f) × tsp)

Фактически, время выполнения N транзакций является взвешенным средним между временем выполнения рабочей нагрузки из только однораздельных транзакций и временем выполнения рабочей нагрузки из только многораздельных транзакций. При возрастании f пропускная способность будет уменьшаться от 2 / tsp до 1 / tmp. Поскольку tmp > tsp, пропускная способность будет быстро падать даже при небольшой доли многораздельных транзакций.

Экспериментальная оценка

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

Наш прототип написан на языке C++ и выполняется под управлением Linux. Мы используем шесть двухпроцессорных серверов с процессорами Xeon 3.20 GHz и двумя гигабайтами основной памяти каждый. Машины соединены одним коммутатором гигабайтного Ethernet. Клиенты выполняются в разных потоках управления на одной машине. Для каждого теста мы использовали 15 секунд "разогрева", после чего следовали 60 секунд измерений (более долгие тесты не приводили к изменению результатов). Мы измеряли число транзакций, завершенных всеми клиентами в период измерения. Каждое измерение повторялось три раза. Мы показываем только средние значения, поскольку расхождения между реальными результатами измерений составляют всего несколько процентов.

Для пропуска микротестов в качестве исполнительного механизма использовалось простое хранилище данных "ключ-значение", в котором ключами и значениями являлись произвольные строки байтов. Поддерживалась одна транзакция, которая читала и обновляла некоторый набор значений. Мы использовали небольшие 3-байтовые ключи и 4-байтовые значения, чтобы избежать сложностей, порождаемых временем передачи данных.

Для пропуска тестов TPC-C мы использовали специально разработанный исполнительный механизм, который выполнял транзакции прямо над данными в основной памяти. Каждая таблица представлялась в завимости от обстоятельств в виде либо B-дерева, либо двоичного дерева, либо хэш-таблицы.

На всех тестах сравнивались три схемы управления параллелизмом, описанные в разд. 4.

Экспериментальная валидация

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

Переменная	Измеренное значение	Описание
tsp	64 миллисекунды	Время не спекулятивного выполнения однораздельной транзакции
tspS	73 миллисекунды	Время спекулятивного выполнения однораздельной транзакции
tmp	211 миллисекунд	Время выполнения многораздельной транзакции, включая обработку двухфазной фиксации
tmpC	55 миллисекунд	Процессорное время выполнения многораздельной транзакции
tmpN	40 миллисекунд	Сетевая задержка при выполнении многораздельной транзакции
l	13,2%	Накладные расходы синхронизационных блокировок. Доля дополнительного времени выполнения

Табл. 2. Переменные аналитической модели

Рис. 10. Модельная пропускная способность

Компоненты системы

Система состоит из трех типов процессов, показанных на рис. 1. Во-первых, данные сохраняются в разделах, для каждого из которых один процесс отвечает за хранение данных в основной памяти и выполнение хранимых процедур с использованием одного потока выполнения. В действительности для каждого раздела имеются один основной (primary) процесс и k - 1 резервных (backup) процессов, что обеспечивает устойчивость данных к k - 1 отказу. Во-вторых, имеется один процесс, называемый центральным координатором и используемый для координации всех распределенных транзакций. Это обеспечивает глобальную упорядоченность распределенных транзакций, как описывается в подразделе 3.3. Наконец, клиентские процессы являются приложениями конечных пользователей, запускающими в системе транзакции в форме вызовов хранимых процедур. Когда клиентская библиотека подключается к базе данных, она загружает часть системного каталога, в которой описываются доступные хранимые процедуры, сетевые адреса разделов и способ распределения данных. Это позволяет клиентской библиотеке направлять транзакции в соответствующие процессы.

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

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

Конфликты

Эффективность схемы с синхронизационными блокировками зависит от наличия или отсутствия конфликтов между транзакциями. При отсутствии конфликтов транзакции выполняются параллельно. Однако при их наличии возникают дополнительные накладные расходы на приостановку и возобновление выполнения. Для изучения влияния конфликтов мы изменяем распределение ключей, к которым обращаются клиенты. При запуске однораздельных транзакций первый клиент запускает только транзакции в первом разделе, а второй – только во втором разделе (вместо того чтобы выбирать раздел для своей транзакции случайным образом). Значения с ключами первых двух клиентов в их транзакциях изменяются. Чтобы вызвать конфликты, другие клиенты производят доступ к одному из таких "конфликтных" ключей с вероятностью p или обращаются к одному из своих частных ключей с вероятностью 1 - p. С высокой вероятностью такие транзакции попытаются изменить некоторое значение в то же время, что и первые два клиента. Увеличение p приводит к большему числу конфликтов. Синхронизационные тупики в этой рабочей нагрузке невозможны, что позволило нам избежать влияния на производительность зависящих от реализации политик разрешения такие ситуаций.

Рис. 5. Микротестирование при наличии конфликтов

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

Литература

[1] TPC benchmark C. Technical report, Transaction Processing Performance Council, February 2009. Revision 5.10.1.

[2] A. Adya, R. Gruber, B. Liskov, and U. Maheshwari. Efficient optimistic concurrency control using loosely synchronized clocks. In Proc. ACM SIGMOD, 1995.

[3] R. Agrawal, M. J. Carey, and M. Livny. Concurrency control performance modeling: Alternatives and implications. ACM Trans. Database Syst., 12(4):609–654, 1987.

[4] S. Agrawal, V. Narasayya, and B. Yang. Integrating vertical and horizontal partitioning into automated physical database design. In Proc. ACM SIGMOD, 2004.

[5] P. A. Bernstein and N. Goodman. Timestamp-based algorithms for concurrency control in distributed database systems. In Proc. VLDB, 1980.

[6] H. Boral, W. Alexander, L. Clay, G. Copeland, S. Danforth, M. Franklin, B. Hart, M. Smith, and P. Valduriez. Prototyping bubba, a highly parallel database system. IEEE Trans. on Knowl. and Data Eng., 2(1):4–24, 1990.

[7] L. Camargos, F. Pedone, and M. Wieloch. Sprint: a middleware for high-performance transaction processing. SIGOPS Oper. Syst. Rev., 41(3):385–398, June 2007.

[8] S. Ceri, S. Navathe, and G. Wiederhold. Distribution design of logical database schemas. IEEE Trans. Softw. Eng., 9(4):487–504, 1983.

[9] D. J. Dewitt, S. Ghandeharizadeh, D. A. Schneider, A. Bricker, H. I. Hsiao, and R. Rasmussen. The gamma database machine project. IEEE Trans. on Knowl. and Data Eng., 2(1):44–62, 1990.

[10] G. Eadon, E. I. Chong, S. Shankar, A. Raghavan, J. Srinivasan, and S. Das. Supporting table partitioning by reference in oracle. In Proc. ACM SIGMOD, 2008.

[11] H. Garcia-Molina, R. J. Lipton, and J. Valdes. A massive memory machine. Computers, IEEE Transactions on, C-33(5):391–399, 1984.

[12] H. Garcia-Molina and K. Salem. Main memory database systems: An overview. IEEE Trans. on Knowl. and Data Eng., 4(6):509–516, 1992.

[13] R. Gupta, J. Haritsa, and K. Ramamritham. Revisiting commit processing in distributed database systems. In Proc. ACM SIGMOD, pages 486–497, New York, NY, USA, 1997. ACM.

[14] S. Harizopoulos, D. J. Abadi, S. Madden, and M. Stonebraker. OLTP through the looking glass, and what we found there. In Proc. ACM SIGMOD, pages 981–992, 2008.

Имеется перевод на русский язык: Ставрос Харизопулос, Дэниэль Абади, Сэмюэль Мэдден, Майкл Стоунбрейкер. OLTP в Зазеркалье.

[15] P. Krishna Reddy and M. Kitsuregawa. Speculative locking protocols to improve performance for distributed database systems. Knowledge and Data Engineering, IEEE Transactions on, 16(2):154–169, March 2004.

[16] K. Li and J. F. Naughton. Multiprocessor main memory transaction processing. In Proc. Databases in Parallel and Distributed Systems (DPDS), 1988.

[17] M. Livny, S. Khoshafian, and H. Boral. Multi-disk management algorithms. SIGMETRICS Perform. Eval. Rev., 15(1):69–77, 1987.

[18] M. Mehta and D. J. DeWitt. Data placement in shared-nothing parallel database systems. The VLDB Journal, 6(1):53–72, 1997.

[19] C. Mohan, B. Lindsay, and R. Obermarck. Transaction management in the R* distributed database management system. ACM Trans. Database Syst., 11(4):378–396, 1986.

[20] I. Pandis, R. Johnson, N. Hardavellas, and A. Ailamaki. Data-oriented transaction execution. In PVLDB, 2010.

[21] S. Papadomanolakis and A. Ailamaki. Autopart: Automating schema design for large scientific databases using data partitioning. In Proc. Scientific and Statistical Database Management, 2004.

[22] D. V. Pattishall. Friendster: Scaling for 1 billion queries per day. In MySQL Users Conference, April 2005.

[23] D. V. Pattishall. Federation at Flickr (doing billions of queries per day). In MySQL Conference, April 2007.

[24] D. Sacca and G. Wiederhold. Database partitioning in a cluster of processors. ACM Transactions on Database Systems, 10(1):29–56, 1985.

[25] R. Shoup and D. Pritchett. The eBay architecture. In SD Forum, November 2006.

[26] M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era: (it’s time for a complete rewrite). In Proc. VLDB, 2007.

Имеется перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными.

[27] A. Whitney, D. Shasha, and S. Apter. High volume transaction processing without concurrency control, two phase commit, SQL or C++. In Int. Workshop on High Performance Transaction Systems, 1997.

[28] D. C. Zilio. Physical Database Design Decision Algorithms and Concurrent Reorganization for Parallel Database Systems. PhD thesis, University of Toronto, 1998.

Микротесты

В нашем микротестовом наборе использовалась простая смесь однораздельных и многораздельных транзакций, поволяющая понять влияние на пропускную способность распределенных транзакций. Мы создали базу данных, состоящую из двух разделов, каждый из которых размещался в отдельной машине. В каждом разделе хранилась половина ключей. От каждого клиента поступали транзакции с операциями чтения и записи значений, связанных с 12 ключами. В этом тесте отсутствовало совместное использование: операции записи каждого клиента затрагивали свой набор ключей. В следующем подразделе описываются эксперименты при наличии совместно используемых данных. Для создания однораздельной транзакции в клиенте случайным образом выбирался раздел, и затем производился доступ к 12 ключам в этом разделе. Для создания многораздельной транзакции ключи делились поровну, чтобы в каждом разделе производился доступ к 6 ключам. С целью полной загрузки процессоров в обоих разделах мы использовали 40 одновременно работающих клиентов. Каждый клиент выдавал один запрос, ждал ответа, после чего выдавал следующий запрос.

Рис. 4. Микротестирование без конфликтов

Мы изменяли долю многораздельных транзакций и измеряли пропускную способность системы. Результаты показаны на рис. 4. С точки зрения приложения многораздельные и однораздельные транзакции выполняют один и тот же объем работы, так в что идеале пропускная способность системы должна была бы оставаться постоянной. Однако накладные расходы на управление параллелизмом отклоняют нас от этого идеала. Производительность системы при использовании блокировок меняется линейно в диапазоне от 16 до 100% многораздельных транзакций. Это объясняется отсутствием конфликтов между этими транзакциями, так что все они могут выполняться одновременно. Небольшое снижение производительности при росте числа многораздельных транзакций связано с тем, что многораздельным транзакциям свойственны дополнительные коммуникационные накладные расходы, и поэтому производительность системы немного падает при росте доли таких транзакций в общей рабочей нагрузке.

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

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

При наличии доли многораздельных транзакций в диапазоне от 0 до 50% производительность систем со спекулятивной схемой и синхронизационными блокировками на графике изображается почти параллельными кривыми, хотя производительность системы со спекулятивной схемой примерно на 10% выше. Поскольку рабочая нагрузка в данном случае состоит из одноузловых и простых многоузловых транзакций, для спекулятивного выполнения всех этих транзакций оказывается достаточно одного координатора. Это позволяет выполнять транзакции параллельно, как и при использовании синхронизационных блокировок, но без накладных расходов на отслеживание блокировок. Когда доля многораздельных транзакций составляет более 50%, производительность системы со спекулятивной схемой начинает падать. В этой точке центральный координатор использует 100% ресурсов процессора и не может обрабатывать большее число сообщений. Для масштабирования системы в диапазоне от 50 до 100% доли многораздельных транзакций нужно было бы реализовать распределенное упорядочивание транзакций, как это описывалось в п. 4.2.2.

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

Многораздельное масштабирование TPC-C

Чтобы проанализировать влияние многораздельных транзакций на более сложную рабочую нагрузку, мы увеличивали долю транзакций TPC-C, затрагивающих несколько разделов. Мы выполняли рабочую нагрузку, на 100% состоящую из новых транзакций заказа с 6 складами. Затем мы соответствующим образом подбирали вероятность того, что некоторая позиция заказа поступает из "удаленного" склада, в результате чего получалась многораздельная транзакция. При параметрах TPC-C, используемых по умолчанию, эта вероятность составляет 0,01 (1%), что обеспечивает долю многораздельных транзакций, равную 9,5%. Мы изменяли этот параметр и вычисляли вероятность того, что транзакция является многораздельной. Пропускная способность системы при этой рабочей нагрузке показана на рис. 9.

Рис. 9. 100% новых транзакций заказа из TPC-C

Результаты системы с блокировочной и спекулятивной схемами очень похожи на результаты микротестирования с рис. 4. В этом эксперименте производительность системы со схемой синронизационных блокировок очень быстро деградирует. При отсутствии многораздельных транзакций (0%) такая система работает эффективно без запросов блокировок. Но при появлении многораздельных транзакций блокировки должны запрашиваться. Накладные расходы на синхронизационные блокировки в тестовом наборе TPC-C выше, чем при микротекстировании, по трем причинам: больше блокировок запрашивается в каждой транзакции; более сложен сам менеджер блокировок; имеется большее число конфликтов. В частности, в этой рабочей нагрузке проявляются локальные и распределенные синхронизационные тупики, причиняющие существенный ущерб производительности. Это еще раз показывает, что конфликты делают традиционное управление параллелизмом более дорогостоящим, возрастают преимущества более простых схем.

Анализ результатов выборочного профилировщика при пропуске системы со схемой синхронизационных блокировок на TPC-C с вероятностью многораздельных транзакций, равной 10%, показывает, что 34% времени выполнения тратится на поддержку блокировок. Примерно 12% времени тратится на управление таблицы блокировок, 14% – на запросы блокировок, и 6% – на освобождение блокировок. Хотя в нашей реализации имеется простор для оптимизаций, эти цифры схожи с теми, которые были получены для Store, где на работу с синхронизационными блокировками тратилось до 16% команд процессора [14].

Многораздельные транзакции

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

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

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

Многораздельные транзакции выполняются с использованием буфера отката, а для принятия решения об успешности завершения транзакций применяется двухфазный протокол фиксации (two-phase commit, 2PC). Это позволяет системе сохранять работоспособность при выходе из строя отдельных разделов. Если при выполнении транзакции один из разделов выходит из строя, или если сеть теряет связность, то другие участники транзакции могут откатиться и продолжить выполнение транзакций, не зависящих от отказавшего раздела. При отсутствии информации, требуемой для отката, системе пришлось бы заблокироваться до восстановления работоспособности отказавшего раздела.

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

При выполнении многораздельных транзакций при ожидании данных от процессов других разделов в процессе основного раздела могут возникнуть сетевые задержки. Этот простой может стать фактором, ограничивающим производительность, даже если многораздельные транзакции составляют лишь малую долю рабочей нагрузки. В нашей экспериментальной системе, описываемой в разд. 5, минимальное время на передачу и подтверждение приема (измеряемое с использованием ping) между двумя машинами в сети, подключенными к одному и тому же коммутатору гигабитного Ethernet, составляет примерно 40 миллисекунд. Среднее процессорное время выполнения транзакции TPC-C в нашей системе – 26 миллисекунд. Таким образом, за время ожидания сетевого подтверждения процесс раздела смог бы выполнить почти две однораздельных транзакции. Что обеспечить системе возможность выполнения полезной работы в то время, которое иначе было бы временем простоя, требуется некоторая разновидность управления параллелизмом. Проблема состоит в том, чтобы это не привело к снижению эффективности простых однораздельных транзакций. В следующем разделе описываются две схемы управления параллелизмом, которые мы разработали для преодоления этой проблемы.

Многораздельные транзакции общего вида

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

Рис. 7. Микротестирование транзакций общего вида

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

Однораздельные транзакции

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

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

Отсутствие использования дисковой памяти

Сегодня даже у относительно низкопроизводительных серверов 1U может иметься до 128 гигабайт основной памяти, что обеспечивает в центре данных с 40 такими серверами основную память объемом более 5 терабайт. Таким образом, при наличии умеренного объема аппаратных средств можно разместить в основной памяти даже самые крупные базы данных OLTP, что устраняет потребность в доступе к дискам в течение обычного функционирования системы баз данных. Это устранение задержек из-за обменов с дисками еще в большей степени сокращает потребность в управлении параллелизмом.

В традиционных системах баз данных использование дисковой памяти обеспечивает долговечность хранения. Однако в критически важных приложениях OLTP требуется высокий уровень доступности, для обеспечения которой используется репликация. В H-Store за счет репликации поддерживается не только высокий уровень доступности, но и долговечность хранения. Транзакция фиксируется только в том случае, когда ее результаты получены в k > 1 репликах, где k – настраиваемый параметр.

Предположения по поводу общей организации системы

Наши схемы управления параллелизмом разработаны для систем разделенных данных в основной памяти типа H-Store [26]. В этом разделе приводится обзор уместных аспектов общей организации H-Store.

На традиционное управление параллелизмом тратится почти половина команд процессора, выполняемых сервером баз данных [14]. Это наводит на мысль, что отказ от поддержки управления параллелизмом может привести к значительному повышению пропускной способности. H-Store явным образом разрабатывалась с учетом этой возможности.

Разделение

При отсутствии задержек из-за ожидания реакции пользователей или обменов с дисками в H-Store транзакции выполняются с начала до конца в одном потоке управления. Для получения преимуществ от наличия нескольких физических машин и нескольких процессоров данные должны быть разбиты на разъединенные разделы. В каждом разделе транзакции выполняются независимо. Возникает проблема нахождения способа разделения данных, при котором каждая транзакция обращается к данным только одного раздела. Для многих приложений OLTP можно достаточно просто разделить приложение вручную. Например, тестовый набор OLTP TPC-C можно разделить по складам, так что 89% транзакций обращаются к данным одного раздела [26]. Имеются факты, показывающие, что разработчики OLTP-приложений уже выполняют подобные их разделения для повышения уровня масштабируемости приложений [22], [23], [25], и в академических исследованиях сформированы некоторые подходы к автоматическому выбору правильных ключей разделения [4], [21], [28]. Однако, если схема разделения не гарантирует, что 100% транзакций обращаются к данными только одного раздела, координация нескольких разделов, затрагиваемых многораздельными транзакциями, приводит к возникновению сетевых задержек, и выполнение транзакций с начала до конца без простаивания процессора становится невозможным. В этой статье мы сосредотачиваемся на том, что следует делать системе в таком случае.

Наши результаты показывают, что выбор

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

Табл. 1. Сводка наилучших схем управления параллелизмом для разных ситуаций. Спекулятивная схема является предпочительной, когда имеется немного транзакций с несколькими циклами коммуникаций (транзакций общего вида) и аварийных завершений транзакций
Другим "стандарным" алгоритмом управления параллелизмом является оптимистическое управление (optimistic concurrency control, OCC). При таком подходе отслеживается каждый прочитанный или записанный элемент, а затем на стадии валидации при наличии конфликтов некоторые транзакции завершаются аварийным образом. Интуитивно мы полагаем, что эффективность OCC должна быть близка к эффективности нашей схемы с синхронизационными блокировками. Дело в том, что, в отличие от традиционных реализаций синхронизационных блокировок, в которых требуются сложные менеджеры блокировок и тщательная синхронизация с помощью защелок для поддержки физической согласованности, наша схема является значительно более легковесной, поскольку в каждом разделе имеется только один поток управления (т.е. нам приходится заботиться только о логической согласованности). Поэтому наша реализация выполняет ненамного больше действий, чем требуется для отслеживания наборов чтения/записи для каждой транзакции, – а это приходится делать и OCC. Следовательно, основное преимущество OCC перед синхронизационными блокировками исчезает. У нас имеются некоторые начальные результаты, подтверждающие эту гипотезу, а в будущем мы планируем более тщательно сравнить плюсы и минусы OCC (и других методов управления параллелизмом) и нашей спекулятивной схемы.

Родственные работы

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

Похоже, что Гарсиа-Молина (Garcia-Molina), Липтон (Lipton) и Вальдес (Valdes) первыми предложили подход к использованию основной памяти большого объема для устранения управления параллелизмом [11-12]. Этот метод использовался в некоторых ранних системах управления базами данных в основной памяти [16]. Шаша (Shasha) и др. в [27] представили механизм исполнения запросов к базам данных, похожий на нашу разработку. Они также отмечали, что схема, похожая на нашу блокировочную схему, может обеспечить существенный выигрыш в производительности при наличии рабочих нагрузок обработки транзакций. Однако их исследование выполнялось в контексте дисковых систем баз данных, требующих журналирования, и они не исследовали спекулятивную схему и схему с синхронизационными блокировками при наличии однопотокового выполнения. Вместо этого они позволяли пользователям указывать, какие транзакции конфликтуют. В системе промежуточного программного обеспечения (middleware) Sprint данные разделяются по нескольким экзмплярам коммерческой системы управления базами данных в основной памяти [7]. Транзакции должны заранее классифицироваться на однораздельные и многораздельные. В отличие от нашей схемы, журналы транзакций пишутся на диск, и используется традиционное управление параллелизмом, обеспечиваемое в используемой СУБД.

Одним из вариантов двухфазной фиксации, похожим на нашу работу, является OPT [13]. В этом протоколе допускает "заимствование" транзакциями незафиксированных ("грязных") данных некоторой транзакции, находящейся на фазе подготовки к фиксации. Хотя в этой работе предполагается использование синхронизационных блокировок, она очень похожа на нашу схему "локального спекулятивного выполнения". Однако в OPT спекулятивно выполняется только одна транзакция, в то время как при применении нашего спекулятивного управления параллелизмом спекулятивно выполняется много транзакций, и может совмещаться двухфазная фиксация многораздельных транзакций с одним и тем же координатором. Редди (Reddy) и Кицурегава (Kitsuregawa) предлагали спекулятивные синхронизационные блокировки, когда транзакция обрабатывает версии "до" и "после" изменяемых элементов данных [15]. Во время фиксации путем отслеживания зависимостей по данным между транзакциями выбирается и применяется корректный вариант выполнения. В этом подходе предполагается, что имеются обильные вычислительные ресурсы. В нашей среде возможности процессоров ограничены, и поэтому наше управление параллелизмом всегда действует на версии данных "после", а также не производит отслеживание зависимостей на мелкоструктурном уровне.

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

Разделение данных – это хорошо изученная проблема систем баз данных (среди прочего, см. [18], [24], [8], [17], [10]). В предыдущих исследованиях отмечалось, что разделение данных может эффективно повысить уровень масштабирования систем баз данных за счет распараллеливания ввода-вывода [17] или связывания с каждым разделом отдельного обработчика в кластере [18]. В отличие от этого, нас интересует разделение данных как средство освобождения от потребности в управлении параллелизмом.

H-Store [26] представляет собой инфраструктуру для системы, использующей разделение данных и однопотоковое выполнение для упрощения управления параллелизмом. Мы развиваем эту работу, предлагая несколько схем управления параллелизмом в системах разделенных баз данных в основной памяти и приходя к выводу, что спекулятивная схема часто превосходит по производительности комбинированную схему блокирования и OCC, описанную в статье про H-Store.

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

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

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

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

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

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

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

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

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

время = N × f × l × tmpC + ((N × (1- f)) / 2) × l × tspS

пропускная способность = N / время = 2 / (2 × f × l × tmpC + (1- f) × l × tspS)

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

Рассмотрим похожий пример, в котором система выполняет транзакции 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. Чтобы система могла получить пользу от этой оптимизации при применении нескольких координаторов, каждый координатор должен распределять транзакции по пакетам. Это может приводить к задержке выполнения транзакций и требует настройки числа координаторов в соответствии с особенностями рабочей нагрузки.

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

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

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

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

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

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

Спекулятивная схема

Сначала рассмотрим локальную спекулятивную схему, описанную в п. 4.2.1. Для спекуляции нам требуется знать время простоя процесса каждого раздела в течение выполнения многораздельной транзакции. Если время процессора, требующееся для выполнения многораздельной транзакции в одном разделе, равно tmpN, то величина сетевой задержки tmpN равняется tmp - tmpC. Поскольку мы можем совместить выполнение следующей многораздельной транзакции с периодом ожидания ответа от сети, предельное время при выполнении рабочей нагрузки из только многораздельных транзакций tmpL вычисляется как max(tmpN, tmpC), а время простоя процессора tmpI – как max(tmpN, tmpC) - tmpC.

Предположим, что для спекулятивного выполнения однораздельной транзакции требуется время tspS. За время простоя, возникающее при выполнении многораздельной транзакциии, в каждом разделе можно выполнить не более tmpI / tspS однораздельных транзакций. При выполнении в системе N × f многораздельных транзакций в каждом разделе выполняется N × (1- f) / 2 однораздельных транзакций. Следовательно, в среднем каждая многораздельная транзакция отделяется (1- f) / 2 × f однораздельными транзакциями. Поэтому для каждой многораздельной транзакции число однораздельных транзакций, которые можно спекулятивно выполнить в каждом разделе, задается следующей формулой:

Nhidden = min ((1- f) / (2 × f), tmpI / tspS)

Тем самым, время выполнения N и результирующая пропускная способность вычисляются следующим образом:

время = N × f × tmpL + (N × (1- f) - 2 × N × f × Nhidden) × (tsp / 2)

пропускная способность = 2 / (2 × f × tmpL + ((1- f) - 2 × f × Nhidden) × tsp)

В нашем конкретном случае tmpN > tmpC, и поэтому мы можем упростить формулы:

Nhidden = min ((1- f) / (2 × f), (tmp - 2 &times tmpC) / tspS)

пропускная способность = 2 / (2 × f × (tmp - tmpC) + ((1- f) - 2 × f × Nhidden) × tsp)

Разные значения функции min соответствуют двум разным поведениям системы. Если (1- f) / (2 × f) ≥ tmpI / tspS, то время простоя полностью используется. В противном случае в системе отсутствует нужное число однораздельных транзакций, чтобы можно было полностью скрыть сетевые задержки, и пропускная способность будет быстро падать после того, как значение f превзойдет tspS / (2 × tmpI + tspS).

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

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

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

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

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

В соответствии с п. 4.2.2 эту модель можно расширить, включив в нее возможность спекулятивного выполнения многораздельных транзакций. В ранее описанном выводе формулы для времени выполнения предполагалось, что одна многораздельная транзакция выполняется tmpL секунд, включая время ожидания ответа от сети. Если допустить спекулятивное выполнение многораздельных транзакций, то это ограничение снимается. Вместо этого мы должны подсчитать время процессора, требуемое для выполнения многораздельных транзакций и спекулятивного и не спекулятивного выполнения однораздельных транзакций. В предыдущей модели подсчитывалось число спекулятивных однораздельных транзакций для одной многораздельной транзакции – Nhidden. Мы можем подсчитать время для многраздельных транзакций и спекулятивных однораздельных транзакций как tperiod = tmpC + Nhidden × tspS. Это время заменяет tmpL в предыдущей модели, и пропускная способность вычисляется по следующей формуле:

пропускная способность = 2 / (2 × f × tperiod + ((1- f) - 2 × f × Nhidden) × tsp)

TPC-C

Тестовый набор TPC-C моделирует рабочую нагрузку системы обработки заказов. Он состоит из смеси из шести транзакций с разными свойствами. Размер данных масштабируется путем добавления складов, в результате чего наборы соответствующих записей добавляются к другим таблицам. Как описывается в статье Стоубрейкера (Michael Stonebraker) и др. [26], мы разделяем базу данных TPC-C по складам. Мы вертикально разделяем таблицу наличных товаров и реплицируем во всех разделах только читаемые столбцы, оставляя обновляемые столбцы в одном разделе. Такое разделение приводит к тому, что 89% транзакций является однораздельными, а остальные – простыми многораздельными транзакциями.

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

Рис. 8. Пропускная способность на TPC-C при изменении числа складов

Мы пропускали TPC-C над базой данных, в которой склады были поровну поделены между двумя разделами. В этой рабочей нагрузке доля многораздельных транзакций варьировалась от 5,7% с 20 складами до 10,7% с 2 складами. Пропускная способность для изменяющегося числа складов показана на рис. 8. При этой рабочей нагрузке производительность вариантов системы с блокировочной и спекулятивной схемами относительно мало меняется при возрастании числа складов. Наименьшая производительность демонстрируется при наличии двух складов, поскольку в этой ситуации наиболее велика вероятность появления многораздельных транзакций (10,7% против 7,2 при 4 складах и 5,7 при 20 складах) из-за применяемого способа генерации новых транзакций заказа. После возрастания числа складов до четырех производительность вариантов системы с блокировочной и спекулятивной схемами слегка падает. Это происходит из-за более крупного размера рабочего набора и соответствующего возрастания числа промахов при поиске данных в кэше и TLB. Производительность системы со схемой синхронизационных блокировок при росте числа складов возрастает, потому что уменьшается число конфликтующих транзакций. Так происходит из-за того, что на один склад TPC-C приходится меньше клиентов, а почти каждая транзакция модифицирует записи склада и округа. Эта рабочая нагрузка также приводит к синхронизационным тупикам, из-за чего возникают накладные расходы на обнаружение локальных тупиков и таймауты для распределенных тупиков. Это снижает производительность схемы с синхронизационными блокировками. Спекулятивная схема работает лучше всех других, поскольку доля многораздельных транзакций находится в пределах диапазона, для которого эта схема более всего пригодна. При 20 складах система со спекулятивной схемой обеспечивает производительность, на 9,7% более высокую, чем система с блокировочной схемой, и на 63% более высокую, чем система со схемой синхронизационных блокировок.

Транзакции как хранимые процедуры

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

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

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

Оригинал: Evan P.C. Jones, Daniel J. Abadi, Samuel Madden. Low Overhead Concurrency Control for Partitioned Main Memory Databases. SIGMOD’10, Indianapolis, Indiana, USA, June 6–11, 2010

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

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

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

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

В системах баз данных управление

В системах баз данных управление параллелизмом используется для обеспечения иллюзии последовательного выполнения транзакций, в то время как на самом деле одновременно выполняется несколько транзакций. Однако в нескольких исследовательских статьях высказывается мнение, что для некоторых специальных баз данных управление параллелизмом может не требоваться [11, 12, 27, 26]. В частности, если данные размещаются в основной памяти, и рабочая нагрузка состоит из транзакций, которые могут выполняться без задержек по вине пользователей, то нет потребности в параллельном выполнении транзакций для полного использования ресурсов одного процессора. Вместо этого, каждую транзакцию можно полностью выполнить до начала обработки следующей транзакции. В предыдущем исследовании системы баз данных Shore [14] было установлено, что при выполнении части тестового набора TPC-C [1] на поддержку блокировок, защелок (latch) и буфера откатов, которая требуется при наличии многопотокового управления параллелизмом, уходит 42% команд процессора. Это говорит о том, что устранение управления параллелизмом может привести к значительному повышению производительности.
В системах баз данных управление параллелизмом также применяется для использования нескольких процессоров путем назначения каждой транзакции своего потока управления. Однако в статье Пэндиса и др. [20] демонстрируется, что этот подход не масштабируется до большого числа процессорных ядер; вместо этого они предлагают подход, ориентированный на данные, при котором каждый поток управления "владеет" некоторым разделом данных, и транзакции передаются разным потокам управления в зависимости от данных, к которым они обращаются. Аналогично этому, в системе H-Store каждому разделу данных также соответствует один поток управления. В этих системах к каждому элементу данных может обратиться только один поток управления, и традиционное управление параллелизмом не требуется.
Разделение данных также применяется в системах без совместного использования ресурсов (sharing-nothing). Данные разделяются между n серверами баз данных, и транзакции направляются в разделы, содержащие требуемые им данные. Этот подход часто используется для повышения производительности систем баз данных. Некоторые приложения являются "полностью разделяемыми", такими, что каждая транзакция может полностью выполняться в некотором одном разделе. В таком случае, если данные сохраняются в основной памяти, каждая транзакция может пропускаться без управления параллелизмом, полностью выполняясь в соответствующм разделе. Однако во многих приложениях имеются некоторые транзакции, охватывающие несколько разделов. Для этих транзакций требуется некоторая форма управления параллелизмом. Поскольку возникают сетевые задержки, необходимо координировать выполнение этих "многораздельных" транзакций, и при отсутствии управления параллелизмом каждый процессор вынуждается ждать.


Эта статья концентрируется на этих "не полностью разделяемых" приложениях. В таких рабочих нагрузках имеются некоторые многораздельные транзакции, вызывающие сетевые задержки, и некоторые "однораздельные" транзакции, которые могут полностью выполняться без задержек, вызываемых обменами с дисками, ожидаением реакции пользователей и передачей данных по сети. Цель состоит в том, чтобы использовать схему управления параллелизмом, позволяющую процессору делать что-нибудь полезное при возникновении сетевых задержек, не нанося при этом значительного ущерба производительности однораздельных транзакций.
Мы изучаем две таких схемы. Первая представляет собой спекулятивный подход, работающий следующим образом: когда многораздельная транзакция t заканчивает работу в одном разделе, но ожидает завершения в других участвующих разделах, выполняются дополнительные спекулятивные транзакции. Однако они не фиксируются до тех пор, пока не зафиксируется t. При спекуляции не удерживаются блокировки и не отслеживаются наборы чтения и записи. Вместо этого предполагается, что спекулятивная транзакция конфликтует с любой транзакцией t, с которой она выполняется параллельно. По этой причине, если t завершается аварийным образом, все спекулятивные транзакции должны быть выполнены повторно.
Вторая схема основывается на двухфазных блокировках. Если отсутствуют какие-либо активные многораздельные транзакции, то однораздельные транзакции успешно выполняются без запроса блокировок. Однако появление любых многораздельных транзакций приводит к тому, что при доступе к данным эти данные блокируются и разблокируются всеми транзакциями с использованием стандартного двухфазного протокола блокировок.
Мы сравниваем сильные стороны и ограничения этих двух схем управления параллелизмом для систем разделенных баз данных в основной памяти, а также простой блокирующей схемы, в которой допускается одновременное выполнение только одной транзакции. Наши результаты показывают, что этот простой блокирующий метод хорошо работает, только если имеется очень мало многораздельных транзакций. Спекулятивное выполнение лучше всего подходит для рабочих нагрузок, состоящих из однораздельных транзакций и многораздельных транзакций, выполняющих по одной порции работы в каждом из затрагиваемых разделов. В частности, из наших экспериментов следует, что спекулятивный подход может удвоить пропускную способность модифицированной рабочей нагрузки TPC-C. Однако для рабочих нагрузок с частым аварийным завершением транзакций этот подход работает плохо, поскольку он приводит к каскадному аварийному завершению одновременно выполняемых транзакций. Схема с блокировками лучше всего годится для рабочих нагрузок, в которых имеется много многораздельных транзакций, в особенности, в тех случаях, когда участники должны выполнить несколько циклов работы с сетевыми взаимодействиями друг с другом. Однако эта схема работает все хуже по мере увеличения числа конфликтов по данным, и хуже всего то, что при ее использовании могут возникать распределенные тупиковые ситуации (distributed deadlock).

Выполнение транзакций

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

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

В этой статье описываются результаты

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

---

---