Теорема CAP и PACELC простыми словами: что выбирает база при сбое сети

Коротко

• CAP не предлагает выбрать две буквы из трёх. Разделение сети случается независимо от ваших желаний, а выбор появляется в момент, когда оно уже произошло.
• Пока сеть работает, теорема ничего не запрещает: система может быть и согласованной, и доступной.
• Метки «CP» и «AP» плохо описывают реальные базы: поведение зависит от настроек и часто задаётся на уровне отдельного запроса.
• На собеседовании обсуждайте не «какая база», а «какая операция»: что она делает при разделении, сколько платит за согласованность в обычном режиме и какой настройкой это обеспечено.

Что именно утверждает теорема

Эрик Брюэр сформулировал эту идею как гипотезу около 2000 года, а в 2002 году Сет Гилберт и Нэнси Линч её формально доказали. Важная деталь: в доказательстве у каждой буквы узкое определение, и оно заметно отличается от обиходного смысла.

Отсюда формулировка без лозунгов: если сообщения между репликами могут теряться, система не может одновременно гарантировать и линеаризуемость, и ответ от каждого живого узла.

Доказательство на пальцах

Есть два узла, $G_1$ и $G_2$, с одним значением $x = 0$. Связь между ними пропала.

1. Клиент пишет $x = 1$ на $G_1$. Узел жив, значит по определению A обязан ответить успехом.
2. Другой клиент читает $x$ с $G_2$. Этот узел тоже жив и тоже обязан ответить.
3. Про новую запись $G_2$ узнать неоткуда, поэтому он вернёт $x = 0$.

Запись подтверждена, а следующее чтение её не видит: C нарушена. Сохранить C можно, только если $G_1$ откажется принимать запись или $G_2$ откажется отвечать. Но тогда нарушена A. Третьего варианта в этой модели нет.

Чего теорема не говорит

Теорема намеренно узкая. Её модель — один регистр с чтением и записью, поэтому она ничего не говорит о таких вещах:

• о задержках: ответ через десять минут по её определению считается доступностью;
• о падениях узлов, потере дисков и ошибках в коде;
• о транзакциях по нескольким ключам;
• о более слабых гарантиях, чем линеаризуемость.

Поэтому «теорема CAP запрещает мне сделать X» часто оказывается неверным утверждением. Она запрещает ровно одну комбинацию.

Что считать разделением

Разделение (partition) — это не обязательно перерубленный кабель. С точки зрения узла всё выглядит одинаково: сообщение отправлено, ответа нет. Причиной может быть что угодно:

• сбой коммутатора или связи между дата-центрами;
• перегруженный узел, который не успевает отвечать;
• длинная пауза сборщика мусора;
• односторонняя потеря: A слышит B, а B не слышит A.

Отличить медленный узел от недоступного нельзя. Поэтому Брюэр в статье 2012 года предлагает смотреть на разделение как на ограничение по времени: если за отведённый срок ответа нет, система считает связь потерянной и принимает решение.

На практике вся CAP сводится к одной развилке в коде, когда сработал таймаут:

• отменить операцию и вернуть ошибку — теряем доступность;
• продолжить без подтверждения другой стороны — рискуем согласованностью.

Бесконечные ретраи — это тоже выбор: вы откладываете ответ и фактически выбираете C. Заодно отсюда следует, что единого «момента разделения» у кластера нет: один узел уже считает связь потерянной, а другой ещё нет.

Частые заблуждения

«Выбери любые две из трёх»

Самая живучая формулировка и треугольник с тремя вершинами на слайдах. Проблема в том, что P — не свойство, которое можно не выбрать. Сеть ломается независимо от вашего решения. Настоящий вопрос звучит так: когда сеть сломалась, что делаем — C или A? Брюэр сам написал в 2012 году, что формула «две из трёх» вводит в заблуждение.

«Моя система CA»

Один сервер PostgreSQL без реплик формально можно назвать CA: расходиться нечему. Но как только появляется вторая копия данных по сети, разделение становится возможным, и выбор тоже. «CA» в распределённой системе обычно значит «мы надеемся, что разделений не будет». Это допустимая ставка, если заранее понимать, что произойдёт, когда она не сыграет.

«CP-система жертвует доступностью всегда»

Нет, только на время разделения и только там, где нет связи с большинством. Кластер etcd из пяти узлов при отрыве одного узла продолжает работать на остальных четырёх. По определению CAP это уже не A, потому что оторванный узел не может обслужить обычный запрос. Но клиенты, которые могут переключиться на большинство, этого почти не заметят.

«Высокая доступность — это A из CAP»

Аптайм из SLA и A из теоремы — разные вещи. SLA считает долю успешных запросов всей системы, а A требует ответа от каждого живого узла. Поэтому система может быть не CAP-доступной и при этом иметь отличный аптайм. Spanner — хороший пример: об этом ниже.

«C в CAP — это C из ACID»

Совпала только буква. C из ACID — это соблюдение ограничений и инвариантов базы, а C из CAP — линеаризуемость, то есть гарантия про порядок операций и реплики. Подробнее про ACID и уровни изоляции — в статье про SQL на собеседовании. Можно иметь сериализуемые транзакции и при этом читать устаревшие данные с асинхронной реплики.

«AP — данные как попало, CP — всегда актуально»

Обе половины неверны. AP-система может давать read-your-writes, если клиент «прилипает» к реплике, и сходится к одному состоянию после восстановления связи. А популярное CP-хранилище ZooKeeper по умолчанию отдаёт чтения локально с сервера, поэтому они могут быть устаревшими, и его документация прямо называет такие чтения нелинеаризуемыми.

«База либо CP, либо AP»

Мартин Клеппман разобрал это в статье «Please stop calling databases CP or AP»: многие системы не подходят ни под одно определение, а поведение зависит от настроек. Классический лидер с асинхронными репликами не A, потому что отрезанный от лидера клиент не может писать, и не C, потому что реплика отдаёт устаревшие чтения. Какую метку ему дать? Никакую.

Один кластер, разные настройки

Возьмём три реплики в разных дата-центрах и условие из кворумных систем. $N$ — число реплик, $W$ — сколько подтверждений ждём при записи, $R$ — сколько реплик опрашиваем при чтении. Если $R + W > N$, множества записи и чтения обязательно пересекаются, и чтение увидит подтверждённую запись.

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

Это одна и та же база и одна и та же сеть. Выбор сделан параметрами запроса, поэтому вопрос «CP или AP?» тут просто не имеет ответа.

Одна оговорка: пересечение кворумов само по себе ещё не линеаризуемость. Конкурентные записи, частично применившиеся неудачные записи и разрешение конфликтов по времени могут её нарушить. Если на собеседовании скажете «у нас кворум, значит линеаризуемо», интервьюер почти наверняка попросит разобрать именно эти случаи.

PACELC: вторая половина правды

Разделения случаются редко. Задержку же вы платите на каждом запросе. Этот перекос заметил Дэниел Абади: он описал идею в блоге в 2010 году и подробно изложил в журнале IEEE Computer в 2012-м. Модель читается как условный оператор:

if P then A or C else L or C

Если есть разделение (Partition), выбираем между Availability и Consistency. Иначе (Else) выбираем между Latency и Consistency.

Почему компромисс есть и без сбоев: чтобы все реплики договорились, нужны сетевые обмены, а скорость света никто не отменял. Либо ждём подтверждений, либо отвечаем раньше и допускаем, что кто-то прочитает старое значение. Формальную трактовку PACELC через нижние границы задержки дал Войцех Голаб в 2018 году.

Сколько стоит согласованность

Условный пример: запись приходит в реплику, до второй реплики 10 мс туда и обратно, до третьей 80 мс. Цифры выбраны для наглядности, а не измерены.

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

Четыре класса

Два последних класса на первый взгляд странные, и тут есть полезная тонкость: буквы C в двух половинах PACELC не обязаны означать одно и то же. Абади на примере PNUTS показывает, что система может постоянно жить с ослабленной согласованностью, а при разделении отказать в записи, чтобы не ослаблять её ещё сильнее.

Важно и другое. У MongoDB разные источники дают разные метки: у Абади PA/EC, а во многих современных обзорах PC/EC. Это не чья-то ошибка: сама база и её значения по умолчанию заметно изменились. С Cassandra похожая история: на уровне ONE она ведёт себя как PA/EL, а с QUORUM на чтение и запись ближе к PC/EC. Классы полезны как язык для обсуждения, но не как постоянный ярлык на продукте.

Как ведут себя реальные базы

Всё, что ниже, описывает типичное поведение при типичных настройках. Оно зависит от версии, топологии и параметров драйвера, поэтому перед проектированием проверяйте документацию своей версии и тестируйте отказы сами.

Две вещи из таблицы особенно полезны.

DynamoDB выставляет PACELC в прайсе. Eventually consistent чтение стоит вдвое дешевле сильного: компромисс из ветки Else можно буквально посчитать в деньгах.

Spanner показывает, что ярлык и аптайм — разные вещи. Брюэр отвечал, что формально Spanner не CA, но на практике пользователи могут считать его таковым: разделения в частной сети Google достаточно редки. Это не обход теоремы, а очень дорогая сеть, которая сделала неприятную ветку редкой.

Что делать после разделения

Если во время разделения вы выбрали A, реплики разъехались. Самая недооценённая часть темы — как их потом свести. Брюэр описывает три шага: обнаружить разделение, перейти в особый режим работы и восстановиться после него. Режим обычно значит либо ограничить набор операций, либо продолжать, но вести журнал для восстановления.

Компенсация встречается чаще, чем кажется. Продали последний товар двоим, отменили один заказ и извинились. На уровне сервисов та же идея лежит в основе паттерна Saga.

Выбирайте для операции, а не для базы

Брюэр отмечал, что выбор может отличаться между подсистемами и даже отдельными операциями. Разберём один маркетплейс:

Хороший способ принять решение — сравнить две цены: сколько стоит ответить неправильно и сколько стоит не ответить. Если устаревший ответ дороже ошибки, нужна C. Если дороже ошибка, нужна A.

Как отвечать на собеседовании

Если спрашивают определение

Ответ укладывается в 30 секунд:

CAP говорит, что при разделении сети реплицированная система не может одновременно гарантировать линеаризуемость и ответ от каждого живого узла. Разделение от нас не зависит, поэтому выбор идёт между C и A и только на время разделения. CAP ничего не говорит про задержки, поэтому я дополняю её PACELC: без разделения остаётся компромисс между задержкой и согласованностью, и он действует на каждый запрос.

Больше всего очков здесь приносит уточнение определений. Оно сразу показывает, что вы знаете теорему, а не слайд с треугольником.

Если это часть системного дизайна

Не начинайте с названия базы. Удобный порядок:

1. Разбейте систему на операции. Деньги и лайки редко требуют одного и того же.
2. Спросите про цену ошибки. Что хуже для этой операции: отказ или устаревшие данные?
3. Определите поведение при разделении. Какая сторона работает, что видит клиент на другой стороне.
4. Определите поведение без разделения. Какая нужна задержка, насколько далеко реплики, как читаем и пишем.
5. Назовите механизм. Кворум, лидер, настройка уровня согласованности, чтение с лидера.
6. Опишите восстановление. Как сливаем данные и как компенсируем ошибки.

Плохой и хороший ответ

Вопрос: «Какую базу взять для бронирования билетов?»

Плохо: «Нам нужна согласованность, значит берём CP-базу, например MongoDB. А для ленты событий — AP, Cassandra».

Здесь нет ни операций, ни настроек, а метки выданы продуктам целиком.

Хорошо: «Разделю по операциям. Бронирование места не должно продать его дважды. Поэтому при разделении лучше вернуть ошибку на стороне меньшинства и подсказать пользователю повторить попытку. Значит, запись идёт через лидера или кворум, и за это мы платим задержкой, что здесь приемлемо. Карта свободных мест, наоборот, может отставать на пару секунд: читаю её с реплик или из кэша, а финальная проверка всё равно будет при бронировании. Если нужен конкретный продукт, сравню варианты по настройкам и проверю поведение при отказах, а не по ярлыку».

Вопросы, которые спрашивают вдогонку

Типичные ошибки

• Рисовать треугольник и говорить «выбираем две».
• Называть продукт CP или AP без указания настроек.
• Говорить, что «согласованность» и «доступность» значат то же, что в обычной речи или в SLA.
• Обсуждать только сбой и забыть про задержку в обычном режиме.
• Забыть про восстановление после разделения: выбрать A легко, а потом надо сводить данные.
• Уверенно утверждать детали поведения конкретной БД. Лучше сказать: «насколько помню, по умолчанию так, но это зависит от версии, я бы проверил».

Что почитать в оригинале

• Гилберт и Линч, доказательство гипотезы Брюэра, 2002.
• Брюэр, CAP Twelve Years Later, 2012.
• Абади, Consistency Tradeoffs in Modern Distributed Database System Design, 2012.
• Клеппман, Please stop calling databases CP or AP, 2015.
• Голаб, Proving PACELC, 2018.
• Брюэр, Spanner, TrueTime and the CAP Theorem, 2017.