CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 6 of 7 · 3 min read

The weaker models

Sequential, causal and eventual consistency.

The weaker models

Think of a group chat that shows messages late on some phones. You might accept delay as long as replies never appear before the question. That is a weaker promise than "everyone sees it at once", and it is cheaper.

Sequential consistency. The UDS book describes how reads can be sent to followers, to avoid a bottleneck at the leader. A follower may lag, but it receives updates in the same order as the leader. The model in which all observers see operations in the same order, but with no promise about how soon, is sequential consistency. Its lack of real-time guarantees is what separates it from linearizability. A producer and consumer on a queue are an example: both see the items in the same order, but the consumer lags.

Causal consistency. In the DDIA book, if one operation happened before another (a question and its answer), every replica must process them in that order. Concurrent operations may be processed in any order. This is a partial order. The book notes that linearizability implies causality, but causal consistency is cheaper: it is the strongest model that does not slow down because of network delays, and stays available during network failures, so the CAP theorem does not apply to it. Many systems that seem to need linearizability only need causal consistency. To track causality, version vectors can be generalised across the database (Level 4). In practice, tracking every dependency is costly, so systems often use sequence numbers: a leader's log gives a total order consistent with causality.

Eventual consistency. A client might read from any follower, for availability. Followers may be at different points, so one read can show newer state than the next. The only guarantee is that if writes stop, all followers eventually converge. The UDS book warns that it is hard to build on, because behaviour is unlike single-threaded programs and subtle bugs are hard to reproduce. It fits a visit counter, but not a payment system.

The session guarantees of Level 4 (read your writes, monotonic reads) are small additions on top of eventual consistency.

A worked example, a message board with three replicas.

Model What Bob may see after Alice posts a question and Carol answers
Linearizable Everything Alice and Carol posted, as soon as each post finished
Sequential The same order as everyone else, maybe a few seconds late
Causal Never the answer without the question; unrelated posts in any order
Eventual Possibly the answer first, then the question, then both after some time

Interview angle

Answer in your head first, then open it.

What is linearizability?

Behaves like one copy; once a new value is read, no later read returns the old one. Give the score example.

Linearizable versus serializable?

Recency of a single object versus isolation of multi-object transactions.

Do quorum reads give strong consistency?

Not necessarily. Give the n = 3, w = 3, r = 2 trap.

Which model do you pick for a social feed? For a bank balance?

Eventual or causal for the feed. Linearizable for the balance.

What does strong consistency cost?

Latency and availability under network faults.

Check yourself:

  • What does sequential consistency guarantee that eventual consistency does not?
  • Why is causal consistency attractive?

Words you will meet

Word Plain meaning
Consistency model A promise about what readers may see
Linearizability (strong consistency) One-copy behaviour with recency
Recency guarantee Once a new value is seen, old ones are not
Register A single object that can be read and written
Serializability Transactions behave as in some serial order
Strict serializability Serializable and linearizable together
Split brain Two nodes both believing they are the leader
Sequential consistency Same order for all observers, no timing promise
Causal consistency Cause is seen before effect
Eventual consistency Copies converge if writes stop
Read repair Fixing stale copies when a read finds them
Total order Every pair of operations can be ranked
Partial order Only related operations are ranked