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

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

Оригинал: 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

Содержание

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

Аннотация

1. Введение

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

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

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

2.3. Разделение

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

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

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

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

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

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

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

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

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

5.1. Микротесты

5.2. Конфликты

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

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

5.5. TPC-C

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

5.7. Резюме

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

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

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

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

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

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

8. Заключение

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

10. Литература

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

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

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

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

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

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

• Даниела Флореску, Дональд Коссман. Переосмысление стоимости и производительности систем баз данных;
• Тим Краска, Мартин Хеншель, Густаво Алонсо, Дональд Коссман. Рационализация согласованности в "облаках": не платите за то, что вам не требуется и
• Пэт Хелланд, Дейв Кэмпбел. Дом на песке.

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

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

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

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

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

Аннотация

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

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

1. Введение

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

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

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

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

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

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

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

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

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

2.3. Разделение

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

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