Consistency Models and Quorums - Systems - Jordi Villar
Consistency Lab
System design prep · ClickHouse Core Engineer

Consistency Models & Quorums Lab

What each guarantee promises, which histories it allows, why R + W > N is weaker than it sounds, and what a ClickHouse SELECT actually sees. Everything below is interactive: click the map, break the cluster, build your own history.

Linearizable⊃Sequential⊃Causal⊃PRAM⊃{RYW, MR, MW}· · ·Eventual (liveness)
One-liner: linearizable = one copy, real time. Sequential = one order, any time. Causal = cause before effect.
Quorums: overlap ≠ linearizability.
A · Models

Six guarantees, from strongest to weakest

The chip says what the model costs under a network partition, using Jepsen's availability classes. Sticky available means a client stays available only if it keeps talking to the same replica.

A · Map

Hierarchy of models

After Jepsen's map. An arrow from A to B means every A history is also a B history. Click a model to highlight everything it implies.

Unavailable under partition Sticky available Totally available
B · Client histories

Which models does a history satisfy?

One register x, initial value 0, unique write values. Bars span invocation to completion; time runs right. Verdicts are computed live by the checker below, so you can load any of these and edit it.

C · Quorum simulator

When does R + W > N save you?

A Dynamo-style key with N home replicas. Writes carry a client timestamp; replicas keep the highest (last-write-wins). Click a replica to kill it, turn on the partition to split the cluster, and switch to a sloppy quorum to see hint nodes take over. Each read is judged against the most recent acknowledged write.

Scenario

Quorum type
Write delivery
replicas the last write reached replicas the last read contacted "latest" = holds the newest acked write
C · History checker

Build a history, get a verdict

Brute-force search over orderings, the same idea as Knossos at toy scale. Linearizable needs one order that respects real time. Sequential needs one order that respects each process's program order. Causal lets each process have its own order, as long as it respects happens-before. Times are integer ticks; an op precedes another in real time when it ends strictly before the other starts.

D · The ClickHouse angle

What consistency does a SELECT actually get?

Short version: replication of data is asynchronous, coordination goes through Keeper, and stronger guarantees are opt-in per insert and per query. Each SELECT reads an immutable snapshot of the parts that were active when it started.

ReplicatedMergeTree

self-managed
client Replica 1writes part all_7_7_0 Keeper (Raft)/log /blocks /quorum Replica 2replication queue 1 2 log entry 3 sees entry 4 fetch part 5 quorum mark ack after 2 (quorum=0)ack after 5 (quorum=k)
  • Insert writes a part locally, then commits block number, dedup hash and a log entry to Keeper. Other replicas fetch the part over interserver HTTP, asynchronously.
  • insert_quorum (default 0; 'auto' = majority) holds the ack until k replicas have the part, within insert_quorum_timeout (default 10 min). On timeout, retry the same block.
  • insert_quorum_parallel (default 1, since 21.1) allows several quorum inserts in flight. Set it to 0 to linearize quorum inserts per table; a second insert is rejected while one is pending.
  • select_sequential_consistency = 1: the replica must have every quorum-written part, or the SELECT throws instead of returning stale data.

SharedMergeTree

ClickHouse Cloud
client Compute Astateless replica Keeperpart metadata Object storageS3 / GCS / Blob Compute Bpulls metadata 1 upload part 2 commit → ack 3 async pull 4 read part on demand
  • Data lives in shared object storage; replicas never fetch parts from each other. The ack comes after the part is uploaded and its metadata is committed to a Keeper quorum, so every insert is effectively a quorum insert.
  • insert_quorum and insert_quorum_parallel do not apply.
  • Other replicas learn about new parts by pulling metadata from Keeper asynchronously, usually within milliseconds.
  • Fresh reads, in order of preference: same session or node; SYSTEM SYNC REPLICA t LIGHTWEIGHT after writing; select_sequential_consistency = 1 as a last resort (extra Keeper load per SELECT).

SELECT consistency explorer

Pick the engine, how the insert was made and how the read is routed.

Engine
Read routing

True regardless of settings

  • Part-level atomicity. An inserted block becomes one part per partition and appears all at once. A big insert split into several blocks or partitions is not atomic as a whole. There are no general multi-statement transactions (only experimental support).
  • Snapshot per SELECT. The set of active parts is fixed at query start, so merges finishing mid-query don't change the result. It is per table and per replica, not a cross-table or cross-shard snapshot.
  • Distributed tables pick one replica per shard per query (load_balancing, default random). max_replica_delay_for_distributed_queries skips lagging replicas, but fallback_to_stale_replicas_for_distributed_queries = 1 still uses them if all lag. Different shards can be at different freshness.
  • Idempotent retries. Replicated tables deduplicate inserted blocks by hash stored in Keeper (insert_deduplicate, insert_deduplication_token), so retrying the same block after a timeout does not double-count.
  • Keeper down ⇒ writes stop, reads continue. Replicated tables go read-only without Keeper, while SELECTs keep serving local parts. Inserts are CP; reads are AP and possibly stale.
  • Other eventual surfaces: ReplacingMergeTree dedup happens at merge time (use FINAL), mutations are async (mutations_sync), ALTERs need alter_sync, and async_insert with wait_for_async_insert = 0 acks before data is durable.
E · Likely interviewer follow-ups

Ten questions, short model answers

Answer in this shape: the guarantee, the mechanism, the cost, then the ClickHouse knob.

F · Further reading

Further reading

  • Jepsen — Consistency Models (the map)jepsen.io/consistency ↗ Clickable hierarchy with one page per model and its availability class. Read linearizable, sequential, causal, and the session guarantees.
  • DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007PDF ↗ Sections 4.5–4.7: preference lists, sloppy quorums, hinted handoff, Merkle-tree anti-entropy, vector clocks for siblings.
  • Kleppmann, Designing Data-Intensive Applications — ch. 5 Replication, ch. 9 Consistency and Consensusdataintensive.net ↗ Ch. 5: replication lag, read-your-writes, monotonic reads, leaderless quorums and their limits. Ch. 9: linearizability, ordering, total order broadcast, consensus. Chapter numbers are from the 1st edition.
  • ClickHouse docs — insert_quorum (and insert_quorum_parallel, insert_quorum_timeout)clickhouse.com ↗ Semantics, defaults, the 'auto' majority value, and the retry-same-block rule on timeout.
  • ClickHouse docs — select_sequential_consistencyclickhouse.com ↗ Behavior for ReplicatedMergeTree vs SharedMergeTree. Pair with the knowledge-base note on read consistency.
  • Extra: SharedMergeTree and read consistency in ClickHouse CloudSharedMergeTree ↗ Why insert_quorum is unnecessary there, and when to use SYSTEM SYNC REPLICA … LIGHTWEIGHT. See also the read-consistency KB article.