http://habrahabr.ru/post/231703/

В любом обнаружении NoSQL баз данных кто-нибудь обязательно вспомнит о CAP-«теореме». Я не случайно пишу слово «теорема» в кавычках. CAP-«теорема» вовсе не теорема в математическом понимании этого слова. Это неформальное утверждение, сделанное Эриком Брюером в докладе на конференции Principles of Distributed Computing (PODC) в 2000 году. Эрик утверждал, что невозможно создать распределенное (состоящие из нескольких равноценных экземпляров — звеньев) веб-приложение, которое будет одновременно обладать тремя свойствами: согласованность (consistency), доступность(availability) и устойчивость к разделению(partition tolerance), сокращенно CAP. Неформальность утверждения заключается в том, что Брюер не дал определения этим трем понятиям.

Спустя два года Сет Гилберт и Ненси Линч опубликовали исследование, где дали определения понятиям CAP а также формализовали "отложенную согласованность" (Delayed Consistency), которую потом прозвали "согласованность в конечном счете" (Eventual Consistency) и доказали CAP-«теорему» в терминах указанных определений. Если вы еще не читали исследование, то это обязательно стоит сделать — lpd.epfl.ch/sgilbert/pubs/BrewersConjecture-SigAct.pdf

Эта «теорема» так бы и не была никому нужна, если бы её не взяли на вооружение маркетологи NoSQL.

Факт №1

Согласованность в CAP означает вовсе не то, что согласованность в ACID. Гилберт и Личн определяют согласованность как существование единого порядка операций чтения\записи в рамках всей системы. То есть если в момент времени T1 было записано значение X, то в любой момент времени T2>T1 пользователь сможет прочитать X, пока не произойдет другая операция записи. Более человеческая формулировка согласованности в CAP — пользователь всегда прочитает то, что записал, если никто другой не успел перезаписать данные. В ACID это понятие совпадает с атомарностью.
Согласованность в ACID дает гораздо более сильные гарантии — целостность (уникальность) ключей и целостность внешних ключей (внешний ключ всегда ссылается на существующую запись), а также выполнение всех ограничений, описанных в схеме данных. Кроме того ACID дает гарантии не только на одно операцию, а на транзакции, которые могут состоять из множества операций. Некоторые сценарии, например продажа билетов, вообще невозможны без ACID гарантий.

Факт №2

Доступность в CAP, означает совсем не то, что вы думаете. Гилберт и Личн определяют доступность как возможность любого звена, работоспособность которого не нарушена, ответить на запрос. Что есть нарушение работоспособности не уточняется.

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

Есть еще один логический недочет в определении доступности — время, требуемое для ответа, не ограничено, главное чтобы оно было конечным. То есть сервис может пытаться обращаться к общей базе сколь угодно долго, пока связь не восстановится. «А что если связь вообще не восстановится?» — спросите вы, об этом как раз чуть дальше.

Таким образом Доступность в CAP — это далеко не та же доступность в обывательском понимании смысла этого слова.

Факт №3

CAP предполагает, что разделения сети случаются и могут длиться неограниченно долго. Разделение сети означает потерю любого числа сообщений между серверами.
Тут сразу два заблуждения.

1. При неограниченно долгом разделении сети невозможно выполнить свойство Согласованности и даже Согласованности в конечном счете. Фактически при неограниченно долгом разделении веб-сервис перестает быть единым с точки зрения пользователя. Гилберт и Личн в своем исследовании не рассматривают случай неограниченно долгого разделения, а только лишь заранее неизвестного числа потерянных сообщений.
2. Разделение сети — крайне редкое явление в наше время. Гилберт и Личн прямо заявляют, что системы, работающие в локальной сети, можно считать не подверженными разделению.

Таки образом большинство информационных систем и веб-сайтов не попадают под CAP-«теорему».

Факт №4

CAP никак не описывает поведение клиента. Пропадание связи между клиентом и веб-приложением — гораздо более частое явление, чем разделение сети или даже отказ серверов. Механизмы повторных запросов и возобновления передачи заложены во многие клиенты. Диссертация Роя Филдинга, появившаяся примерно в одно время с CAP, описывает как строить веб-сервисы и клиенты для них на базе HTTP протокола (REST-сервисы), с максимальной отказоустойчивостью и согласованностью (в смысле ACID).
В большинстве случаев на принципах REST можно построить систему (клиент+сервис), которая сможет преодолеть отсутствие доступности с точки зрения CAP, а в некоторых случаях и отсутствие согласованности.

Факт №5

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

Факт №6

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

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

Факт №7

Отложенная согласованность или согласованность в конечном счете не дает никаких гарантий. Если система поддерживает лишь согласованность в конечном счете, то невозможно гарантировать её корректность. Любое звено может опираться на устаревшие данные и не знать об этом. Более того, невозможно ввести дополнительные ограничения и контролировать их на уровне программного кода чтобы получить гарантии, так как для проверки ограничений надо опираться на согласованное состояние.

Заключение

У CAP-«теоремы» довольно тяжелая судьба. Изначально она являлась утверждением, основанным на практических соображениях. Но для доказательства была выдуман формальная модель, которая довольно далека от реального мира. И все бы ничего, если бы CAP-«теорема» не стала способом продвижения NoSQL баз данных, вызвав волну споров, негодований и заблуждений. Надеюсь, что разобравшись в CAP, вы сможете принимать решения на основе практических соображений, а не маркетинговых заявлений.