llmdocsсправочник разработчика

CAP-теорема

Материал из llmdocs — справочник разработчика
Портал: Основы CS
CAP-теорема
Автор гипотезыЭрик Брюер (2000)
ДоказательствоСет Гилберт и Нэнси Линч (2002)
Cсогласованность (линеаризуемость)
Aдоступность (каждый запрос к живому узлу получает ответ)
Pустойчивость к разделению сети
РасширениеPACELC (Дэниел Абади, 2010)

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

История

Эрик Брюер (Калифорнийский университет в Беркли, Inktomi) сформулировал гипотезу в докладе 2000 года.[1] В 2002 году Сет Гилберт и Нэнси Линч из MIT строго определили термины и доказали её.[2] Теорема стала популярным аргументом в эпоху NoSQL: многие системы объясняли отказ от строгой согласованности именно ею.

Три свойства

В доказательстве Гилберта и Линч свойства определены узко:

Свойство Строгий смысл
C — согласованность линеаризуемость: система ведёт себя как одна копия данных; каждое чтение видит результат последней завершённой записи
A — доступность каждый запрос к работающему узлу получает ответ (не ошибку), без ограничения по времени
P — устойчивость к разделению система продолжает работать, когда сеть теряет сообщения между группами узлов

«C» в CAP — не то же самое, что «C» в ACID: там речь о соблюдении ограничений целостности, а здесь — о том, все ли копии отвечают одинаково.

Суть доказательства

Пусть данные реплицированы на два узла, и связь между ними пропала. Клиент записывает новое значение на первый узел, а другой клиент читает со второго. Второй узел может:

  • ответить старым значением — система доступна, но не согласована (AP);
  • отказать или ждать восстановления связи — система согласована, но недоступна (CP).

Третьего варианта нет: узел не может узнать о записи, не получив сообщения.

CP и AP

  • CP-системы при разделении отказывают в обслуживании меньшей части кластера. Пример — системы на алгоритмах консенсуса Raft и Paxos: etcd, ZooKeeper, Consul; распределённые SQL-базы вроде CockroachDB и Google Spanner. Узел без связи с большинством перестаёт принимать записи.
  • AP-системы продолжают отвечать на всех узлах, а расхождения устраняют позже (согласованность в конечном счёте, eventual consistency) — с помощью версий, векторных часов, «последняя запись побеждает» или CRDT. Пример — Cassandra, Riak, DynamoDB в режиме по умолчанию, DNS.

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

Критика и уточнения

Сам Брюер в 2012 году отметил, что формула «выберите два из трёх» вводит в заблуждение.[3] Основные замечания:

  • Разделения редки. Большую часть времени сеть работает, и CAP ничего не говорит о поведении в нормальном режиме.
  • Выбор не бинарный. Систему можно настраивать для каждой операции: в Cassandra и MongoDB уровень согласованности задаётся на запрос (чтение и запись с кворумом дают строгую согласованность при отсутствии сбоев).
  • Определения слишком узки. Многие реальные базы не являются ни CP, ни AP в строгом смысле — например, реплика асинхронной репликации PostgreSQL не даёт ни линеаризуемости, ни полной доступности. Поэтому Мартин Клеппман предлагает не навешивать ярлыки, а описывать конкретные гарантии.[5]

PACELC

Дэниел Абади предложил более полезную модель PACELC: если есть разделение (P), выбирай между доступностью (A) и согласованностью (C); иначе (E — else) — между задержкой (L — latency) и согласованностью (C).[4] Даже без сбоев синхронная репликация на другой континент добавляет десятки миллисекунд к каждой записи. Например, DynamoDB и Cassandra по умолчанию — PA/EL (жертвуют согласованностью ради доступности и скорости), а Spanner и CockroachDB — PC/EC.

Модели согласованности

Между линеаризуемостью и согласованностью в конечном счёте лежит спектр промежуточных гарантий: последовательная согласованность, причинная согласованность, «читаю свои записи», монотонное чтение. Проект Jepsen систематически проверяет, какие гарантии реально дают популярные базы данных, и нередко находит расхождения с документацией.[6] Связанное понятие внутри одной базы — уровни изоляции транзакций.

Практические выводы

  • Выясните, что важнее для конкретных данных: остатки на счёте и уникальность логинов требуют согласованности; лента новостей, счётчики просмотров и корзина переживут кратковременные расхождения.
  • Читайте документацию базы о поведении при сбоях и уровнях согласованности, а не ярлык «CP/AP».
  • Проектируйте приложение с учётом возможных расхождений: идемпотентные операции, разрешение конфликтов, повторные попытки.

См. также

Источники

  1. Brewer — Towards Robust Distributed Systems (PODC 2000 keynote)
  2. Gilbert, Lynch — Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002)
  3. Brewer — CAP Twelve Years Later: How the "Rules" Have Changed (IEEE Computer, 2012)
  4. Abadi — Consistency Tradeoffs in Modern Distributed Database System Design (PACELC, 2012)
  5. Kleppmann — Please stop calling databases CP or AP (2015)
  6. Jepsen — Consistency Models
Категории: