Consistency patterns

The spectrum of consistency

When data is replicated across multiple physical machines or geographic regions, updates take time to propagate. A system's consistency pattern defines when a read is guaranteed to observe a previous write.

1. Strong consistency

After a write completes, every subsequent read sees it.

• Mechanism: Data is replicated synchronously, or writes go through a consensus algorithm such as Raft or Paxos, so a write is acknowledged only once enough replicas have it.
• Trade-off: Each write waits for other replicas, which adds latency, and if a partition stops the system reaching the replicas it needs, it must refuse requests rather than answer with stale data.
• Where it is used: File systems and relational databases; anything that needs transactions.

2. Eventual consistency

After a write, reads will eventually see it (typically within milliseconds). Data is replicated asynchronously.

• Stale reads: If no new updates are made, eventually all reads return the last written value. Until then, a read from a replica that has not caught up returns the old value.
• Stronger variants: Plain eventual consistency promises nothing about the order in which a client sees values. Two common additions fix that: read-your-writes (after you update a value, you never see an older one) and monotonic reads (once you have seen a value, you never see an earlier one).
• Where it is used: DNS and email; systems that put high availability first.

3. Weak consistency

After a write, reads may or may not see it: a best-effort approach, as in memcached.

• Where it is used: Real-time uses such as VoIP, video chat and multiplayer games. If a phone call drops for a few seconds, you do not hear what was said while you were disconnected.

Quorums: tuning consistency with N, W and R

Dynamo-style stores replicate each item to $N$ nodes, wait for $W$ of them to acknowledge a write, and ask $R$ of them on a read. If

then every read set overlaps every write set, so a read reaches at least one replica that has the latest acknowledged write. Werner Vogels calls this strong consistency. Daniel Abadi points out that such systems still fall short of the strict definition of consistency used in the CAP proof, even when $R + W > N$, so treat the quorum rule as "reads normally see the latest write", not as a guarantee of linearizability. Raising $W$ or $R$ buys consistency at the cost of latency.