В этом посте представлен обзор текущих проблем, возникающих при создании систем удовлетворяющих требованиям ACID и возможности их преодоления без перехода к NoSQL системам.

Широко известно, что набирающее последнее время популярность NoSQL движение направлено отнюдь не на исключение SQL из СУБД. Скорее основной целью систем, подобных Bigtable, HBase, Hypertable, Cassandra, Dynamo, SimpleDB (и множеству других хранилищ "ключ-значение"), PNUTS/Sherpa и прочих является масштабируемость системы. Масштабирование традиционных ACID реляционных СУБД на дешевых серверах и архитектуре "shared-nothing", оказывается очень сложной задачей. Поэтому вышеуказанные системы отбрасывают некоторые из ACID требований, чтобы достичь масштабируемости. Однако масштабируемость в данном случае достигается за счет усложнения разработки приложений, т.к. необходимые примитивы синхронизации запросов и транзакций нужно создавать самостоятельно. Таким образом, NoSQL скорее означает NoACID.

В этой заметке нам хотелось бы прежде всего объяснить, почему так тяжело масштабируется ACID-система. В то же время хочется подчеркнуть, что NoSQL\NoACID слишком "простой" путь на наш взгляд. Вместо того, чтобы обходить проблемы, мешающие масштабированию ACID систем, было бы лучше попытаться их решить. Несомненно, это сложная задача, но у нас есть пара новых идей.

ACID, Масштабируемость и репликация.

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

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

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

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

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

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

Решения класса NoACID.

Разработчки NoSQL систем, зная о подобных ограничениях, снижают ACID требования для достижения масштабируемости и высокой доступности. Обычно ACID требования изменяются двумя способами.
Во-первых, системы типа BigTable, SQL Azure, репликаций MySQL и хранилищ типа "ключ-значения" поддерживают атомарность и изолированность транзакций только когда каждая транзакция затрагивает только данные некоторого подмножества записей бд (одного кортежа в BigTable и хранилищах "ключ-значения" или одну секцию базы данных в SQL Azure и репликаций Azure). Это устраняет необходимость в дорогостоящем протоколе распределенной фиксации транзакций, но в результате любая транзакция, затрагивающая больше чем одно подмножество должна быть разбита на разные транзакции на уровне приложения. В этой ситуации система больше не гарантирует атомарность или изолированность на уровне подобных логических транзакций. Поэтому разработчик должен реализовывать требуемую ACID функциональность для подобных транзакций на уровне приложения.

В качестве второго варианта испольуется "ленивая" репликация, при которой согласованность достигается со временем. Жертвуя строгой согласованностью, можно достичь высокой доступности в сетевой среде, в соответствие с CAP-теоремой. Исключая случаи некоторых широко известных Web 2.0 приложений, потеря согласованности является слишком дорогой ценой и ведет к усложнению разработки приложений.

Как можно изменить ACID без перехода к NoSQL решениям.

Как нам кажется, решение разработчиков NoSQL систем снизить ACID требования является слишком простым ответом на возникающие проблемы с масштабируемостью и реплицируемостью систем. В NoSQL системах заботы об атомарности, согласованности и изолированности транзакций просто перекладываются на плечи разработчика. На наш взгляд, необходимо придумать решения, позволяющие масштабировать ACID системы на shared-nothing архитектурах. Решению подобных проблем посвящено наше иссследование и статья, которую мы будем представлять на конференции VLDB'10.

Как бы парадоскально это не казалось, на наш взгляд, проблема не в том, что ACID требования слишком высокие, что серьезно мешает масштабировать подобные системы на shared-nothing кластерах, а скорее, наоборот, требования слишком низкие и из-за этого старадает масштабируемость систем.

Корнем этих проблем является изолируемость транзакций в ACID системе. В частности, требование сериализуемости транзакций (стандартный уровень изолированности транзакций в ACID системе) гарантирует что выполнение набора транзакций происходит в порядке, эквивалентном некоторому последовательному, монопольному запуску каждой из этих транзакций. В реальности выполнение может быть многопоточным и параллельным. Т.е. если три транзакции A, B и C выполняются одновременно в ACID системе, ее финальное состояние будет одинаковым, если запустить их последовательно одну за одной. Однако нет никаких гарантий относительно порядка выполнения транзакций, это может быть и A-B-C и В-A-C и пр.

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

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

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

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

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

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

В нашей статье, “The Case for Determinism in Database Systems”, мы предлагаем архитектуру, модель выполнения и прототип системы, которая обрабатывает взаимные блокировки, сбои без отката транзакций и позволяет параллельное выполнение. Более полное описание системы содержится в нашей статье. Основной идеей является упорядоченное блокирование вкупе с оптимистичной моделью эскалирования блокировок. При этом система, будучи полностью детерминированной, легко реплицируется и обеспечивает восстановление от сбоев.

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

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