Пожалуйста, перестаньте называть базы данных CP или AP

Мартин Клеппман опубликовал эту заметку в своём блоге 11 мая 2015 года please-stop-calling-databases-cp-or-ap, когда писал первое издание designing-data-intensive-applications; диаграмма линеаризуемости в посте - это превью ещё не вышедшей тогда главы книги. Поводом послужила статья Джеффа Ходжеса "Notes on Distributed Systems for Young Bloods", где рекомендовалось использовать теорему CAP для анализа систем. Клеппман согласен со всем остальным в тексте Ходжеса, но именно здесь возражает. По его мнению, теорема CAP слишком упрощена и слишком превратно понимается, чтобы по ней можно было характеризовать системы, поэтому пора перестать делить хранилища данных на CP и AP и начать описывать их компромиссы точнее. Он признаёт иронию написания статьи на тему, о которой призывает перестать писать, и говорит, что суть в том, чтобы иметь под рукой ссылку, которую можно скинуть. Его более поздняя статья, A Critique of the CAP Theorem, развивает эту мысль и предлагает альтернативу.

Теорема намного уже своей репутации

Теорема верна только в рамках тех определений, которые используются в её доказательстве, а доказательство Сета Гилберта и Нэнси Линч (2002) опирается на узкие формулировки.

Согласованность (Consistency) означает линеаризуемость - конкретную и очень строгую модель, не имеющую никакого отношения к букве C в ACID. Доступность (Availability) означает, что на каждый запрос, полученный не вышедшим из строя узлом, должен быть возвращён успешный (не ошибочный) ответ. Недостаточно, чтобы запрос мог обработать хоть какой-то узел, и многие системы, которые называют высокодоступными в смысле низкого времени простоя, под это определение не подпадают. Устойчивость к разделению (Partition tolerance), название которой Клеппман считает ужасно неудачным, означает работу поверх асинхронной сети, способной задерживать или терять сообщения. Этим свойством обладают и интернет, и любой дата-центр, так что выбирать его никому не приходится.

Модель системы тоже узкая. Это одиночный регистр для чтения и записи, так что транзакции, затрагивающие несколько объектов, выходят за рамки теоремы. Единственный рассматриваемый сбой - сетевое разделение (partition), в то время как реальные системы также теряют узлы из-за падений, исчерпания места на диске и программных ошибок. К тому же теорема ничего не говорит о задержках (latency), которые людей часто волнуют сильнее, чем доступность, поэтому система, загружающая страницу по две минуты, формально всё ещё считается доступной.

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

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

Два дата-центра реплицируют данные друг другу, и связь между ними обрывается. Первый вариант - продолжать принимать записи в обоих, из-за чего клиент в одном дата-центре может не увидеть запись, уже подтверждённую в другом, а это нарушает линеаризуемость. Второй вариант - направлять все чтения и записи в один ведущий (leader) дата-центр, а второй заставить прекратить обслуживание до устранения разделения сети; в этом случае его узлы работают, но не являются CAP-доступными. Клеппман отмечает, что в этом, по сути, и заключается всё доказательство, и оно точно так же применимо к разделению сети внутри одного дата-центра.

Второй вариант вовсе не обязательно означает простой. Если клиентов можно переключить на ведущий дата-центр, они простоя вообще не заметят. SLA вроде 99.9% корректных запросов, выполненных за одну секунду, могут соблюдать как CAP-доступные, так и CAP-недоступные системы. Когда распределённые по нескольким дата-центрам системы используют асинхронную репликацию и отказываются от линеаризуемости, причиной часто становится задержка в глобальной сети (WAN latency), а не стремление пережить сбои.

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

Репликация с одним лидером (single-leader), стандартная схема для реляционных баз данных, не является CAP-доступной, поскольку клиент, отрезанный от лидера из-за сетевого разделения, не может выполнять запись. Но она не является и CP-системой, как только приложение начинает читать с асинхронно реплицируемых follower'ов, ведь такие чтения могут возвращать устаревшие данные. Базы данных со snapshot isolation или MVCC нелинеаризуемы по замыслу, поскольку линеаризуемость снизила бы уровень параллелизма. Serializable snapshot isolation в PostgreSQL обеспечивает сериализуемость без линеаризуемости, а Oracle, судя по цитируемой им статье, не даёт ни того, ни другого. Вывеска ACID на базе данных вовсе не означает соответствия определению согласованности из CAP.

В MongoDB на каждый шард приходится один лидер, поэтому она не является CAP-доступной, а Кайл Кингсбери незадолго до этого показал нелинеаризуемые чтения при максимальных настройках согласованности, так что она не является и CAP-согласованной. Производные от Dynamo вроде Riak, Cassandra и Voldemort зависят от конфигурации: при R=W=1 они CAP-доступны, а при кворумных чтениях и записях меньшинство узлов при разделении сети не может собрать кворум. При этом кворумы тоже не гарантируют линеаризуемости. Нестрогие кворумы (sloppy quorums) и read repair порождают пограничные случаи, когда удалённые данные возвращаются, а число реплик отклоняется от заданных W и N.

Такие системы оказываются "просто P", что лозунг "два из трёх" формально допускает. Клеппман подчёркивает, что это не плохие системы и их успешно эксплуатируют в production. Их просто невозможно строго классифицировать: ответ зависит от конкретной операции или конфигурации, либо система не удовлетворяет ни одному из строгих определений.

ZooKeeper: казалось бы, однозначный случай

ZooKeeper использует протокол консенсуса, поэтому его обычно безоговорочно причисляют к CP-системам. Согласно его же документации, чтения в нём по умолчанию не линеаризуемы: каждый клиент общается с одним сервером и видит данные этого сервера, даже если в других местах уже существуют более свежие записи. Вызов sync перед чтением делает его линеаризуемым ценой падения производительности. Записям требуется кворум большинства, поэтому узлы на стороне меньшинства при сетевом разделении писать не могут, хотя и продолжают работать. Начиная с версии 3.4.0 режим read-only позволяет этим узлам в меньшинстве продолжать обслуживать чтения без кворума, что отвечает определению CAP-доступности. Таким образом, по умолчанию ZooKeeper - это "просто P", при вызове sync он превращается в CP, а по чтению становится AP, если включить нужную опцию.

Клеппман называет этот вердикт раздражающим, поскольку он совершенно искажает суть системы с превосходной согласованностью. ZooKeeper обеспечивает atomic broadcast (сводимый к консенсусу) в сочетании с причинной согласованностью (causal consistency) в качестве сессионной гарантии, а это сильнее, чем read-your-writes, monotonic reads и consistent prefix reads вместе взятые. Документация заявляет лишь sequential consistency, принижая реальные возможности. В классификации PACELC Абади система попадает в категорию PC/EL, что Клеппман считает не более информативным, чем CAP.

Почему от ярлыков нужно отказаться

Раз ни одно хранилище данных не удалось однозначно классифицировать как CP или AP, это явный признак того, что сами ярлыки негодны. Разные операции в рамках одной программы могут обладать разными характеристиками согласованности. Многие системы не относятся ни к тому, ни к другому, и никто не называет свою систему "P", потому что это звучит плохо, хотя с точки зрения архитектуры это может быть совершенно разумным решением. Те, кто всё равно пытается втиснуть систему в одну из корзин, неизбежно подгоняют значения согласованности или доступности под себя. Но как только смысл слов меняется, теорема перестаёт действовать, а разделение теряет смысл. Один бит не способен выразить отказоустойчивость, задержки, простоту модели программирования и удобство эксплуатации: режим read-only в ZooKeeper (якобы "AP") всё равно сохраняет полный порядок прошлых записей, что даёт куда более сильные гарантии, чем "AP" в Riak или Cassandra. Да и сам Эрик Брюэр в 2012 году писал, что CAP вводит в заблуждение и чрезмерно упрощает картину. В 2000 году его целью было начать дискуссию о компромиссах в распределённых системах данных. С этой задачей формулировка справилась отлично, но, как добавляет Клеппман, она никогда не задумывалась как прорывной строгий результат или схема классификации систем хранения данных.

Что почитать вместо этого

Клеппман не предлагает нового ярлыка взамен и говорит, что единственно правильного ответа не существует. Его список литературы открывает статья Дага Терри, объясняющая уровни eventual consistency на примере бейсбола, затем идёт его собственный проект Hermitage об уровнях изоляции транзакций, а затем статья Питера Бейлиса и соавторов о Highly Available Transactions, связывающая согласованность реплик, изоляцию и доступность. Далее следуют статьи, на которые даны ссылки по всему тексту поста, его книга как крайняя мера для тех, кто не хочет читать научные статьи, а также книга Флавио Хункьейры и Бенджамина Рида о правильном использовании ZooKeeper.

Связи

• linearizability - буква C в CAP с приведённым в посте примером того, что она запрещает и какую цену требует
• designing-data-intensive-applications - книга, параллельно с которой писался этот пост; страница в базе отслеживает второе издание
• meerkat-introduction - Cloudflare описывает свой сервис консенсуса в тех терминах, к которым призывает Клеппман: линеаризуемость плюс точное условие доступности (клиент связывается с любой машиной, подключённой к живому большинству), без ярлыков CP или AP
• distributed-consensus - алгоритмы на базе кворума большинства, лежащие в основе поведения ZooKeeper при записи в условиях разделения сети
• redis-cost-of-ambition - выводы Кингсбери об устаревших чтениях в Redis-Raft; свидетельства того же рода, что в посте приводятся против MongoDB
• on-transactional-concurrency-control - snapshot isolation и сериализуемость: транзакционные гарантии, которые в посте отделяются от согласованности реплик