Теорема CAP

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

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

Акроним CAP в наименовании теоремы сформирован из первых букв английских наименований этих трёх свойств.

Принцип был предложен профессором Калифорнийского университета в Беркли Эриком Брюером в июле 2000 года^[1][2] и впоследствии получил широкую популярность и признание в среде специалистов по распределённым вычислениям^[3][4]. Концепция NoSQL, в рамках которой создаются распределённые нетранзакционные системы управления базами данных, зачастую использует этот принцип в качестве обоснования неизбежности отказа от согласованности данных^[5][6][7]. Однако многими учёными^[8] и практиками^[9] теорема CAP критикуется за вольность трактовки и даже недостоверность в том смысле, в котором она распространена в сообществе.

Обоснования

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

Следствия

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

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

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

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

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

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