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

Инженер приходит с багом: «пользователь нажал “Сохранить”, получил зелёную галочку, обновил страницу — старые данные». Дальше обычно начинается охота на «гонку», «кэш» или «баг в ORM». Но в большинстве случаев никакого бага нет: система вела себя ровно так, как ей разрешено. Просто никто никогда не выписал, что именно ей разрешено.

Модель согласованности — это и есть та самая выписка. Формально: контракт между хранилищем и клиентом, описывающий множество допустимых историй — последовательностей вызовов и ответов. Попала наблюдаемая история в это множество — система корректна, даже если результат выглядит дико. Не попала — это дефект. Без модели слово «дефект» не определено, и любая странность превращается в спор о вкусах.

Статья центральная в треке. В 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/03-cap-and-pacelc/ — какой выбор навязывают физика и топология. Здесь — какие именно обещания можно дать клиенту и во сколько сетевых обменов каждое обещание обходится.

1. История, спецификация, модель

Возьмём один объект — регистр с операциями write(v) и read() → v. Операция в распределённой системе не мгновенна: у неё есть момент вызова (клиент отправил запрос) и момент ответа (клиент получил результат). Между ними операция «где-то произошла», но где именно — клиент не знает и знать не может.

История — множество таких интервалов с аргументами и результатами. Последовательная спецификация — описание объекта в однопоточном мире («read возвращает значение последнего write»). Модель согласованности — правило, по которому история сопоставляется со спецификацией.

Почти все модели устроены одинаково: «найдите последовательный порядок операций, который (а) удовлетворяет спецификации объекта и (б) уважает некоторый порядок, наблюдаемый снаружи». Отличаются они только пунктом (б).

Карта с формальными определениями и стрелками «строго сильнее» — jepsen.io/consistency; обзор с полусотней моделей — Viotti & Vukolić, «Consistency in Non-Transactional Distributed Storage Systems» (arXiv:1512.00168).

Словосочетание «сильная согласованность» само по себе не значит ничего. В маркетинге оно означает то линеаризуемость, то сериализуемость, то «мы делаем кворумную запись», то «мы делаем fsync». Всегда переспрашивайте: какие операции, над каким объектом, с каким порядком, при каком числе отказов.

2. Две разные оси: согласованность и изоляция

Самая частая путаница в теме: «C» в ACID и «C» в CAP — два разных слова, случайно совпавших буквой. Изоляция (serializability и её ослабления) — про транзакции, группы операций над разными объектами; вопрос: можно ли объяснить результат каким-то последовательным выполнением транзакций? Согласованность репликации (linearizability и её ослабления) — про один объект и реальное время; вопрос: не увидел ли клиент значение старее того, что уже официально подтверждено кому-то?

Сериализуемость не запрещает выполнить вашу транзакцию «в прошлом»: read-only транзакция, вернувшая данные часовой давности, вполне сериализуема. Линеаризуемость не запрещает нарушить инвариант между двумя объектами: два линеаризуемых счётчика по отдельности не дают атомарного перевода денег. Их сумма называется strict serializability — это то, что Google называет external consistency в Spanner. Разбор изоляции — https://courses.digitable.life/post/databases/07-transactions-and-isolation/; дальше говорим про ось репликации.

Третья ось — долговечность — ортогональна обеим, и про неё регулярно забывают: линеаризуемая система, подтверждающая запись до fsync, потеряет подтверждённые данные при отключении питания в стойке. Формально контракт не нарушен: линеаризуемость ничего не обещает про выживание после краха.

3. Линеаризуемость

Определение (Herlihy & Wing, «Linearizability: A Correctness Condition for Concurrent Objects», TOPLAS 1990, PDF): история линеаризуема, если каждой операции можно назначить точку линеаризации внутри её интервала так, что порядок этих точек даёт корректную последовательную историю. Практический перевод: система ведёт себя так, будто существует одна копия данных, и каждая операция происходит атомарно в какой-то момент между запросом и ответом. Запись подтверждена — любое последующее чтение по настенным часам, любым клиентом, обязано её увидеть.

Ради двух свойств её и выбирают. Первое — локальность (композиционность): если каждый объект по отдельности линеаризуем, то система из этих объектов линеаризуема; последовательная согласованность таким свойством не обладает. Второе — на ней можно строить: распределённая блокировка, уникальность имени, «ровно один лидер», barrier, монотонный счётчик требуют именно её. Нелинеаризуемая блокировка — не блокировка.

Сценарий отказа: чтение с реплики. Классика — приложение пишет в лидера, а читает с ближайшей реплики ради латентности.

Характерный признак в логах — обе стороны считают себя правыми, ошибок со стороны хранилища нет:

14:02:11.418 api-w7  INFO  order.created id=77 lsn=0/16B3748 dur_ms=8
14:02:11.442 api-r3  WARN  order.not_found id=77 replica=eu-west-1b lag_bytes=1441792
14:02:11.443 web     ERROR GET /orders/77 -> 404 trace=6b1f... user=u-9912
14:02:12.907 api-r3  INFO  order.found id=77 replica=eu-west-1b lag_bytes=0

lag_bytes=1441792 — весь диагноз: реплика отставала на 1.4 МБ WAL. Никакого бага нет. Есть незадокументированное решение читать с асинхронной реплики, то есть выбрать модель слабее линеаризуемой, не изменив при этом контракт API.

Цена. Линеаризуемое чтение стоит как минимум один раунд подтверждения с кворумом: иначе лидер не знает, что он всё ещё лидер — его могли снять, пока он не смотрел. Это причина существования механизма ReadIndex и оптимизации lease read в Raft (Ongaro & Ousterhout, «In Search of an Understandable Consensus Algorithm», raft.github.io/raft.pdf, §8). В etcd v3 линеаризуемое чтение по умолчанию идёт через ReadIndex, а WithSerializable() этот раунд отключает (гарантии API etcd).

// Линеаризуемое чтение — по умолчанию: подтверждение лидерства через кворум.
resp, err := cli.Get(ctx, "/service/leader")

// Serializable-чтение: локально с любого узла, может быть устаревшим.
// Годится для дашбордов и не годится для решения «я ли лидер».
resp, err = cli.Get(ctx, "/service/leader", clientv3.WithSerializable())

Нижняя граница известна и теоретически: Attiya & Welch показали, что при неопределённости задержки u линеаризуемое чтение стоит порядка u/4, запись — u/2, тогда как последовательная согласованность позволяет сделать одну из двух операций локальной («Sequential Consistency versus Linearizability», ACM TOCS 1994). Отсюда правило: линеаризуемость нельзя сделать бесплатной, её можно только правильно локализовать — на маленький набор ключей, где она реально нужна.

4. Последовательная согласованность

Lamport, 1979 («How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs»): существует один общий порядок всех операций, согласованный с программным порядком каждого процесса, но не обязанный уважать реальное время. Разница тонкая и практически важная: последовательная система может отвечать «из прошлого», лишь бы делала это последовательно и не прыгала назад. Вы записали x=1 и получили ok, а коллега за соседним столом читает x=0 — это не нарушение, потому что «за соседним столом» не выражается в модели без часов.

Она не композиционна, и это ломает интуицию. Два последовательно согласованных объекта вместе могут дать историю, не объяснимую никаким общим порядком: процесс P пишет x=1 и читает y=0, процесс Q пишет y=1 и читает x=0. Каждый объект по отдельности объясним, композиция — нет. Вывод: строите координацию — вам нужна линеаризуемость.

ZooKeeper — самый честный пример в проде. Его записи линеаризуемы, а чтения — нет: клиент может быть подключён к отставшему follower и увидеть старое состояние; гарантируется лишь отсутствие отката назад и общий порядок обновлений. Поэтому в документации явно предписан вызов sync() перед чтением, если нужна свежесть (ZooKeeper Guarantees). Кто про это не знает — пишет распределённую блокировку, которая иногда выдаётся двоим; как это чинится лизами и fencing-токенами — https://courses.digitable.life/post/distributed-systems/10-coordination/.

5. Причинная согласованность

Идея: сохранять порядок только там, где он наблюдаем через причинно-следственную связь. Отношение happens-before введено Лампортом в «Time, Clocks, and the Ordering of Events in a Distributed System» (CACM 1978, PDF) и разобрано в https://courses.digitable.life/post/distributed-systems/02-time-and-clocks/. Операция A предшествует B, если они в одном процессе и A раньше; либо B прочитала записанное A; либо есть цепочка из первых двух случаев.

Модель обязана доставить p1 раньше c1 всем читателям, но про порядок c1 и p2 не говорит ничего: они конкурентны.

Сценарий отказа: комментарий раньше поста. Соцсеть, два датацентра, асинхронная репликация; пост Алисы едет по медленному каналу, комментарий Боба — по быстрому.

09:41:02.110 dc-eu  post.write     id=p1  author=alice  repl_target=dc-us
09:41:02.640 dc-eu  comment.write  id=c1  parent=p1     author=bob repl_target=dc-us
09:41:02.902 dc-us  comment.apply  id=c1  parent=p1
09:41:02.903 dc-us  ERROR render.thread parent_missing parent=p1 comment=c1
09:41:04.371 dc-us  post.apply     id=p1

Пользователь в США видит одинокий комментарий «Счастливо!» без поста, к которому тот относится. Полторы секунды инверсии — и поддержка получает тикет «у нас каша в ленте». Ни одна запись не потеряна; нарушен только порядок. Фикс — не «сделать всё синхронным», а передавать зависимости: комментарий несёт версию (вектор или скалярный clusterTime) поста, получатель откладывает применение, пока зависимость не удовлетворена. Так устроены COPS (Lloyd et al., SOSP 2011, PDF) и causal consistency в MongoDB.

// Причинно согласованная сессия: драйвер таскает operationTime/clusterTime
// между вызовами и шлёт afterClusterTime в readConcern.
const session = client.startSession({ causalConsistency: true });
await db.collection("posts").insertOne({ _id: "p1", text: "Уезжаю в отпуск" }, { session });
// Чтение с вторичной реплики не вернётся раньше, чем реплика догонит insert выше.
await db.collection("comments").find({ parent: "p1" }, { session }).toArray();

Причинность + сходимость = causal+. Чистая причинная согласованность допускает вечное расхождение конкурентных веток, поэтому практические системы дополнительно требуют детерминированного слияния (LWW-правило либо CRDT). Причинность — самая сильная модель, совместимая с полной доступностью при сетевом разделении (Mahajan, Alvisi, Dahlin, «Consistency, Availability, and Convergence», 2011), то есть верхняя граница для AP-системы из https://courses.digitable.life/post/distributed-systems/03-cap-and-pacelc/.

Цена, из-за которой её редко включают: метаданные зависимостей растут с числом реплик и длиной цепочек. Векторные часы на 200 узлов — 200 счётчиков в каждой записи; для мелких значений метаданные превышают данные. Отсюда компромиссы: сжатие векторов, серверные векторы вместо клиентских (как в Riak), одна скалярная метка на датацентр — или отказ от полной причинности в пользу гарантий сессии.

6. Гарантии сессии: минимум, который замечает пользователь

Terry et al., «Session Guarantees for Weakly Consistent Replicated Data» (PDIS 1994, PDF) — статья из проекта Bayou, описавшая четыре гарантии. Они дешевле причинной согласованности и закрывают большинство пользовательских жалоб.

Способ первый и самый честный — токен свежести: клиент получает от записи позицию в логе и предъявляет её при чтении. В PostgreSQL это LSN.

-- На первичном узле сразу после коммита: узнаём позицию записи.
SELECT pg_current_wal_lsn();               -- например, 0/16B3748

-- На реплике перед чтением: догнала ли она нашу запись?
SELECT pg_last_wal_replay_lsn() >= '0/16B3748'::pg_lsn AS fresh_enough;
-- false → идём в primary либо ждём; true → читаем с реплики спокойно

Способ второй — synchronous_commit = remote_apply на синхронной реплике: коммит не вернётся, пока реплика не применит запись, а не просто получит её. Дороже по латентности записи, зато read-your-writes работает без токенов. Способ третий — липкие сессии, маршрутизация клиента всегда на одну реплику; работает ровно до того момента, ради которого мы вообще строили распределённую систему. Сценарий отказа, на который наступают все, — липкость плюс failover:

11:07:44.002 lb   INFO  route user=u-4471 -> replica-3 (sticky cookie)
11:07:44.310 app  INFO  profile.update user=u-4471 lsn=0/9A11C40
11:09:02.771 pg   FATAL replica-3 terminating: primary promoted replica-1
11:09:02.980 lb   INFO  route user=u-4471 -> replica-2 (sticky miss, rehash)
11:09:03.004 app  WARN  profile.read user=u-4471 stale applied=0/9A0F118 want=0/9A11C40

Липкость — не гарантия, а оптимизация. Гарантия — токен, переживающий смену маршрута. Отдельно: после failover токен из старой временной линии может стать невалидным (часть WAL откатилась) — состояние Failover на диаграмме именно про это, и обрабатывать его надо явно, а не «клиент как-нибудь перезайдёт».

7. Eventual consistency: что именно обещано

Формулировка: если записи прекратятся, все реплики в конце концов сойдутся к одному значению. Всё. Здесь нет обещания когда («в конце концов» не имеет верхней границы: хинт, застрявший на упавшем узле, применится через сутки); нет обещания, какое значение победит (это отдельное правило разрешения конфликтов, не часть модели); нет обещания монотонности (без гарантий сессии значение мигает между старым и новым); нет обещания, что записи не потеряются (LWW честно выбрасывает проигравшую).

Родоначальник практического подхода — Dynamo (DeCandia et al., SOSP 2007, PDF): sloppy quorum, hinted handoff, anti-entropy на деревьях Меркла, векторные часы и разрешение конфликтов на стороне приложения. Деталь, сделанная в Dynamo осознанно, а в клонах регулярно теряемая: система возвращала клиенту несколько конкурентных версий (siblings) и требовала слить их прикладной логикой. Корзина покупок сливается объединением; баланс — нет.

Сценарий отказа: LWW плюс расхождение часов. Cassandra по умолчанию разрешает конфликты по timestamp ячейки — last write wins. Разъехались клиентские или узловые часы — побеждает не последняя запись, а запись с самыми «убежавшими вперёд» часами.

# Узел A, часы убежали на +9 с
15:22:03.100 A  MUTATION key=user:41 col=email val=old@example.com ts=1721654532100000
# Узел B, часы верные — реальная, более поздняя запись
15:22:05.400 B  MUTATION key=user:41 col=email val=new@example.com ts=1721654525400000
# Через 40 минут — read repair
16:02:11.980 B  READ_REPAIR key=user:41 col=email winner_ts=1721654532100000
16:02:11.981 B  INFO   key=user:41 col=email val=old@example.com

Пользователь поменял email и ушёл — а через сорок минут anti-entropy тихо вернул старый. В логах приложения нет ни одной ошибки: обе записи успешны, обе подтверждены, ни одного исключения. Худший класс инцидентов — молчаливая потеря данных, обнаруживаемая только жалобой. Смягчения: NTP с жёстким мониторингом (https://courses.digitable.life/post/distributed-systems/02-time-and-clocks/), серверные timestamp вместо клиентских, лёгкие транзакции на Paxos, а лучше — не хранить в LWW-модели данные, потеря которых неприемлема. Разбор движка — https://courses.digitable.life/post/databases/12-cassandra-and-wide-column/.

Сценарий отказа: «запись есть, записи нет». Ловушка, которую часто считают невозможной из-за арифметики R + W > N.

Пересечение кворумов гарантирует, что читатель встретит реплику со свежим значением. Оно не гарантирует, что частичная, оборванная таймаутом запись либо целиком применится, либо целиком исчезнет. Клиент получил таймаут, считает запись неудавшейся, а система показывает её то одному читателю, то другому. Формально: кворумная запись без консенсуса даёт eventual consistency, а не линеаризуемость. Поэтому в Cassandra для настоящей атомарности нужны LWT:

-- QUORUM: быстро, но линеаризуемости нет — оборванная запись даст «мигание».
UPDATE accounts SET balance = 900 WHERE id = 42;

-- LWT: раунд Paxos, консистентность SERIAL, ~4 сетевых обхода вместо одного.
-- Возвращает applied=false, если условие не выполнилось.
UPDATE accounts SET balance = 900 WHERE id = 42 IF balance = 1000;

Конфликты, CRDT и способы жить с расхождением без потери данных — https://courses.digitable.life/post/distributed-systems/05-replication/. Здесь важно зафиксировать: eventual consistency — не «чуть похуже», а качественно другой контракт, требующий других прикладных механизмов.

8. Как проверить, что модель соблюдается

Тестирование «глазами» тут не работает: аномалия проявляется раз в тысячу прогонов и только под разделением. Стандартный подход — записать историю (вызов/ответ с временными метками) и прогнать чекер по алгоритму Wing & Gong: перебирать допустимые «следующие» операции, отсекая нарушающие порядок реального времени или спецификацию.

from dataclasses import dataclass
from typing import Any, FrozenSet, Optional

@dataclass(frozen=True)
class Op:
    """Операция над регистром: интервал [start, end] в реальном времени."""
    pid: str      # кто вызвал
    kind: str     # 'w' — запись, 'r' — чтение
    value: Any    # что записали или что вернулось
    start: int
    end: int

def is_linearizable(ops, init: Any = 0) -> Optional[list]:
    """Ищет порядок линеаризации; возвращает список операций либо None."""
    memo: set = set()                             # (оставшиеся, состояние) → тупик

    def rec(remaining: FrozenSet[Op], state: Any, order: list):
        if not remaining:
            return list(order)
        if (remaining, state) in memo:            # подслучай уже признан безнадёжным
            return None
        # Самый ранний ответ: всё, что вызвано позже него, обязано идти после.
        earliest_end = min(o.end for o in remaining)
        for cand in remaining:
            if earliest_end < cand.start:
                continue                          # нарушили бы порядок реального времени
            if cand.kind == 'r' and cand.value != state:
                continue                          # чтение не сходится с состоянием
            next_state = cand.value if cand.kind == 'w' else state
            order.append(cand)
            found = rec(remaining - {cand}, next_state, order)
            if found is not None:
                return found
            order.pop()
        memo.add((remaining, state))
        return None

    return rec(frozenset(ops), init, [])

# История из схемы выше: запись конкурентна обоим чтениям — порядок находится.
good = [Op('A', 'w', 1, 10, 60), Op('B', 'r', 1, 30, 82), Op('C', 'r', 0, 14, 46)]
print([(o.pid, o.kind, o.value) for o in is_linearizable(good)])
# [('C', 'r', 0), ('A', 'w', 1), ('B', 'r', 1)]

# Чтение стартовало после ответа на запись, но вернуло старое значение.
print(is_linearizable([Op('A', 'w', 1, 10, 60), Op('B', 'r', 0, 70, 90)]))  # None

Сложность. Без мемоизации — O(n!) по времени. С мемоизацией по паре «множество оставшихся + состояние» — O(2^n · n) по времени и O(2^n) по памяти. Экспонента не случайна: проверка линеаризуемости NP-полна в общем случае (Gibbons & Korach, «Testing Shared Memories», SIAM J. Comput. 1997). На практике истории режут на независимые куски по ключам и проверяют окнами по 100–1000 операций.

Готовые инструменты: Jepsen (jepsen.io) — фреймворк Кайла Кингсбери, генерирующий нагрузку, вносящий разделения, собирающий историю и проверяющий её чекером (отчёты по конкретным БД — обязательное чтение перед выбором хранилища); Knossos и Porcupine (github.com/anishathalye/porcupine) — чекеры линеаризуемости; Elle (Kingsbury & Alvaro, VLDB 2020, arXiv:2003.10554) — чекер изоляции, выводящий аномалии из графа зависимостей за полиномиальное время. Методика — https://courses.digitable.life/post/distributed-systems/13-testing-distributed/.

9. Что реально дают промышленные системы

Spanner покупает external consistency за счёт TrueTime: атомные часы и GPS дают интервал неопределённости ε, и коммит ждёт 2ε (порядка 5–10 мс), чтобы метка гарантированно оказалась в прошлом относительно любого последующего наблюдателя (Corbett et al., OSDI 2012, PDF). Буквально «строгая согласованность, купленная за железо и за ожидание».

Kafka даёт порядок только внутри партиции. Как только вы шардируете по ключу — а вы шардируете, см. https://courses.digitable.life/post/distributed-systems/06-partitioning/ — глобального порядка сообщений нет и не будет. Все «нарушения порядка» в Kafka-пайплайнах при разборе оказываются либо разными партициями, либо max.in.flight.requests.per.connection > 1 без идемпотентного продюсера, либо ребалансировкой потребителей. DynamoDB по умолчанию читает eventually consistent — самый частый источник «магических» багов у команд из мира РСУБД; флаг ConsistentRead=true стоит вдвое дороже по RCU и через глобальные вторичные индексы не работает вообще.

10. Почему exactly-once — миф

Это не философия, а следствие из двух результатов. Задача двух генералов: если канал может терять сообщения, никакое конечное число раундов не даёт обеим сторонам общего знания о доставке. Отправитель, не получивший подтверждения, физически не может отличить три ситуации — запрос не дошёл; запрос дошёл и обработан, а подтверждение потеряно; запрос обработан частично. Вариантов действия ровно два: повторить (риск дубля) или не повторять (риск потери). FLP (Fischer, Lynch, Paterson, JACM 1985, PDF): в асинхронной системе с одним отказом нет детерминированного консенсуса за конечное время, а значит, нет и протокола доставки, всегда завершающегося ровно раз.

В логах дубликат выглядит так — и обратите внимание, что ошибок здесь снова нет:

12:31:04.882 producer WARN  timeout waiting ack topic=payments key=r-88 attempt=1
12:31:05.401 producer INFO  sent topic=payments key=r-88 attempt=2 offset=104013
12:31:11.204 consumer INFO  handle key=r-88 offset=104012 -> charge_id=ch_7f21
12:31:11.209 consumer FATAL process exited, offset not committed
12:31:19.660 consumer INFO  handle key=r-88 offset=104012 -> charge_id=ch_7f21 (dedup hit)
12:31:19.884 consumer INFO  handle key=r-88 offset=104013 -> charge_id=ch_7f21 (dedup hit)

Строка dedup hit — единственное, что отделяет систему от тройного списания.

Что делают вместо. At-least-once доставка + идемпотентная обработка = effectively-once эффект. Это стандартный ответ индустрии, и он не эквивалентен exactly-once доставке: дубликаты по сети всё равно летают, просто они не производят второго эффекта. Компоненты рецепта: (1) ключ идемпотентности, сгенерированный на стороне отправителя и стабильный между ретраями (r-88 выше), а не uuid4() внутри обработчика — он новый на каждой попытке; (2) дедупликация с атомарной фиксацией эффекта — ключ и результат пишутся в одной транзакции с бизнес-эффектом, минимальная рабочая форма INSERT ... ON CONFLICT DO NOTHING по уникальному ключу; (3) хранение результата, а не только флага: повтор должен вернуть тот же ответ; (4) окно дедупликации с явным TTL и решением, что делать после его истечения; (5) мониторинг доли повторов — внезапный рост означает деградацию сети или зацикленные ретраи.

Kafka действительно предлагает «exactly-once semantics», и важно понимать границу зоны действия (KIP-98, описание).

# Продюсер: идемпотентность = дедупликация брокером по (PID, epoch, sequence).
enable.idempotence: true          # снимает дубли ТОЛЬКО от ретраев этого продюсера
acks: all
max.in.flight.requests.per.connection: 5   # порядок сохраняется при enable.idempotence
transactional.id: order-processor-1        # атомарность «прочитал → обработал → записал»

# Консьюмер: не видит записи незавершённых транзакций.
isolation.level: read_committed

Что это даёт: атомарность связки «сдвиг оффсета + запись результата» внутри одного кластера Kafka. Что не даёт: как только обработчик дёргает внешний HTTP API, шлёт письмо или пишет в стороннюю БД, транзакция Kafka этот эффект не откатит. Граница атомарности проходит по границе кластера — и ровно там снова нужна прикладная идемпотентность. Отдельно: transactional.id должен быть стабильным между перезапусками инстанса, иначе zombie fencing не работает и «зависший» старый обработчик продолжит писать; классический баг — генерировать его из hostname пода. Полный разбор с кодом — https://courses.digitable.life/post/distributed-systems/09-idempotency-and-delivery/, паттерн outbox — https://courses.digitable.life/post/distributed-systems/08-distributed-transactions/.

11. Как выбирать модель

Правило одно: берите самую слабую модель, при которой ваш инвариант остаётся верным. Не «самую сильную, которую тянет бюджет» — сильные модели платят латентностью и доступностью при каждом разделении.

Ветка «проверяется локально» опирается на I-confluence (Bailis et al., «Coordination Avoidance in Database Systems», VLDB 2015, PDF): если инвариант сохраняется при слиянии любых двух допустимых состояний, координация не нужна вообще. I-confluent: «множество только растёт», «счётчик только увеличивается», «ключ уникален при генерации UUID». Не I-confluent: «баланс ≥ 0», «email уникален среди всех пользователей», «мест продано не больше вместимости». Практический приём — разделять данные по требуемой модели, а не грести всё под одну гребёнку:

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

Мини-итог

• Модель согласованности — контракт о допустимых историях, а не свойство «хорошести» системы.
• Модели различаются одним: какой внешний порядок обязаны сохранить. Линеаризуемость — реальное время, последовательная — программный порядок процессов, причинная — happens-before, сессионные — взгляд одного клиента, eventual — ничего.
• Линеаризуемость композиционна и потому нужна для координации; последовательная — нет.
• Причинность — потолок для AP-систем: сильнее неё при разделении быть доступным нельзя.
• Гарантии сессии закрывают большую часть жалоб дешевле полной причинности и реализуются токенами свежести, а не липкостью.
• Eventual consistency требует прикладных механизмов — разрешения конфликтов, идемпотентности, компенсаций.
• Exactly-once доставки не существует; есть at-least-once плюс идемпотентная обработка, дающая effectively-once эффект в границах одного транзакционного домена.
• Каждый выбор проверяйте сценарием отказа: что именно увидит клиент и что появится в логах, когда упадёт вот этот узел.

Источники

• Herlihy, Wing. Linearizability: A Correctness Condition for Concurrent Objects, TOPLAS 1990.
• Lamport. Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978.
• Terry et al. Session Guarantees for Weakly Consistent Replicated Data, PDIS 1994.
• DeCandia et al. Dynamo: Amazon’s Highly Available Key-value Store, SOSP 2007.
• Lloyd et al. Don’t Settle for Eventual: COPS, SOSP 2011.
• Corbett et al. Spanner: Google’s Globally-Distributed Database, OSDI 2012.
• Ongaro, Ousterhout. In Search of an Understandable Consensus Algorithm, USENIX ATC 2014.
• Bailis et al. Coordination Avoidance in Database Systems, VLDB 2015 и Highly Available Transactions, VLDB 2014.
• Fischer, Lynch, Paterson. Impossibility of Distributed Consensus with One Faulty Process, JACM 1985.
• Viotti, Vukolić. Consistency in Non-Transactional Distributed Storage Systems, 2016.
• Kingsbury, Alvaro. Elle: Inferring Isolation Anomalies from Experimental Observations, VLDB 2020.
• Kleppmann. Designing Data-Intensive Applications, гл. 5 и 9. O’Reilly, 2017.
• Jepsen: Consistency Models, etcd API Guarantees, ZooKeeper Guarantees.

Что дальше

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

Репликация: лидер и последователи, кворумы, конфликты, CRDT