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

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


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

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

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

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

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

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

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

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



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

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



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

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

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

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



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

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

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

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

Как считает Майкл Стоунбрейкер , залогом построения качественной современной СУБД является правильный выбор технических компромиссов.


При выборе конкретного инженерного решения нужно учитывать множество факторов – требования будущих пользователей, вероятности возникновения различных сбойных ситуаций и т.д., а не руководствоваться догматическим образом каким-либо общими теоретическими указаниями (в том числе, и "теоремой" CAP).

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

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

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


Содержание раздела