Causal and session guarantees

Linearizability is expensive, and many features do not need it. Two weaker models cover most of what users actually notice. Causal consistency keeps related events in order. Session guarantees protect what one client sees across its own requests.

The big idea

Causal consistency says: if one operation could have influenced another, everyone sees them in that order. A reply must never show up before the post it answers.

Think of a reply in a thread. Nobody should see "So sorry!" attached to nothing. Operations that are concurrent, meaning neither could have seen the other, may appear in different orders to different readers. That is fine.

The idea breaks down for unrelated events. Two posts by strangers can appear in any order.

Walking through it

Alice posts "I lost my job". After reading the replies, she posts "Never mind, it was a prank". Bob replies "So sorry!" to the first post.

Post 1:  "I lost my job"           (Alice)
Post 2:  "Never mind, a prank"     (Alice, after reading replies)
Reply:   "So sorry!" to Post 1     (Bob, who saw Post 1)

Under causal consistency, no reader sees the reply without Post 1. Under plain eventual consistency, a reader can see the reply before the post it belongs to, or see it attached to nothing.

Causal consistency is attractive because it can stay available during a partition. It was shown to be the strongest model with that property in 2011. Tracking causality needs metadata, such as vector clocks.

Session guarantees are weaker and cover one client only. They are cheap, and they fix the most common bugs:

Together, these four approximate causal consistency for a single client.

Common mistakes

• Assuming eventual consistency keeps replies after posts. It does not. Only causal consistency promises that.
• Expecting read-your-writes for free from replicas. A read that lands on a lagging replica can miss your own write.
• Thinking session guarantees protect other users. They only cover one client's view. Two users can still see different orders.

Check yourself

1. Why can a comment appear, disappear, and reappear on refresh? That is a monotonic reads failure. Each read hits a different replica with a different lag.
2. Does causal consistency order two unrelated posts by two strangers? No. Concurrent operations may be seen in different orders.

Key takeaways

• Causal consistency keeps operations that influenced each other in the same order everywhere.
• Concurrent operations may appear in different orders, and that is allowed.
• The four session guarantees cover one client: read-your-writes, monotonic reads, monotonic writes and writes-follow-reads.
• These models are cheap enough to keep available during partitions, which linearizability cannot do.

Further learning

Next, see how these models differ from transaction isolation in isolation vs consistency.

Martin Kleppmann's companion lecture covers eventual consistency, session guarantees and the trade-off with availability.