Теорема CAP

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

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

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

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

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

Однако это противопоставление не совсем точно, поскольку первое имеет отношение к логическим аспектам работы транзакций, а второе – к физическим свойствам распределенных систем. Таким образом, для работы с такими системами приходится применять две различные схемы работы, которые могут нести несовместимые требования.

4.2 Доказательство «теоремы»

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

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

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

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

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

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

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

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

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

4.3 ACID-транзакции

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

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

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

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

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

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

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

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

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

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

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