Пусть расцветают сто цветов

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

1. Введение

Около года тому назад я написал и опубликовал статью «К свободе от проблемы Больших Данных», посвященную проблемам горизонтального масштабирования аналитических систем управления базами данных (СУБД). Тогда я решил сосредоточиться на аналитических системах, поскольку данные, с которыми им приходится работать, имеют предельно большие объемы, и возникающие проблемы можно наиболее очевидным образом считать проблемами «больших данных».

В той же статье я отмечал, что проблемы «больших данных» свойственны и второму массово распространенному классу систем и приложений – транзакционным системам. Конечно, в абсолютном исчислении объемы транзакционных данных в среднем на порядки меньше объемов аналитических данных (хотя бы из-за отсутствия потребности в хранении исторических данных), но и в транзакционных системах постоянно возрастают и объемы данных, и число обрабатываемых транзакций, и требуется обеспечить подходы, которые надежно обеспечивали бы масштабирование этих систем.

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

Попробуем разобраться в том,

• какая разновидность масштабирования хороша для мира транзакционных систем,
• какие проблемы при этом возникают,
• какие видны пути решения этих проблем и,
• каковы истинные причины появления систем NoACID.

2. Почему транзакционным системам требуется возможность горизонтального масштабирования?

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

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

Известно, что имеются два основных подхода к масштабированию программных систем – вертикальное (scale up) и горизонтальное (scale out) масштабирование. Вертикальное масштабирование предполагает повышение производительности оборудования (каждого его компонента) для достижения требуемой производительности программной системы. При горизонтальном масштабировании желательная производительность программной системы достигается за счет увеличения числа компонентов оборудования.

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

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

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

3. Проблемы горизонтально масштабируемых транзакционных систем

В области управления данными на аппаратном уровне горизонтальная масштабируемость программных систем и приложений поддерживается массивно-параллельными архитектурами без использования общих ресурсов узлами вычислительной системы. Если говорить сугубой прозой, то речь идет о традиционных кластерных системах, состоящих из процессорных узлов, каждый из которых имеет собственную основную и внешнюю память. Ни один узел не использует ресурсы, непосредственно не входящие в его собственную конфигурацию. В сообществе баз данных такие вычислительные системы и разработанные для них программные системы и приложения принято объединять термином shared nothing, чтобы отличать их от симметричных мультипроцессорных архитектур (в частности, многоядерных), которые называют shared everything, и кластерных архитектур с выделенной общей системой хранения (shared disks).

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

Что же касается транзакционных горизонтально масштабируемых систем, то основным выводом из текста предыдущего абзаца следует то, что в таких системах теоретически невозможно избежать появления распределенных транзакций, т.е. транзакций, которые при своем выполнении читают и/или обновляют данные, хранящиеся в нескольких разделах базы данных в нескольких узлах вычислительной системы. Как будет видно дальше, именно распределенные транзакции составляют главную проблему горизонтально масштабируемых транзакционных СУБД и основную причину появления систем NoACID.

Но сначала разберемся в том, почему именно аббревиатура ACID (от Atomicy, Consistency, Isolation, Durability) стала для одних людей почти священным заклинанием (каюсь, я вхожу в их число), а для других словом, близким к ругательному. Понятие транзакции баз данных со свойствами ACID первым предложил Джим Грей (Jim Gray) в своей статье «The Transaction Concept: Virtues and Limitations». По его мнению, которое вполне соответствует житейскому смыслу слова «транзакция», транзакция базы данных должна поддерживать свойства

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

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

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

Атомарность. Если поддерживается изолированность транзакций, то для обеспечения атомарности нужно уметь откатывать (Rollup) транзакции, которые по каким-то причинам (например, по причине нарушения требования согласованности) не удается зафиксировать. В среде shared nothing откат распределенной транзакции означает выполнение требуемых действий во всех узлах, где от имени этой транзакции изменялись данные. В принципе, ничего страшного в этом нет, проблема решается, если мы умеем эффективно фиксировать распределенные транзакции.

Согласованность. Концептуально проверка выполнения требования согласованности для данной транзакции выполняется при выполнении ее фиксации. Если ограничения целостности выполняются, транзакция фиксируется, если не выполняются – откатывается. В среде shared nothing проверка выполнения требования согласованности для распределенной транзакции означает выполнение требуемых действий во всех узлах, где от имени этой транзакции изменялись данные. Опять же, в принципе проблема решается, если имеется эффективная поддержка фиксации распределенных транзакций.

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

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

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

Пусть в распределенной транзакции участвуют n узлов системы T₁, T₂, …, T_n (соответствующие части распределенной транзакции принято называть транзакциями-участниками). В некотором узле T_k (возможно, одном из узлов-участников) выполняется программный компонент, который принято называть координатором распределенной транзакции. Координатор получает от приложения, от имени которого выполняется данная распределенная транзакция, сообщение с требованием ее фиксации. На первой фазе работы протокола координатор рассылает всем участникам сообщение «подготовиться к фиксации». Если все участники подтверждают свою готовность к фиксации, то на второй фазе координатор рассылает участникам сообщение с требованием их фиксации. Иначе на второй фазе участникам рассылается сообщение с требованием отката.

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

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

4. Попытки решения проблемы распределенных транзакций с сохранением свойств ACID

С моей точки зрения, наиболее интересные подходы к построению горизонтально масштабируемых транзакционных систем были разработаны в проекте H-Store, выполняющемся исследователями из Массачусетского технологического института, Брауновского и Йельского университетов и HP Labs. Идейным вдохновителем проекта является Майкл Стоунбрейкер (Michael Stonebraker), основавший несколько лет назад компанию VoltDB (http://www.voltdb.com/) с целью коммерциализации H-Store.

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

Общая архитектура H-Store показана на рисунке, который я позаимствовал из упомянутой статьи.

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

Кстати, заметим, что при использовании многоядерных процессоров разработчики H-Store трактуют каждое ядро как отдельный узел с собственной основной памятью. Это не очень хорошо, потому что не используется факт реального наличия общей памяти у многоядерного компьютера. И здесь стоило бы обратить внимание на проект DORA, которым руководила Анастасия Айламаки (Anastasia Ailamaki). В этом проекте ядра многоядерного процессора образуют как бы систему shared nothing, но разделение данных в основной памяти производится за счет использования механизма виртуальной памяти. Такой подход кажется мне очень перспективным.

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

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

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

5. Что такое теорема CAP и обосновывает ли она отказ от поддержки ACID-транзакций в новых распределенных системах управления данными?

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

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

Как ни странно, несмотря на тривиальность «теоремы» CAP, ею серьезно заинтересовались теоретики распределенных систем. В частности, в статье Сета Джильберта (Seth Gilbert) и Нэнси Линч (Nancy Lynch) «Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services» эта «теорема» по-настоящему формализуется и доказывается, не переставая быть, на мой взгляд, очевидной.

Самое странное в «теореме» CAP то, что ее «выводами» руководствовались вдохновители части направления, которое в целом принято называть NoSQL, отказываясь от поддержки в своих распределенных системах управления данными ACID-транзакций (кстати, поскольку представители этой части NoSQL отрицают не столько язык SQL, сколько ACID-транзакции, было бы правильно называть его NoACID). Мне кажется, что путаницу внесло использование термина consistency в аббревиатурах ACID и CAP в разных смыслах.

Как отмечалось в разд. 3, в контексте ACID имеется в виду логическая согласованность базы данных, т.е. соответствие ее содержимого некоторому инвариантному логическому значению. В контексте же CAP имеется в виду физическая идентичность реплик. Нужно было бы отдельно исследовать возможность поддержки логической целостности в двух одновременно доступных разделах сети, в которой работает транзакционная СУБД, но уж точно логическую согласованность можно поддерживать, если разрешить продолжать работу только в одном разделе.

Я считаю, что в направлении NoACID работают достаточно квалифицированные специалисты, которые не могли не заметить наличие этой путаницы, и утверждаю, что истинной причиной отказа от поддержки ACID-транзакций в системах NoACID является нежелание иметь дела с фиксацией распределенных транзакций. Проблемы, описанные в разд. 3, обеспечивают существенно более серьезный повод для отказа от ACID, чем «теорема» CAP. Сообщество NoACID борется не за соответствие формулировке «теоремы» CAP, а за горизонтальную масштабируемость своих систем.

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

6. Заключение, или «О правильном разрешении противоречий внутри народа»

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