CAP-теорема (Brewer) в контексте распределённых систем: невозможно одновременно и в полном объёме обеспечить три свойства — согласованность (Consistency, $C$), доступность (Availability, $A$) и устойчивость к разбиениям сети (Partition tolerance, $P$). Формально при наличии сетевого разбиения приходится выбирать между $C$ и $A$:
$$\neg (C\wedge A\wedge P).$$ Значения терминов:
- Согласованность (C): все корректные операции видят одни и те же данные (вплоть до сильной согласованности/линеаризуемости).
- Доступность (A): каждый корректный запрос получает ответ (в разумное время).
- Устойчивость к разделениям (P): система продолжает работать при разрыве связи между узлами (части сети не могут общаться).
Практические смысл и компромиссы
- В реальных сетях $P$ считается обязательным (сеть может разделиться), значит при проектировании системы фактически нужно выбирать между $C$ и $A$.
- Выбор C (жертвовать A при P): система отвергает запросы, которые не могут быть безопасно согласованы. Обычно реализуется через консенсусные протоколы (Paxos/Raft). Примеры: etcd, Zookeeper, некоторые конфигурации HBase. Поведение при partition: некоторые узлы перестают обслуживать записи до восстановления кворума.
- Выбор A (жертвовать C при P): система отвечает на запросы локально, допускает расхождения данных, которые потом сливают (eventual consistency). Примеры: Dynamo, Cassandra, CouchDB. Поведение при partition: доступность сохраняется, возможны конфликтные версии, требующие разрешения (read-repair, vector clocks, CRDT).
Примеры конкретных компромиссов и практик
- Кворумы: при $N$ репликах, чтобы гарантировать согласованное чтение/запись часто применяют правило
$$R+W>N,$$ где $R$ — число реплик для чтения, $W$ — для записи. Увеличение $W$ повышает согласованность, но снижает доступность и повышает задержку.
- Синхронная междц-региональная репликация (желать $C$) → большая задержка на запись. Альтернатива: асинхронная репликация (выбирают $A$), но возможны потеря/расхождение данных при сбоях.
- Банковская транзакция: обычно выбирают C (неприемлемы рассогласованные балансы) — система может отклонять операции во время разрыва сети (CP).
- Социальная лента/лайки: часто выбирают A — разрешают локальные обновления и синхронизируют позже (AP), жертвуя немедленной глобальной согласованностью.
- Использование CRDT/коммутативных операций: позволяет повысить практическую согласованность при выборе A, но требует ограничения модели данных (конфликтоустойчивые структуры).
Короткая сводка практических инструментов
- CP (консистентность в ущерб доступности на разбиениях): etcd, Zookeeper, Consul, некоторые конфигурации SQL-кластеров.
- AP (доступность в ущерб мгновенной согласованности): Cassandra, DynamoDB (в некоторых режимах), CouchDB, Riak.
- CA (и C и A, без $P$) — возможны только в системах, где сетевые разрывы считаются невозможными (одноузловые или учебные модели), поэтому не применимы к отказоустойчивым распределённым системам.
Дополнение (обобщение): PACELC — расширение CAP: если Partition (P) — выбирать между A и C; Else (E) — выбирать между Latency (L) и Consistency (C). Это помогает формализовать компромиссы и при нормальной работе без разбиений.
Вывод: при проектировании распределённой системы нужно явно выбирать, какие свойства приоритизировать, и строить архитектуру (репликация, кворумы, протоколы согласования, модели разрешения конфликтов) в соответствии с этими приоритетами.