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

Транзакционные параллельные СУБД: новая волна

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

Источник: http://citforum.ru/database/articles/kuz_oltp_2010/

Аннотация

Возможность построения неограниченно масштабируемых кластерных систем привела к резкой активизации исследований и разработок архитектур систем управления данными без совместного использования ресурсов. Образовались два основных фронта: "NoSQL", где отрицаются основные принципы, свойственные СУБД, и "один размер непригоден для всех", где упор делается на специализацию систем при сохранении важнейших свойств СУБД. Особенно интересным является противостояние этих фронтов в области "транзакционных" систем управления данными. Опираясь на "теорему" CAP Эрика Брювера (Eric Bruwer), представители лагеря NoSQL отказываются от обеспечения в своих системах традиционных свойств ACID в транзакциях баз данных. В этой статье обсуждается суть "теоремы" Брювера и обосновывается, что она не имеет отношения к свойствам ACID. Рассматриваются наиболее интересные современные исследовательские работы, обеспечивающие классические ACID-транзакции в параллельных средах без общих ресурсов, а также наиболее здравые подходы, в которых из чисто прагматических соображений свойства ACID частично ослабляются (но совсем не в связи с "теоремой" CAP).

1. Введение

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

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

На втором фронте, с моей точки зрения, находятся последователи концепции Майкла Стоунбрейкера (Michael Stonebraker) "один размер непригоден для всех" [1], в которой, по сути, основными являются два соображения: (a) прошло время универсальных систем управления базами данных, пригодных для поддержки приложений всех возможных разновидностей, и (b) при разработке новых систем необходимо пользоваться всеми полезными технологиями и идеями, накопленными в сообществе баз данных. К этому лагерю относятся исследовательские группы ряда университетов США, компании VoltDB, Vertica, Asterdata и т.д.

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

На обоих фронтах ведутся работы в двух наиболее важных направлениях управления данными – аналитические системы управления данными (т.е. системы, пригодные для построения над ними приложений категории OLAP (online analytical processing, оперативная аналитическая обработка данных) и транзакционные системы управления данными (т.е. системы, пригодные для построения приложений категории OLTP (online transaction processing, оперативная обработка транзакций). В первом направлении представителей двух рассматриваемых лагерей в прошлые годы разделяло, прежде всего, отношение к NoSQL-технологии анализа данных MapReduce [2]. Не так давно представители лагеря NoSQL считали, что MapReduce заменит в динамических кластерных архитектурах параллельные аналитические системы баз данных, а исследователи из второго лагеря обвиняли создателей MapReduce к возврату в дремучее прошлое, когда технология баз данных не существовала [3-4]. Однако это время, как кажется, миновало. По крайней мере, сообщество баз данных приняло технологию MapReduce и научилось ее использовать [5], и я (может быть, временно) считаю эту тему закрытой (в [5] можно найти много полезных ссылок на эту тему).

1.1 Цель статьи

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

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

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

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

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

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

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

Среди работ, в которых ни в коей мере не затрагиваются фундаментальные свойства ACID и при этом обеспечивается горизонтальное масштабирование параллельных систем баз данных, мне больше всего нравится проект H-Store [10], в котором участвуют исследователи Массачусетского технологического института, Йельского университета и университета Браун при участии таких "грандов" области баз данных, как Майкл Стоунбрейкер и Стенли Здоник (Stanley Zdonik). На основе предварительных результатов этого проекта была основана компания VoltDB [11], выпустившая в середине 2010 г. свой первый коммерческий программный продукт (кстати, с открытыми исходными текстами и лицензией GPL3).

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

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

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

1.2 Структура статьи

Оставшаяся часть статьи организована следующим образом. В разд. 2 напоминается исходный смысл свойств ACID транзакций баз данных. Затем анализируется, как связано свойство "consustency" в смысле "теоремы" CAP с соответствующим свойством ACID. Разд. 3 посвящен рассмотрению наиболее интересных архитектур и методов построения параллельных СУБД, в обязательном порядке поддерживающих ACID-транзакции. В разд. 4 обсуждаются подходы к обоснованному ослаблению свойства согласованности. Наконец, разд. 5 содержит заключение.

2. Классические свойства транзакций и "теорема" CAP

Во введении отмечалось, что многочисленные обсуждения следствий "теоремы" CAP на возможность поддержки ACID-транзакций в распределенных СУБД без совместно используемых ресурсов часто демонстрируют непонимание авторами сути свойств ACID и/или смысла "теоремы" CAP. В этом разделе, прежде всего, напоминается исходный смысл свойств ACID, который имелся в виду изобретателями этой аббревиватуры. Затем я постараюсь прояснить смысл "теоремы" Брювера и подвести читателей к мысли, что consistensy в этой теореме имеет мало общего с consistensy, входящей в число свойств ACID.

2.1 ACID: вернемся к истокам

Впервые аббревиатура ACID появилась в 1983 г. в статье Тео Хаердера (Theo Haerder) и Адреаса Рейтера (Andreas Reuter) [16]. Для упрощения текста и пущей убедительности я приведу перевод фрагмента этой статьи (с небольшими сокращениями). В этом фрагменте используется пример банковской транзакции из [17], в которой деньги переводятся с одного счета на другой (рис. 1).

Концепция транзакции, включающей в приведенном примере все взаимодействия с базой данных между $BEGIN_TRANSACTION и $COMMIT_TRANSACTION, требует, чтобы все действия выполнялись нераздельно (indivisibly): либо все действия должным образом отражаются в состоянии базы данных, либо ничего не происходит. Если в какой-либо момент времени до достижения $COMMIT_TRANSACTION пользователь вводит оператор ERROR, содержащий $RESTORE_TRANSACTION, то в базе данных не отражаются никакие изменения. Для достижения такой неделимости транзакция должна обладать следующими четырьмя свойствами:
Атомарность (Atomicity). Транзакция должна иметь описанный выше тип "все или ничего", и, что бы ни произошло, пользователь должен знать, в каком состоянии находится его транзакция.
Согласованность (Consistency). Транзакция, достигающая своего нормального завершения (EOT – end of transaction, завершение транзакции) и, тем самым, фиксирующая свои результаты, сохраняет согласованность базы данных. Другими словами, каждая успешная транзакция по определению фиксирует только допустимые результаты. Это условие является необходимым для поддержки четвертого свойства – долговечности.
Изоляция (Isolation). События, происходящие внутри транзакции, должны быть скрыты от других одновременно выполняемых транзакций. Если бы это условие не выполнялось, то по причинам, упомянутым выше, транзакцию было бы невозможно вернуть к своему началу. Для достижения изоляции используются методы, называемые синхронизацией...
Долговечность (Durability). После того, как транзакция завершилась и зафиксировала свои результаты в базе данных, система должна гарантировать, что эти результаты переживут любые последующие сбои. Поскольку отсутствует какая-либо область управления, охватывающая наборы транзакций, у системы управления базами данных (СУБД) нет никакого контроля вне пределов границ транзакций. Поэтому пользователю должно гарантироваться, что если система сообщает ему о том, что нечто произошло, то это "нечто" действительно произошло. Поскольку по определению любая (успешно завершенная – С.К.) транзакция является корректной, результаты неизбежно появляющихся некорректных транзакций (т.е. транзакций, содержащих ошибочные данные), могут быть устранены только соответствующей "контр"-транзакцией (countertransaction).
Эти четыре свойства – атомарность, согласованность, изоляция и долговечность (ACID) – описывают основные черты парадигмы транзакций, которые влияют на многие аспекты разработки систем баз данных. Поэтому мы считаем, что способность какой-либо системы к поддержке транзакций является пробным камнем (ACID test) качества этой системы.

FUNDS_TRANSFER. PROCEDURE,
 $BEGIN_TRANSACTION;
 ON ERROR DO;                                   /* in case of error */
          $RESTORE_TRANSACTION,                 /* undo all work */
          GET INPUT MESSAGE;                    /* reacquire input */
          PUT MESSAGE ('TRANSFER FAILED');      /* report failure */
          GO TO COMMIT;
          END;
 GET INPUT MESSAGE;                             /* get and parse input */
 EXTRACT ACCOUNT_EBIT, ACCOUNT_CREDIT,
  AMOUNT FROM MESSAGE,
 $UPDATE ACCOUNTS                               /* do debit */
              SET BALANCE ffi BALANCE - AMOUNT
     WHERE ACCOUNTS.NUMBER = ACCOUNT_DEBIT;
 $UPDATE ACCOUNTS                               /* do credit */
              SET BALANCE = BALANCE + AMOUNT
     WHERE ACCOUNTS.NUMBER = ACCOUNT_CREDIT;
 $INSERT INTO HISTORY                           /* keep audit trail */
    <DATE, MESSAGE>;
 PUT MESSAGE ('TRANSFER DONE');                 /* report success */
COMMIT:                                         /* commit updates */
 $COMMIT_TRANSACTION;
 END;                                           /* end of program */

Рис. 1. Простая программа на языке PL/1-SQL, переводящая средства с одного счета на другой.

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

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

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

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

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

Займемся теперь "теоремой" CAP и постараемся разобраться, что же означает согласованность в смысле Брювера.

2.2 Согласованность по Брюверу

Начнем с того, что Эрик Брювер не является и никогда не объявлял себя специалистом в области баз данных. Он относится к сообществу распределенных систем, и его знаменитый доклад [7], в котором появилась "теорема" CAP, был сделан на конференции "Принципы распределенных вычислений". (Кстати, десять лет спустя, в 2010 г. он еще раз выступил с приглашенным докладом [18] на той же конференции, и в этом докладе привел, в частности, ряд примеров распределенных систем, при разработке которых учитывалась "теорема" CAP.) В этой области имеется свое толкование терминов, используемых в области баз данных.

В частности, термин мгновенная согласованность (immediate consistency) означает, что после того как пользователь получает от системы извещение об успешном выполнении некоторой операции обновления данных, результат этой операции становится мгновенно видимым для всех наблюдателей. Согласованность в конечном счете (eventual consistency) означает, что если в течение достаточно долгого периода времени в систему не поступают новые операции обновления данных, то можно ожидать, что результаты всех предыдущих операций обновления данных в конце концов распространятся по всем узлам системы, и все реплики данных согласуются (по всей видимости, это нужно понимать как "у всех реплик будет одно и то же состояние" – С.К.). Скорее всего, в [7] под согласованностью понимается именно мгновенная согласованность данных.

Имея в виду этот смысл понятия согласованность, можно считать "теорему" Брювера вполне понятной и очевидной: в любой распределенной системе с разделенными данными можно одновременно обеспечить только любые два свойства из согласованности, доступности и устойчивости к разделению сети. В связи с этим Брювер даже противопоставляет набор свойств ACID предлагаемому им набору свойств BASE (Basically Available, Soft-state, Eventual consistency – доступность в большинстве случаев; неустойчивое состояние; согласованность в конечном счете). Но это противопоставление, по моему мнению, неправомерно, поскольку в первом случае речь идет о логических характеристиках транзакций, а во втором – о физических свойствах распределенных систем.

Многие считают, что "теорема" Брювера формально доказана. Действительно, в статье Сета Гильберта (Seth Gilbert) и Нэнси Линч (Nancy Lynch) [19] вводятся некоторые (почти) формальные определения, в контексте которых "теорема" действительно становится теоремой и доказывается. Однако давайте разберемся, как же определяются те три свойства распределенной системы, из числа которых по "теореме" Брювера можно одновременно обеспечить поддержку только двух свойств.

Согласованностью в [19] называется атомарная, или линеаризуемая согласованность (atomic, or linearizable consistency), являющаяся свойством системы, все индивидуальные объекты данных которой являются атомарными (линеаризуемыми). В свою очередь, атомарным объектом называется объект с несколькими операциями, такими что вызов операции и получение ответных данных происходят как бы мгновенно, т.е. объект не принимает вызов следующей операции до полного завершения предыдущей операции. При этом порядок приема операций должен быть таким, что если операция типа чтения поступает после выполнения некоторой операции типа записи, то операция чтения должна вернуть значение, записанное этой или какой-либо более поздей операцией записи.

Распределенная система является постоянно доступной, если на каждый запрос, полученный не отказавшим узлом, должен быть получен ответ. Устойчивость системы к разделению сети в [19] моделируется как сохранение жизнеспособности системы при потере произвольного числа сообщений, посылаемых из одного узла в другой.

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

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

Эта теорема действительно достаточно просто формально доказывается методом "от противного". Далее в [19] выводится следствие, заключающееся в том, что:

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

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

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

Вот что пишет по этому поводу в своей заметке [20], посвященной обсуждению "теоремы" CAP и статьи [19], Джулиан Браун (Julian Browne):

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

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

А вот что уже совсем серьезно пишут в своей заметке [8] представители сообщества баз данных Дэниэль Абади (Daniel Abadi) и Александер Томсон (Alexander Thomson):

... все более критичным становится требование к доступности масштабируемых транзакционных систем, и обычно оно удовлетворяется за счет репликации и автоматического перенаправления запросов в случае сбоя одного из узлов. Поэтому разработчики приложений ожидают, что гарантии согласованности (consistency) ACID-систем (первоначально заключавшиеся в локальной поддержке определенных пользователями инвариантов) будут распространены на обеспечение строгой согласованности (того, что все реплики одних и тех же данных в любой момент времени будут являться идентичными копиями, т.е. в этом случае согласованность подразумевается в смысле CAP/PACELC (про PACELC см. в [21] – C.K.).

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

Как считает Майкл Стоунбрейкер [12-13], залогом построения качественной современной СУБД является правильный выбор технических компромиссов. При выборе конкретного инженерного решения нужно учитывать множество факторов – требования будущих пользователей, вероятности возникновения различных сбойных ситуаций и т.д., а не руководствоваться догматическим образом каким-либо общими теоретическими указаниями (в том числе, и "теоремой" CAP).

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

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

Посмотрим, как отвечает на этот вызов сообщество баз данных.

3. Новые транзакционные архитектуры, поддерживающие классические свойства транзакций

Понятно, что конкурировать на рынке OLTP с системами основных поставщиков SQL-ориентированных СУБД (IBM, Oracle и Microsoft), которые в течение многих лет оптимизировались именно для обработки ACID-транзакций, может только СУБД, обладающая некоторыми принципиально отличными качествами. В настоящее время такими потенциально достижимыми новыми качествами являются существенно (в десятки раз) большая пропускная способность транзакций и горизонтальная масштабируемость (т.е. возможность линейного повышения пропускной способности при наращивании аппаратных ресурсов). Все более распространенным (и подтверждаемым практикой) мнением является то, что такие качества можно обеспечить только при использовании архитектур без совместного использования ресурсов (shared-nothing). Одним из наиболее ярких свидетельств правильности этого мнения являются проект H-Store [10] и достижения компании VoltDB [11], которым посвящается подраздел 3.1.

С другой стороны, нельзя не учитывать, что продолжает действовать закон Мура, в соответствии с новой трактовкой которого экспоненциально возрастает число ядер в микропроцессорах. В действительности в узлах массивно-параллельной СУБД (даже основанной на использовании компьютеров категории массового спроса) применяются мощные компьютеры, позволяющие эффективно использовать локальные СУБД с совместным использованием ресурсов. Другими словами, для построения предельно эффективной транзакционной массивно-параллельной СУБД нельзя не позаботиться об эффективности локальных СУБД, работающих на многоядерных процессорах. В этом направлении исследований мне хочется выделить проект DORA [15], в котором оригинальным образом сочетаются подходы shared-everything на физическом уровне архитектуры СУБД и shared-nothing на логическом уровне. Этот проект обсуждается в подразделе 3.2.

3.1 H-Store: ничего лишнего Впервые краткое описание исходных идей проекта H-Store появилось в 2007 г. в [22]. Эта статья была последней в цикле "один размер непригоден для всех" (см. также [1, 23]), в котором доказывалось, что прошло время универсальных, пригодных для поддержки любых приложений баз данных SQL-ориентированных СУБД, и обосновывались преимущества специализированных архитектур. В [22] речь идет исключительно о специализированных транзакционных системах, основанных на следующих пяти основных соображениях.

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

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

Кажется правдоподобным, что в следующем десятилетии будут доминировать компьютерные системы без общих ресурсов, и все СУБД следует оптимизировать в расчете на использование такой архитектуры. Если система с N узлами не обеспечивает достаточной мощности, должна иметься возможность добавления к ней дополнительных K узлов без потребности в каких-либо сложных действиях над используемой СУБД (то самое горизонтальное масштабирование – С.К.).

В будущем высокий уровень доступности и встроенные средства восстановления после отказов станут важными чертами рынка OLTP. Из этого следует несколько выводов.
1. В любой СУБД, ориентированной на поддержку OLTP, потребуется согласованная репликация данных.
2. Наиболее эффективной является поддержка архитектуры shared-nothing на всех уровнях системы (как я уже говорил, это неочевидно, см. следующий подраздел – С.К.)
3. Наилучший способ поддержки архитектуры без общих ресурсов состоит в использовании нескольких машин в одноранговой (peer-to-peer) конфигурации. Тогда нагрузка OLTP может быть распределена между несколькими машинами, а межмашинную репликацию можно использовать для обеспечения отказоустойчивости.
4. В мире высокой доступности не требуется поддержка журнала повторного выполнения операций, а нужен только временный, сохраняемый в основной памяти журнал откатов.
5. Основные расходы IT-подразделений уходят на содержание персонала. Единственным выходом из этого положения является перевод систем на «самообслуживание» (самовосстановление, автоматическое техническое обслуживание, автоматическую настройку и т.д.). Требуется полный пересмотр процесса настройки системы без явных ручек управления.
Эти соображения приводят к следующим выводам.
1. Основным препятствием для достижения высокой производительности системы почти наверняка станет журнал повторного выполнения операций, сохраняемый в дисковой памяти. Без него можно обойтись за счет подсистемы поддержки высокого уровня доступности и обработки отказов.
2. Следующим по значимости узким местом системы является вызов в ней операций и возврат результатов в приложение. Наиболее эффективным способом решения этой проблемы является выполнение логики приложений в виде хранимых процедур внутри системы баз данных.
3. Во всех возможных случаях следует отказаться от поддержки и журнала откатов транзакций, поскольку он тоже будет сдерживать производительность.
4. Следует приложить все усилия, чтобы максимально освободиться от затрат на синхронизационные блокировки.
5. Желательно освободиться и от синхронизации на основе "защелок" при доступе к одним и тем же структурам данных из нескольких потоков управления. С учетом кратковременности транзакций эти накладные расходы можно устранить путем перехода к однопотоковой модели выполнения транзакций.
6. По мере возможности следует избегать применения двухфазного протокола фиксации распределенных транзакций.
3.1.1 Свойства схем транзакционных баз данных и типичных транзакций
В H-Store требуется наличие заранее специфицированного набора классов транзакций, которые могут входить в рабочую нагрузку системы. Каждый класс характеризует транзакции с одними и теми же операторами SQL и логикой приложения, различающиеся только значениями констант времени выполнения. Это требование не является неестественным, поскольку для транзакционных приложений нехарактерно наличие непредвиденных запросов, явно вводимых пользователями во время выполнения транзакции. Таким образом, задержки выполнения транзакций по вине пользователей невозможны.
Аналогичным образом, считается, что заранее известна логическая схема базы данных, над которой будут выполняться эти транзакции. Авторы [22] обнаружили, что многие транзакционные базы данных обладают древовидной логической схемой, в которой каждая таблица (кроме одной – корневой) имеет связь n:1 ровно с одной таблицей-предком (т.е. она естественным образом соединяется только с одной таблицей). Для баз данных с древовидной схемой имеется очевидный метод горизонтального разделения данных: корневая таблица разделяется по диапазонам значений первичного ключа (или на основе хэширования этих значений); каждая таблица-потомок разделяется таким образом, чтобы при естественном соединении с каждым разделом таблицы-предка потребовались бы строки только одного раздела таблицы-потомка, причем этот раздел размещается в том же узле, что и соответствующий раздел таблицы-предка.
Если в каждом операторе SQL каждой транзакции содержится условие, выделяющее ровно одну строку корневой таблицы (например, любая операция относится к некоторому клиенту онлайнового магазина, и таблица клиентов является корневой), то при таком разделении каждый оператор будет выполняться ровно в одном узле (будет являться локальным для этого узла). Если все операторы каждой транзакции локальны для одного и того же узла, то соответствующее приложение называется приложением над ограниченным деревом (constrained tree application, CTA). Ценное свойство CTA-приложений состоит в том, что все его транзакции могут быть полностью выполнены в одном узле, т.е. являются одноузловыми. Такие транзакции выполняются без каких-либо задержек из-за коммуникации с другими узлами (кроме возможных задержек из-за синхронизации обновления реплик).
По опыту авторов, многие приложения OLTP сразу разрабатываются в стиле CTA, а во многих других случаях их можно преобразовать в CTA-приложения. (Заметим, что здесь и далее очень заметно влияние на ранней стадии проекта H-Store Пэта Хелланда (Pat Helland), который входит в число авторов [22], а ранее, будучи сотрудником Amazon, написал статью [24], где высказывал схожие соображения. Интересно также отметить, что в дальнейших работах, посвященных H-Store, влияние идей Хелланда почти незаметно.)
Для преобразования к виду CTA приложений, изначально таковыми не являющихся, в [22] предлагалось использовать два подхода. Во-первых, можно выделить все таблицы, которые во всех транзакциях только читаются. Такие таблицы можно реплицировать во всех узлах. Если некоторое приложение обладает свойством CTA по отношению ко всем остальным таблицам, то после такой репликации оно станет CTA-приложением. Во-вторых, имеется еще один важный класс OLTP-приложений, части транзакций которых можно выполнять параллельно без потребности в передаче между узлами промежуточных результатов, причем результаты операций SQL никогда не требуются при выполнении последующих операций. Транзакции таких приложений с одноразовым использованием результатов (one-shot) можно преобразовать в набор одноузловых планов, каждый из которых выполняется только в одном узле. Часто такие преобразования можно произвести за счет вертикального разделения таблиц между узлами (только читаемые вертикальные разделы реплицируются).
Некоторые классы транзакций обладают свойством двухфазности (two-phase) или могут быть преобразованы к двухфазным транзакциям. На первой фазе такой транзакции выполняются только операции чтения, и только на этой фазе допускается аварийное завершение транзакции по ее собственной инициативе (т.е. в это время производятся все возможные проверки, вследствие которых может потребоваться аварийное завершение транзакции). Важным свойством двухфазных транзакций является то, что при их выполнении можно обойтись без журналов откатов транзакций. Класс двухфазных транзакций называется строго двухфазным (strongly two-phase), если на первой фазе выполнения транзакции во всех узлах, участвующих в ее выполнении, принимается одно и то же решение относительно ее продолжения или аварийного завершения.
Две параллельно выполяемые транзакции (из одного или разных классов) называются коммутативными, если при любом чередовании их одноузловых планов производится одно и то же окончательное состояние базы данных (если обе транзакции фиксируются). Класс транзакций, коммутативных со всеми транзакциями, называется стерильным (sterile).
3.1.2 Как был устроен и как работал начальный вариант H-Store
H-Store выполняется в кластере компьютеров (почему-то в [22] эта аппаратная среда упорно называется grid'ом – С.К.). При конфигурировании системы можно указать желаемый уровень ее надежности – число узлов, при выходе из строя которых система может восстановить работоспособность без потери выполняемых транзакций в течение заданного времени. (Поскольку восстановление системы основано на использовании реплик, то, очевидно, уровень надежности коррелирует с числом поддерживаемых реплик данных – С.К.).
В каждом узле строки разделов таблиц размещаются вплотную одна к другой, и доступ к ним производится на основе B-деревьев (т.е. строки размещаются в порядке сортировки по значениям ключа B-дерева). Размер блока B-дерева соответствует размеру блока кэша второго уровня используемого процессора. (Сравнительно ясно, что является ключом B-дерева для баз данных с древовидной схемой – первичный ключ для корневой таблицы и внешний ключ для любой таблицы-потомка. Что выбирается в качестве ключа B-дерева раздела таблицы при наличии других схем, неясно – С.К.).
В каждом узле H-Store поддерживает ровно один поток управления, в котором полностью, без каких-либо задержек выполняется каждая поступающая операция SQL. Узлы, в процессорах которых имеется несколько ядер, разбиваются на соответствующее число логических узлов. В H-Store каждый логический узел трактуется так же, как и любой физически независимый узел, и основная память многоядерного компьютера разделяется между логическими узлами.
Транзакции представляются в виде хранимых процедур базы данных, и в системе поддерживается только одна внешняя операция Execute transaction (parameter_list), позволяющая в любом узле инициировать выполнение любой предопределенной транзакции с передачей ей значений параметров. Внутри таких хранимых процедур (для написания которых в исходном прототипе использовался язык C++) сочетается логика приложений и операции манипулирования базами данных, причем вызовы SQL производятся как локальные вызовы. Журнал повторного выполнения операций не поддерживается, а журнал отката (сохраняемый в основной памяти и освобождаемый при завершении транзакции) ведется только для транзакций, не являющихся двухфазными.
В исходном прототипе H-Store отсутствовал компилятор SQL, и планы всех операций SQL генерировались и оптимизировались вручную. Однако в [22] отмечалось, что планируется разработка компилятора SQL с оценочной (cost-based) оптимизацией, и что этот компилятор-оптимизатор должен быть сравнительно простым, поскольку в типичном OLTP-запросе всегда идентифицируется некоторый опорный кортеж (anchor tuple), с которым соединяются несколько (немного) таблиц. И некоторый компилятор SQL действительно появился в коммерческом варианте H-Store – VoltDB (см., например, [25]), хотя по доступной документации системы трудно судить, какие возможности оптимизации в нем реализованы.
Для обеспечения возможности использования H-Store без потребности в "ручках управления" планировалось создание средства автоматического проектирования физических схем баз данных (дизайнера баз данных), определяющего горизонтальное разделение, репликацию и выбор ключей индексов. Цель дизайнера состоит в том, чтобы сделать как можно больше транзакций одноузловыми (т.е. избежать появления распределенных транзакций). (И, кроме того, насколько я понимаю, добиться выявления двухфазных и стерильных транзакций – С.К.).
Мне с самого начала возможность создания такого средства казалась сомнительной. Уж очень трудна задача статического анализа многочисленных хранимых процедур с многочисленными вызовами операций SQL. К настоящему времени (конец 2010 г.) эта задача, по всей видимости, не решена. В документации VoltDB [25] разработчикам приложений предлагается лишь методика физического проектирования баз данных, да и то подчеркивается необходимость многократного выполнения тестовых испытаний (benchmarking, benchmarking, benchmarking!) на реальных данных до вывода приложения в производственный режим. С другой стороны, некоторую надежду на продвижение в этом направлении дает работа [14], хотя она основывается уже не на статическом анализе, а на анализе трасс выполнения рабочей нагрузки (см. ниже).
Выполнение транзакций в исходном прототипе H-Store происходило по следующей схеме. На входе в систему каждой транзакции назначалась временная метка (timestamp) в формате (site_id, local_unique_timestamp). Если поддерживается порядок на множестве узлов кластера, то все метки являются уникальными и полностью упорядоченными. Предполагалось, что локальные часы в каждом узле некоторым образом синхронизуются.
Если все классы транзакций являются одноузловыми, то каждая транзакция может быть направлена в узел с требуемыми копиями данных и полностью в нем выполнена. Если не все классы транзакций являются стерильными, то узел, в котором завершилось выполнение некоторой транзакции, в течение небольшого времени (времени сетевых задержек – для локальной сети в пределах нескольких миллисекунд) ожидает поступления транзакций от других узлов-инициаторов, чтобы выполнение транзакций происходило в порядке временных меток. За счет этого все реплики будут обновляться в одном и том же порядке, и их состояние после конца любой транзакции будет идентично. Следовательно, для выполнения одноузловых транзакций не требуется журнал повторного выполнения операций, какое-либо управление параллелизмом и распределенная фиксация транзакций. Если же, в придачу ко всему остальному, транзакция является двухфазной, то для нее не требуется и журнал отката.
Если все транзакции являются стерильными, то обычно для их выполнения не требуется какое-либо управление параллелизмом. Более того, в этом случае не требуется назначение транзакциям временных меток и их выполнение в одном и том же порядке надо всеми репликами. Но если транзакция распространяется на несколько узлов, то отсутствует гарантия, что она будет во всех узлах успешно выполнена или аварийно завершена. Поэтому каждый исполнитель должен послать диспетчеру выполнения транзакции (в том узле, в котором она была инициирована) сообщение "аварийное завершение" или "нормальное завершение" в той точке своей части транзакции, после которой соответствующее решение изменить уже нельзя (для двухфазных транзакций – в конце первой фазы). Диспетчер, в свою очередь, должен рассылать эти сообщения в другие узлы-исполнители. Другими словами, в этом случае приходится выполнять обычную процедуру фиксации распределенной транзакции. Если транзакция является строго двухфазной, этих накладных расходов можно избежать.
В общем случае (когда тразакция не является одноузловой или стерильной), приходится применять средства управления параллелизмом. При реализации исходного прототипа H-Store было принято решение отказаться от традиционной для SQL-ориентированных СУБД пессимистической схемы синхронизационных блокировок в пользу более оптимистических методов (как показывают более поздние статьи, посвященные H-Store в целом [26] и управлению транзакциями в H-Store [27-28], это решение не является стратегическим – поиск методов продолжается; кстати, совершенно неясно, какая схема управления параллелизмом применяется в VoltDB – С.К.).
В схеме управления параллелизмом, описываемой в [22], применяются три стратегии – основная, промежуточная и усложненная. Для каждого класса транзакций определяются классы транзакций, с которыми транзакции данного класса могут конфликтовать (по-видимому, выявляются стандартные конфликты "запись-запись", "чтение-запись" и "запись-чтение" на уровне таблиц – С.К.). Каждая транзакция инициируется в некотором узле системы, и ее выполнение отслеживается координатором транзакций в этом узле. Координатор выполняет роль диспетчера транзакций в узле инициации и рассылает фрагменты транзакции в соответствующие узлы.
При применении основной стратегии сайт-исполнитель получает фрагмент и выжидает в течение времени сетевых задержек на предмет возможного поступления транзакции с большим значением временной метки. Если после этого в узле обнаруживаются транзакции с более поздними временными метками из классов, потенциально конфликтующих с данной транзакцией, то исполнитель не выполняет ее фрагмент и посылает координатору сообщение "аварийное завершение". В противном случае фрагмент выполняется, и результирующие данные возвращаются в узел, из которого этот фрагмент был получен. Если координатор получает сообщение о нормальном выполнении фрагментов от всех узлов, он продолжает выполнение транзакции при наличии следующего набора ее фрагментов или же фиксирует транзакцию. В противном случае транзакция завершается аварийным образом.
Если при использовании основной стратегии возникает слишком много аварийных завершений транзакций (т.е. в данной рабочей нагрузке имеется высокий уровень потенциальной конфликтности транзакций – С.К.), применяется более сложная промежуточная стратегия. В этом случае каждый исполнитель до принятия решения о выполнении или аварийном завершении полученного фрагмента выжидает интервал времени величиной MaxD * среднее_время_обмена_сетевыми_сообщениями (где MaxD – максимальное число межузловых сообщений, которое потребуется для выполнения любой потенциально конфликтующей транзакции), чтобы установить, не появится ли фрагмент транзакции с меньшим значением временной метки. В этом случае исполнитель получает возможность корректного упорядочивания фрагментов, что уменьшает вероятность аварийного завершения транзакций.
Наконец, усложненная стратегия, к которой планировалось прибегать в тех случаях, когда ни основная, ни промежуточная стратегии не позволяют в достаточной степени сократить число аварийных завершений транзакций, – это достаточно традиционная стратегия оптимистического управления параллелизмом. В этом случае конфликты распознаются во время выполнения, для чего в каждом узле отслеживаются наборы прочитанных данных (read set) и наборы измененных данных (write set) каждой транзакции. Любой исполнитель запускает выполнение любого фрагмента и аварийно его завершает, если это требуется для разрешения динамически обнаруженной конфликтной ситуации.
Авторы [22] сравнивали производительность начального прототипа H-Store с производительностью неназываемой коммерческой SQL-ориентированной СУБД на эталонном тестовом наборе TPC-C. В обоих случаях транзакции реализовывались в виде хранимых процедур и запускались внешней командой, передаваемой по сети. За счет специально подобранного метода разделения базы данных TPC-C и тщательного анализа транзакций удалось преобразовать все классы транзакций к стерильному и строго двухфазному виду. В результате на одной и той же аппаратной конфигурации (один компьютер с двухъядерным процессором) H-Store показала производительность, в 82 раза превышающую производительность традиционной СУБД. По наблюдениям авторов, главным тормозом традиционной СУБД стала система журнализации изменений в дисковой памяти. На втором месте – накладные расходы на управление параллелизмом.
Кстати, в 2008 г. основные авторы [22] опубликовали результаты более глубокого исследования влияния на производительность традиционных механизмов транзакционных СУБД [29]. Это исследование, фактически, объясняет, за счет чего в H-Store удалось добиться такой производительности. Авторы взяли не очень известную систему Shore [30] с открытыми исходными текстами, сконфигурировали ее таким образом, чтобы требуемая для их экспериментов база данных полностью помещалась в основной памяти, и измерили производительность полученной системы базы данных на смеси двух транзакций из тестового набора TPC-C. Затем они последовательно стали удалять из состава Shore компоненты журнализации, синхронизации и управления буферным пулом, и в результате получили вариант системы с ограниченной функциональностью, которая показала на том же тестовом наборе производительность, в 20 раз большую, чем у исходной Shore.
Литература
1. Michael Stonebraker, Ugur Cetintemel. "One Size Fits All": An Idea Whose Time Has Come and Gone. Proceedings of the 21st International Conference on Data Engineering, 2005, pp. 2-11.
  Перевод на русский язык: Майкл Стоунбрейкер, Угур Кетинтемел. "Один размер пригоден для всех": идея, время которой пришло и ушло, 2007.
2. 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.
3. Michael Stonebraker, David J. DeWitt. MapReduce: A major step backwards, Database Column, January 17, 2008.
4. Michael Stonebraker, David J. DeWitt. MapReduce II, Database Column, January 25, 2008.
5. С.Д. Кузнецов. MapReduce: внутри, снаружи или сбоку от параллельных СУБД?, Труды Института системного программирования, т. 19, М., ИСП РАН, 2010, стр. 35-40.
6. 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.
7. Eric Brewer, Towards Robust Distributed Systems, Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 2000, p. 7.
8. Daniel Abadi, Alexander Thomson. The problems with ACID, and how to fix them without NoSQL. DBMS Musings, August 31, 2010.
  Перевод на русский язык: Дэниел Абади и Александер Томсон. Проблемы с ACID, и как их устранить, не прибегая к использованию NoSQL, 2010.
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. Домашняя страница проекта H-store, 2010.
11. Официальный сайт компании VoltDB, 2010.
12. Michael Stonebraker. Errors in Database Systems, Eventual Consistency, and the CAP Theorem. BLOG@CACM, April 5, 2010.
  Перевод на русский язык: Майкл Стоунбрейкер. Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP, 2010.
13. Michael Stonebraker. Clarifications on the CAP Theorem and Data-Related Errors. VoltDB.com, October 21, 2010.
  Перевод на русский язык: Майкл Стоунбрейкер. Уточнения по поводу теоремы CAP и ошибок, связанных с данными, 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. 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.
16. Theo Haerder, Andreas Reuter. Principles of transaction-oriented database recovery. ACM Computing Surveys, Volume 15, Issue 4, December 1983, pp. 287 - 317.
17. Jim Gray, Paul McJones, Mike Blasgen, Bruce Lindsay, Raymond Lorie, Tom Price, Franco Putzolu, Irving Traiger. The recovery manager of the System R database manager. ACM Computing Surveys, Volume 13, Issue 2, June 1981, 223-242.
18. Eric Brewer. A certain freedom: thoughts on the CAP theorem. Proceeding of the 29th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing, 2010, p. 335.
19. Seth Gilbert, Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, Volume 33 Issue 2, June 2002, pp. 51-59.
20. Julian Browne. Brewer's CAP Theorem, January 11, 2009.
21. Daniel Abadi. Problems with CAP, and Yahoo’s little known NoSQL system. DBMS Musings, April 23, 2010.
22. Michael Stonebraker, Samuel Madden, Daniel J. Abadi, Stavros Harizopoulos, Nabil Hachem, Pat Helland. The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of the 33rd International Conference on Very Large Data Bases, 2007, pp. 1150-1160.
  Перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными, 2007.
23. M. Stonebraker, C. Bear, U. Cetintemel, M. Cherniack, T. Ge, N. Hachem, S. Harizopoulos, J. Lifter, J. Rogers, and S. Zdonik. One Size Fits All? - Part 2: Benchmarking Results. Proceedings of the Third Biennial Conference on Innovative Data Systems Research (CIDR 2007), January 7-10, 2007, Asilomar, Pacific Grove, CA USA.
  Перевод на русский язык: Майкл Стоунбрейкер, Чак Беэ, Угур Кетинтемел, Мич Черняк, Тиньян Ге, Набил Хачем, Ставрос Харизопулос, Джон Лифтер, Дженни Роджерс, Стэн Здоник. Пригоден ли один размер для всех? Часть 2: результаты тестовых испытаний, 2007.
24. Pat Helland. Life beyond Distributed Transactions: an Apostate's Opinion. Proceedings of the Third Biennial Conference on Innovative Data Systems Research (CIDR 2007), January 7-10, 2007, Asilomar, Pacific Grove, CA USA.
25. Using VoltDB, V1.2, VoltDB, Inc., June 13, 2010.
26. Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alexander Rasin, Stanley Zdonik, Evan P. C. Jones, Samuel Madden, Michael Stonebraker, Yang Zhang, John Hugg, Daniel J. Abad. HStore: A HighPerformance, Distributed Main Memory Transaction Processing System. Proceedings of the VLDB Endowment, Volume 1 Issue 2, August 2008, pp. 1496-1499.
27. 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.
28. 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.
29. Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, Michael Stonebraker. OLTP Through the Looking Glass, and What We Found There, Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, June 2008, pp. 981-992.
  Перевод на русский язык: Ставрос Харизопулос, Дэниэль Абади, Сэмюэль Мэдден, Майкл Стоунбрейкер. OLTP в Зазеркалье, 2010.
30. Домашняя страница проекта Shore, 2010.
31. G. Karypis. METIS - Family of Multilevel Partitioning Algorithms, 2010.
32. Домашняя страница проекта WEKA (Waikato Environment for Knowledge Analysis), 2010.
33. Домашняя страница проекта Shore-NT, 2010.
34. R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. Falsafi. Shore-MT: A Scalable Storage Manager for the Multicore Era. Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT 2009), 2009, pp. 24-35.
35. Spinlock. Материал из Википедии – свободной энциклопедии, 2010
36. Сергей Кузнецов. Базы данных. Вводный курс. 13.3.1. Синхронизационные блокировки, 2008.
37. TPC BENCHMARK C. Standard Specification. Revision 5.11. Transaction Processing Performance Council, 2010.
38. Daniela Florescu, Donald Kossmann. Rethinking Cost and Performance of Database Systems. SIGMOD Record, Vol. 38, No. 1, March 2009, pp. 43-48.
  Перевод на русский язык: Даниела Флореску, Дональд Коссман. Переосмысление стоимости и производительности систем баз данных, 2009.
39. Werner Vogels. Data Access Patterns in the Amazon.com Technology Platform. Proceedings of the 33rd International Conference on Very Large Data Bases, Sep 2007, p. 1.
40. M. Brantner, D. Florescu, D. Graf, D. Kossmann, and T. Kraska. Building a Database on S3. Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, June 2008, pp. 251–264.
41. A. Tanenbaum and M. van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ, 2002.
  Перевод на русский язык: Э. Таненбаум, М. ван Стеен. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003, 889 стр.
42. Н.А. Олифер, В.Г. Олифер, П.Б. Храмцов, В.И. Артемьев, С.Д. Кузнецов. Стратегическое планирование сетей масштаба предприятия. Центр Информационных Технологий, 1997.
43. Домашняя страница компании 28msec/проекта Sausalito, 2010.
44. Домашняя страница Amazon Simple Storage Service (Amazon S3), 2010.
45. Домашняя страница Amazon Elastic Compute Cloud (Amazon EC2), 2010.
46. XQuery 1.0: An XML Query Language (Second Edition), W3C Recommendation, 14 December 2010.
47. Werner Vogels. Eventually Consistent. ACM Queue, Vol. 6 No. 6, October 2008, pp. 15-19.
48. Matthias Brantner, Daniela Florescu, David Graf, Donald Kossmann, Tim Kraska. Building a Database in the Cloud. Technical Report, ETH Zurich, 2009.