CAP, PACELC и модели консистентности

ЦЕНТРАЛЬНЫЙ УНИВЕРСИТЕТ

Лекция

История про реальные компромиссы распределенных систем

/ CAP, PACELC и модели консистентности · Центральный университет

Содержание слайдов

1. CAP, PACELC и модели консистентности

История про реальные компромиссы распределенных систем

2. Карта лекции

От теорем к инженерным решениям

Сначала — CAP: C/A/P и корректная трактовка.

Затем — PACELC: профиль под продукт.

Финал — Jepsen, модели и Cassandra.

3. CAP-теорема в одной фразе

Во время partition нельзя одновременно обеспечить и C, и A

Для shared-data систем

C: linearizability

A: ответ от живой ноды

P: потеря сообщений

4. C, A и P: что внутри

Формальные определения вместо маркетинга

Consistency

Один глобальный порядок

Read-after-write актуален

Это linearizability

Availability + Partition

Availability: ответ без deadline

Partition: потеря сообщений

Вместе конфликтуют с C

5. Consistency в CAP = Linearizability

Почему это строже, чем «просто одинаковые данные»

Total order совместим с time

Операция выглядит мгновенной

Система как один узел

Desync реплик нарушает гарантию

6. Availability в теореме

Слабое по времени, но сильное по обязательности свойство

Живая нода должна ответить

Дедлайна нет, завершение есть

Ждать sync — потеря A

CP часто отвечает error/timeout

7. Как появилась CAP

От гипотезы к доказательству

1998: Brewer формулирует CAP-гипотезу.

1999: harvest/yield и fault tolerance.

2000: Brewer выводит CAP на PODC.

2002: Gilbert/Lynch доказывают.

8. Миф «выбери 2 из 3»

Полезно, но слишком грубо

Компромисс возникает при partition

В норме возможны C и A.

Стратегия задается по операциям

Нужны правила деградации

9. Partition: редкость, не экзотика

Игнорировать нельзя

Packet loss и zone breaks регулярны

Вопрос — поведение системы

Timeouts дают ложный partition

Нужны runbook-и recovery

10. Решение принимается по операциям

Один продукт может сочетать CP и AP-поведение

Деньги часто требуют CP

Ленты допускают AP

API могут вести себя по-разному

Stale read фиксируется явно

11. C/A/P — спектры

Архитектура про градации

Availability = uptime/error budget.

Consistency: eventual → linearizable.

Partition бывает частичным.

Управляем вероятностью и ущербом.

12. Partition mode как явный state machine

Detect → Decide → Recover

Detect / Decide

Симптомы: latency, majority, heartbeats

Policy: fail-fast или stale

Ограничения: read-only/degrade

Recover

Reconciliation между репликами

Conflict resolution и compensation

Метрики: lag, conflicts, recovery

13. Latency управляет CAP

Partition часто начинается с timeout

Slow network выглядит как partition

Ждать дольше помогает C

Отвечать быстрее помогает A

Timeout/retry — часть CAP

14. ACID vs CAP: разная буква C

Путаница терминов ломает архитектуру

C в ACID

Бизнес-правила и инварианты

Баланс, FK, схемы

Транзакционная корректность

C в CAP

Линеаризуемость в distributed system

Узлы видят несовместимые результаты

Реплики и сеть под сбоями

15. BASE: ответ на доступность

Soft state, eventual consistency

Временная рассогласованность ради A.

Soft state меняется сам.

Eventual convergence без новых writes.

Это другой профиль гарантий.

16. Gilbert–Lynch: формальные определения

Почему теорема строгая

C = atomic consistency.

A: healthy node отвечает.

P: произвольная потеря сообщений.

Read/write объект не даст A+C.

17. Асинхронная невозможность

Две ноды, contradiction

Пусть есть A + atomic C

G1 и G2 не обмениваются сообщениями

Write в G1, read из G2

A требует ответ; C — write

18. Частичная синхронность не спасает

Часы не отменяют CAP

Clocks и deadlines помогают.

Потеря сообщений сохраняет A/C conflict.

Timeouts только обнаруживают проблему.

Поведение на инциденте выбираем.

19. Что берем из CAP в реальную архитектуру

Опишите критичные операции

Согласуйте отказ и деградацию

Свяжите timeout/retry с CAP

Подготовьте reconciliation заранее

CAP — это управляемая деградация, а не теоретическая головоломка.

20. CAP: что делать при сбое

PACELC добавляет вопрос «что делать, когда сбоев нет»

P-блок — При partition выбираем A или C.

ELSE-блок — В норме выбираем L или C.

Почему важно — Большинство решений — в мирном режиме.

21. PACELC formula

if P then A/C else L/C

P: availability или consistency

ELSE: latency или consistency

Trade-off есть всегда

Лучше объясняет современные БД

22. Зачем появилась PACELC

CAP молчит про штатный режим

Partition редок; Cassandra eventual.

Ответ: latency и пропускная способность.

Cross-region sync повышает p99.

PACELC показывает мирный выбор.

23. Latency vs Consistency в штатном режиме

Наибольшая архитектурная боль происходит именно здесь

Глобальный порядок требует координации

Координация бьет по p95/p99

Eventual/causal меняет логику

Считаем цену delay vs error

24. Четыре категории PACELC

PA/EL, PC/EC, PA/EC, PC/EL

A-профили

PA/EL: A при P, L normally.

PA/EC: A при P, C normally.

C-профили

PC/EC: C при P и normally.

PC/EL: C при P, L normally.

Формализуйте профиль в ADR/SLO.

25. PA/EL: скорость и доступность в приоритете

Типичный выбор для high-scale контентных сценариев

При partition продолжает отвечать

В норме оптимизирована под latency

Примеры: Cassandra/DynamoDB/Riak

Нужны compensation mechanisms

26. PC/EC: консистентность прежде всего

Подходит, когда ошибка чтения/записи дороже задержки

Partition блокирует часть операций

В норме тоже ставка на C

Примеры: Spanner-like системы

Домены: payments, ledger, limits

27. PA/EC: надежность и строгая норма

Доступность на инциденте; C в норме

Partition: не прерывать сервис

Норма: сильнее consistency

Зависит от quorum/read concern

Staleness только в аварии

28. PC/EL: редкий, но важный профиль

Строго при сбоях, быстро при нормальной сети

Partition: часть запросов reject

Норма: низкая latency

Сложный routing/failover

Ниша: strict incident policy

29. Как связать PACELC-профиль с продуктовой задачей

Не «какая БД модная», а «какая ошибка недопустима»

Приоритет C

Платежи и проводки.

Остатки/лимиты без oversell.

Юридические журналы и аудит.

Приоритет L/A

Ленты и рекомендации.

Поиск с допустимым drift.

Near-real-time аналитика.

30. Как считать latency/consistency бюджет

PACELC должен попадать в метрики команды

Фиксируем p95/p99 и stale reads

Разделяем downtime и freshness

Write: latency, lag, conflicts

Read: lagging share, version age

31. Что PACELC добавляет к CAP

CAP: авария; PACELC: авария + норма.

Главный выбор часто в else-ветке.

Категория следует из цены бизнес-ошибки и SLA.

Решение обязательно валидировать тестами и наблюдаемостью.

Эксперимент подтверждает инженерный компромисс.

32. Jepsen: проверка распределенных систем

От документации к проверяемым гарантиям

Что это — Тестирование корректности под сбоями.

Что делает — Генерирует операции, инжектит сбои и проверяет историю.

Почему важно — Отделяет гарантии от маркетинга.

33. Зачем архитекторам Jepsen

Баги видны на сбоях

Проверяет partition/crash/clock skew.

Находит lost writes и atomicity bugs.

Вендоры уточняют гарантии.

Команда видит риски до внедрения.

34. Пятишаговый цикл Jepsen

Setup → Generate → Nemesis → Record → Check

Setup: кластер и expected model

Generate: concurrent read/write/CAS

Nemesis: failures and anomalies

Record + Check: counterexample

35. Какие сбои обычно моделирует Jepsen

И почему именно они ломают «почти корректные» системы

Сетевые сценарии

Полный partition между группами.

Асимметричная потеря и видимость.

Высокий jitter, нестабильные связи.

Процессные/временные

Crash/restart процессов или лидеров.

Clock skew и time-sync drift.

Наслаивающиеся сценарии.

36. Типичные находки Jepsen

Где обещания расходятся с реальностью

Lost writes при failover/split-brain.

Read-your-writes нарушен; stale read.

Транзакционные аномалии под concurrency.

«Strong consistency» без формальной модели.

37. Jepsen-карта моделей: две ветки, одна вершина

Serializable (RDBMS) и Linearizable (Distributed)

Transactional ветка — Изоляция и допустимые аномалии.

Distributed ветка — Глобальный порядок read/write.

Вершина — Strict Serializable объединяет обе оси.

38. Serializable vs Linearizable

Похожие слова, разные гарантии

Serializable

Эквивалентно serial execution

Порядок не обязан совпадать с time

Фокус: transaction isolation

Linearizable

Одна commit-точка операции

Порядок уважает real time

Фокус: replicated read/write

39. Выбор модели под продукт

Гарантия должна стоить ошибки

Eventual — когда stale допустим

Causal — для причинных цепочек

Linearizable — для read/write truth

Strict Serializable — для инвариантов

40. Общий framework: CAP + PACELC + Jepsen

1) Формализуйте инварианты и недопустимые бизнес-ошибки.

2) Опишите partition mode по операциям.

3) Выберите PACELC-профиль и latency/consistency budget.

4) Зафиксируйте целевую модель консистентности формально.

5) Проверяйте chaos/Jepsen до критичной нагрузки.

Компромисс подтверждает эксперимент.

41. Реальная БД: Cassandra через призму CAP/PACELC

Bigtable + Dynamo, tunable consistency и AP-профиль

Происхождение — Bigtable: wide-column и LSM write path. Dynamo: hashing, gossip, peer-to-peer.

Классификация — CAP: AP. PACELC: PA/EL — partition availability, normal low latency.

Практика — Сильная сторона — tunable consistency: ANY/ONE → QUORUM/ALL/SERIAL.

42. Cassandra: tunable consistency

Гарантия зависит от R/W levels

Writes: ANY, ONE, QUORUM, ALL

Reads: ONE, QUORUM, ALL

W+R>RF повышает latest read.

QUORUM — частый production balance

43. Как Cassandra держит масштаб и доступность

LSM + ring + repair

Путь записи и хранения

Commit Log -> MemTable -> SSTable (immutable files).

Compaction чистит версии.

LSM оптимизирован под writes.

Распределение и устойчивость

Consistent hashing + vnodes.

Gossip без мастера.

Repair-механизмы для сходимости.

44. Ссылки и материалы

CAP: https://system-design.space/chapter/cap-theorem

PACELC: https://system-design.space/chapter/pacelc-theorem

Модели консистентности (Jepsen): https://system-design.space/chapter/jepsen-consistency

Cassandra: https://system-design.space/chapter/cassandra

Все 4 исходные главы system-design.space в одном месте.