linearizability-deep.js·3 scenarios
Linearizability deep dive — strongest single-object consistency model. Shows etcd-style 3-node Raft cluster with leader and 2 followers (one in-sync, one lagging ~80ms). Two clients: A writes, B reads. Three scenarios: (1) linearizable read via leader with quorum read-index — B sees A's write immediately; (2) non-linearizable stale read directly from lagging follower — B sees old value violating real-time order; (3) comparison of linearizable vs sequential vs causal consistency — what each model guarantees and where it breaks. Includes ADR on the cost of linearizability and when to use it (locks, leader election, unique constraints) vs skip it (feeds, analytics, counters).
Linearizability — самая строгая single-object consistency. Каждая операция выглядит мгновенной в какой-то конкретный момент между invoke и response, а real-time order между клиентами сохраняется: если op A ответила раньше, чем op B стартовала, то в любой допустимой сериализации A < B. Это поведение «выглядит как одна машина, даже под нагрузкой».
Понимание нужно для серьёзного выбора БД и для дизайна distributed coordination: distributed locks, leader election, unique constraints, exactly-once gating, финансовые state transitions. Везде, где нарушение инварианта — это наблюдаемый баг, а не «временное расхождение, которое сойдётся».
«Я расставляю все операции на одной timeline. Между моментом invoke и моментом response — операция случилась атомарно в одной точке. Если A закончилась до того, как B началась — A стоит левее B. После A.response любой клиент видит результат A.»
Это не про порядок сети, не про физическое время, не про vector clocks. Это про существование валидной последовательной истории, в которую укладываются все наблюдения и которая уважает реальное время ответов.
Соседи по шкале:
3-нодовый etcd-style кластер на Raft:
Edges не описывают направление данных — это физические соединения. Ответы по тем же edges идут reverse.
Linearizable read через leader. Client A пишет x=5, дожидается ACK от quorum (leader + follower-1). Через 200ms Client B читает с consistency=LINEARIZABLE. Leader не отвечает «из памяти» — он сначала выполняет read-index: посылает heartbeat в кворум, дожидается подтверждения leadership, и только потом возвращает значение. Это гарантирует, что B не прочитает старое значение от смещённого leader (split-brain).
Цена: дополнительный round-trip к follower на каждый read. На geo-distributed это 50–200ms. Поэтому etcd/ZooKeeper держат в одном дата-центре.
Tradeoff наоборот: B читает напрямую с follower-2 ради latency. Write A уже закоммичен и ответ ушёл клиенту (T50). В T100 B запрашивает x — но AppendEntries к follower-2 ещё в очереди. Follower возвращает старое x=0. Real-time order нарушен: A.response (T50) < B.invoke (T100), но B не видит A.
Это не обязательно баг — это сознательный выбор. Cassandra с consistency=ONE, DynamoDB eventual, Mongo с read preference secondary — все жертвуют linearizability ради latency и multi-DC доступности. Опасно становится только когда инвариант приложения требует real-time гарантию (двойная продажа билета, повторное списание).
Показывает, что именно ломается на более слабых моделях:
A видит собственный x=1), но другие клиенты могут видеть x=0 — допустимо, потому что операции не causally-related.B всегда видит то, что A уже завершил.В конце сценария — упоминание, как это проверяют: Jepsen + Knossos brute-force ищут историю операций, для которой не существует ни одной валидной linearization. Если такая история найдена — система не linearizable, точка.
Контекст. Linearizability стоит дорого:
| Цена | Что это значит на практике |
|---|---|
| 1 round-trip к quorum на каждый read/write | minimum ~RTT × 2 на single-DC, 50–200ms cross-region |
| Single point of bottleneck per object/range | весь трафик на ключ идёт через leader; шардинг помогает, но не для cross-shard ops |
| Read availability привязана к leader liveness | leader election (Raft) занимает 150–500ms; в это время reads блокируются |
| Цена fsync на write path | каждый committed write — fsync на N машин из quorum |
Большинство NoSQL намеренно жертвуют linearizability: Cassandra (ONE/QUORUM tunable), DynamoDB (по умолчанию eventually consistent), MongoDB (secondary reads), Riak — всё ради latency и multi-DC availability.
Решение. Включай linearizability только там, где нарушение даёт наблюдаемый баг:
Для feeds, аналитики, счётчиков, рекомендаций, поисковых индексов — eventual или causal достаточно, и они в 10–100× дешевле.
Тестируй. Race-conditions на dev-стенде не воспроизведёшь — там нет partition'ов и сетевых джиттеров. В проде они ломают инвариант через месяц, и debug стоит на порядок дороже. Jepsen + Knossos — индустриальный стандарт.
IF NOT EXISTS, lightweight transactions) — linearizable per partition через Paxos. Дорого: 4 round-trip'а вместо 1. Используется точечно для дедупликации и unique constraints.