Что именно зашифровано в аббревиатуре CAP

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

Согласованность данных (Consistency) в формулировке Гилберта и Линч эквивалентна линеаризуемости. Любая операция чтения возвращает значение самой последней успешной операции записи. Все серверы кластера ведут себя так, будто существует только одна копия данных, изменяющаяся мгновенно. Пользователь отправляет запрос на сервер в Токио и тут же опрашивает сервер во Франкфурте, получая абсолютно идентичную свежую информацию без задержек на синхронизацию.

Доступность (Availability) означает, что каждый работающий узел кластера обязан вернуть успешный содержательный ответ на любой корректный запрос без зависаний и без возврата системных ошибок. Если сервер не сгорел физически, он обязан отдать данные клиенту. Ответ с кодом ошибки или сообщением о сбое связи доступностью по Брюеру не считается.

Устойчивость к разделению сети (Partition Tolerance) гарантирует сохранение работоспособности системы при обрыве любых каналов связи между серверами. Разделение сети происходит, когда серверы делятся на изолированные группы из-за повреждения кабелей, падения маршрутизаторов или задержек пакетной передачи.

Физическая неизбежность сетевых сбоев

Серверы в дата-центрах соединены физическими проводами, свитчами и сетевыми картами. Кабели физически повреждаются во время строительных работ, сетевое оборудование зависает под высокой нагрузкой, а в операционных системах происходят длинные паузы сборщика мусора, во время которых сервер перестаёт отвечать соседям по кластеру. Сетевые задержки и потери пакетов происходят в распределённых системах постоянно.

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

Мысленный эксперимент с разделением кластера

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

  1. Клиент отправляет на узел A запрос на обновление баланса пользователя со ста рублей до двухсот рублей.
  2. Узел A записывает новое значение, но не может отправить подтверждение и реплицировать данные на узел B из-за разорванного канала связи.
  3. Другой клиент отправляет на узел B запрос на чтение баланса того же самого пользователя.
  4. У узла B возникает фундаментальная дилемма.

Узел B может вернуть старое значение баланса, равное ста рублям. Клиент получит ответ без ошибки и быстро, доступность системы сохранится, но данные окажутся устаревшими и несогласованными. Это архитектурный путь AP.

Узел B может заблокировать запрос или ответить ошибкой, сообщив о невозможности получить актуальное подтверждение от узла A. Согласованность данных сохранится, клиент не увидит ложные сведения, но система нарушит требование доступности. Это путь CP.

Как реальные СУБД решают проблему теоремы

Архитекторы современных систем управления базами данных проектируют свои решения под конкретные бизнес-задачи, выбирая приоритетную сторону компромисса.

Системы с упором на согласованность

К CP-системам относятся etcd, Apache ZooKeeper, Consul и Google Cloud Spanner. Алгоритмы распределённого консенсуса вроде Raft и Paxos требуют подтверждения операции от большинства серверов кластера, образующих кворум. При делении кластера из пяти узлов на сегменты из двух и трёх машин активной остаётся только группа из трёх серверов. Меньшая группа полностью замораживает обработку запросов на запись ради сохранения чистоты данных.

Системы с упором на доступность

К AP-системам относятся Apache Cassandra, Amazon DynamoDB и Couchbase. При разрыве связности все узлы продолжают принимать чтения и записи локально. СУБД опираются на модель согласованности в конечном счёте (eventual consistency). Конфликты версий данных между изолированными серверами разрешаются позже с помощью специальных структур вроде CRDT, векторных часов или правила победы последней записи.

Расширение теоремы — модель PACELC

В 2012 году профессор Йельского университета Дэниел Абади заметил недостаток CAP-теоремы. Теорема описывает поведение систем только в моменты редких аварий, но ничего не говорит о штатном режиме работы, когда сеть абсолютно исправна. Абади предложил расширенную классификацию PACELC.

Формулировка строится на логическом условии. Если происходит разделение сети (If there is Partition), система выбирает между доступностью (Availability) и согласованностью (Consistency). Иначе (Else), в нормальном режиме работы, система неизбежно выбирает между задержкой ответа (Latency) и согласованностью (Consistency).

Скорость света в оптоволокне ограничена константой около 200 000 километров в секунду. Даже при идеальной исправной сети передача пакета туда и обратно между дата-центрами в Нью-Йорке и Франкфурте занимает около 70-80 миллисекунд. Инженер вынужден выбирать: либо ждать подтверждения записи от удалённого узла на другом континенте ради максимальной согласованности, увеличивая время ожидания клиента, либо подтверждать запись мгновенно на локальном сервере, жертвуя строгой согласованностью ради низкой задержки.

Частые вопросы

Существуют ли настоящие CA-базы данных?

Свойствами CA обладают одноузловые СУБД вроде классического SQLite или одиночного экземпляра PostgreSQL. В них нет сети, разделение невозможно в принципе, поэтому данные согласованы и доступны. В распределённых системах сетевые сбои неизбежны, поэтому построить чистое CA-решение на множестве серверов технически невозможно.

Как Google Spanner решает проблему CAP-теоремы?

Инженеры Google установили в свои серверные стойки атомные часы и GPS-приёмники через систему TrueTime. Это сократило неопределённость системного времени между серверами до нескольких миллисекунд. Spanner остаётся строгой CP-системой, но благодаря высоконадёжной внутренней оптической сети и синхронизации часов сбои происходят крайне редко, создавая внешнюю иллюзию идеальной базы данных.

Что такое кворум и формула R + W > N?

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

Связана ли согласованность Consistency из CAP с буквой C в аббревиатуре ACID?

Эти понятия означают разные вещи. В ACID буква C обозначает логическую непротиворечивость бизнес-правил и целостность ограничений схемы данных. В CAP-теореме согласованность означает исключительно линеаризуемость, то есть одновременную видимость последней операции записи для всех клиентов на всех серверах кластера.