Базы данных

CAP-теорема

2012 год. Amazon DynamoDB переходит в режим eventual consistency под Black Friday нагрузкой. Пользователи видят старые данные корзины - но сайт работает. Конкурент выбрал строгую consistency и лежит под нагрузкой 20 минут. Amazon потерял несколько миллионов на устаревших данных, конкурент потерял на недоступности в 100 раз больше. CAP-теорема в продакшене: нет правильного выбора, есть только trade-offs.

**DynamoDB**: AP (Availability + Partition Tolerance) - eventual consistency для максимальной доступности
**HBase**: CP (Consistency + Partition Tolerance) - строгая согласованность для финансовых данных
**PostgreSQL**: CA (без partition tolerance) - для одноузловых систем с ACID гарантиями
**Cassandra**: AP по умолчанию, настраиваемый quorum для баланса C/A

Теорема, ставшая законом распределённых систем

В 2000 году на конференции PODC Эрик Брюэр из UC Berkeley представил гипотезу: распределённая система не может одновременно гарантировать Consistency, Availability и Partition Tolerance. В 2002 году Seth Gilbert и Nancy Lynch из MIT формально доказали теорему. До CAP разработчики пытались получить все три свойства и не понимали, почему это не работает. После CAP появился осознанный выбор: Dynamo (Amazon, 2007) и Bigtable (Google, 2006) - две противоположные стратегии, обе правильные для своих use case.

Три свойства CAP

CAP-теорема формулирует три фундаментальных свойства, которые распределённая система может предоставить, и доказывает, что все три одновременно - невозможно.

**Consistency** - каждый read получает самую последнюю запись или ошибку. Все узлы видят одни данные в один момент времени. Это НЕ то же самое, что Consistency в ACID (там про транзакции). **Availability** - каждый запрос получает ответ (не обязательно последние данные), без гарантии, что ответ актуален. **Partition Tolerance** - система продолжает работать при разрывах сети между узлами.

**Partition ВСЕГДА случается в продакшене.** Сетевые разрывы, задержки, потеря пакетов - это нормальная работа датацентра. Поэтому реальный выбор не CA/CP/AP, а: при partition жертвуем Consistency или Availability?

Банк хранит балансы счетов. Узел A принял перевод 1000 рублей. Узел B ещё не синхронизировался. Пользователь читает баланс с узла B - видит старый баланс. Какое свойство CAP нарушено?

Trade-offs: CA, CP, AP

На практике каждая категория CAP соответствует определённому классу систем с разными характеристиками.

Категория	Жертвуют	Примеры	Use Case
CA	Partition Tolerance	PostgreSQL, MySQL (single node)	OLTP на одном сервере
CP	Availability	HBase, Zookeeper, MongoDB (strict)	Финансы, координация
AP	Consistency	Cassandra, DynamoDB, CouchDB	Социальные сети, каталоги

**PACELC - расширение CAP (2012, Abadi):** Даже без partition есть trade-off: Latency (L) vs Consistency (C). Synchronous replication - высокая consistency, высокая latency. Asynchronous replication - низкая latency, eventual consistency. DynamoDB - AP/EL (при partition -> AP, без partition -> предпочитает Low latency).

DynamoDB под нагрузкой отвечает устаревшими данными, но не падает. HBase при разрыве сети возвращает ошибку. Как классифицировать эти системы по CAP?

BASE vs ACID

BASE - программная модель для AP-систем, противопоставленная ACID. Не "кислота vs щелочь" - это осознанные trade-offs.

Аспект	ACID	BASE
Consistency	Строгая (после каждой транзакции)	Eventual (через какое-то время)
Availability	Может отказать при failures	Высокая - всегда отвечает
Transactions	COMMIT/ROLLBACK атомарно	Нет традиционных транзакций
Примеры	PostgreSQL, Oracle	Cassandra, DynamoDB, Redis

**Вектор конфликтов в AP:** Если два узла получили разные записи в один ключ при partition, нужна стратегия разрешения конфликта. Last-Write-Wins (LWW) по timestamp - просто, но теряет данные. Vector Clocks - сложнее, но сохраняет историю. DynamoDB использует LWW, Riak - Vector Clocks.

Социальная сеть позволяет ставить лайки. При network partition два узла получили лайк одного поста. После восстановления - счётчик лайков на разных узлах разный. Какая стратегия разрешения конфликта потеряет меньше данных?

Eventual Consistency на практике

Eventual consistency не означает 'когда-нибудь'. На практике это миллисекунды-секунды при нормальной работе сети. Важно знать, когда это приемлемо, а когда нет.

**Read-your-writes consistency:** Пользователь должен видеть свои собственные записи немедленно, даже если другие пользователи видят их с задержкой. Cassandra реализует это через sticky sessions или client-side routing к тому же узлу.

CAP-теорема устарела и не применима к современным базам данных

CAP описывает фундаментальные ограничения, которые не исчезают с появлением новых технологий. NewSQL (CockroachDB, Spanner) делают CP более доступным, но не отменяют теорему.

Google Spanner достигает глобальной CP через TrueTime API и атомарные часы - это не нарушение CAP, а снижение времени partition до наносекунд. Теорема остаётся в силе, просто окно несогласованности стало ничтожно малым.

Пользователь меняет пароль. Немедленно после смены пытается войти - система использует AP с eventual consistency. Что произойдёт?

Ключевые идеи

**CAP**: Consistency (все узлы видят одни данные), Availability (каждый запрос получает ответ), Partition Tolerance (система работает при разрывах сети)
**Невозможно иметь все три** при partition - нужно выбрать CA, CP или AP
**PACELC** расширяет CAP: даже без partition есть trade-off между Latency и Consistency
**BASE vs ACID**: Basically Available, Soft state, Eventually consistent - альтернатива ACID для AP систем
**Практика**: Partition всегда случается в продакшене - реальный выбор между C и A

Вопросы для размышления

Amazon выбрал AP для DynamoDB - это правильно для интернет-магазина. Что если бы это была банковская система с балансами счетов?
PACELC говорит: даже без network partition есть trade-off между Latency и Consistency. Как это проявляется в synchronous vs asynchronous replication?
Cassandra позволяет выбрать quorum для каждого запроса (ONE, QUORUM, ALL). Как это меняет позицию в CAP-треугольнике динамически?

Связанные уроки