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

Дэниел Абади и Александер Томсон
Перевод: Сергей Кузнецов

Оригинал: Daniel Abadi, Alexander Thomson. The Case for Determinism in Database Systems. 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 70-80.

Содержание

От переводчика

Аннотация

1. Введение

1.1. Репликация

1.2. Горизонтальная масштабируемость

1.3. Вклад авторов

2. Поддержка эквивалентности предопределенному порядку следования

3. Доводы в пользу недетерминизма

4. Прототип детерминированной СУБД

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

4.2. Трудные классы транзакций

5. TPC-C и разделенные данные

6. Родственные исследования

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

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

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

Приложение

Реализация прототипа и экспериментальная установка

Аналитическая модель производительности системы при наличии "загромождения"

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

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

Дополнительные характеристики производительности TPC-C

Предстоящая работа

От переводчика

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

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

В направлении исследований транзакционных систем нового поколения наиболее известным является проект H-Store, в котором участвуют специалисты Массачусетского технологического института, Йельского университета, университета Браун и HP Labs. Общеизвестно, что этот проект были инициирован Майклом Стоунбрейкером (Michael Stonebraker), и на основе его начальных результатов при активнейшем участии того же Стоунбрейкера была создана компания VoltDB, первая версия коммерческого продукта которой была выпущена в самом конце весны 2010 г.

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

В Трудах недавно прошедшей конференции VLDB'2010 опубликованы еще две статьи участников проекта: статья Абади и Томсона из Йельского университета, перевод которой вам предлагается в этот раз, и статья группы авторов из MIT, которую я также вскоре собираюсь перевести. Хотя на VLDB'2010 эти две статьи были поданы вне прямой связи с H-Store, я думаю, что какие-то результаты почти наверняка будут использованы в этом проекте.

В статье Абади и Томсона описывается подход к управлению транзакциями, при котором удается приблизиться к желательным уровням доступности и масштабируемости массивно-параллельных тразакционных систем за счет отказа от недетерминированного планирования транзакций. Описываются результаты теоретических и экспериментальных исследований, выполненных на очень высоком уровне. Вместе с тем, текст статьи нельзя считать идеальным: многие важные аспекты описаны "скорописью", некоторые важные выводы недостаточно обоснованы и т.д. Возможно, это связано с тем, что Александер Томсон (который, скорее всего, и писал статью) – всего лишь аспирант второго года обучения, и эта статья – первая в его жизни. Думаю, что для первого раза результат можно считать просто блестящим.

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

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

Аннотация

Репликация – это широко распространенный метод достижения высокого уровня доступности в системах баз данных. Однако из-за недетерминизма, присущего традиционным схемам управления параллелизмом (concurrency control), для обеспечения согласованности реплик требуются специальные усилия. К числу основных методов надежной репликации баз данных относятся пересылка журнала (log shipping), протоколы "энергичной" фиксации (eager commit protocol) и протоколы "отложенной" синхронизации (lazy synchronization protocol), но применение каждого из них приводит к потерям в уровнях доступности, производительности и/или согласованности реплик.

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

1. Введение

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

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

Недетерминированное поведение в системах баз данных приводит к трудностям при реализации репликации баз данных и горизонтально масштабируемых распределенных баз данных. Обсудим эти проблемы по порядку.

1.1. Репликация

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

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

• согласованность реплик;
• корректность всех реплик;
• низкие накладные расходы.

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

• Репликация после записи (post-write replication). Здесь записи сначала выполняются над одной репликой, а репликация происходит после завершения записей. К этой категории относится традиционная репликация "ведущий-подчиненный" (master-slave), где все транзакции выполняются основной "ведущей" системой, наборы записи (write set) которой затем передаются во все "подчиненные" системы с репликами, обновляющие данные в том же порядке, чтобы обеспечить сближение своего результирующего состояния с состоянием базы данных ведущей системы. Обычно это реализуется на основе "пересылки журнала" (log shipping) [14, 20] – ведущая система рассылает журнал транзакций, который воспроизводится подчиненными системами над каждой репликой.

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

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

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

• Активная репликация с использованием синхронизированных блокировок (active replication with synchronized locking). В этом случае все узлы, содержащие реплики, должны договориться о блокировках по записи, которые должны накладываться на элементы данных [4]. Поскольку записи могут происходить только при наличии согласованной монопольной блокировки, во всех узлах, содержащих реплики, обновления будут происходить некоторым образом, эквивалентным такому же последовательному порядку, что гарантирует согласованность реплик. Недостатком этой схемы является дополнительная задержка, вызываемая сетевыми комуникациями для обеспечения синхронизации на основе блокировок. По этой причине такая схема на практике используется намного реже схем с репликацией после записи.

• Репликация с отложенной синхронизацией (replication with lazy synchronization). Транзакции выполняются независимо в нескольких активных узлах, содержащих реплики (которые, возможно, временно рассогласуются), а позже их состояния синхронизуются [10, 7, 17]. Схемы с отложенной синхронизацией обеспечивают хорошую производительность за счет (временной) утраты согласованности реплик.

Если бы система баз данных могла выполнять последовательности поступающих транзакций полностью детерминированным образом, то можно было бы полностью избежать компромиссов между описанными выше желательными свойствами. Транзакции можно было бы заранее упорядочивать на некотором центральном сервере (или путем использования некоторой распределенной службы [18, 24]), а затем направлять их пакетами в каждый узел, содержащий реплики, для детерминированного выполнения. Это будет гарантировать, что в каждом из этих узлов результирующее состояние реплики будет согласовано с состояниями всех других реплик, и не потребуются накладные расходы для достижения каких-либо дополнительных соглашений или синхронизации.

1.2. Горизонтальная масштабируемость

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

Для обеспечения гарантий ACID в системах распределенной обработки транзакций в большинстве случаев используется распределенный протокол фиксации, обычно двухфазный. Такой протокол предназначен для сбора решений всех участвующих узлов о фиксации или аварийном завершении транзакции и гарантирования того, что достигнуто единое решение – даже несмотря на то, что во время выполнения протокола участвующие узлы могут выходить из строя. Накладные расходы на выполнение этих двух фаз протокола фиксации (а также дополнительное время, требуемое для удержания блокировок) снизить потенциально достижимую транзакционную пропускную способность разделенной системы. Это препятствие на пути к достижению высокой производительности привело к использованию технологий, ослабляющих свойства ACID (а именно, атомарность (atomicy) или изоляцию (isolation) транзакций) с целью получения масштабируемых распределенных систем баз данных (например, многих так называемых "NoSQL"-систем).

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

1.3. Вклад авторов

В этой статье мы представляем модель выполнения транзакций баз данных, обладающую тем свойством, что результаты любой транзакции T_n однозначно определяются исходным состоянием базы данных и упорядоченной последовательностью предыдущих транзакций {T₀, T₁, ..., T_n-1} (разд. 2).

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

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

2. Поддержка эквивалентности предопределенному порядку следования

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

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

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

• Упорядоченные блокировки (ordered locking). Для любой пары транзакций T_i и T_j, запрашивающих блокировку некоторой записи r, если i < j, то T_i должна запросить свою блокировку раньше, чем это сделает T_j¹.


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

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

---

¹ Это известный метод предупреждения тупиковых ситуаций. Примером системы, в которой блокировки производятся таким образом, является Postgres-R [13].

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

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