Аналитическая модель производительности декомпозированных зависимых транзакций первого порядка
Чтобы выявить и классифицировать ситуации, в которых эффективен метод декомпозиции транзакций, описанный в подразделе 4.2, мы вводим понятие изменчивости (volatility) – часто обновления данной записи.
При наличии рабочих нагрузок, насыщенных декомпозированными зависимыми транзакциями, можно расчитывать на хорошую производительность, если зависимости транзакции обновляются не часто. Когда записи, от которых зависят транзакции рабочей нагрузки, становятся более изменчивыми, можно ожидать ухудшения производительности.
Пусть (T1, T2) – это декомпозиция зависимой транзакции первого порядка T, набор чтения/записи которой зависит от множества записей
P = (1 - V/R)DR,
и ожидаемое число раз выполнения T2 вычисляется следующим образом:
.
Рис. 5. Ожидаемое число перезапусков декомпозированной зависимой транзакции первого порядка как функция от общей изменчивости ее зависимостей.
На рис. 5 показано ожидаемое число перезапусков типичной декомпозированной транзакции как функция от изменчивости ее зависимостей.
Аналитическая модель производительности системы при наличии "загромождения"
Мы рассматриваем систему баз данных, выполняющую рабочую нагрузку, которая однородным образом составлена из транзакций с n операциями обновления, где два обновления не затрагивают общих данных с вероятостью s (т.е. они конфликтуют с вероятностью 1 - s). Если мы запускаем транзакцию Ti в ситуации, когда k блокировок удерживается другими транзакциями, мы ожидаем, что для Ti будет немедленно удовлетворен запрос всех n блокировок с вероятностью
pn = (sk)n = skn
В этом случае мы предполагаем (поскольку транзакции являются короткими), что Ti зафиксируется и сразу освободит свои блокировки, так что Ti+1 также будет выполняться в среде, в которой блокированы k записей.
Однако если Ti обратится к какой-либо из этих k записей, она не сможет завершиться. В этом случае мы хотим оценить число удерживаемых Tiблокировок новых записей, чтобы определить, как изменяется k. В традиционной модели Ti запрашивает блокировки по ходу своего выполнения, блокируясь при возникновении первого конфликта, и больше блокировки не запрашивая. Поэтому ожидаемое приращение числа k в традиционном случае зависит от числа блокировок (обозначенного ниже как m), которые удалось получить в транзакции Ti до того, как она наткнулась на одну из k блокировок, уже удерживаемых другими транзакциями:
где
Еще раз повторим, что
При использовании нашей детерминированной модели выполнения Ti запрашивает все блокировки в начале своего выполнения, независимо от того, какие из запросов удовлетворяются, так что ожидаемое приращение числа k зависит от общего числа записей, по которым Ti конфликтует при наличии k заранее удерживаемых запросов (ниже это обозначается как n-m, где m – это снова число новых запрашиваемых блокировок):
Рис.4. Вероятность того, что каждая новая транзакция, поступающая в систему, конфликтует с удерживаемыми к этому времени блокировками.
В обоих случаях нас интересует не просто то, сколько записей блокируется, а как это повлияет на последующее выполнение. На рис. 4 показано значение 1 - pn (вероятность того, что поступающие транзакции не смогут выполняться из-за конфликта блокировок) как функция от i (числа новых транзакций, поступивших в систему после транзакции T0).
Начало координат представляет собой точку выполнения транзакций сразу после приостановки T0: i = 0 и
Поскольку назначение этой модели состоит не в том, чтобы предсказывать характеристики производительности реальных систем, а лишь в том, чтобы прояснить загроможденное поведение в целом, мы опускаем какие-либо аспекты горизонтального масштабирования и отмечаем, что для любых s, n и начального значения k наша модель приводит к графику подобного вида, возможно, уплотненному или сдвинутому. В этой простой модели имеются два недостатка, препятствующие ее полному соответствию экспериментальным данным. Во-первых, в ней не учитается активное переупорядочивание (путем освобождения блокировок и перезапуска всех медленных транзакций, кроме одной, приостановленной специальным образом) в случае традиционного выполнения.Во-вторых, на оси абцисс отмечается, сколько новых транзакций поступило в систему после приостановки T0, а число таких транзакций зависит от времени нелинейно, особенно в тех случаях, когда транзакции периодически перезапускаются, и когда выполнение производится за счет использования пула потоков управления фиксированного размера.
Аннотация
Репликация – это широко распространенный метод достижения высокого уровня доступности в системах баз данных. Однако из-за недетерминизма, присущего традиционным схемам управления параллелизмом (concurrency control), для обеспечения согласованности реплик требуются специальные усилия. К числу основных методов надежной репликации баз данных относятся пересылка журнала (log shipping), протоколы "энергичной" фиксации (eager commit protocol) и протоколы "отложенной" синхронизации (lazy synchronization protocol), но применение каждого из них приводит к потерям в уровнях доступности, производительности и/или согласованности реплик.
В этой статье мы предлагаем подход к организации распределенной системы баз данных, в котором техника предупреждения тупиковых синхронизационных ситуаций объединяется со схемами управления параллелизмом, гарантирующими эквивалентность некоторому предопределенному порядку выполнения транзакций. По существу, это устраняет недетерминизм из типичных рабочих нагрузок категории OLTP, позволяя производить активную репликацию без каких-либо накладных расходов на синхронизацию. Кроме того, в нашей системе отсутствует потребность в двухфазной фиксации каких бы то ни было распределенных транзакций, даже таких, которые распространяются на несколько узлов в пределах одной реплики. За счет отсутствия потребности в выявлении тупиковых ситуаций и двухфазной фиксации для многих рабочих нагрузок наша система превосходит по производительности традиционные системы допускающие недетерминированное переупорядочивание транзакций.
Архитектура системы
Наш прототип детерминированной системы баз данных состоит из препроцессора поступающих транзакций, объединенного с произвольным числом систем, хранящих реплики базы данных (рис. 2).
Рис.2. Архитектура детерминированной СУБД.
Препроцессор является границей внутренней детерминированной вселенной системы. Он принимает запросы на образование транзакций, упорядочивает их и заранее выполняет всю необходимую недерминированную работу (например, обрабатывает вызовы sys.random() и time.now, содержащиеся в коде транзакции), передавая свои результаты в качестве аргументов транзакции. Затем запросы на образование транзакции объединяются в пакет и синхронно записываются на диск, что гарантирует долговечность. В этот важнейший момент система берет на себя обязательство выполнить все зарегистрированные транзакции, и после этого все выполнение должно производиться в соответствии с выбранным порядком. Наконец, все собранные в пакет запросы на образование транзакции широковещательным образом отправляются во все системы, содержащие реплики базы данных, с использованием надежного, вполне упорядоченного коммуникационного уровня.
Каждая система, содержащая реплику базы данных, может включать одну машину или разделять данные между несколькими машинами. В любом случае, в ней должна быть реализована модель выполнения, гарантирующая отсутствие синхронизационных тупиков и эквивалентность порядку следования транзакций, заданному препроцессором. Разделенный вариант более подробно обсуждается в разд. 5.
При отказе системы, содержащей реплику базы данных, восстановление в нашей системе производится путем копирования базы данных из какой-либо работоспособной реплики. Возможны и другие схемы (например, повторное выполнение транзакций из долговечного списка транзакций препроцессора), лишь бы только схема восстановления соблюдала инвариант детерменизма.
Детали эксперимента с транзакциями New Order
тестового набора TPC-C
В этом эксперименте мы распределяли данные по двум разделам в разных физических машинах нашего кластера. Среднее время обмена сетевыми сообщениями составляло 130 микросекунд. В каждом разделе одно ядро выделялось для выполнения запросов. Все измерения производились в течение 10 секунд, после чего в течение короткого времени изменялись характеристики рабочей нагрузки.
Дополнительные характеристики производительности TPC-C
Для подкрепления результатов анализа положительного влияния на производительность возможности избежать двухфазной фиксации в распределенных системах баз данных (обсуждавшейся в разд. 5), мы включили в графики на рис. 7 результаты измерений, полученных при выполнении тех же экспериментов, результаты которых приводились на рис. 3, – интенсивность конфликтов блокировок и средняя задержка транзакций (для удобства восприятия в верхней части рис. 7 воспроизводится рис. 3). Интенсивность блокировок измерялась как доля от общего числа транзакций тех транзакций, которые хотя бы раз блокировались из-за невозможности удовлетворить из запросы блокировок. Задержка транзакции измерялась с момента начала выполнения транзакции в системе, содержащей реплику базы данных, до момента ее фиксации в этой системе.
Графики интенсивности конфликтов блокировок и задержки демонстрируют два важных эффекта, которые помогают лучше понять детали поведения систем во время проведения наших экспериментов:
Стоимость двухфазной фиксации. При наличии многораздельных транзакций традиционное выполнение приводит к большим задержкам транзакций, чем детерминированное выполнение. Это приводит к более длительному удержанию блокировок, что, в свою очередь, способствует повышению интенсивности конфликтов блокировок.
Относительная стоимость возрастающей интенсивности конфликтов. Уменьшение числа складов с десяти до двух приводит к повышению интенсивности конфликтов и увеличению задержки при применении обеих схем выполнения. Влияние этого эффекта на пропускную способности ясно видно в традиционном случае. В детеминированном случае это влияние не настолько очевидно, поскольку для версии тестового набора с двумя складами демонстрируется лучшая производительность, чем для версии с десятью складами, почти для любой доли многораздельных транзакций. Однако истинное поведение системы затуманивается тем, что в случае с двумя складами лучше работает кэш. Углубленный анализ графиков показывает более резкое падение производительности при увеличении доли многораздельных транзакций в случае двух, а не десяти складов. Следовательно, возрастающая интенсивность конфликтов в случае двух скдадов при детерминированной реализации не способствует повышению производительности. В целом, мы видем, что возрастание интенсивности конфликтов при использовании обеих систем оказывает качественно одинаковое воздействие на пропускную способность. Но из-за большей величины задержки транзакций при традицонном выполнении падение производительности проявляется при гораздо меньшей доли многораздельных транзакций.
Доводы в пользу детерминизма в системах баз данных
Дэниел Абади и Александер Томсон
Перевод: Сергей Кузнецов
Дэниел Абади и Александер Томсон
Перевод: Сергей Кузнецов
Дэниел Абади и Александер Томсон
Перевод: Сергей Кузнецов
Дэниел Абади и Александер Томсон
Перевод: Сергей Кузнецов
Оригинал: 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.
Доводы в пользу недетерминизма
Прежде чем приводить доводы в пользу запрета недерминированного поведения в системах баз данных, важно заново рассмотреть аргументы в пользу его допущения.
Хорошая транзакционная система баз данных должна быть быстрой, гибкой и отказоустойчивой. Особо важной считается способность транзакционных систем обеспечивать высокие уровни изоляции, поддерживая при этом оптимальное использование компьютерных ресурсов. Также желательна поддержка по существу произвольных определяемых пользователями транзакций, представляемых на развитом и выразительном языке запросов.
Исторически решения многих проблем разработки таких систем в очень значительной степени основывались на обсуждавшихся ранее либеральных ограничениях сериализации. Чтобы проиллюстрировать значимость переупорядочивания транзакций для достижения этих целей, рассмотрим гипотетическую транзакционную систему баз данных, работающую под типичной транзакционной рабочей нагрузкой. Когда транзакция поступает в систему, ей назначается поток управления, в котором выполняются операции, составляющие эту транзакцию. В частности, в этом потоке управления запрашиваются нужные блокировки, а при фиксации транзакции накопленные блокировки освобождаются. Предположим, что эта гипотетическая система хорошо спроектирована, что в ней используются безупречная схема управления буферами, эффективный менеджер блокировок, поддерживается высокий уровень локальности, так что хорошо работает кэш. Тогда большинство транзакций выполняется очень быстро, удерживая свои блокировки в течение минимального времени. Конфликты по поводу блокировок возникают редко, и транзакции завершаются после сразу после входа в систему, обеспечивающую отличную пропускную способность.
Теперь предположим, что некоторая транзакция входит в систему, запрашивает некоторые блокировки и по какой-то причине сама блокируется (например, из-за возникновения синхронизационного тупика, из-за обращения к медленному устройству хранения данных или, если наша гипотетическая система баз данных работает на нескольких машинах, из-за потери критического сетевого пакета).
Что бы ни привело к такой задержке, в подобной ситуации очень полезно наличие у системы небольшой гибкости. В случае синхронизационного тупика или аппаратного сбоя может оказаться разумным аварийным образом завершить транзакцию и перезапустить ее позже. В других случаях имеется много сценариев, в которых можно значительно повысить уровень использования ресурсов путем изменения порядка следования, которому будет эквивалентно наше (не сериальное) выполнение транзакций. Например, предположим, что наша система получает (в указанном порядке) последовательность из следующих трех транзакций:
T0: read(A); write(B); read(X);
T1: read(B); write(C); read(Y);
T2: read(C); write(D); read(Z);
Если T0 откладывается при попытке прочитать X, то T1 не получит блокировку по чтению записи B и не сможет продолжать выполняться. В детерминированной системе T2 застрянет вслед за T1 из-за наличия зависимости "чтение-запись" на записи C. Но если мы можем изменить порядок следования, эквивалентность которому будет обеспечиваться, T2 сможет получить требуемую блокировку записи C (поскольку транзакция T1 заблокировалась до того, как запросила блокировку C) и завершить свое выполнение, заняв место перед T0 и T1 в эквивалентном порядке следования. Следовательно, если система требует эквивалентности только некоторому последовательному порядку выполнения, не обязательно тому порядку, в котором транзакции поступают в систему, простаивающие ресурсы можно немедленно начать эффективно использовать для выполнения T2.
Приведенный пример позволяет немного понять суть класса проблем, с которыми позволяет справиться динамическое переупорядочивание транзакций. Для количественной оценки преимуществ этого подхода мы создали аналитическую модель и выполнили эксперимент, в котором наблюдали эффекты от появления блокированной транзакции в традиционной системе и в системе, основанной на описанной выше детерминированной модели выполнения. Из-за ограничений на объем статьи аналитическая модель представлена только в приложении, но полученные на ее основе результаты согласуются с результатами описываемых здесь экспериментов.
В своем эксперименте мы реализовали простую рабочую нагрузку, в которой каждая транзакция обращается к 10 записям базы данных, содержащей 106 записей. После поиска каждой требуемой записи во вторичном индексе запрашивается ее блокировка, и запись обновляется. Транзакции являются достаточно короткими: по нашим измерениям, блокировки освобождаются примерно через 30 микросекунд после удовлетворения запроса последней из них. Выполнение рабочей нагрузки происходит в благоприятных условиях до тех пор, пока через одну секунду после начала работы в системе не появляется транзакция, которая запрашивает 10 блокировок, после чего полностью блокируется на одну секунду. После этого она активизируется, освобождает свои блокировки и фиксируется. Мы измеряли пропускную способность каждой системы как функцию от времени, а также вероятность того, что новая поступающая в систему транзакция не сможет полностью выполниться из-за конфликта блокировок. При использовании детерминированной схемы все 10 блокировок каждой транзакции запрашиваются сразу после входа транзакции в систему, а в традиционной системе блокировки запрашиваются последовательно, и выполнение транзакции приостанавливается, если очередную блокировку получить не удалось. В традиционной схеме также реализуется выявление тупиковых ситуаций на основе таймаутов: любая транзакция (кроме первой, медленной транзакции), которая не выполняется в течение заданного промежутка времени, аварийно завершается и запускается заново. Подробности об экспериментальной установке см. в приложении.
Рис.1. Измеренные вероятность конфликта блокировок и транзакционная пропускная способность за интервал времени в три секунды. Две транзакции конфликтуют с вероятностью 0,01%, 0,1% и 1% соответственно.
На рис. 1 показаны результаты нашего исследования застопоренного поведения при разных вероятностях конфликтов блокировок. На графиках показаны вероятности того, что поступающие транзакции не смогут сразу завершиться, а также общая транзакционная пропускная способность как функция от времени.
Отчетливо видны три основных вида поведения:
Сравнимая производительность при отсутствии заблокированных транзакций. Пока все транзакции своевременно завершаются, имеются весьма незначительные отличия в производительности детерминированной и недетерминированной схем упорядочивания транзакций (независимо от вероятности конфликтов между их наборами чтения и записи). В действительности, оказывается, что в этом промежутке времени транзакционная система выполняет и фиксирует транзакции почти в том же порядке, что и детерминированная система.
Относительная чувствительность к наличию заблокированных транзакций. Когда одна из транзакций приостанавливает свое выполнение на одну секунду, детерминированная система быстро загромождается транзакциями, которые не могут ни завершиться (из-за конфликта блокировок), ни аварийно прекратить свое выполнение и перезапуститься. В традиционных случаях, в которых все блокировки сразу не запрашиваются, и реализуются другие недетерминированные механизмы переупорядочивания транзакций, производительность падает гораздо более плавно. Пологий участок кривой вероятности конфликтов блокировок, который намного быстрее достигается при наличии более высокой вероятности конфликтов двух транзакций, возникает из-за насыщенности системного пула потоков управления блокированными транзакциями.
В обеих системах чувствительность к застопориванию и серьезность его воздействия зависит от вероятности конфликтов транзакций. Во многих современных рабочих нагрузках OLTP эта вероятность невелика.
Поведение после исчезновения заблокированных транзакций. Независимо от модели поведения, после того, как приостановленная транзакция наконец-то завершается и освобождает свои блокировки, нагромождение запросов блокировки в менеджере блокировок почти мгновенно рассеивается, и пропускная способность восстанавливается до уровня, который наблюдался в первой фазе эксперимента.
Этот эксперимент ясно показывает, что в случаях, в которых возможны тупики или приостановка транзакций по каким-то другим причинам, схемы выполнения, обеспечивающие эквивалентность некоторому предопределенному порядку следования, непригодны.Следовательно, в эпоху, когда операции чтения с диска произвольным образом влияют на время выполнения транзакций, единственным жизнеспособным вариантом является недетерминированная схема переупорядочивания транзакций.
Другие детерминированные схемы управления параллелизмом
Предложенная в этой статье детерминированная система, основанная на блокировках, обеспечивает эквивалентность некоторому предопределенному порядку следования транзакций, но, конечно, имеются и другие механизмы, обеспечивающие поддержку этого свойства. Было бы интересно разработать, сравнить и испытать на тестовых наборах детерминированные варианты других схем управления параллелизмом – в частности, версионное управление параллелизмом.
Гладкие переходы между детерминированной и недетерминированной моделями выполнения/репликации
Почти наверняка иногда будет разумно допускать недетерминированное переупорядочивание транзакций и их аварийное завершение в некоторых репликах. Очевидно, это нельзя делать бесконтрольным образом, потому что реплики могут рассогласоваться. Поэтому мы планируем проанализировать возможность поддержки других традиционных методов репликации (протоколов фиксации внутри реплики, согласованности в конечном счете и методов пересылки журнала) таким образом, чтобы система могла гладко динамически переключаться между традиционной и детерминированной моделями выполнения и репликации в зависимости от имеющейся рабочей нагрузки и других изменяющихся условий.
Горизонтальная масштабируемость
Горизонтальная масштабируемость – возможность разделить данные, которыми управляет СУБД, между несколькими (обычно недорогими) машинами ("узлами") и распределить выполнение транзакций между несколькими разделами, поддерживая такой же интерфейс, как и у одноузловой системы – является все более важной целью разработчиков систем баз данных. По мере того, как все большее число приложений нуждается в транзакционной пропускной способности, превышающий ту, которую способна рентабельным образом обеспечить одна машина, растет потребность в горизонтально масштабируемых системах баз данных. Однако недерменированное поведение существенно увеличивает сложность и снижает производительность конструктивных решений ACID-совместимых систем баз данных.
Для обеспечения гарантий ACID в системах распределенной обработки транзакций в большинстве случаев используется распределенный протокол фиксации, обычно двухфазный. Такой протокол предназначен для сбора решений всех участвующих узлов о фиксации или аварийном завершении транзакции и гарантирования того, что достигнуто единое решение – даже несмотря на то, что во время выполнения протокола участвующие узлы могут выходить из строя. Накладные расходы на выполнение этих двух фаз протокола фиксации (а также дополнительное время, требуемое для удержания блокировок) снизить потенциально достижимую транзакционную пропускную способность разделенной системы. Это препятствие на пути к достижению высокой производительности привело к использованию технологий, ослабляющих свойства ACID (а именно, атомарность (atomicy) или изоляцию (isolation) транзакций) с целью получения масштабируемых распределенных систем баз данных (например, многих так называемых "NoSQL"-систем).
В детерминированных системах баз данных, основанных на использовании активной репликации, требуется использовать всего лишь однофазный протокол фиксации. Так получается из-за того, что в узлах, содержащих реплики, транзакции выполняются параллельно, так что отказ одной реплики не влияет на результирующее решение о фиксации или аварийном завершении транзакции. Поэтому не требуются дополнительные действия, предусматриваемые в двухфазном протоколе для обеспечения соответствующего выполнения при наличии потенциальной возможности отказа узла. Для транзакций, в которых отсутствует возможность нарушения ограничений целостности или возникновения других условий, приводящих к аварийному завершению, потребность в распределенном протоколе фиксации устраняется полностью (поскольку невозможны непредвиденные события типа возникновения тупиковой ситуации, приводящие к недетерминированному аварийному завершению транзакций). Тем самым, использование детерминированной схемы выполнения уменьшает, а для некоторых транзакций полностью устраняет наиболее значительную преграду на пути к созданию выскопроизводительных распределенных транзакционных систем.
Экспериментальные измерения декомпозированных зависимых транзакций первого порядка
Для экспериментального подтверждения описанных выше результатов мы реализовали декомпозицию простой зависимой транзакции первого порядка, схожей по структуре с транзакцией U из разд. 4. Эта транзакция производит поиск по вторичному индексу и обновляет запись, идентифицируемую результатом этого поиска. В качестве "линии отсчета" мы также реализовали транзакцию, которая выполняет ту же задачу (индексный поиск с последующим обновлением записи), но без наличия зависимости (т.е. с передачей в качестве аргумента полного набора чтения/записи). Затем выполняли изменяемую смесь этих двух транзакций, а отдельный, выделенный процессор изменяемое число раз в секунду обновлял каждый элемент индекса, вынуждая этот элемент указывать на другую запись.
Рис. 6. Измеренные пропускная способность и среднее число перезапусков зависимых транзакций первого порядка как функция от изменичивости их зависимостей.
На рис. 6 показаны общая транзакционная пропускная способность и среднее число перезапусков транзакции до того, как она могла выполниться вплоть до завершения – и то, и другое как функции от средней изменчивости элементов индекса. Приведены результаты для рабочих нагрузок, включающих 0%, 20%, 40%, 60%, 80% и 100% зависимых транзакций.
Как и следовало ожидать на рабочую нагрузку, состоящую полностью из независимых транзакций, по сути, не влияет частоты изменений индекса, в производительность более зависимых рабочих нагрузок падает по мере роста изменчивости.
Однако мы выяснили, что при наличии даже сильно зависимых рабочих нагрузок, если изменчивость находится в разумных пределах (меньше 1000 обновлений каждой записи в секунду), то декомпозиция транзакций для обеспечения возможности работы с вычисляемыми наборами чтения/записи оказывает пренебрежимо малое влияние на производительность.
Рис. 7. Транзакционная пропускная способность TPC-C (100% транзакций New Order), измеренная интенсивность конфликтов блокировок и средняя задержка транзакций.
От переводчика
В области транзакционных систем управления данными в новых средах, обеспечивающих простое горизонтальное масштабирование массивно-параллельных аппаратных средств (в частности, в "облачных" средах), продолжается борьба двух направлений. Первое из них ориентируется на обеспечение повышенных уровней масштабируемости и доступности за счет отказа от некоторых из свойств ACID транзакций. Представители второго направления стремятся полностью сохранить свойства ACID и добиться масштабируемости и доступности за счет, например, отказа от работы с дисковой памятью (т.е. в их системах базы данных поддерживаются только в основной памяти).
В обоих направлениях ведутся активные исследовательские (и даже производственные) работы, и регулярно публикуются интересные статьи. Чтобы не повторяться, сошлюсь на перечень переведенных на русский язык статей, авторов которых, скорее, можно отнести к лагерю "NoACID". Этот перечень содержится в моей вступительной заметке к ранее переведенной статье.
В направлении исследований транзакционных систем нового поколения наиболее известным является проект H-Store, в котором участвуют специалисты Массачусетского технологического института, Йельского университета, университета Браун и HP Labs. Общеизвестно, что этот проект были инициирован Майклом Стоунбрейкером (Michael Stonebraker), и на основе его начальных результатов при активнейшем участии того же Стоунбрейкера была создана компания VoltDB, первая версия коммерческого продукта которой была выпущена в самом конце весны 2010 г.
Однако это вовсе не означает конца работы над проектом H-Store. В начальной версии прототипа системы поддерживался только достаточно узкий класс транзакций, недостаточно были проработаны возможности горизонтального масштабирования системы. Участники проекта активно ищут новые методы управления транзакциями, которые позволили бы расширить круг возможных применений системы и добиться при этом не меньших уровней доступности и масштабируемости, чем те, которые обеспечиваются в системах NoACID.
Очень интересная статья была опубликована в Трудах конференции SIGMOD'2010.
В Трудах недавно прошедшей конференции VLDB'2010 опубликованы еще две статьи участников проекта: статья Абади и Томсона из Йельского университета, перевод которой вам предлагается в этот раз, и статья группы авторов из MIT, которую я также вскоре собираюсь перевести. Хотя на VLDB'2010 эти две статьи были поданы вне прямой связи с H-Store, я думаю, что какие-то результаты почти наверняка будут использованы в этом проекте.
В статье Абади и Томсона описывается подход к управлению транзакциями, при котором удается приблизиться к желательным уровням доступности и масштабируемости массивно-параллельных тразакционных систем за счет отказа от недетерминированного планирования транзакций. Описываются результаты теоретических и экспериментальных исследований, выполненных на очень высоком уровне. Вместе с тем, текст статьи нельзя считать идеальным: многие важные аспекты описаны "скорописью", некоторые важные выводы недостаточно обоснованы и т.д. Возможно, это связано с тем, что Александер Томсон (который, скорее всего, и писал статью) – всего лишь аспирант второго года обучения, и эта статья – первая в его жизни. Думаю, что для первого раза результат можно считать просто блестящим.
Так что прошу вас не обращать внимание на технические погрешности статьи, а постараться понять ее суть. Возможно, именно этот подход станет основой будущих транзакционных СУБД.
Сергей Кузнецов
Переупорядочивание в препроцессоре
В то время как произвольное переупорядочивание транзакций во время их выполнения, вероятно, подорвет детерминизм, начальный выбор порядка транзакций, эквивалентность которому обеспечивается, является гораздо более свободным. Нетрудно видеть, что если запрос на образование некоторой локальной транзакции поступает сразу после поступления заявки на образование некоторой конфликтной распределенной транзакции, то при сохранении порядка возникнет конфликт, а если поменять порядок локальной и распределенной транзакций, то вероятность конфликта, возможно, уменьшится. Мы планируем исследовать методы переупорядочивания транзакций, которые можно реализовать в препроцессоре, чтобы можно было снижать уровень конфликтности в рабочих нагрузках и расширять набор рабочих нагрузок, для которых была бы жизнеспособна модель детерминированного выполнения.
Планирование потоков управления в детерминированных системах
В традиционных системах транзакции блокируются только при запросе какой-либо одной блокировки. Поэтому планирование рабочих потоков управления может производится достачно простым образом: при освобождении ресурса нужно просто активизировать поток управления, который был блокирован вследствие его запроса. Если транзакции запрашивают сразу все блокировки и могут блокироваться из-за наличия нескольких конфликтов, такое решение может не быть наилучшим. Выполненные нами эксперименты показывают, что устранение лишних переключений контекста (т.е. отказ от преждевременной активизации потоков управления, заблокированных из-за наличия нескольких конфликтов) является важным фактором поддержки приемлемой производительности детерминированных систем при наличии высокой интенсивности конфликтов транзакций. В нашем текущем прототипе для обеспечения осмысленного планирования потоков управления используются методы, основанные на использовании таймеров, а также рандомизированные методы, но мы надеемся, что продолжение исследований в этой области позволит добиться более качественного планирования с меньшими накладными расходами.
Поддержка эквивалентности предопределенному порядку следования
Поскольку недерминированные аспекты современных систем проистекают из неточности ограничений сериализуемости ACID, для достижения полностью предсказуемого поведения мы требуем, чтобы допустимое поведение было эквивалентно одному предопределенному последовательному выполнению.
Простейшим способом, за счет которого протокол управления параллелизмом мог бы гарантировать эквивалентность некоторому порядку выполнения {T0, T1, ..., Tn, было бы устранение всякого параллелизма и выполнение транзакций по очереди в указанном порядке. Однако при наличии современных многоядерных машин схемы, допускающие простой большей части процессоров, очевидно, приводят к неоптимальному использованию компьютерных ресурсов и, соответственно, плохой производительности.
К счастью, можно использовать блокировки, чтобы допустить некоторую параллельность, по-прежнему гарантируя эквивалентность предопределенному порядку следования. Эквивалентности предопределенному порядку следования (равно как и освобождения от тупиковых ситуаций) можно достичь путем ограничения набора допустимых планов выполнения теми, которые обладают следующими свойствами:
Упорядоченные блокировки (ordered locking). Для любой пары транзакций Ti и Tj, запрашивающих блокировку некоторой записи r, если i < j, то Ti должна запросить свою блокировку раньше, чем это сделает Tj.
Выполнение вплоть до завершения (execution to completion). Каждая транзакция, поступающая в систему, должна продолжать выполняться вплоть до своего завершения – пока она либо не зафиксируется, либо не завершится аварийным образом вследствии детерминированной логики программы. Поэтому, если завершение транзакции по какой-либо причине задерживается (например, из-за аппаратного отказа в пределах системы, поддерживающей реплику базы данных), то система должна поддерживать эту транзакцию активной до тех пор, пока она не завершится, или пока сама эта система-реплика не будет ликвидирована – даже если другие транзакции ожидают освобождения блокировок, удерживаемых блокированной транзакцией.
На практике упорядоченное блокирование обычно реализуется таким образом, что от транзакций требуется запрос всех блокировок сразу после входа в систему, хотя существуют классы транзакций, для которых это может оказаться невозможным. Мы подробно анализируем эти случаи в подразделе 4.2. Однако для целей сравнения, описываемого в следующем разделе, мы рассматриваем очень упрощенную реализацию такой схемы.
Это известный метод предупреждения тупиковых ситуаций. Примером системы, в которой блокировки производятся таким образом, является Postgres-R [13].
В некоторых ситуациях – например, в тех случаях, когда транзакция детерминированным образом застопоривается – может оказаться разумным временно переключиться на традиционную схему выполнения и репликации. Нахождение бесшовной модели переключения "на лету" моделей выполнения может стать увлекательным предметом будущих исследований.
Подробности эксперимента с "загромождением"
Индексный поиск происходил путем обхода B+-деревьев, а записи напрямую адресовались их первичными ключами. Обновляемые записи выбирались с использованием распределения Гаусса таким образом, чтобы любая пара транзакций конфликтовала, по крайней мере, на одном элементе данных с легко измеряемой и переменной вероятностью.
Рис.1. Измеренные вероятность конфликта блокировок и транзакционная пропускная способность за интервал времени в три секунды. Две транзакции конфликтуют с вероятностью 0,01%, 0,1% и 1% соответственно.
Как показывает рис. 1, независимо от схемы выполнения, пиковая производительность системы оказывается выше при более высокой интенсивности конфликтов. Возрастающий перекос в распределении выбора записей приводит к большей интенсивности конфликтов блокировок, поскольку возрастает вероятность обращения к некоторым записям всех транзакций. Но одновременно возрастает вероятность нахождения требуемых данных в кэше, что положительно влияет на пропускную способность при отсутствии загромождения.
Прототип детерминированной СУБД
Поскольку все большее число транзакционных приложений полностью помещается в основной памяти, аппаратные средства становятся все более быстрыми, дешевыми и надежными, а в рабочих нагрузках OLTP все более преобладают короткие, четко организованные транзакции, реализуемые на основе хранимых процедур, мы предвидим все более редкое появление сценариев, вызывающих загромождение детерминированных систем. В пользу детерминированных систем также говорят следующие простые наблюдения:
Использование преимуществ согласованной активной репликации. Механизмы мгновенного преодоления отказов (failover) систем баз данных с активной репликацией могут радикально сократить воздействие отказов аппаратуры внутри системы, содержащей реплику. Сильно реплицированные системы могут также помочь скрыть падение производительности, затрагивающее только часть реплик.
Распределенные запросы только по чтению. Запросы только по чтению требуется направлять только в одну реплику. В качестве варианта, более продолжительные запросы только по чтению часто можно расщепить по нескольким репликам для сокращения задержки, балансировки нагрузки и уменьшения эффекта загромождения, которое могло бы возникнуть, если бы запрос целиком выполнялся над одной репликой. Конечно, долговременные запросы только по чтению все чаще избегаются разработчиками сегодняшних транзакционных приложений – вместо этого они направляются в хранилища данных.
Реализация прототипа и экспериментальная установка
Наш прототип реализован на языке Си++. Все транзакции вручную закодированы внутри системы. Все тестовые испытания производились на Linux-кластере, состоящем из четырехъядерных машин Intel Xeon 5140, каждая из которых была оснащена четырьмя гигабайтами основной памяти 667 MHz FB-DIMM DDR2. Все машины были объединены в полнодуплексную 100-мегабитную локальную сеть. Ни в одном из наших экспериментов пропускная способность сети не становилась узким местом.
Репликация
Поддержка репликации в базах данных 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]), а затем направлять их пакетами в каждый узел, содержащий реплики, для детерминированного выполнения. Это будет гарантировать, что в каждом из этих узлов результирующее состояние реплики будет согласовано с состояниями всех других реплик, и не потребуются накладные расходы для достижения каких-либо дополнительных соглашений или синхронизации.
Родственные исследования
Системы баз данных, в которых обеспечиваются более строгие гарантии сериализуемости, чем эквивалентность некоторому порядку следования, существуют более трех десятилетий. Например, предлагалось гарантировать эквивалентность заданному порядку временных меток транзакций с использованием разновидности схемы управления параллелизмом с упорядочиванием на основе временных меток, называемой консервативной схемой упорядочивания по временным меткам (conservative T/O) [3]. (Позже эту схему стали называть "предельной консервативной схемой временных меток" ("ultimate conservative T/O" )[5], чтобы отличать ее от других схем управления параллелизмом с упорядочиванием по временным меткам, в которых допускается аварийное завершение транзакций и переупорядочивание.) Conservative T/O задерживает выполнение любой операции над базой данных до тех пор, пока заведомо не будут выполнены все потенциально конфликтующие операции с меньшими значениями временных меток. Как правило, это реализуется за счет того, что планировщик операций ожидает получения сообщений от всех возможных источников транзакций, а затем планирует выполнение операции чтения или записи с наименьшей временной меткой среди всех источников.
Эта бесхитростная реализация чрезмерно консервативна, поскольку, как правило, сериализует все операции записи в базу данных. Однако можно добиться дополнительного параллелизма метода разбиения транзакций на классы, использованного в SDD-1 [6], где каждая транзакция включалась в некоторый класс транзакций, и только для потенциально конфликтующих классов транзакций требовалась консервативная обработка. Такому подходу способствует заблаговременное объявление наборов чтения и записи транзакций. В нашей работе совершенствуются эти старые методы для обеспечения эквивалентности одному порядку следования. Однако мы решили реализовать свою детерминированную систему баз данных с использованием техники блокировок и оптимистических методов, позволяющих обойтись без заблаговременного знания наборов чтения и записи, поскольку в большинстве современных систем баз данных управление параллелизмом основывается на технике блокировок, а не технике временных меток.
Теоретическое обоснование того, что детерминированное выполнение внутри каждой системы, содержащей реплику базы данных, облегчает активную репликацию, можно найти в работе Шнейдера (Schneider) [23]. В этой работе демонстрируется, что если каждая система, содержащая реплику базы данных, получает транзакции в одном и том же порядке и обрабатывает их детерминированным, последовательным образом, то все реплики останутся согласованными. К сожалению, то требование, что каждая система с репликой базы данных выполняет транзакции с использованием одного потока управления, для сегодняшних высокопараллельных систем баз данных не является реалистичным. К аналогичному выводу пришли и Хименес-Перис (Jimenez-Peris) и др. [11]. Поэтому они применили детерминированный планировщик потоков управления, позволяющей системе с репликой базы данных выполнять транзакции с использованием нескольких потоков управления. Каждый поток управления одинаково планируется в каждой системе-реплике (с тщательным учетом возможности чередования работы локальных потоков управления с работой, возникающей в результате получения сообщений от других серверов в ходе выполнения распределенных транзакций). Наша работа отличается от работы Хименеса-Периса и др., поскольку мы допускаем произвольное планирование потоков управления (что обеспечивает планировщику большую гибкость и позволяет незамедлительно обрабатывать приходящие сетевые сообщения, а не ждать, пока не завершится работа локальных потоков управления) и обеспечиваем детерминизим за счет изменения протокола управления параллелизмом в системе баз данных.
В недавней работе Басиле (Basile) и др. [1] подход Хименеса-Периса и др. расширяется за счет перехвата запросов взаимного исключения (mutex), поступающих от потоков управления перед тем, как они обращаются к совместно используемым данным. Это позволяет повысить уровень параллелизма, позволяя планировать произвольным образом потоки управления, в которых не производится доступ к одним и тем же данным.
Однако в этом решении требуется посылка сетевых сообщений от ведущих узлов в узлы-реплики для обеспечения взаимного исключения конфликтующих потоков управления, в то время как в нашем решении для управления параллелизмом обмен сетевыми сообщениями между репликами не требуется.
Идея упорядочивания тразакций и предоставлении блокировок на запись в соответствии с этим порядком была представлена в работе Кемме (Kemme) и Алонсо (Alonso) [13]. Наша работа отличается от предложенного ими подхода тем, что в нашем случае не используются теневые копии (shadow copy), и требуется всего лишь надежный протокол обмена груповыми сообщениями, гарантирующий порядок их доставки, при посылке сообщений от препроцессора к базе данных – никогда внутри многораздельных транзакций, поскольку в детерминированной системе это привело бы к недопустимо долгим интервалам удержания блокировок. Кроме того, мы обрабатываем зависимые транзакции с использованием оптимистического метода.
Гарсиа-Молина (Garcia-Molina) и Салем (Salem) [9] заметили, что использование систем баз данных в основной памяти (main memory database system) приводит к убыстрению транзакций и снижению вероятности конфликтов блокировок. Кроме того, они утверждают, что во многих случаях лучше всего выполнять транзакции полностью последовательно и полностью избегать накладных расходов блокировок. В нашей работе приходится не только учитывать, что транзакции над данными основной памяти выполняются быстрее транзакций, которым приходится обращаться к дискам, но и принимать во внимание, что продолжительность некоторых транзакций увеличивается из-за потребности в передачи и приеме сетевых сообщений (требуемых для выполнения распределенных транзакций). Кроме того, мы не требуем, чтобы транзакции выполнялись последовательно (хотя обеспечиваем эквивалентность заданному порядку следования); несколько разных транзакций может параллельно выполняться в нескольких потоках управления.
Уитни (Whitney) и др. [26], Пачитти (Pacitti) и др. [18], Стоунбрейкер (Stonebraker) и др. [24] и Джонс (Jones) и др. [12] предлагают обрабатывать транзакции в распределенных системах баз данных без управления параллелизмом путем последовательного выполнения транзакций в одном потоке управления на каждом узле (где в некоторых случаях узел может являться одним ядром процессора в многоядерном сервере [24]).
Уитни и др. не поддерживают активную репликацию (обновления для реплик сначала журнализуются), но авторы двух последних статей используют преимущества детерминизма для выполнения активной репликации. Однако в обоих случаях проблему представляют многоузловые (распределенные) транзакции. В нашей схеме детерминированное управление параллелизмом позволяет обойтись без двухфазной фиксации, что существенно снижает стоимость многоузловых транзакций и обеспечивает высокий уровень параллелизма потоков управления.
Разработчики решений уровня промежуточного программного обеспечения (middleware), таких как, например, разработка компании xkoto (недавно поглощенной компанией Teradata) и Tashkent-API [8], пытаются производить репликацию в нескольких системах баз данных путем выполнения в каждой системе одних и тех же транзакций в одном и том же порядке. Однако поскольку системы баз данных не обеспечивают эквивалентности какому-либо заданному порядку следования, в этих системах middleware для предотвращения расхождения реплик снижается уровень параллелизма транзакций, отправляемых в системы баз данных, что потенциально приводит к понижению пропускной способности. Наше решение реализуется внутри баз данных, что позволяет избежать чрезмерной сложности систем, основанных на промежуточном программном обеспечении.
Тэй (Tay) и др. с использованием детальной аналитической модели сравнивают традиционную динамическую схему блокировок со статической схемой (когда все блокировки в транзакции запрашиваются при ее начале) [25]. Однако в случае статической схемы, если невозможно получить все блокировки сразу, транзакция аварийно завершается и запускается заново (и, следовательно, протокол не является детерминированным). Кроме того, эта модель не работает в том случае, когда местоположение данных, которые требуется блокировать, заранее не известно.
TPC-C и разделенные данные
Для изучения характеристик производительности своего детерминированного протокола выполнения транзакций в распределенной и разделенной системе мы реализовали подмножество тестового набора TPC-C, на 100% состоящее из транзакций New Order. Транзакция New Order имитирует клиента, размещающего некоторый электронный заказ, вставляющего несколько записей и изменяющего уровень запасов для 5-15 типов товаров (из 100000 видов товаров, имеющихся на каждом складе).
Рис.3. Детерминированная и традиционная пропускная способность рабочей нагрузки TPC-C (100% транзакций New Order) при изменении частоты многораздельных транзакций.
На рис. 3 показана пропускная способность для детерминированного и традиционного выполнения рабочей нагрузки, состоящей из транзакций New Order тестового набора TPC-C, при изменении частоты появления многораздельных транзакций (в которых часть заказа клиента должна заполняться за счет склада, данные которого располагаются в удаленном узле). В этих экспериментах данные распределялись по двум разделам. В показанные результаты включены измерения для двух и десяти складов (в первом случае по одному складу на каждый раздел, во втором – по пять складов). Более подробное обсуждение экспериментальной установки см. в приложении.
Пока частота появления многораздельных транзакций невелика, транзакции New Order остаются исключительно короткими, и обе схемы выполнения при заданном размере набора данных обеспечивают сравнимую пропускную способность – как и в экспериментах, описанных в разд. 3, когда в среде выполнения отсутствовали аномально медленные транзакции. При наличии всего двух складов обе схемы обеспечивают лучшее использование кэша, чем в случае десяти складов, что приводит в более высокой пропускной способности при отсутствии многораздельных транзакций. Однако чем меньше имеется записей, тем больше наблюдается конфликтов блокировок. Транзакции New Order конфликтуют с вероятностью примерно 0,05 при наличии двух складов и с вероятностью около 0,01 при наличии десяти складов.
Поэтому для обеих систем общее падение производительности при возрастании частоты появления многораздельных транзакций оказывается большим при наличии двух складов, чем в случае десяти складов (поскольку многораздельные транзакции выполняются дольше, и это усиливает эффект конфликта блокировок).
При сравнении пропускной способности систем, основанных на двух разных моделях выполнения, можно было бы ожидать, что, как только сетевые задержки начнут приводить к более продолжительному удержанию блокировок, застопоренное поведение детерминированной систем приведет к большему падению ее производительности, чем у традиционной системы (особенно в случае двух складов, в котором вероятность конфликта блокировок очень высока). На самом же деле, вы видим обратное: независимо от числа складов (и, следовательно, вероятности конфликтов) при появлении многораздельных транзакций производительность детерминированного протокола падает медленнее производительности традиционных блокировок.
Этот эффект можно объяснить тем, что при использовании традиционной схемы выполнения блокировки удерживаются дополнительное время при выполнении двухфазного протокола фиксации. В традиционном случае все блокировки удерживаются на все время двухфазной фиксации. Однако при использовании детерминированного выполнения наш препроцессор направляет каждую новую транзакцию в каждый узел, участвующий в ее обработке. Фрагмент транзакции, посылаемый в каждый узел, снабжается информацией о том, какие данные потребуются из каждого другого узла (например, потребуется ли удаленное чтение, и могут ли произойти условные аварийные завершения), прежде чем обновления, производимые этим фрагментом можно будет "зафиксировать". После получения всех требуемых данных из всех ожидаемых узлов данный узел может безопасным образом освободить блокировки текущей транзакции и перейти к следующей транзакции. Не требуется никакого протокола фиксации, чтобы гарантировать, что отказ узла не влияет на окончательное решение о фиксации или аварийном завершении, потому что отказ узла – это недетерминированное событие, а недетерминированные события не могут служить причиной аварийного завершения транзакции (транзакция зафиксируется в некоторой реплике, которую, как отмечалось ранее, можно будет использовать для восстановления отказавшего узла).
Это означает, что при обработке многораздельной транзакции с использованием детерминированного управления параллелизмом каждому узлу, участвующему в обработке транзакции, требуется послать по одному сообщению в каждый другой узел, участвующий в обработке той же транзакции, и получить от каждого такого узла не более одного сообщения. Если все узлы, участвующие в выполнении многораздельной транзакции, посылают сообщения примерно в одно и то же время (как часто бывало в наших экспериментах, поскольку многораздельные транзакции естественным образом порождают синхронизационные события в рабочей нагрузке), блокировки удерживаются только в течение дополнительного времени, требуемого для однонаправленной передачи одного сетевого сообщения.
При применении традиционной модели выполнения каждая поступающая транзакция, которая блокируется незавершенной многораздельной транзакцией New Order вынуждена оставаться блокированной на все время выполнения двухфазной фиксации, что приводит к загромождению системы неработающими транзакциями и еще больше повышает вероятность конфликтов блокировок у последующих поступающих транзакций. Измерения реальной вероятности конфликтов блокировок и средней задержки транзакций, выполненные в ходе этих экспериментов, приведены в приложении. Они показывают, что увеличение продолжительности распределенных транзакций приводит как к большей вероятности конфликтов блокировок, чем та, которая наблюдается при использовании детерминированной схемы, так и к более высокой стоимости, связанной с каждым проявлением конфликта блокировок.
Трудные классы транзакций
Не для всех транзакций можно запросить блокировки всех записей, к которым в ней будут происходить обращения, сразу после поступления транзакции в систему. Рассмотрим транзакцию
U(x): y ← read(x) write(y)
где x является первичным ключом записи, y – локальная переменная, и write(y) обновляет запись, первичный ключ которой содержится в y.
Очевидно, что для транзакций типа U невозможно запросить блокировки сразу после входа в систему (если только не заблокировать целиком таблицу, связанную с y), поскольку механизм исполнения никаким образом не может определить значение y, не выполнив до этого чтение записи x. Мы называем такие транзакции зависимыми транзакциями (dependent transactions). В нашей схеме проблема зависимых транзакций решается путем их разбиения на несколько транзакций, из которых все транзакции, кроме последней, работают с целью обнаружения полного набора чтения/записи, так что последняя транзакция может начать свое выполнение при наличии полного знания о том, к чему она будет обращаться. Например, транзакцию U можно разбить на транзакции:
U1(x): y ← read(x) newtxnrequest(U2(x, y))
и
U2(x, y): y' ← read(x) if (y' ≠ y) newtxnrequest(U2(x, y')) abort() else write(y)
U2 не включается в упорядоченные пакеты транзакций, направляемые препроцессором в системы, которые содержат реплики, до тех пор, пока в препроцессор не поступит результат U1 (в этот промежуток времени может выполняться произвольное число транзакций). В U2 имеется некоторая информация о том, что, вероятно, следует заблокировать, и соответствующие элементы данных немедленно блокируются. После этого U2 проверяет, что заблокированы корректные элементы данных (т.е. что никакая транзакция, выполнявшаяся в промежуток времени между завершением выполнения U1 и началом выполнения U2 не изменила зависимость). Если эта проверка удается, то выполнение U2 может продолжаться. Иначе U2 должна завершиться аварийным образом (и освободить свои блокировки).
Препроцессор оповещается об этом аварийном завершении и снова включает U2 в следующий пакет транзакций, направляемый в системы с репликами базы данных. Заметим, что все действия "аварийно завершить и сделать новую попытку" являются детерминированными (в промежутке времени между завершением выполнения U1 и началом выполнения U2 над всеми репликами будут выполняться одни и те же транзакции, и, поскольку повторная попытка выполнить U2 после ее аварийного завершения делается препроцессором, все последующие действия "аварийно завершить и сделать новую попытку" также являются детерминированными).
Поскольку для разбиения U требуется всего одна дополнительная транзакция, вычисляющая полный набор чтения/записи, мы называем U зависимой транзакцией первого порядка. Зависимые транзакции первого порядка часто встречаются в рабочих нагрузках OLTP в виде последовательности "индексный поиск – доступ к записи". Зависимые транзакции более высокого порядка, такие как следующая зависимая транзакция второго порядка:
V(x): y ← read(x) z ← read(y) write(z)
в реальных рабочих нагрузках встречаются гораздо реже, но тот же самый метод разбиения позволяет справиться с обработкой зависимых транзакций произвольного порядка.
Принцип работы этого метода похож на принцип оптимистического управления параллелизмом (optimistic concurrency control, OCC), и так же, как в в OCC, при выполнении декомпозированных зависимых транзакций имеется риск "зависания" (starvation), если их зависимости будут часто изменяться в промежутках между выполнением декомпозированных частей.
Чтобы лучше понять применимость и стоимость этого метода разбиения, мы выполнили ряд экспериментов и подкрепили их исследованиями на основе аналитической модели. Детали экспериментов и описание модели содержатся в приложении. Мы установили, что производительность при наличии рабочих нагрузок, насыщенных зависимыми транзакциями первого порядка, обратно пропорциональна интенсивности обновлений зависимостей декомпозированных транзакций.
Например, при наличии рабочей нагрузки, состоящей из транзакций Payment из тестового набора TPC-C (в которых вместо первичного ключа часто задается имя заказчика, что делает необходимым индексный поиск), пропускная способность заметным образом пострадает только в том случае, если имя каждого заказчика будет обновляться исключительно часто – сотни или даже тысячи раз в секунду. Накладные расходы, вызываемые добавлением читающей транзакции, которая устанавливает зависимость, почти совсем незаметны. Поскольку в реальных рабочих нагрузках OLTP редко встречаются зависимости по часто обновляемым данным (например, над изменчивыми данными обычно не создаются вторичные индексы), мы заключаем, что наличие рабочих нагрузок с большим числом зависимостей не может служить основанием для отказа от детерминированной схемы управления параллелизмом.
Эта схема также хорошо встраивается в среды систем баз данных, позволяющие пользователям регулировать уровни изоляции своих транзакций для повышения производительности. Возможна простая оптимизация, приводящая к тому, что зависимые чтения будут выполняться на уровне изоляции чтения зафиксированных данных (read-committed) (а не на уровне изоляции полной сериализуемости (serializable)). Тогда зависимая транзакция будет по-прежнему разбиваться на две транзакции, но во второй транзакции больше не потребуется проверять, что ранее прочитанные данные по-прежнему являются точными. Тем самым, эта проверка (и потенциальное аварийное завершение транзакции) устраняется. Заметим, что в системах баз данных, основанных на традиционной двухфазной блокировке, также приходится бороться с высокой интенсивностью конфликтов, которые свойственны рабочим нагрузкам, насыщенным долговременными запросами только на чтение, и что во многих таких системах уже поддерживается выполнение транзакций на более низких уровнях изоляции. Мы предвидим, что разработчикам приложений, предупрежденным о том, что производительность выполнения зависимых транзакций может быть повышена, если эти транзакции выполняются на более низком уровне изоляции, понадобится некоторый период времени для "выяснения отношений" с детерминированной системой баз данных.
В системах, основанных на поддержке версий (multiversion) и мгновенных снимков (snapshot), запросы только на чтение не порождают проблем, но этот подход ортогонален подходу, описываемому в данной статье, поскольку возможны версионные реализации детеминированных систем баз данных.
Вклад авторов
В этой статье мы представляем модель выполнения транзакций баз данных, обладающую тем свойством, что результаты любой транзакции Tn однозначно определяются исходным состоянием базы данных и упорядоченной последовательностью предыдущих транзакций {T0, T1, ..., Tn-1} (разд. 2).
Кроме того, мы реализуем прототип системы баз данных с использованием своей схемы детерминированного выполнения, а также (для сравнения) другой схемы, поддерживающей традиционные выполнение и протокол управления параллелизмом (двухфазный протокол блокировок). Сравнительное тестирование нашего начального прототипа на одной системе (без учета репликации), сопровождавшееся аналитическим моделированием, показывает, что при использовании современной аппаратуры соотношение показателей производительности детерминированного и недетерминированного решений значительно изменяется. Детерминированная схема обеспечивает значительно более низкую пропускную способность, чем традиционные схемы, при наличии долгих задержек при выполнении транзакции (возникающих, например, из-за чтения страницы с диска). Однако по мере того, как транзакции становятся короче и меньше различаются по длине, детерминированная схема приводит к почти полному исчезновению накладных расходов (разд. 3 и 4). Поэтому мы приходим к выводу, что следует пересмотреть проектные решения, допускающие недетерминизм.
Мы также проанализировали характеристики производительности своей детерминированной схемы выполнения в случае, когда данные разделяются по нескольким машинам (разд. 5). Мы установили, что на рабочих нагрузках, содержащих транзакции, которые затрагивают несколько разделов, наш прототип превосходит по производительности системы, основанные на традиционном блокировочном управлении параллелизмом и двухфазной фиксации.
в системах баз данных исторически
Протоколам управления параллелизмом в системах баз данных исторически свойственно порождение недетерминированного поведения. Эти протоколы традиционно допускают параллельное выполнение нескольких транзакций, чередуя их операции чтения из базы данных и записи в базу данных и обеспечивая при этом эквивалентность результирующего состояния базы данных такому состоянию, которое было бы получено при выполнении этих транзакций в некотором последовательном порядке. В этой фразе ключевым модификатором является слово некоторый. Никогда заранее не известно, какой именно порядок выполнения транзакций будет обеспечиваться алгоритмом сериализации транзакций; он зависит от большого числа факторов, полностью ортогональных к порядку реального поступления транзакций в систему, частности, от следующего:
планирования процессов и потоков управления;
управления буферами и кэшем;
сбоев аппаратуры;
изменяющейся задержке сети;
схем разрешения тупиковых ситуаций.
Недетерминированное поведение в системах баз данных приводит к трудностям при реализации репликации баз данных и горизонтально масштабируемых распределенных баз данных. Обсудим эти проблемы по порядку.
В этой статье мы заново
В этой статье мы заново рассмотрели плюсы и минусы наличия недетерминированного поведения в системах баз данных.
Мы показали, что в свете современных технологических тенденций модель выполнения транзакций в системах баз данных, гарантирующая эквивалентность некоторому предопределенному последовательному порядку выполнения с целью обеспечения детерминированного поведения, является жизнеспособной при наличии рабочих нагрузок OLTP над базами данных в основной памяти, значительно облегчая активную репликацию. Кроме того, в детерминированных системах баз данных становится ненужной двухфазная фиксация, что снимает преграды на пути наращивания их производительности.
