CAP и PACELC: что теорема на самом деле говорит и чего не говорит

CAP — самая цитируемая и самая неправильно цитируемая теорема в нашей профессии. Её пересказывают как «выбери два из трёх», рисуют треугольник, наклеивают на базы ярлыки «CP» и «AP» — и на этом заканчивают. Почти каждое слово в этом пересказе неверно: выбирать можно не два из трёх, а один из двух; выбор делается не для системы, а для операции; и пока сеть исправна, CAP вообще ничего не запрещает — зато запрещает кое-что другое, о чём теорема молчит. Возьмём формальную постановку Gilbert и Lynch, разберём доказательство, перечислим, чего теорема не утверждает, и перейдём к PACELC — расширению Дэниела Абади, добавляющему отсутствующее в CAP измерение: латентность. Каждый тезис подпираем сценарием отказа — что ломается и какие строчки появятся в логах в три часа ночи. Предполагается, что вы прочли https://courses.digitable.life/post/distributed-systems/01-failure-models/ и https://courses.digitable.life/post/distributed-systems/02-time-and-clocks/; иерархия моделей согласованности — следом, в https://courses.digitable.life/post/distributed-systems/04-consistency-models/.

1. Три буквы и их точные определения

Половина споров про CAP умирает, если участники согласуют определения. Вот они, дословно по Gilbert–Lynch 2002.

C — atomic / linearizable consistency. Существует полный порядок всех операций такой, что каждая операция выглядит выполненной мгновенно в момент между её началом и завершением, и чтение возвращает значение последней предшествующей записи. Это линеаризуемость Херлихи и Винга (1990): для клиента система неотличима от одного экземпляра данных, обслуживающего запросы по одному.

A — availability. Каждый запрос, полученный не отказавшим узлом, обязан завершиться ответом. Не «быстро», не «в 99,9% случаев» — просто завершиться, за конечное время, с не-ошибочным результатом. Свойство тотальное: одного запроса, вернувшего 503, достаточно, чтобы A не выполнялось.

P — partition tolerance. Система работает корректно, когда сеть теряет произвольное число сообщений между группами узлов. В доказательстве это моделируется предельно: между двумя группами теряются все сообщения.

Заметьте: A — свойство каждого узла, а не системы: если из пяти узлов трое обслуживают запросы, а двое отвечают ошибкой, система в смысле CAP недоступна, хотя эксплуатационно она в полном порядке. Отсюда репутация ярлыка «CP». И помните хронологию: «теорема», которую цитируют, — это доклад 2000 года; строгую форму ей придали Гилберт и Линч в 2002-м, PACELC появился в 2012-м, а последние уточнения — только в 2017-м, вместе с разбором Spanner.

2. Доказательство на салфетке

Теорема: не существует реализации read/write-регистра в асинхронной сети, гарантирующей одновременно C, A и P.

Пусть такая система есть. Разобьём узлы на непересекающиеся группы G1 и G2, все сообщения между ними теряются (P это разрешает).

1. Клиент шлёт в G1 запись x := v2 (изначально x = v1). По A узел из G1 обязан ответить «записано»: ждать G2 он не может — сообщения не доходят, а ждать бесконечно A запрещает.
2. Клиент шлёт в G2 чтение x; по A узел обязан ответить за конечное время, но про v2 он не знает и вернёт v1. Чтение началось строго после завершения записи — линеаризуемость требует v2. Противоречие.

Модель асинхронная: глобальных часов нет, и узел не отличит «партнёр умер» от «партнёр жив, но сообщение идёт долго» — поэтому нельзя «подождать чуть-чуть и решить». Тот же корень у FLP-невозможности (Fischer, Lynch, Paterson, 1985): детерминированный консенсус недостижим уже при одном отказе. Доказательство касается одного регистра, а не базы данных. Есть и позитивная часть: в частично синхронной модели строится система, которая гарантирует C всегда, A — когда разделения нет, и никогда не возвращает некорректных данных. Это делают Paxos и Raft (https://courses.digitable.life/post/distributed-systems/07-consensus/).

3. Чего теорема не говорит: шесть заблуждений

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

Самое вредное. P — не свойство вашей системы, а свойство среды: сети рвутся, коммутаторы перегружаются, виртуалка уходит в stop-the-world GC на восемь секунд и выглядит отсутствующей. Отказаться от P — значит объявить, что разделений не бывает; тогда при разделении система просто не определена: она не «CA», она сломана. Честно так: разделение случается независимо от вас; выбор происходит внутри разделения и только между C и A. Брюер зафиксировал это сам в «CAP Twelve Years Later» (2012): «два из трёх» было упрощением для доклада, вводящим в заблуждение. Единственная честная CA-система — та, что живёт в одном процессе: SQLite, одиночный PostgreSQL, in-memory кэш.

3.2. C в CAP ≠ C в ACID

Совпадение букв историческое. C в ACID — «транзакция переводит БД из одного корректного состояния в другое, не нарушая инвариантов»: свойство приложения и схемы. C в CAP — линеаризуемость, свойство упорядочивания операций во времени. Они ортогональны: система может быть линеаризуемой и при этом позволять отрицательный баланс, если ограничение не описано. Про изоляцию — https://courses.digitable.life/post/databases/07-transactions-and-isolation/.

3.3. A в CAP ≠ доступность в SLA, а латентности в теореме нет вовсе

CAP-A булево: все запросы ко всем живым узлам; SLA — доля успешных запросов за окно. Система может быть «не-A» по CAP и иметь пять девяток, если разделения случаются раз в квартал и длятся минуту. Ровно этот аргумент Брюер приводит в «Spanner, TrueTime and the CAP Theorem» (2017): Spanner формально CP, но частота разделений в сети Google так мала, что фактическая доступность выше 99,999%. И отдельно: «за конечное время» — это хоть тридцать секунд; CAP не различает 2 мс и 2 с, а в этом промежутке живёт вся ваша эксплуатация.

3.4. Разделение — это не только «перерезали кабель»

• асимметричное: A видит B, B не видит A. Даёт вечные перевыборы: узел считает себя лидером, остальные — мёртвым;
• частичное: A↔B и B↔C работают, A↔C нет. Ломает больше протоколов, чем полный разрыв;
• stop-the-world пауза: full GC, fsync на перегруженном диске, live migration. Процесс жив, но пять секунд ничего не делает — для остальных он отсутствует. Сюда же перегрузка: задержка в секунды по таймауту неотличима от обрыва;
• разделение на уровне приложения: пул соединений исчерпан, health-check отвечает 200, бизнес-запросы висят. Самый коварный вид: инфраструктура рапортует «всё зелено».

Таксономия целиком — в https://courses.digitable.life/post/distributed-systems/01-failure-models/. Вывод: надёжно детектировать разделение нельзя, можно лишь предполагать его по таймауту — а значит, и обещание «мы просто переключимся в CP-режим» тоже вероятностное.

3.5. Ярлык на всей системе бессмысленен

Мартин Клеппман в «Please stop calling databases CP or AP» и «A Critique of the CAP Theorem» показывает: одна и та же СУБД в разных конфигурациях попадает в разные клетки. Cassandra с CL=QUORUM ведёт себя иначе, чем с CL=ONE, а её же lightweight transactions работают по Paxos и являются CP. Правильная гранулярность выбора — операция, а не продукт.

3.6. Восстановление стоит дороже самого выбора

В CP-системе восстановление — это дочитывание лога, операция механическая. В AP-системе это разрешение конфликтов, операция семантическая: кто-то должен решить, что делать с двумя версиями корзины. Эта разница стоит дороже самого выбора в момент разделения, и её почти всегда недооценивают.

4. Сценарий отказа: split-brain и как он выглядит в логах

Redis с автофейловером через Sentinel, три сентинела, кворум 2. Мастер 10.0.1.10 в стойке A, реплика 10.0.2.20 и два сентинела — в стойке B. Ломается uplink стойки A.

# sentinel в стойке B
20:14:03.180 # +odown master mymaster 10.0.1.10 6379 #quorum 2/2
20:14:03.181 # +try-failover master mymaster 10.0.1.10 6379
20:14:04.512 # +switch-master mymaster 10.0.1.10 6379 10.0.2.20 6379

# старый мастер 10.0.1.10, через 40 секунд, когда uplink починили
20:14:44.901 * Connecting to MASTER 10.0.2.20:6379
20:14:45.117 * Full resync from master: 8f2b1c...:15243
20:14:45.118 * MASTER <-> REPLICA sync: Flushing old data

Между этими двумя блоками старый мастер был жив, о фейловере не знал и продолжал принимать записи от клиентов своей стойки: репликация в Redis асинхронная, кворума старый мастер ни у кого не спрашивает. Строчка Flushing old data — надгробие всем этим записям: они подтверждены клиентам и удалены без единого сообщения об ошибке. Тихая потеря данных — худший вид: приложение считает заказы созданными, в базе их нет, метрики ошибок ровные. С точки зрения CAP система выбрала A на обеих сторонах разделения и тем самым отказалась от C.

Как ловить. Два узла с ролью master одновременно (redis_instance_info{role="master"} > 1), скачок master_repl_offset назад, Full resync вместо частичной синхронизации после сетевого события. Для Patroni — два узла в состоянии Leader в patronictl list, для MySQL — два узла с read_only=OFF. Лечится fencing’ом (STONITH, лизы — https://courses.digitable.life/post/distributed-systems/10-coordination/) либо кворумной репликацией: узел не подтверждает запись, пока её не приняло большинство. Второе — уже CP, и означает, что в меньшей секции запись не пройдёт.

5. PACELC: недостающая половина

Абади заметил простую вещь: CAP описывает поведение при разделении, а разделения редки — то есть CAP описывает 0,01% времени жизни системы. Чем же объяснить, что Dynamo, Cassandra и Riak жертвуют согласованностью постоянно? Ответ: они торгуют её не на доступность, а на латентность.

if (P) then (A or C) else (L or C)

Если есть разделение (P) — выбирай между доступностью (A) и согласованностью (C); иначе (E — else) — выбирай между латентностью (L) и согласованностью (C).

Ветка else — та, в которой вы живёте каждый день. Она не про катастрофы, а про физику: чтобы дать линеаризуемое чтение, узел обязан либо спросить большинство, либо доказать, что его знание свежее — минимум один round-trip, а в мультирегионе сотни миллисекунд.

Клетка PA/EC редка: жертвуем согласованностью при разделении, но платим за неё в норме — обычно это признак того, что дефолты складывались исторически (так было с MongoDB до 5.0, где w:majority стал значением по умолчанию и клетка сменилась на PC/EC). Клетку определяют по конфигурации: «Cassandra» в таблице выше стоит дважды и в разных углах.

6. Сценарий отказа: EL приняли за EC, или почему QUORUM — не линеаризуемость

Самая частая ошибка после «двух из трёх»: инженер видит W + R > N, ставит CL=QUORUM на чтение и запись в Cassandra и считает, что получил линеаризуемость. Не получил. W + R > N гарантирует ровно одно: множества реплик, участвующих в записи и в чтении, пересекаются, значит читатель увидит хотя бы одну реплику с последним значением. Но:

1. Конфликт разрешается по timestamp, а не по порядку операций: две конкурентные записи дают last-write-wins по времени клиента. Если часы разъехались (https://courses.digitable.life/post/distributed-systems/02-time-and-clocks/), выигрывает не последняя запись, а та, у которой часы убежали вперёд: timestamp из будущего «затеняет» все последующие, пока время его не догонит.
2. Read-modify-write не атомарен. SELECT → вычисление → UPDATE при двух конкурентных клиентах теряет одно обновление даже на QUORUM/QUORUM. Кворум даёт свежесть, но не взаимное исключение.
3. Частичная запись видна. Координатор записал на 2 из 3 реплик, вернул клиенту WriteTimeout — но данные уже видны читателям. Ошибка записи не означает её отсутствие.

-- Не атомарно: между чтением и записью вклинится другой клиент.
SELECT balance FROM accounts WHERE id = 42;          -- CL=QUORUM
UPDATE accounts SET balance = 900 WHERE id = 42;     -- CL=QUORUM, потерянное обновление

-- Атомарно: lightweight transaction, под капотом Paxos и SERIAL consistency.
-- Цена: четыре сетевых круга вместо одного, пропускная способность падает на порядок.
UPDATE accounts SET balance = 900 WHERE id = 42 IF balance = 1000;

Явные ошибки при потере кворума читаемы, а тихая деградация — нет:

WriteTimeoutException: Cassandra timeout during SIMPLE write query at consistency QUORUM
  (2 replica were required but only 1 acknowledged the write)
INFO [ScheduledTasks:1] MessagingService.java:1281 -
  MUTATION messages were dropped in last 5000 ms: 4127 internal and 0 cross node
INFO [HintsDispatcher:3] HintsDispatchExecutor.java:289 -
  Finished hinted handoff of file 5c1e...-1.hints to endpoint /10.0.2.7

MUTATION messages were dropped означает, что узел перегружен и молча выбросил записи из очереди; всплеск hinted handoff — что реплики были недоступны и данные осели у соседей. При CL=ONE ни то, ни другое не даёт ошибки клиенту, о расхождении вы узнаете лишь по метрикам read-repair. Это и есть цена клетки EL: отказ проявляется не как ошибка, а как устаревшие данные (движок подробно — https://courses.digitable.life/post/databases/12-cassandra-and-wide-column/).

7. Арифметика кворумов и её пределы

N — фактор репликации, W — сколько подтверждений нужно записи, R — сколько ответов нужно чтению. Кворум строгий, если W + R > N (множества чтения и записи пересекаются), и безопасен по записи, если 2W > N (две конкурентные записи не зафиксируются параллельно на разных наборах реплик); запись переживает N - W отказов, чтение — N - R.

Три ловушки, о которых таблица молчит.

Sloppy quorum. В Dynamo (SOSP 2007, раздел 4.6) W подтверждений собираются с любых W живых узлов, не обязательно из «домашних» реплик ключа. Это повышает доступность записи — и ломает гарантию пересечения: чтение с домашних реплик может не увидеть запись, ушедшую к чужим узлам через hinted handoff. W + R > N верно только для строгих кворумов.

Отсутствие порядка. Даже строгий кворум не упорядочивает конкурентные операции: нужен либо единственный сериализатор (лидер), либо консенсус на каждую операцию — LWT в Cassandra, linearizable в MongoDB, ReadIndex в etcd.

Вероятностная свежесть. Для нестрогих кворумов Peter Bailis и соавторы формализовали PBS — Probabilistically Bounded Staleness (VLDB 2012): вместо «нет гарантии» можно посчитать «с вероятностью 99,9% данные не старше 12 мс».

import random

def staleness_probability(n, w, r, write_ms, read_ms, delta_ms, trials=100_000):
    """Доля чтений через delta_ms после записи, которые её не увидят.
    Сложность: O(trials * n) по времени, O(n) по памяти."""
    stale = 0
    for _ in range(trials):
        applied = sorted(write_ms() for _ in range(n))              # запись доехала до каждой реплики
        ack, probed = applied[w - 1], random.sample(range(n), r)    # ack клиенту; кого опросит чтение
        stale += not any(applied[i] <= ack + delta_ms + read_ms() for i in probed)
    return stale / trials

На типичных задержках при W=1, R=1 сразу после записи устаревает больше половины чтений, а через 100 мс — доли процента. Это инженерный ответ на вопрос «насколько плох eventual consistency»: он не «плох», у него есть измеримое распределение, сопоставимое с требованием продукта (https://courses.digitable.life/post/distributed-systems/05-replication/, https://courses.digitable.life/post/distributed-systems/06-partitioning/).

8. Ветка E в проде: где именно платится латентность

Линеаризуемое чтение нельзя обслужить локально: узел не знает, не сместили ли его с лидерства секунду назад. Варианты от дорогого к дешёвому: чтение через лог (оформить чтение как запись в реплицируемый лог и дождаться коммита — стоит полного круга консенсуса, так работал ранний ZooKeeper с sync + read); ReadIndex (лидер запоминает commit index, подтверждает лидерство heartbeat’ом у большинства и обслуживает чтение локально — один round-trip; оптимизация из Raft paper, раздел 6.4, Ongaro & Ousterhout, 2014, так делает etcd); lease read (лидер держит лизу короче election timeout и, пока она жива, отвечает без сети — быстро, но корректность держится на предположении об ограниченном дрейфе часов). В etcd выбор ветки PACELC — это один флаг в запросе:

// Линеаризуемое чтение (по умолчанию): ReadIndex, лидер подтверждает лидерство
// у большинства. Стоит один RTT, при потере кворума вернёт ошибку. Ветка PC/EC.
resp, err := cli.Get(ctx, "/service/orders/leader")

// Сериализуемое чтение: локальный ответ реплики без сетевого согласования.
// Быстро, но состояние может отставать; работает даже в меньшей секции. Ветка PA/EL.
resp, err = cli.Get(ctx, "/service/orders/leader", clientv3.WithSerializable())

Разница принципиальная: сериализуемое чтение из меньшей секции вернёт устаревшую запись о лидере, и сервис попытается писать в узел, который лидером быть перестал. Гарантии описаны в etcd API guarantees, поведение под разделениями проверено Jepsen. Что видно в логах при потере кворума:

# etcd в меньшей секции
{"level":"warn","msg":"lost the TCP streaming connection with peer","remote-peer-id":"8211f1d0f64f3269"}
{"level":"warn","msg":"failed to send out heartbeat on time","heartbeat-interval":"100ms","exceeded":"1.2s"}
{"level":"info","msg":"8211f1d0f64f3269 became follower at term 42"}

# kube-apiserver, который на этот etcd опирается
E0716 20:14:07.442 storage_factory.go: etcdserver: request timed out
E0716 20:14:07.443 rpc error: code = DeadlineExceeded desc = context deadline exceeded

Это и есть выбор C: control plane Kubernetes недоступен на запись, но не расходится — два контроллера с разной картиной мира устроили бы куда более дорогой инцидент (https://courses.digitable.life/post/distributed-systems/10-coordination/). Spanner решает ту же задачу иначе: TrueTime даёт интервал неопределённости с гарантированной границей, и транзакция ждёт commit-wait длиной в этот интервал: плата за согласованность внесена явно, в миллисекундах.

9. Как выбирать: процедура вместо ярлыка

Выбор делается на операцию, и вопрос всегда один: что дороже — отдать устаревший ответ или не отдать никакого.

Деградация вместо отказа. Брюер называет это «partition mode»: заранее решено, какие операции разрешены в меньшей секции. Банкомат при обрыве связи выдаёт наличные до лимита — риск овердрафта ограничен и застрахован, а полный отказ обслуживания стоил бы дороже; лимит записан явно, а не оставлен на «авось не разделится».

Read-your-writes вместо линеаризуемости. Пользователю нужен не глобальный порядок, а собственные изменения, и это на порядок дешевле: липкая сессия к реплике или токен версии — «дай реплику с offset >= 15243» (https://courses.digitable.life/post/distributed-systems/04-consistency-models/). Выбрали AP — задокументируйте SLA на сходимость («2 секунды в 99,9% случаев»), измеряйте метрикой, покажите признак в UI: расхождение, о котором знают, — фича, о котором не знают, — инцидент.

10. Откуда растёт миф про exactly-once

У ветки A есть следствие, которое почти никогда не проговаривают: отправитель не может отличить «запрос не выполнен» от «выполнен, но подтверждение потерялось». Таймаут — не ответ, а отсутствие ответа: «не дошло», «применилось, ack потерян» и «ещё обрабатывается» неразличимы принципиально. Отсюда два честных варианта: at-most-once (потери есть, дубликатов нет) и at-least-once (потерь нет, дубликаты есть). «Exactly-once доставка» требовала бы, чтобы сеть гарантировала и сообщение, и подтверждение, то есть отрицала бы P — задача двух генералов. В логах миф выглядит так:

14:02:08.101 orders    POST /v1/charge order=8831 amount=4990 -> отправлен
14:02:11.204 orders    upstream timeout after 3000ms order=8831
14:02:11.205 orders    retry 1/3 order=8831
14:02:11.940 payments  charge accepted id=ch_7ff2 order=8831 amount=4990   <- первая попытка ДОШЛА
14:02:12.688 payments  charge accepted id=ch_a013 order=8831 amount=4990   <- дубликат

Клиента списали дважды, и ни один компонент не сделал ничего неправильного. Работающая формула — at-least-once доставка плюс идемпотентная обработка, что даёт эффект effectively-once: сообщение приходит много раз, состояние меняется один.

def handle_charge(msg, store) -> str:
    """Идемпотентный приём: ключ дедупликации приходит от ОТПРАВИТЕЛЯ.

    Сложность: O(1) по времени (одна атомарная вставка), O(k) памяти на окно
    дедупликации из k ключей. TTL берут больше горизонта ретраев отправителя.
    """
    key = msg.headers["Idempotency-Key"]              # ord-8831
    inserted, previous = store.insert_if_absent(key, ttl_seconds=86_400)
    if not inserted:
        return previous                               # тот же ответ, побочных эффектов нет
    result = apply_charge(msg.payload)                # единственный побочный эффект
    store.complete(key, result)
    return result

Три условия, без которых схема ломается: ключ генерирует отправитель (иначе повтор придёт с новым ключом); вставка ключа и применение эффекта атомарны — в одной транзакции или через outbox (https://courses.digitable.life/post/distributed-systems/08-distributed-transactions/); окно дедупликации больше горизонта ретраев.

А как же «exactly-once» в Kafka? KIP-98 даёт идемпотентный producer (брокер дедуплицирует по тройке producer id, epoch, sequence number) и транзакции, атомарно фиксирующие запись в топики вместе со смещениями потребителя. Это настоящая строгая гарантия — но внутри границы Kafka: как только обработчик вызывает HTTP наружу или пишет в стороннюю БД без общей транзакции, побочный эффект происходит вне транзакционного домена и гарантия испаряется. Честная формулировка — «атомарная обработка read-process-write внутри Kafka», а не «exactly-once доставка» (https://courses.digitable.life/post/distributed-systems/09-idempotency-and-delivery/, порядок сообщений и backpressure — https://courses.digitable.life/post/distributed-systems/11-messaging/).

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

• «У нас CA, мы же в одном дата-центре». Один ДЦ — это всё ещё сеть, коммутаторы и GC-паузы. Разделения внутри стойки происходят чаще, чем между регионами: там больше компонентов и меньше внимания.
• Автофейловер без fencing. Переключение ролей без изоляции старого лидера — машина по производству split-brain. Fencing token, лиза с истечением или отзыв доступа к хранилищу обязательны.
• Чётный кворум и одна зона отказа. N=4 переживает один отказ — как N=3, но чаще попадает в тупик 2/2; N=3 в одной AZ — это N=1 по корреляции отказов; N=3 в трёх регионах — запись за 150 мс, о которой продукт не предупредили.
• Таймаут клиента меньше таймаута консенсуса. Клиент отваливается по 1 с, кворум собирается за 1,5 с. Операции проходят, клиент видит ошибки и ретраит — лавина дубликатов на фоне «всё работает» в логах сервера.
• Ярлык вместо измерения. «Взяли AP-базу, нужна же доступность» — и никто не измерил реальное расхождение данных.

12. Как проверять свои допущения

Ни одно утверждение про CAP-позицию системы не принимайте на веру, включая утверждения вендора. Стандарт индустрии — Jepsen: фреймворк вносит реальные разделения, паузы процессов и рассинхрон часов, записывает историю операций и проверяет её на линеаризуемость. Минимальная программа для своей системы: воспроизвести разделение (iptables -A INPUT -s <peer> -j DROP, tc netem, chaos-mesh) и зафиксировать ответы клиентов в каждой секции; отдельно проверить асимметричное и частичное разделения; сымитировать GC-паузу через SIGSTOP на 30 секунд («зомби-лидер»); проверить восстановление — сошлись ли данные, за какое время, потерялось ли подтверждённое. Методология — https://courses.digitable.life/post/distributed-systems/13-testing-distributed/, наблюдаемость — https://courses.digitable.life/post/distributed-systems/12-observability/. Прикладные стили поверх этих компромиссов (микросервисы, saga, event-driven) разбираются в треке «Паттерны архитектуры».

Мини-итог

• CAP говорит: в асинхронной сети нельзя одновременно иметь линеаризуемость и тотальную доступность, если сеть теряет сообщения. Всё. Доказательство — шесть строк, и оно про один регистр, а не про продукт.
• «Два из трёх» — неверная формулировка. P не выбирают, его получают вместе с сетью; выбор возникает внутри разделения и всегда между C и A. CAP-A — не SLA, CAP-C — не ACID-C, ярлык на всём продукте бессмысленен.
• PACELC добавляет то, о чём CAP молчит: пока сеть исправна, вы платите латентностью за согласованность — и эта ветка определяет ваш опыт эксплуатации в 99,99% времени.
• W + R > N даёт пересечение множеств, но не порядок операций и не атомарность read-modify-write. Из неразличимости «не выполнено» и «выполнено, ack потерян» следует, что exactly-once доставка невозможна: работает at-least-once плюс идемпотентность, а строгая гарантия Kafka действует только внутри границы Kafka.
• Проверяйте, а не верьте: Jepsen, искусственные разделения, SIGSTOP лидеру, измерение реального окна сходимости.

Источники

• Seth Gilbert, Nancy Lynch. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News, 2002.
• Eric Brewer. Towards Robust Distributed Systems, PODC keynote, 2000; CAP Twelve Years Later, IEEE Computer, 2012; Spanner, TrueTime and the CAP Theorem, 2017.
• Daniel Abadi. Consistency Tradeoffs in Modern Distributed Database System Design. IEEE Computer, 2012.
• Fischer, Lynch, Paterson. Impossibility of Distributed Consensus with One Faulty Process. JACM, 1985.
• Leslie Lamport. Time, Clocks, and the Ordering of Events, CACM, 1978, и The Part-Time Parliament, ACM TOCS, 1998.
• Maurice Herlihy, Jeannette Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM TOPLAS, 1990.
• DeCandia et al. Dynamo: Amazon’s Highly Available Key-value Store, SOSP, 2007; Corbett et al. Spanner, OSDI, 2012.
• Diego Ongaro, John Ousterhout. Raft: In Search of an Understandable Consensus Algorithm, USENIX ATC, 2014; Peter Bailis et al. Probabilistically Bounded Staleness, VLDB, 2012.
• Martin Kleppmann. A Critique of the CAP Theorem и Please stop calling databases CP or AP, 2015; Kyle Kingsbury, Jepsen; etcd API guarantees.

Что дальше

Мы выяснили, где именно делается выбор между согласованностью и доступностью. Следующий шаг — то, что лежит между линеаризуемостью и eventual: sequential, causal, read-your-writes, monotonic reads; нужная модель почти всегда посередине, а не в крайности.

Модели согласованности: от линеаризуемости до eventual