CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 5 of 7 · 2 min read

Consistent prefix reads

Preventing an effect from being seen before its cause.

Think of watching a play where the scenes are shown out of order. The audience hears a character say "Yes, ten seconds usually" and only afterwards hears the question "How far into the future can you see?". The answer comes before the question.

The book tells the story of Mr. Poons and Mrs. Cake. One asks how far the other can see into the future, and she answers about ten seconds. A third person listens through followers. Mrs. Cake's words pass through a follower with little lag, and Mr. Poons's through a follower with more lag. The listener hears the answer first, as if she knew the question before it was asked.

Consistent prefix reads

Consistent prefix reads is the guarantee that if a series of writes happens in a certain order, then anyone reading them sees them appear in the same order.

Example: a question posted at 10:00:00 and its answer at 10:00:05 are always seen in that order, never the answer alone.

This is a particular problem in partitioned (sharded) databases (module 4). If the database applies all writes in a single order, reads always see a consistent prefix. But in many distributed databases, partitions work independently, so there is no global order. A reader may see one partition in a newer state and another in an older state.

The book offers two answers:

  • Write causally related items to the same partition. Often this cannot be done efficiently.
  • Use algorithms that explicitly track causal dependencies [what depends on what; covered in a later level].

A worked example. A chat database is split into two partitions by user. Alice's messages are in partition A, Bob's replies in partition B.

  1. Alice writes "Shall we meet at six?" (partition A, lag 2 seconds).
  2. Bob replies "Yes, six is fine." (partition B, lag 0.2 seconds).
  3. Carol reads from followers. At second 0.5 she sees Bob's reply but not Alice's question.

If the chat were stored by conversation (all messages of one conversation in one partition), both messages would be in order. The choice of the partition key (module 8) can prevent the anomaly.

Check yourself:

  • Why can a single-partition database avoid this anomaly more easily?
  • Name one way to prevent it in a partitioned database.