Распределённые системы
CAP-теорема
Цели урока
- Понимать интуицию CAP через сценарий partition двух узлов
- Различать CP и AP поведение и знать примеры каждого
- Применять PACELC для анализа trade-off в нормальном режиме работы
- Выбирать тип системы исходя из требований к consistency и availability
Предварительные знания
- Понятие распределённой системы и сетевого partition
- Базовое знакомство с CAP из вводного урока
- Опыт работы с любой БД (SQL или NoSQL)
Greg Linden, Amazon, 2006: внутренний A/B тест зафиксировал +100 мс latency = -1% продаж. Через год Werner Vogels публикует Dynamo paper: eventual consistency в обмен на 99.999% availability корзины. CAP-теорема монетизируется в реальном времени: 503 во время шоппинга дороже корзины, отстающей на 200 мс.
- **etcd в Kubernetes** - CP, потому что split-brain в оркестраторе контейнеров хуже даунтайма etcd
- **DynamoDB (Amazon)** - AP с eventual consistency для shopping cart: 99.999% availability важнее мгновенной консистентности
- **Google Spanner** - PC/EC через TrueTime (атомные часы + GPS) для финансовых транзакций Google
- **Cassandra в Netflix** - AP/EL для user preferences и viewing history: задержка в обновлении истории просмотров некритична
- **PostgreSQL** - CP: при потере primary write блокируется, но это приемлемо для финансовых данных
Эрик Брюер и гипотеза которая стала теоремой
В 2000 году Брюер был CTO Inktomi (первый веб-поисковик) и президентом ACM SIGOPS. На конференции PODC он представил conjecture (гипотезу) о CAP. Через два года Гилберт и Линч из MIT опубликовали формальное доказательство. В 2012 сам Брюер написал ревизию: "CAP Twelve Years Later" - признав что теорема огрублена и реальность сложнее, особенно с partial failures.
Интуиция: почему нельзя иметь все три
**Эрик Брюер, PODC 2000 - "Inktomi и урок масштабирования". Гипотеза:** распределённая система не может одновременно гарантировать Consistency, Availability и Partition tolerance. **2002:** Сет Гилберт и Нэнси Линч из MIT доказали это формально. Не Best Practice, не рекомендация - теорема с доказательством, как в геометрии. Семантика сбоев за partition вводится в введении в распределённые системы.
| Свойство | Что означает | Нарушение выглядит как |
|---|---|---|
| **C**onsistency | Все узлы видят одинаковые данные в любой момент. Запись на одном узле немедленно видна на любом другом. | Запросил баланс - получил 1000 рублей. Снова запросил через 100мс - получил 800 рублей (хотя никто не списывал) |
| **A**vailability | Каждый запрос к живому узлу получает ответ (успех или ошибка). Ни один живой узел не молчит. | Сервер поднят, пинг проходит, но запрос висит бесконечно - нет ни ответа, ни таймаута |
| **P**artition tolerance | Система продолжает работать при разрыве сети между узлами. | Два дата-центра потеряли связь - обе половины стали недоступны, хотя каждая сама по себе здорова |
Интуиция через конкретный сценарий: два узла A и B, клиент пишет x=1 в узел A, сеть между A и B рвётся. Что должен делать узел B когда клиент читает x? **Вариант 1:** вернуть старое значение x=0 (нарушает Consistency). **Вариант 2:** отказать в ответе, ждать восстановления сети (нарушает Availability). Третьего нет.
**Ключевой вывод:** P (Partition tolerance) не опция. Сети рвутся всегда - переполнение буфера, BGP-флуктуация, GC-пауза на 10 секунд, физический кабель. В реальном мире выбор между **CP** и **AP**, а не между CAP и CA.
CAP-теорема значит что нужно выбрать ровно два свойства раз и навсегда при проектировании
P неизбежен, реальный выбор - CP или AP. Причём разные операции в одной системе могут делать разный выбор.
Cassandra позволяет задавать consistency level на каждый запрос: QUORUM для критичных операций (CP-поведение), ONE для некритичных (AP-поведение). MongoDB с minority reads даёт AP-поведение на чтение при CP-поведении на запись.
Два узла A и B разделены partition. Клиент читает x с узла B. Узел B отвечает x=0 (старое значение). Какое свойство CAP нарушено?
CP-системы: консистентность ценой доступности
CP-система при partition отказывает в обслуживании - возвращает ошибку или ждёт восстановления кворума. Это не баг, это осознанный выбор: лучше сказать "не знаю" чем дать неверный ответ. Паттерн для финансов, inventory, конфигурации кластера - всего, где неконсистентность дороже простоя. Механика кворума живёт внутри консенсуса (Paxos, Raft).
| Система | Алгоритм консистентности | Когда использовать |
|---|---|---|
| etcd / Consul | Raft - лидер принимает все записи | Service discovery, distributed locks, конфиги кластера |
| ZooKeeper | Zab (Zookeeper Atomic Broadcast) | Координация - выбор лидера, именование, барьеры |
| MongoDB (majority write) | Quorum writes + Raft oplog | Финансовые данные, инвентарь, user profile |
| Google Spanner | TrueTime + 2PC | Глобальные транзакции, банки, Google Ads |
etcd в Kubernetes: почему именно CP
etcd хранит всё состояние кластера Kubernetes: какие поды запущены, на каких нодах, какие ConfigMap активны. При network partition etcd отказывает в записи если нет кворума (>50% нод etcd). Это защищает от split-brain: двух half-кластеров которые начинают независимо управлять подами. Временная недоступность etcd (секунды-минуты) намного лучше чем два scheduler-а которые думают что они главные.
CP-поведение стоит latency: каждая запись ждёт подтверждения кворума. Raft с 3 узлами в одном DC - 2-5мс overhead. Raft с узлами в разных регионах - 50-150мс. Google Spanner с TrueTime добавляет commit-wait 7-14мс на каждую транзакцию.
etcd-кластер из 5 нод, 3 ноды упали (осталось 2 из 5, кворум потерян). Что происходит с операциями записи?
AP-системы: доступность ценой консистентности
AP-система при partition продолжает работать на всех узлах - принимает записи, отдаёт ответы. Данные в итоге сойдутся (eventual consistency), но в момент partition разные узлы видят разное. Выбор для пользовательских данных, корзин, лент, счётчиков - везде где недоступность хуже устаревшести. Механика сходимости для AP-хранилищ разбирается в CRDTs.
| Система | Конфликты при AP | Стратегия разрешения |
|---|---|---|
| DynamoDB | Concurrent writes на разные реплики | Last-writer-wins (timestamp) или CRDTs |
| Cassandra | Разные значения на разных узлах | Read repair + LWW или пользовательский merge |
| CouchDB | Divergent document revisions | Explicit conflict detection, пользователь решает |
| Riak | Sibling values | CRDTs (G-Counter, LWW-Register) встроены |
DynamoDB и корзина Amazon
Werner Vogels (Amazon CTO) описал решение: корзина покупателя хранится в DynamoDB с eventual consistency. Если клиент добавил товар с телефона пока шоппинг-сессия была открыта на ноутбуке и сеть была нестабильна, могут возникнуть conflicting versions. Amazon выбрал стратегию: при конфликте показывать объединение обеих версий (union). Лучше показать лишний товар в корзине, чем потерять добавленный клиентом товар или выдать ошибку 503.
**Eventual consistency - не значит "долго"**. В нормальной работе (без partition) Cassandra реплицирует запись за 1-5мс внутри одного DC. "Eventual" означает гарантию конечной сходимости, а не конкретный таймаут.
AP-система возвращает случайные данные - нельзя понять что получишь
AP-система возвращает данные которые были актуальны до последнего partition. После восстановления сети узлы автоматически синхронизируются.
Eventual consistency предсказуема: при отсутствии новых записей все реплики сойдутся к одному значению. Cassandra гарантирует это через anti-entropy (Merkle trees) и read repair. Непредсказуемость - только в момент конкурентных записей при активном partition.
Cassandra настроена с consistency level ONE (читать/писать на одну реплику). При network partition между DC1 и DC2, клиент читает с DC2. Что получит?
PACELC: CAP - это только половина истории
CAP описывает поведение только при partition. Но 99.9% времени сеть работает нормально. **PACELC** (Daniel Abadi, 2012) закрывает этот пробел: **P**artition -> **A** или **C**; **E**lse (в нормальной работе) -> **L**atency или **C**onsistency. Это точнее описывает реальные trade-off. Полный ландшафт согласованности разобран в уроке про consistency models.
| Система | При partition | В норме | PACELC класс |
|---|---|---|---|
| DynamoDB (eventual) | AP | EL (низкий latency) | PA/EL |
| Cassandra (ONE) | AP | EL | PA/EL |
| MongoDB (majority) | CP | EC (consistency) | PC/EC |
| etcd / Zookeeper | CP | EC | PC/EC |
| Google Spanner | CP | EC (с TrueTime overhead) | PC/EC |
| MySQL (semi-sync) | CP | EC | PC/EC |
В нормальной работе EC-системы жертвуют latency ради гарантии что читаемые данные всегда актуальны. EL-системы возвращают ответ немедленно с локальной реплики - latency меньше, но при конкурентных записях возможна временная рассогласованность.
**Cassandra - уникальна:** tunable consistency на каждый запрос. QUORUM даёт PC/EC-поведение, ONE - PA/EL. Один и тот же кластер может быть CP для критичных операций и AP для некритичных - редкое сочетание гибкости.
CAP и PACELC: главное
- CAP: доказано (Gilbert & Lynch 2002) - нельзя иметь C, A и P одновременно
- P неизбежен - реальный выбор между CP (точность) и AP (доступность)
- CP: write rejected при потере кворума. Примеры: etcd, PostgreSQL, Spanner
- AP: write принимается локально, реплицируется async. Примеры: Cassandra ONE, DynamoDB
- PACELC: в нормальной работе тоже есть trade-off Latency vs Consistency
- Cassandra позволяет выбирать CP/AP на уровне каждого запроса через consistency level
Сервис аналитики читает данные из Cassandra с consistency level QUORUM. Как меняется поведение по PACELC при нормальной работе (без partition)?
Ключевые идеи
- **CAP-теорема** - доказана Gilbert & Lynch (2002): нельзя одновременно иметь Consistency, Availability и Partition tolerance
- **P неизбежен** - сети рвутся всегда; реальный выбор между CP (точность) и AP (доступность)
- **CP-системы** - при потере кворума отказывают в записи; примеры: etcd, ZooKeeper, Google Spanner, PostgreSQL
- **AP-системы** - принимают записи локально, реплицируют асинхронно, данные сходятся eventual; примеры: Cassandra ONE, DynamoDB
- **Eventual consistency** - не означает «медленно»: в нормальной работе Cassandra реплицирует за 1-5 мс внутри DC
- **PACELC** - в нормальной работе (без partition) тоже есть trade-off: Latency vs Consistency (EL vs EC)
- **Cassandra - tunable** - consistency level на каждый запрос: QUORUM (CP-поведение) или ONE (AP-поведение)
Вопросы для размышления
- Мессенджер (Telegram, WhatsApp) - какой trade-off CAP использует для хранения сообщений и почему именно такой? Что было бы если выбрать противоположный?
Связанные уроки
- ds-01-intro — Модель сбоев и понятие partition заданы во вводном уроке
- dist-12-consistency — Спектр согласованности продолжает CAP в linearizable vs eventual
- ds-03-consensus — CP-системы опираются на Paxos/Raft чтобы держать сторону C
- prob-22-concentration — Concentration bounds дают рамку для вероятностей кворума
- st-08-resilience — Теория устойчивости отражает AP-стиль graceful degradation
- isd-08-database-selection
- isd-14-consistency-models
- db-03-acid