Будущее транзакционных систем

Происходящие сегодня крупные изменения в области аппаратных средств, а именно возможность сравнительно дешевого построения неограниченно горизонтально масштабируемых кластерных систем — публичных или частных облаков, традиционных кластеров и т.п. — вызвали интерес к СУБД без совместного использования ресурсов (shared nothing). Работы ведутся на двух основных фронтах.

Первый фронт образуют основные поставщики интернет-услуг: Google, Yahoo!, Amazon и т. д., которые для своих собственных нужд и для обеспечения публично доступных облачных сервисов разрабатывают средства управления данными, идеологически и архитектурно отходящие от канонов сообщества баз данных. Во многом именно с деятельностью этих компаний связано возникновение понятия NoSQL.

На втором фронте находятся последователи концепции "один размер непригоден для всех", предложенной Майклом Стоунбрейкером, в которой основными являются два соображения.

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

К этому лагерю относятся исследовательские группы ряда американских университетов, VoltDB, HPVertica, Asterdata и другие компании.

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

На обоих фронтах ведутся работы по двум основным направлениям: аналитические системы управления данными, пригодные для построения над ними приложений категории OLAP (OnLine Analytical Processing — "оперативная аналитическая обработка"), и транзакционные системы управления данными, пригодные для построения приложений категории OLTP (OnLine Transaction Processing — "оперативная обработка транзакций"). В первом направлении представителей двух лагерей в прошлые годы разделяло прежде всего отношение к NoSQL-технологии анализа данных MapReduce [ 1 ]. Не так давно апологеты NoSQL считали, что MapReduce заменит в динамических кластерных архитектурах параллельные аналитические системы баз данных, а исследователи из второго лагеря обвиняли создателей MapReduce в возврате к дремучему прошлому, когда технологий баз данных не существовало [ 2-3 ]. Однако сегодня сообщество баз данных приняло технологию MapReduce и научилось ее использовать.

Транзакции и бизнес

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

При взаимодействии пользователя с онлайн-приложением могут возникать задержки из-за недоступности каких-либо ресурсов на уровне управления данными. В условиях жесткой конкуренции на рынке таких приложений задержки могут оказаться губительными для бизнеса, поэтому не менее важным требованием к системе управления данными является доступность, гарантирующая отсутствие или, как минимум, по возможности снижающая вероятность возникновения таких задержек. Хуже всего на клиентов веб-сервисов действуют сообщения типа service unavailable, поэтому многие компании готовы согласиться с тем, что в некоторых случаях результаты выполнения транзакций системой управления данными будут некорректными, если при этом доступность системы будет максимально возможной. В работе [ 5 ] даже выстраивается некоторая "теоретическая" база, оправдывающая перед пользователями возможное некорректное поведение приложений тем, что "потребность в извинениях возникает в любом бизнесе". Другими словами, поскольку в любом бизнесе могут возникать ошибки, за которые придется извиняться перед клиентами, то почему бы не отнести к числу таких ошибок и подобное поведение приложений — рано или поздно наличие некорректности будет установлено, и соответствующий пользователь получит моральную или материальную компенсацию.

ACID-транзакции и «теорема» Брювера

Более серьезным "теоретическим" основанием NoSQL-разработок, в которых общепринятые полезные свойства систем управления данными приносятся в жертву доступности, является "теорема CAP", впервые сформулированная Эриком Брювером (хотя утверждение, названное Брювером теоремой, таковым признать трудно из-за отсутствия какой-либо формальной постановки задачи). Мало кто из сообщества NoSQL серьезно разбирался в сути этой "теоремы", но широко распространено мнение, что она означает невозможность поддержки в одной распределенной системе управления данными свойств согласованности данных (Consistency), доступности (Availability) и устойчивости к разделению сети (Partitioning). Обобщая consistency в смысле Брювера до полного набора свойств ACID (Atomicy, Consistency, Isolation, Durability) классических транзакций баз данных, сообщество NoSQL с готовностью отказывается от реальной поддержки транзакций в своих системах (поэтому, например, в [ 7 ] предлагается переименовать NoSQL в NoACID).

Аббревиатура ACID впервые появилась в 1983 году в статье Тео Хаердера и Адреаса Рейтера [ 8 ], где, в частности, говорится, что концепция транзакции требует, чтобы все ее действия выполнялись нераздельно: либо все действия должным образом отражаются в состоянии базы данных, либо ничего не происходит. Для достижения такой неделимости транзакция должна обладать следующими четырьмя свойствами:

• атомарность (Atomicity) — транзакция должна иметь тип "все или ничего", и, что бы ни произошло, пользователь должен знать, в каком состоянии находится его транзакция;
• согласованность (Consistency) — транзакция, достигающая своего нормального завершения и тем самым фиксирующая свои результаты, сохраняет согласованность базы данных;
• изоляция (Isolation) — события, происходящие внутри транзакции, должны быть скрыты от других одновременно выполняемых транзакций;
• долговечность (Durability) — после того, как транзакция завершилась и зафиксировала свои результаты в базе данных, система должна гарантировать, что эти результаты переживут любые последующие сбои.

Эти четыре свойства описывают основные черты парадигмы транзакций, которые влияют на многие аспекты разработки СУБД. Чтобы иметь хотя бы какую-нибудь возможность говорить о транзакционной системе управления данными, в которой не поддерживается свойство согласованности транзакций, совершенно необходимо определить, что в этом случае понимается под термином "транзакция". К сожалению, сегодня во многих случаях (в особенности, это свойственно направлению NoSQL) говорят о поддержке OLTP-приложений, не уточняя, что за транзакции имеются в виду. Поэтому разумно использовать сочетание "ACID-транзакции" для обозначения «настоящих» транзакций, а неуточняемый термин "транзакция" применять неформально — по-разному в разных контекстах.

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

Требования мгновенной согласованности (immediate consistency), атомарной согласованности (atomic consistency) или согласованности «в конечном счете» (eventual consistency), появляющиеся в контексте «теоремы» Брювера, нельзя перемешивать с требованиями согласованности транзакций в смысле ACID. Ограничения целостности базы данных – это логические бизнес-требования, вытекающие из логики прикладной области. Требование атомарной согласованности и т. д. совсем другого рода — это реализационные требования, относящиеся к категории, которую традиционно в области баз данных называли физической согласованностью.

Когда стоит платить за ACID?

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

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

Взамен традиционной архитектуры системы баз данных с серверами баз данных и приложений предлагается новая архитектура (рис. 1), реализованная компанией 28msec в продукте Sausalito. В этой архитектуре основные функции СУБД — обработка запросов и управление транзакциями — переносятся на прикладной уровень, а на нижнем поддерживается только распределенное хранение данных с применением службы Amazon S3, хотя теоретически можно использовать и другие аналогичные средства. Согласованность данных поддерживается не на уровне хранения, а на прикладном уровне. Отсутствует какой-либо объект, контролирующий весь доступ к данным, и согласованность данных обеспечивается за счет применения во всех серверах приложений общих протоколов в духе Amazon S3 (протоколы направлены на поддержку согласованности реплик данных, так что здесь имеется в виду именно этот вид согласованности).

Рис. 1. Новая архитектура системы баз данных

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

Новые подходы к обеспечению свойств ACID в параллельных СУБД

Среди работ, в которых совсем не затрагиваются фундаментальные свойства ACID и при этом обеспечивается горизонтальное масштабирование параллельных систем баз данных, выделяется проект H-Store , в котором участвуют исследователи Массачусетского технологического института, Йельского университета и Университета Брауна при участии Майкла Стоунбрейкера и Стэнли Здоника. На базе предварительных результатов этого проекта была образована компания VoltDB, выпустившая в середине 2010 года свой первый коммерческий программный продукт с открытыми исходными текстами и лицензией GPL3. Основной упор в этом проекте делается на достижение максимально возможной эффективности и обеспечение линейной горизонтальной масштабируемости СУБД с массовым параллелизмом (Massive Parallel Processing, MPP), сохраняющей данные в основной памяти, при полной поддержке ACID-транзакций. Во многих своих публикациях Стоунбрейкер вполне убедительно доказывает, что отказ от свойств ACID никоим образом не способствует повышению уровня доступности распределенных систем управления данными. Высокой же производительности и горизонтальной масштабируемости MPP-систем баз данных в наибольшей степени мешают распределенные транзакции и в особенности их двухфазная фиксация.

Устранению отрицательного влияния распределенных транзакций и посвящается основная часть исследований проекта H-Store; например, в работе [12] предлагается метод «спекулятивного» выполнения транзакций, позволяющий избежать простаивания потоков управления, когда выполняемые в них фрагменты распределенных транзакций вынуждаются ожидать поступления сетевых сообщений. Достоинством метода спекуляций является возможность избежать простоев в работе потоков управления основных разделов без использования синхронизационных блокировок и отслеживания наборов чтения и записи транзакций. Недостатками и ограничениями являются: возможность перехода в спекулятивный режим выполнения только после обработки последнего фрагмента многораздельной транзакции (не исключены простои между выполнением последовательных фрагментов одной и той же транзакции); потребность в едином координаторе для всех многораздельных транзакций, чтобы можно было допустить их спекулятивное выполнение; потенциальная возможность лишних откатов, поскольку неявно предполагается, что все транзакции, работающие с одним и тем же разделом базы данных, конфликтуют.

В работе [ 13 ] описывается подход к решению проблем распределенных транзакций, основанный на использовании полностью детерминированной схемы их выполнения. Связанное с поддержкой свойств ACID требование сериализации транзакций, по мнению авторов [ 13 ], традиционно формулируется слишком слабо, поскольку требуется эквивалентность плана выполнения смеси транзакций какому-либо плану их последовательного выполнения, что оставляет простор для недетерминизма. При детерминированной сериализации смеси транзакций {T ₁ , T ₂ ,.. ., T _n } требуется эквивалентность плана выполнения этих транзакций некоторому предопределенному последовательному плану их выполнения (T _i1 , T _i2 ,... , T _in ). Для реализации своего подхода авторы предлагают использовать синхронизационные блокировки, но при соблюдении следующих ограничений, гарантирующих эквивалентность получаемого сериального плана предопределенному плану:

• если двум транзакциям T _i и T _j требуются блокировки одной и той же записи r и в предопределенном плане Ti находится раньше, чем T _j , то T _i должна запросить блокировку r раньше, чем T _j (то есть должна использоваться схема упорядоченного запроса блокировок – помимо прочего, легко видеть, что при использовании такой схемы невозможно возникновение синхронизационных тупиков);
• каждая транзакция, не ожидающая удовлетворения запроса блокировки, должна продолжать выполняться до тех пор, пока не зафиксируется или не будет аварийно завершена детерминированным образом (то есть в соответствии с логикой приложения).

Рис. 2. Детерминированная система

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

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

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

Рис. 3. Примерные база данных и рабочая нагрузка

Рис. 4. Общая идея графа, используемого для разделения базы данных

Параллельные СУБД для многоядерных компьютеров

Параллельным транзакционным СУБД свойственна еще одна проблема, к которой недостаточно внимательно относятся участники проекта H-Store, отказываясь от использования общих ресурсов даже внутри одного узла, в котором установлен компьютер с многоядерным процессором. Такой компьютер используется как набор виртуальных изолированных узлов, каждому из которых соответствует ядро процессора. В проекте DORA [ 15 ] обосновывается неэффективность такого подхода и предлагается оригинальная архитектура параллельной "одноузловой» СУБД, работающей на машине с многоядерным процессором. В этой архитектуре на физическом уровне все основные ресурсы процессора (основная и дисковая память) являются общими для всех потоков управления СУБД, а на логическом уровне данные разделяются между потоками управления. Демонстрируется, что такая организация СУБД позволяет резко снизить нагрузку на центральный менеджер блокировок и обеспечить хорошее масштабирование системы при возрастании числа ядер. Потоки управления (исполнители), в которых выполняются операции транзакций, связываются с данными за счет установки для каждой таблицы базы данных правила маршрутизации. Правило маршрутизации разделяет соответствующую таблицу на наборы записей (фактически разделы) так, что каждая запись относится только к одному набору. Каждый набор записей приписывается одному исполнителю, которому может быть приписано несколько наборов записей одной таблицы. Физический доступ к данным производится через общесистемный буферный пул, и правила маршрутизации не вызывают какого-либо физического разделения или перемещения данных. Правила маршрутизации поддерживаются во время работы системы менеджером ресурсов DORA и периодически им обновляются для балансировки нагрузки.

Что же ждать в будущем?

Будущее поколение ACID-транзакционных систем будет опираться на две основные параллельные архитектуры: одноузловую и многоузловую. Одноузловая предполагает наличие мощного многоядерного компьютера и использование энергонезависимой внешней памяти, в которой, в частности, должен поддерживаться журнал повторного выполнения транзакций. И в этом направлении хороший фундамент закладывает DORA. Но нужно учитывать, что для достижения высокой производительности в такой архитектуре потребуется мощная параллельная система ввода/вывода, стоимость которой, вполне вероятно, будет определять стоимость системы в целом. (В работе [15] эксперименты выполнялись с использованием файловой системы в основной памяти именно из-за отсутствия у авторов такой дорогостоящей дисковой подсистемы.)

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

***

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

Литература

1. Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplifed Data Processing on Large Clusters , Proceedings of the Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004, pp. 137-150.
2. Michael Stonebraker, David J. DeWitt. MapReduce: A major step backwards , Database Column, January 17, 2008.
3. Michael Stonebraker, David J. DeWitt. MapReduce II , Database Column, January 25, 2008.
4. С. Д. Кузнецов. MapReduce: внутри, снаружи или сбоку от параллельных СУБД?, Труды Института системного программирования, т. 19, М., ИСП РАН, 2010, с. 35-40.
5. Pat Helland, Dave Campbell. Building on Quicksand . Proceedings of the Fourth Biennial Conference on Innovative Data Systems Research (CIDR 2009), January 4-7, 2009, Asilomar, Pacific Grove, CA USA. Перевод на русский язык: Пэт Хелланд, Дейв Кэмпбел. Дом на песке, 2010.
6. Eric Brewer, Towards Robust Distributed Systems , Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 2000, p. 7.
7. Daniel Abadi, Alexander Thomson. The problems with ACID, and how to fix them without NoSQL . DBMS Musings, August 31, 2010. Перевод на русский язык: Дэниел Абади и Александер Томсон. Проблемы с ACID и как их устранить, не прибегая к использованию NoSQL, 2010.
8. Theo Haerder, Andreas Reuter. Principles of transaction-oriented database recovery . ACM Computing Surveys, Volume 15, Issue 4, December 1983, pp. 287-317.
9. Tim Kraska, Martin Hentschel, Gustavo Alonso, Donald Kossmann. Consistency Rationing in the Cloud: Pay only when it matters . Proceedings of the 35th VLDB Conference, August 24-28, 2009, Lyon, France, pp. 253-264. Перевод на русский язык: Тим Краска, Мартин Хеншель, Густаво Алонсо, Дональд Коссман. Рационализация согласованности в "облаках": не платите за то, что вам не требуется, 2010.
10. Michael Stonebraker. Errors in Database Systems, Eventual Consistency, and the CAP Theorem . BLOG@CACM, April 5, 2010. Перевод на русский язык: Майкл Стоунбрейкер. Ошибки в системах баз данных, согласованность "в конечном счете» и теорема CAP, 2010.
11. Michael Stonebraker. Clarifications on the CAP Theorem and Data-Related Errors. VoltDB.com, October 21, 2010. Перевод на русский язык: Майкл Стоунбрейкер. Уточнения по поводу теоремы CAP и ошибок, связанных с данными, 2010.
12. Evan P.C. Jones, Daniel J. Abadi, Samuel Madden. Low Overhead Concurrency Control for Partitioned Main Memory Databases . SIGMOD’10, Indianapolis, Indiana, USA, June 6–11, 2010. Перевод на русский язык: Эван Джонс, Дэниэль Абади и Сэмуэль Мэдден.Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти, 2010.
13. 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. Перевод на русский язык: Дэниел Абади и Александер Томсон. Доводы в пользу детерминизма в системах баз данных, 2010.
14. Carlo Curino, Evan Jones, Yang Zhang, Sam Madden. Schism: a Workload-Driven Approach to Database Replication and Partitioning . 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 48-57. Перевод на русский язык: Карло Курино, Эван Джонс, Янг Жанг и Сэм Мэдден. Schism: управляемый рабочей нагрузкой подход к репликации и разделению баз данных, 2010.
15. 15. Ippokratis Pandis, Ryan Johnson, Nikos Hardavellas, Anastasia Ailamaki. Data-Oriented Transaction Execution . 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 928-939. Перевод на русский язык: Иппократис Пандис, Райан Джонсон, Никос Харадавеллас и Анастасия Айламаки. Выполнение транзакций, ориентированное на данные, 2010.

Cтатья публикуется в сокращенном варианте, подготовленном для журнала «Открытые системы.СУБД». Оригинальная версия — на сайте CIT Forum.