Every copy of the data is a moment behind the original. Which reads may see an older copy, and which must not, is a choice you make for each kind of data, and each choice has a price.
Copies everywhere
By now Inkwell keeps copies of its data in many places: read replicas behind the database, copies of every partition in the key-value store, caches, and CDN edges. Each copy is updated a little after the write that changed it.
The leader has the write first; the copies catch up.
A consistency model is the promise a store makes about what a read can return while copies catch up. The stronger the promise, the more work the store does for every read, and the more often it has to say "not now" when machines are unreachable.
Strong and eventual reads
- An eventual read is answered by any copy. If nobody writes for a while, every copy ends up the same, but right after a write a read can return the old value.
- A strong read always returns the latest acknowledged write. The store has to ask the leader, and the leader has to be sure it still leads, so it costs more, and followers no longer share the read load. The formal name for this promise is linearizable: the store behaves as if there were only one copy. It is what the C in CAP, below, means.
| Eventual | Strong | |
|---|---|---|
| Answered by | any copy | the leader |
| Can return | a slightly old value | the latest write |
| Read capacity used in DynamoDB | half a unit per 4 KB | a full unit per 4 KB |
| Speed | fastest | a little slower |
Guarantees for one user
Most users never notice that other people's writes take a moment to arrive. What they notice is their own writes going missing, or the page jumping backwards. Weaker promises, aimed at one user's experience, cover those cases cheaply:
| Guarantee | Promise | Broken when |
|---|---|---|
| Read your writes | you see your own changes | your refresh lands on a lagging copy |
| Monotonic reads | you never see time go backwards | two refreshes hit copies with different lag |
| Consistent prefix | you see changes in the order they happened | a reply shows up before the comment it answers |
Read your writes is the one you met with replicas: send a user's reads of what they just changed to the up-to-date copy. Monotonic reads usually come from pinning each user to one copy.
Cause before effect
Between eventual and strong sits a promise that matches what people notice: causal consistency. If one change could have caused another, everyone sees them in that order; changes with no link between them can show up in any order. Ana removes her manager from her followers, then posts about job hunting: under causal consistency no copy shows the post to the manager, because the post came after the removal. A store gets it by recording what each write depended on (the versions its writer had seen) and holding a write back on a copy until those have arrived. No read has to go to a leader, so it is cheaper than strong reads and works across regions; COPS, the research store that made this practical, works this way. MongoDB's causally consistent sessions give a narrower version: within one session, a read waits until the copy has caught up with what that session already saw, which covers one user's own actions but not the order between two users'.
Two words that sound alike promise different things:
| Linearizable | Serializable | |
|---|---|---|
| About | each read and write of one key | transactions over many rows |
| Promise | every read sees the latest write, as if there were one copy | the result is as if the transactions ran one at a time, in some order |
| Leaves out | anything about groups of operations | that the order matches real time |
A store can offer either without the other. Strict serializable, which Spanner offers, is both.
Choosing per read
Strong or eventual isn't one switch for the whole system. Most reads can be eventual; only a few need the latest value. Two rules are common. Route a user's reads to the leader for a moment after that user writes (read your own writes). Or route reads of a key that was just written to its leader for a moment, whoever reads it; that is what Retrystorm's key-value store does with strong_after_write. Either way a writer refreshing their own post gets the new version while most reads stay cheap.
| Data | Usually |
|---|---|
| A bank balance before a withdrawal | strong |
| A post the writer just published, for that writer | read your writes |
| Like counts, view counts, the feed | eventual |
| A username that must stay unique | strong (on the write) |
The question for every read is: what goes wrong if this answer is a second old?
Quorums
Many stores keep N copies of every key and let you choose how many copies a write waits for (W) and how many a read asks (R). Waiting for more copies is slower; asking fewer is faster but may miss the latest write. When R + W > N, the copies a read asks overlap the ones the last write reached, and the Quorums chapter, later in this track, shows what that overlap guarantees and where it breaks down.
CAP and PACELC
When the network splits machines into groups that can't reach each other (a partition, in the network sense), a store has two options for the side that can't reach the latest data: refuse requests (stay consistent) or answer with what it has (stay available). That's the CAP theorem: during a network partition, pick C or A.
Most of the time the network is fine, and PACELC names the everyday trade: Else, Latency or Consistency. Waiting for more copies is slower; answering from the nearest is faster and maybe behind.
| Store | During a network partition | Normally |
|---|---|---|
| A single relational primary | consistent: writes stop if it's unreachable | consistent |
| Cassandra (no leader, tunable) | available by default | low latency, eventual by default |
| DynamoDB (a leader per partition) | eventual reads go on; writes and strong reads need the leader | eventual reads by default, strong ones on request |
| Spanner, etcd | consistent | consistent, slower writes |
In an interview, say which data needs which promise, and why, rather than picking one for the whole system.
In the wild
The ideas in this chapter, and where you'll meet them in real systems and interviews:
| Idea | Where you'll meet it |
|---|---|
| Per-read consistency | DynamoDB's ConsistentRead, Cassandra's levels (ONE, QUORUM, ALL), MongoDB's read concern |
| Strongly consistent stores | Google Spanner, etcd, and ZooKeeper for writes (its reads can lag unless the client calls sync first) |
| Causal consistency | COPS, the research store that made it practical; MongoDB's causally consistent sessions, for one session's own reads and writes |
| Testing the promises | the Jepsen reports on how real databases behave under network partitions |
Your practice
Inkwell's posts live in a key-value store, and writers who publish a post and refresh sometimes don't see it. Make sure writers always see their own posts, without paying for strong reads that nobody needs.