Теорема CAP (Consistency, Availability и Partition tolerance)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:13, 22 ноября 2016.

Теорема CAР (известная также как теорема Брюера) — эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:

  • согласованность данных (англ. consistency) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;
  • доступность (англ. availability) — любой запрос к распределённой системе завершается корректным откликом;
  • устойчивость к разделению (англ. partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций.[1]

Обоснования

В 2002 году Сет Джилберт и Нэнси Линч из Массачусетского технологического института подобрали формальные модели асинхронных и синхронных распределённых вычислений, в рамках которых показано выполнение теоремы CAP в условиях отсутствия синхронизации (общих часов) у узлов распределённой системы и принципиальную возможность компромисса в частично синхронных системах. В этой работе «согласованность» в смысле теоремы CAP соотнесена с выполнением первых двух требований ACID — атомарности и согласованности. В дальнейшем, многие практики ссылались на данную работу как на доказательство теоремы CAP.

Следствия

С точки зрения теоремы CAP, распределённые системы в зависимости от пары практически поддерживаемых свойств из трёх возможных распадаются на три класса — CA, CP, AP.

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

Система класса CP в каждый момент обеспечивает целостный результат и способна функционировать в условиях распада, но достигает этого в ущерб доступности: может не выдавать отклик на запрос. Устойчивость к распаду на секции требует обеспечения дублирования изменений во всех узлах системы, в связи с этим отмечается практическая целесообразность использования в таких системах распределённых пессимистических блокировок для сохранения целостности.

В системе класса AP не гарантируется целостность, но при этом выполнены условия доступности и устойчивости к распаду на секции. Хотя системы такого рода известны задолго до формулировки принципа CAP (например, распределённые веб-кэши или DNS), рост популярности решений с этим набором свойств связывается именно с распространением теоремы CAP. Так, большинство NoSQL-систем принципиально не гарантируют целостности данных, и ссылаются на теорему CAP как на мотив такого ограничения. Задачей при построении AP-систем становится обеспечение некоторого практически целесообразного уровня целостности данных, в этом смысле про AP-системы говорят как о «целостных в конечном итоге» (англ. eventually consistent) или как о «слабо целостных» (англ. weak consistent).

Примеры

Ниже представлены примеры того, что могут представлять собой системы без одного из этих свойств[2]:

  1. +Availability +Consistency -Parition tolerance. Система, которая рассчитывает на то, что сеть абсолютно надёжна, и благодаря этому может обеспечить консистентность данных на всех живых узлах. Или, в вырожденном случае, система из одного узла, где неконсистентности быть не может, и которая доступна всегда, когда доступен её узел. Другими словами, на практике таких систем или не существует, или они не являются распределёнными (см. также).
  2. +Consistency +Partition tolerance -Availability. Система с несколькими мастер-базами, которые обновляются синхронно. Она всегда корректна, потому что транзакция отрабатывает, только если изменения удалось распространить по всем серверам БД. Она продолжает корректно работать по крайней мере на чтение, если один из серверов падает. А вот попытки записи будут обрываться или сильно задерживаться, пока система не убедится в своей консистентности.
  3. +Availability +Partition tolerance -Consistency. Система с несколькими серверами, каждый из которых может принимать данные, но не обязуется в тот же момент распространять их по всему кластеру. Система переживает падения части серверов, но когда они входят в строй, они будут выдавать пользователям старые данные.

BASE-архитектура

Во второй половине 2000-х годов сформулирован подход к построению распределённых систем, в которых требования целостности и доступности выполнены не в полной мере, названый акронимом BASE (от англ. Basically Available, Soft-state, Eventually consistent — базовая доступность, неустойчивое состояние, согласованность в конечном счёте), при этом такой подход напрямую противопоставляется ACID. Под базовой доступностью подразумевается такой подход к проектированию приложения, чтобы сбой в некоторых узлах приводил к отказу в обслуживании только для незначительной части сессий при сохранении доступности в большинстве случаев. Неустойчивое состояние подразумевает возможность жертвовать долговременным хранением состояния сессий (таких как промежуточные результаты выборок, информация о навигации, контексте), при этом концентрируясь на фиксации обновлений только критичных операций. Согласованности в конечном счёте, трактующейся как возможность противоречивости данных в некоторых случаях, но при обеспечении согласования в практически обозримое время, посвящено значительное количество самостоятельных исследований.

Проблемы связанные с САР теоремой

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

САР использует слишком узкое определение

Если вы хотите ссылаться на САР как на теорему (а не на расплывчатый концепт в маркетинговых материалах к вашей базе данных), вы должны быть точны. Математика требует точности. Доказательство сохраняется только если вы вкладываете в слова, то же самое значение, что было использовано при доказательстве. И оно опирается на очень точные определения:

  • Согласованность (Consistency) в САР на самом деле означает линеаризуемость, что является (и очень сильным) принципом согласованности. В частности, это не имеет ничего общего с «С» из ACID, даже если эта С так же означает «согласованность».
  • Доступность (Availability) в САР определено как «каждый запрос, полученный работающим узлом [базой данных] в системе должен приводить к ответу [не содержащему ошибок]». Недостаточно чтобы некоторые узлы могли обработать запрос: любой работающий узел должен быть способен обработать запрос. Множество так называемых «высокодоступных» (high abailability), т.е. с низким уровнем простоя, систем в реальности не отвечают определению доступности.
  • Устойчивость к разделению (Partition tolerance) – означает, что вы для связи используете асинхронную сеть, которая может терять или задерживать сообщения. Интернет и все дата-центры обладают этим свойством, так что в реальности у вас нет выбора в этом контексте.


Еще хочу заметить, что САР теорема описывает систему очень определенной модели:

  • Модель системы в пространстве САР это единый узел\счетчик (register) чтения-записи – и всё. Например, ничего не говорится о транзакциях, которые затрагивают несколько объектов. Они просто за пределами условий теоремы, до тех пор, пока вы не ужмете каким-то образом те объекты до единого объекта.
  • Единственный тип сбоя о котором упоминает САР теорема – сетевое разделение, т.е. узлы остаются активны, но сеть между некоторыми из них не работает. Такой вид ошибки так или иначе происходит, но это не единственная вещь, которая может пойти не так: узлы могут быть сломаны или в перезагрузке, может закончиться место на диске, можете поймать баг в ПО, и тд и тп. В процессе создания распределенной системы вам надо иметь ввиду гораздо больший спектр возможных ошибок и компромиссов, к которым они ведут. Слишком сильная фокусировка на САР теореме ведет к игнорированию других важных проблем.
  • Более того, САР теорема ничего не говорит о латентности, которая беспокоит большинство разработчиков гораздо больше, нежели доступность. Фактически, САР-совместимые системы могут быть сколь угодно медленными и всё равно называться «доступными». Если доводить всё до крайности, я уверен, что ваши пользователи не будут склонны называть вашу систему «доступной», если для получения веб-страницы потребуется минуты 2.


Если ваше определение совпадает с формальным значением терминов в САР теореме, тогда она подходит вам. Но если вы даёте другое определение терминам согласованности и доступности, то нельзя ожидать того, что САР теорема применима к вам. Конечно, это не значит, что путем переопределения значений вы внезапно сможете сделать невозможные вещи! Просто вы не можете руководствоваться САР теоремой и использовать ее для аргументации в поддержку вашей точки зрения.

Линеаризуемость

Ключевая идея термина "линеаризуемость"(в смысле «целостностью» в контексте САР) такая:

« Если операция В началась после успешного завершения операции А, тогда операция В должна видеть состояние системы в момент завершении А или же в новом состоянии. »

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

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

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

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

САР-доступность

Поговорим немного о том, нужно ли жертвовать линеаризованностью или доступностью в случае с сетевым разделением.

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

Теперь пусть соединение между ДЦ было прервано – это то, что мы подразумеваем под сетевым разделением. Что тогда случится?

Очевидно, что вы можете выбрать один из двух вариантов:

  1. Приложение продолжает работать и позволяет запись в базу данных, оно полностью доступно для обоих дата-центров. Но так как связь между ДЦ прервана, все изменения в одном ДЦ не будут доступны в другом. Это нарушает линеаризуемость.
  2. Eсли вы не хотите терять линеаризуемость, вы должны быть уверены, что вы осуществляете всё чтение и запись в одном дата-центре, который вы можете называть ведущим. В другом ДЦ, данные которого не могут быть в актуальном состоянии из-за потери соединения, база данных должна прекратить обслуживать клиентов на чтение и запись до восстановления синхронизации. Так как зависимая база данных во втором ДЦ не может обрабатывать запросы, то она не САР-доступна.

Заметьте что в нашей условно «недоступной» ситуации во втором варианте, мы вполне успешно можем обрабатывать запросы в одном из ДЦ. Так что если система построена с упором на линеаризуемость (т.е. не САР-доступна), то это не обязательно означает, что сетевая разделенность автоматически ведет к простою приложения. Если вы сможете перевести всех клиентов на использование ведущего ДЦ, клиенты не заметят падения вообще.

Доступность (availability) на практике не то чтобы ссылается на САР-доступность. Доступность вашего приложения скорее всего измеряется в SLA (например, 99,9% правильных запросов должны возвращать результат в течении 1 секунды), но такое соглашение может быть реализовано в системах CAP-доступных и САР-недоступных.

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

СР/АР: ложная дихотомия

Тот обстоятельство, что однозначно классифицировать даже одно хранилище как «АР» или «СР» нельзя должно наводить на определенные мысли: это просто неподходящие определения для описываемых систем.

Причины по которым следует прекратить пытаться определить различные хранилища в категории «АР» или «СР» потому, что:

  • В рамках одно приложения может существовать несколько разных операций с различными характеристиками согласованности данных.
  • Множество систем не отвечают определению согласованности и доступности в рамках САР-теоремы. Однако я никогда не слышал, чтобы кто-то называл свою систему просто «Р», наверно потому что это плохо звучит. Но это не плохо – это может быть идеально спланированная архитектура, которая просто не попадает в категории СР/АР.
  • Даже если большинство ПО не попадают точно в упомянутые категории, люди все равно стараются втиснуть его в одну из категорий, и получается, что неизбежно меняется смысл «согласованности» или «доступности» к тому, что они хотят под этим понимать. К сожалению, если значение слов меняется – САР теорема больше не может применятся, и разделение на СР/АР не имеет значения.
  • Огромное количество нюансов теряется при попытке втиснуть систему в одну из двух категорий. Существует огромное количество аспектов касательно устойчивости к сбоям, латентности, простоты модели программирования, взаимодействия и так далее, что может быть использовано в проектировании распределенных систем. Физически невозможно закодировать все эти нюансы в одном бите информации. Например, даже ZooKeeper поддерживает «AP» в режиме только для чтения, и этот режим дает возможность читать записи в том же самом порядке как они были записаны – это гораздо сильнее, чем «АР» в таких системах как Riak или Cassandra – так что было бы нелепо складывать их в одну кучу.
  • Эрик Брюэр (Eric Brewer) признает, что САР вводит в заблуждение и слишком всё упрощает. В 2000 году было важно начать обсуждение компромиссов в распределенных системах, и это сработало. Не было намерения создать какой-то прорывной формальный документ или строгую классификацию схем для хранилищ данных. 15 лет спустя у нас появился гораздо более богатый набор инструментов с разными подходами к обеспечению целостности данных и защитой к ошибкам. САР сделала свою задачу и теперь время двигаться дальше.

Источники

  1. Википедия [Электронный ресурс] : Теорема CAP / Дата обновления: 11.10.2016. - Режим доступа: http://ru.wikipedia.org/?oldid=81273789 (дата обращения: 11.10.2016)
  2. Softwaremaniacs [Электронный ресурс] : CAP-теорема Брюера / Дата обращения: 26 октября 2016 - Режим доступа: http://softwaremaniacs.org/blog/2010/01/31/brewers-cap-theorem/
  3. Хабрахабр [Электронный ресурс] : Забудьте САР теорему как более не актуальную / Дата обращения: 26 октября 2016 - Режим доступа: https://habrahabr.ru/post/258145/

Ссылки