Модуль: Распределённые системы · Уровень: Senior+

TL;DR#

• CAP — это не «выбери 2 из 3». Сетевые партиции (P) случаются вне твоего контроля, поэтому реальный выбор делается только во время партиции: либо Consistency, либо Availability. В отсутствие партиции можно иметь и C, и A одновременно.
• C в CAP — это linearizability (строгая согласованность по чтению, recency guarantee), а не буква C из ACID (consistency = соблюдение инвариантов/констрейнтов). Это разные понятия, которые путают чаще всего.
• A в CAP — это «каждый запрос к работающему узлу получает (не-error) ответ». Это очень жёсткое определение: latency не учитывается, ответ должен прийти от любой ноды, не упавшей физически.
• P (partition tolerance) — система продолжает работать при потере произвольного числа сообщений между узлами. Для распределённой системы это не опция, а данность.
• CP: при партиции жертвуем доступностью (некоторые узлы отвечают ошибкой/таймаутом ради согласованности). Примеры: etcd, ZooKeeper, Consul, HBase, Spanner, традиционные RDBMS с синхронной репликацией.
• AP: при партиции жертвуем линеаризуемостью (узлы отвечают возможно устаревшими данными). Примеры: Cassandra, DynamoDB, Riak, Voldemort.
• PACELC дополняет CAP: при Partition выбираем между A/C, иначе (Else) — между Latency/Consistency. Это честнее описывает реальные системы.

Теория#

Формулировка и её точный смысл#

Теорему сформулировал Эрик Брюер (2000, conjecture), формально доказали Gilbert & Lynch (2002). Точная формулировка доказанной версии:

В асинхронной сетевой модели невозможно реализовать read/write регистр, который одновременно гарантирует linearizability (C) и availability (A) при наличии partition (P).

Ключевые определения из статьи Gilbert & Lynch:

• Consistency (atomic / linearizable): должна существовать единая total order над всеми операциями такая, что каждая операция выглядит атомарно выполненной в один момент времени; чтение возвращает результат последней завершившейся записи (по реальному времени). Это и есть linearizability.
• Availability: каждый запрос, полученный неупавшим узлом, должен завершиться (вернуть успешный ответ, не ошибку). Важно: нет ограничения на время — но «вернуть ошибку» или «бесконечно ждать» не считается доступностью.
• Partition tolerance: сеть может терять произвольное количество сообщений, отправленных от одного узла другому.

Почему «2 из 3» — заблуждение#

Формулировка «выбери 2 из 3» подразумевает, что CA-система (без partition tolerance) — легитимный выбор. Но:

1. P нельзя «выключить». Партиции — свойство сети, а не дизайна. Кабель оборвётся, GC-пауза заморозит ноду на 10 секунд, switch перегрузится. Вы не выбираете, случится ли партиция; вы выбираете, как себя вести, когда она случилась.
2. CA без P бессмысленна в распределённой системе. «CA» в практике означает «однонодовая система» (или система, которая просто упадёт/потеряет данные при партиции). Это не третий вариант, это отказ от распределённости.

Поэтому корректная ментальная модель: P — это данность, а реальный выбор — C vs A только в момент партиции.

        Партиция случилась?
        ┌──────────────┴──────────────┐
        НЕТ                            ДА
   можно C И A                  выбор: C ИЛИ A
   (PACELC: тут                 ┌──────┴───────┐
    выбор L vs C)             CP            AP
                          (ошибки/         (stale
                           таймауты,        reads,
                           но consistent)   но доступно)

C в CAP ≠ C в ACID#

Это самая частая путаница на собеседованиях.

Можно иметь ACID-C без linearizability (single-node БД с констрейнтами) и наоборот. В CAP под C понимается строго recency-гарантия чтения.

Что значит «availability» во время партиции#

Рассмотрим партицию, разрезавшую систему на две группы узлов {A, B} | {C, D}. Клиент обращается к узлу A.

• CP-выбор: A понимает, что не может связаться с большинством (или не уверен, что у него актуальные данные), и отвечает ошибкой/таймаутом. Система отдала availability, но любой ответ, который она всё-таки даёт, линеаризуем. Пример: запись в etcd на узле меньшинства провалится, потому что Raft требует кворума.
• AP-выбор: A отвечает данными, которые у него есть локально, даже если на стороне {C, D} уже была более свежая запись. Система доступна, но чтение может быть устаревшим (нарушение linearizability). Пример: Cassandra с CL=ONE вернёт значение с доступной реплики.

Заметьте: «доступность» в CAP — это про возврат успешного ответа от каждого работающего узла. Реальные «highly available» системы в маркетинге часто имеют в виду не это (а, скажем, 99.99% uptime), что добавляет путаницы.

Кворумы: не бинарный выбор#

На практике системы настраиваются по осям через кворумы. Для N реплик с W (write quorum) и R (read quorum):

• Если W + R > N — гарантируется пересечение множеств read/write реплик ⇒ строгая согласованность по чтению (при отсутствии конкурентных записей и read-repair-аномалий).
• Если W + R ≤ N — возможны stale reads, зато выше доступность и ниже latency.

Dynamo-style системы (Cassandra, Riak) позволяют выбирать это на каждый запрос: одна и та же система может вести себя как «более CP» (QUORUM/ALL) или «более AP» (ONE) в зависимости от consistency level. Поэтому ярлык «AP-система» — упрощение: это про дефолт и возможности.

N=3, W=2, R=2 → W+R=4 > 3 → пересечение гарантировано (strong-ish read)
N=3, W=1, R=1 → W+R=2 ≤ 3 → возможен stale read (AP-режим)

PACELC#

CAP молчит про поведение в нормальном режиме (без партиций). Daniel Abadi предложил PACELC (2010):

if (P) then choose A or C; ELSE choose L (latency) or C (consistency).

Идея: даже без партиций есть фундаментальный трейдофф между низкой задержкой и сильной согласованностью. Чтобы дать линеаризуемое чтение, надо синхронно дотянуться до кворума/лидера — это latency. Чтобы быть быстрым — читаем с ближайшей реплики, рискуя устаревшими данными.

Классификация (Abadi):

* etcd/ZK могут отдавать линеаризуемые чтения через лидера или быстрые «локальные» чтения с риском staleness — настраивается.

PACELC объясняет, почему две «CP-системы» могут вести себя по-разному в обычной жизни, и почему Spanner (PC/EC) платит latency-цену за глобальную согласованность.

Примеры систем#

CP (consistency > availability при партиции):

• etcd — Raft, требует кворум (N/2+1). Узлы меньшинства не обслуживают записи и (по умолчанию) линеаризуемые чтения. Используется как source of truth для Kubernetes.
• ZooKeeper — Zab-протокол; запись требует кворума; при потере кворума ансамбль перестаёт обслуживать записи. (Нюанс: чтения по умолчанию могут быть слегка устаревшими — ZK гарантирует не полную линеаризуемость чтений, а sequential consistency + sync().)
• Consul — Raft для каталога/KV.
• HBase — каждый регион обслуживается ровно одним RegionServer; при его недоступности регион недоступен до failover (strong consistency, жертвует availability).
• Spanner — синхронная репликация через Paxos + TrueTime, даёт external consistency (strict serializability); при партиции узлы меньшинства недоступны.

AP (availability > consistency при партиции):

• Cassandra — Dynamo-style, tunable consistency, hinted handoff, read-repair, last-write-wins по timestamp. По дефолту склонна к доступности.
• DynamoDB — eventually consistent reads по умолчанию (есть опция strongly consistent read, которая стоит дороже и менее доступна).
• Riak — Dynamo-style, vector clocks для разрешения конфликтов, sibling values.

Доказательство-интуиция (на пальцах)#

Два узла G1 и G2, партиция между ними. Клиент пишет v2 в G1, затем читает с G2.

• Если G2 отвечает (availability) — он не мог узнать про v2 (сообщения теряются), вернёт v1 ⇒ нарушена linearizability (C).
• Если G2 хочет сохранить C — он должен дождаться синхронизации с G1, которая невозможна при партиции ⇒ либо ждёт вечно, либо отвечает ошибкой ⇒ нарушена availability (A).

Нельзя одновременно ответить успешно и ответить свежими данными ⇒ C и A несовместимы при P.

Подводные камни / gotchas#

• «CA-система» — почти всегда маркетинг или непонимание. В распределённой системе P неизбежна; «CA» = «мы не пережили партицию».
• Путаница C (CAP) и C (ACID). Если на собеседовании спрашивают «PostgreSQL — это CP или AP?», корректный ответ требует уточнения топологии (одна нода? синхронная/асинхронная репликация?), и нельзя смешивать ACID-консистентность с линеаризуемостью.
• Ярлык «AP/CP» вешают на систему целиком, хотя многие системы tunable per-request (Cassandra CL, Dynamo consistent read, MongoDB read/write concern). Точнее говорить про конфигурацию.
• Availability в CAP ≠ uptime/SLA. CAP-availability — формальное «каждый живой узел отвечает успехом». 99.99% доступности из SLA — другое.
• CAP — модель read/write регистра, она не охватывает транзакции над несколькими объектами, latency, durability, согласованность реплик при отсутствии партиции — поэтому в реальном проектировании опираются на PACELC и конкретные consistency models.
• Партиция ≠ только обрыв сети. Долгая GC-пауза, перегруженный диск, медленный сосед — для протокола неотличимы от партиции (узел «пропал»). Это влияет на тюнинг таймаутов.
• «Eventually consistent» не значит «несогласованная всегда». Это значит, что при прекращении записей реплики сойдутся; во время записей возможны аномалии.

Вопросы на собеседовании#

В: Почему «выбери 2 из 3» — неправильная трактовка CAP? О: Потому что P (partition tolerance) — не дизайн-решение, а свойство сети: партиции случаются независимо от вас. Реальный выбор — C vs A, и только в момент партиции. Вне партиции можно иметь и C, и A. «CA-система» на практике означает однонодовую систему, которая просто не переживёт партицию.

В: Что именно означает буква C в CAP? О: Linearizability — строгая согласованность по чтению: существует единый порядок всех операций по реальному времени, и чтение возвращает результат самой последней завершившейся записи. Это recency-гарантия, а не ACID-консистентность (соблюдение инвариантов/констрейнтов).

В: Чем C в CAP отличается от C в ACID? О: CAP-C — про согласованность между репликами во времени (linearizability). ACID-C — про то, что транзакция оставляет БД в валидном состоянии относительно прикладных инвариантов и констрейнтов. Можно иметь одно без другого. Single-node БД даёт ACID-C, но к CAP-C отношения не имеет.

В: Что значит «availability» в CAP-смысле? О: Каждый запрос к неупавшему узлу завершается успешным (не-error) ответом. Нет ограничения на время, но возврат ошибки или таймаут — это уже не availability. Это жёстче, чем бытовое «система работает».

В: Как кворумы соотносятся с выбором C/A? О: Для N реплик при W+R>N read- и write-кворумы пересекаются, что даёт строгую согласованность по чтению (склон к CP). При W+R≤N возможны stale reads, зато выше доступность и ниже задержка (склон к AP). Dynamo-style системы позволяют выбирать это на каждый запрос.

В: Что добавляет PACELC к CAP? О: PACELC описывает поведение и в нормальном режиме: «if Partition then A or C, Else then Latency or C». То есть даже без партиций есть трейдофф между низкой задержкой и сильной согласованностью. Это объясняет, почему, например, Spanner (PC/EC) платит latency за глобальную согласованность, а Cassandra (PA/EL) выбирает скорость.

В: К какому классу отнести Cassandra и почему это упрощение? О: По дефолту PA/EL (доступность и низкая задержка). Но Cassandra tunable: с CL=QUORUM/ALL она ведёт себя ближе к CP. Поэтому ярлык описывает дефолт и склонность, а не жёсткое свойство — фактическое поведение задаётся consistency level на запрос.

В: etcd — CP или AP? Что происходит с узлом в меньшинстве при партиции? О: CP. etcd использует Raft и требует кворум большинства. Узел в меньшинстве не может коммитить записи и не обслуживает линеаризуемые чтения — он вернёт ошибку/таймаут. Система жертвует доступностью этой части ради согласованности.

В: Может ли долгая GC-пауза вызвать поведение как при партиции? О: Да. Для протокола узел, замерший на STW-паузе, неотличим от пропавшего из-за обрыва сети: он перестаёт отвечать на heartbeat, его могут исключить из кворума/переизбрать лидера. Поэтому партиции — это не только физический обрыв, и таймауты надо тюнить с учётом GC.

На что копают на senior+#

• Умение развести CAP-C и ACID-C без подсказок и привести пример системы, у которой есть одно, но нет другого.
• Понимание, что P не опциональна, и способность переформулировать любой вопрос «AP или CP?» в «как система ведёт себя в момент партиции».
• Знание PACELC и умение классифицировать реальные системы по обеим осям (Spanner PC/EC, Dynamo PA/EL, MongoDB PC/EL).
• Понимание tunable consistency через кворумы (W+R>N), и того, что один кластер может работать в разных режимах per-request.
• Точное определение availability по Gilbert & Lynch и осознание, что это не про uptime/SLA.
• Знание ограничений модели: CAP — про один read/write регистр, не про мульти-объектные транзакции, durability и latency; для них нужны другие модели (linearizability vs serializability, PACELC).
• Практические следствия для архитектуры: где ставить source of truth (часто CP — etcd/ZK для конфигурации/leader election), а где терпеть eventual consistency ради доступности (корзина, лента, метрики).