CAP-теорема

Общее #

CAP-теорема — одно из фундаментальных понятий теории распределённых систем. Она связывает три свойства: согласованность (Consistency), доступность (Availability) и устойчивость к разделению сети (Partition Tolerance) — и описывает, какой компромисс между ними неизбежен при сбое связи между узлами.

Краткая история:

• В 2000 году Эрик Брюер (Eric Brewer) на симпозиуме PODC высказал гипотезу (conjecture): в распределённой системе нельзя одновременно достичь всех трёх свойств. Это было наблюдением, а не строгим результатом.
• В 2002 году Сет Гилберт и Нэнси Линч (MIT) формализовали и доказали утверждение, после чего оно стало теоремой (статья Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services).
• В 2012 году Брюер вернулся к теме (CAP Twelve Years Later) и уточнил трактовку: разделение сети — редкое событие, и проектировать систему нужно так, чтобы она корректно вела себя и в нормальном режиме, и при partition, а не «жертвовала» свойством на постоянной основе.

Популярная формулировка «выбери любые два из трёх» (часто в виде диаграммы Венна CA / CP / AP) интуитивно понятна, но вводит в заблуждение — подробности ниже.

Согласованность #

Согласованность (Consistency) в CAP означает линеаризуемость (linearizability): для внешнего наблюдателя все операции выглядят так, будто выполняются атомарно в один момент времени. Каждый запрос на чтение возвращает либо результат последней завершённой записи, либо ошибку — но никогда не «отменённое» (устаревшее после новой записи) значение.

Важно отличать это от Consistency в ACID — там это совсем другое свойство (корректность переходов между допустимыми состояниями базы). Совпадение терминов случайно.

Линеаризуемость не означает «немедленной синхронизации всех узлов» — она достижима и при задержках репликации. Существенно лишь, что клиент никогда не видит старое значение после того, как новое уже зафиксировано. Это сильная и дорогая модель: она требует кворума или алгоритма консенсуса (Raft, Paxos).

Доступность #

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

Это строгое определение, и в нём нет оговорок «в среднем» или «99.9%» — отвечает каждый запрос, без исключений.

Устойчивость к разделению #

Устойчивость к разделению (Partition Tolerance): система продолжает работать, когда сеть между узлами теряет или задерживает сообщения. Узлы могут временно не связываться друг с другом, но обязаны корректно реагировать.

Ключевой момент, который чаще всего упускают: P — это не опция. В реальной распределённой системе сеть всегда может разорваться, поэтому «отказаться от P» означает по сути отказаться от распределённости.

Главное: не «два из трёх» #

Популярная трактовка (CA = согласованность + доступность, CP = согласованность + partition, AP = доступность + partition) ошибочна в главном: partition tolerance нельзя «не выбрать». Поскольку сеть может разорваться в любой момент, реально проектное решение одно — как вести себя в момент разделения:

• CP — пожертвовать доступностью. При partition блокировать часть запросов (возвращать ошибку/тайм-аут), чтобы не нарушить согласованность. Так работают HBase, MongoDB (с write majority), Spanner, etcd (Raft).
• AP — пожертвовать согласованностью. Продолжать принимать запросы на обоих «берегах» разрыва, мирясь с тем, что узлы временно расходятся, а после восстановления — сходятся. Так по умолчанию работают Cassandra, DynamoDB, Riak, CouchDB.

А что с «CA»? В распределённой системе «CA без P» невозможен: если сеть может разорваться, система обязана решить, как себя вести. CA имеет смысл только для одного узла (то есть для нераспределённой системы) — там partition просто не возникает.

В нормальном режиме (когда partition нет) распределённая система может обеспечивать и согласованность, и доступность одновременно. Компромисс возникает именно в момент сбоя.

PACELC: более точная модель #

CAP описывает только поведение при partition, но в большинстве систем partition — редкость. PACELC (Абади, 2010) расширяет CAP:

• Partition → выбор между A и C (как в CAP);
• Else (в нормальном режиме) → выбор между Latency и C.

Иначе говоря, даже без разделения существует компромисс: чтобы вернуть ответ быстро (низкая задержка), можно отдать слегка устаревшие данные — это жертва согласованностью ради latency.

Примеры по PACELC:

• PA/EL — Cassandra, DynamoDB, Riak.
• PC/EC — Spanner, MongoDB (с majority), HBase.
• PA/EC — PNUTS.
• PC/EL — MySQL с асинхронной репликацией.

На практике PACELC полезнее CAP: дилемма latency‑vs‑consistency возникает каждый день, а partition — изредка.

Уровни согласованности #

CAP оперирует только сильной (линеаризуемой) согласованностью, но реальные AP‑системы живут в спектре более слабых моделей:

• Linearizability / strong consistency — как в CAP; дорого, требует кворума или консенсуса.
• Sequential consistency — порядок операций согласован, но чтение может отставать.
• Causal consistency — сохраняются причинно‑следственные связи между операциями.
• Read‑your‑writes — клиент всегда видит собственные записи.
• Eventual consistency — если перестать писать, все реплики рано или поздно сходятся; прочитанное может быть устаревшим.

Eventual consistency — самая слабая, но и самая дешёвая по задержке; именно её дают «из коробки» многие AP‑СУБД (Cassandra, DynamoDB). Почти всегда согласованность настраивается: можно запросить сильное чтение (quorum), пожертвовав скоростью.

Зачем это знать #

• При выборе инфраструктуры — понимать, какую модель обеспечивает система и насколько она настраивается.
• При проектировании — явно формулировать требования: финансовый учёт требует согласованности; лента соцсети спокойно живёт с eventual consistency.
• Не попадаться на маркетинг «у нас все три свойства» — это либо преувеличение, либо речь о нормальном режиме без partition.

Важная оговорка про банковские системы: их часто приводят как эталон strong consistency, но на практике многие из них внутри используют eventual consistency, а целостность счёта обеспечивает double‑entry accounting на уровне приложения. Это пример того, как требования согласованности можно закрывать не только средствами СУБД.

Ссылки #

• Brewer, Towards Robust Distributed Systems, PODC 2000 (keynote).
• Gilbert & Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition‑Tolerant Web Services, 2002.
• Brewer, CAP Twelve Years Later, IEEE Computer, 2012.
• Abadi, Problems with CAP, and Yahoo’s Little Known NoSQL System, 2010 (PACELC).
• Kleppmann, Designing Data‑Intensive Applications, гл. 5 (Replication).