These are the notes for System Design episode 15. Last episode, "consistent" sounded like a yes or no. It isn't: there's a ladder of consistency models, and each step fixes a bug real users notice. You'll measure eventual consistency and its inconsistency window, stop your own post from vanishing (read-your-writes), stop the page going back in time (monotonic reads), keep replies after their questions (causal consistency), get the latest value for money (strong consistency, with quorums: W + R > N), and see how DynamoDB lets you choose per read. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). The lags in the demos are made-up numbers.
The six problems
| Problem | What it teaches |
|---|---|
| Copies disagree for a moment | Eventual consistency, the inconsistency window |
| My own post vanished | Read-your-writes, session consistency |
| The page went back in time | Monotonic reads |
| A reply before its question | Causal consistency |
| Money needs the latest | Strong consistency (linearizable), quorums W + R > N |
| Choose per request | The ladder; DynamoDB's ConsistentRead |
A consistency model is a promise a storage system makes about what reads can return after writes. Weaker promises are cheaper and faster; stronger ones cost more.
Problem 1: copies disagree for a moment (eventual consistency)
From episode 11, reads go to replicas (copies), and replicas lag a little behind the primary (the copy that takes writes).
| Watching cricket | Reading from replicas |
|---|---|
| Same match on three channels, each with its own delay | Replicas with lag: each copy is a little behind |
| A six! Channel 1 shows it first, the others seconds later | Inconsistency window: the time until every copy has it |
| After the over, all show the same score | Eventual consistency: no new writes → all agree |
Werner Vogels (Amazon's CTO) defines these in "Eventually Consistent" (ACM Queue, October 2008):
- Inconsistency window: "The period between the update and the moment when it is guaranteed that any observer will always see the updated value".
- Eventual consistency: "if no new updates are made to the object, eventually all accesses will return the last updated value."
- Weak consistency: "The system does not guarantee that subsequent accesses will return the updated value."
Demo 1: three replicas, one new review
class Replica:
def __init__(self, name, lag): # lag: how far behind, in ms
self.name, self.lag, self.log = name, lag, []
def read(self, now): # newest value it has by now
have = [v for t, v in self.log if t + self.lag <= now]
return have[-1]
replicas = [Replica("R1", 0), Replica("R2", 300), Replica("R3", 900)]
def write(value, now):
for r in replicas:
r.log.append((now, value))
write("rating 4.1", now=0)
write("rating 4.3", now=1000) # a new review arrives
for now in [1000, 1200, 1500, 2000]:
print(f"t={now:4} ms:", [r.read(now) for r in replicas])
Output:
t=1000 ms: ['rating 4.3', 'rating 4.1', 'rating 4.1']
t=1200 ms: ['rating 4.3', 'rating 4.1', 'rating 4.1']
t=1500 ms: ['rating 4.3', 'rating 4.3', 'rating 4.1']
t=2000 ms: ['rating 4.3', 'rating 4.3', 'rating 4.3']
A write reaches a replica at t + lag. Here the inconsistency window is 900 ms (R3's lag). For a restaurant rating, that's completely fine. But eventual consistency creates three bugs users notice.
Problem 2: my own post vanished (read-your-writes)
Asha posts a review. The write goes to the primary: "saved". She refreshes; the read goes to a lagging replica, and her review is missing. She posts it again, and now there are two.
| Panel | What happens |
|---|---|
| Asha posts | write → primary, "saved ✓" |
| She refreshes | read → lagging replica, review missing |
| Fix | read-your-writes: her reads always see her own writes |
- Read-your-writes (Vogels): "process A, after it has updated a data item, always accesses the updated value and will never see an older value."
- Session consistency (Vogels): "As long as the session exists, the system guarantees read-your-writes consistency." A session is one user's logged-in visit.
Episode 11's fix: send a user's reads to the primary for a short while after they write. The mini project below does it with version numbers.
Problem 3: the page went back in time (monotonic reads)
Ravi only reads. Refresh 1 lands on R1 (up to date): 3 comments. Refresh 2 lands on R2 (900 ms behind): 2 comments. A comment he just read vanished.
- Monotonic read consistency (Vogels): "If a process has seen a particular value for the object, any subsequent accesses will never return any previous values." Monotonic means "only goes forward".
Demo 2: remember what you saw
read now returns a version number (how many writes this copy has) with the value.
class Replica:
def __init__(self, name, lag):
self.name, self.lag, self.log = name, lag, []
def read(self, now): # (version, value) by now
n = sum(1 for t, _ in self.log if t + self.lag <= now)
return n, self.log[n - 1][1]
R1, R2 = Replica("R1", 0), Replica("R2", 900)
for r in (R1, R2):
r.log += [(0, "2 comments"), (1000, "3 comments")]
for careful in [False, True]:
print("remember what I saw:", careful)
seen = 0
for now, r in [(1100, R1), (1200, R2), (1300, R1)]:
ver, value = r.read(now)
if careful and ver < seen: # this copy is behind me
r = R1 if r is R2 else R2
ver, value = r.read(now)
seen = max(seen, ver)
print(f" t={now} {r.name}: {value}")
Output:
remember what I saw: False
t=1100 R1: 3 comments
t=1200 R2: 2 comments
t=1300 R1: 3 comments
remember what I saw: True
t=1100 R1: 3 comments
t=1200 R1: 3 comments
t=1300 R1: 3 comments
Two common ways to get monotonic reads: remember the last version you saw (like here) and skip copies that are behind it, or stick each user to one replica (practice 2).
Problem 4: a reply before its question (causal consistency)
In the ChaiNow community chat, Priya asks "Is the Andheri shop open?". Ravi replies "Yes, till 11 pm!". His reply is caused by her question. But messages travel separately, and on Meera's replica the reply arrives first: an answer to nothing.
- Causal consistency: if one write was caused by (depends on) another, everyone sees them in that order. Writes that don't depend on each other may appear in any order. Vogels: "a write is guaranteed to supersede the earlier write" for a process that was told of the update.
Demo 3: hold a message until what it replies to is shown
Each message carries after: the id of the message it depends on.
# on this replica, the reply arrived BEFORE the question
arrivals = [{"id": 2, "text": "Ravi: Yes, till 11 pm!", "after": 1},
{"id": 1, "text": "Priya: Andheri shop open?", "after": None}]
print("show as it arrives:")
for m in arrivals:
print(" shows", m["text"])
print("wait for what it replies to:")
shown, held = set(), []
def show(m):
print(" shows", m["text"])
shown.add(m["id"])
for m in arrivals:
if m["after"] is None or m["after"] in shown:
show(m)
for h in [h for h in held if h["after"] == m["id"]]:
held.remove(h)
show(h) # its question is here now
else:
held.append(m)
print(" holds", m["text"], "until message", m["after"])
Output:
show as it arrives:
shows Ravi: Yes, till 11 pm!
shows Priya: Andheri shop open?
wait for what it replies to:
holds Ravi: Yes, till 11 pm! until message 1
shows Priya: Andheri shop open?
shows Ravi: Yes, till 11 pm!
Only cause and effect is protected; unrelated messages can still show in any order. Real systems track dependencies with tools like version vectors, but the idea is exactly this: don't show an effect before its cause.
Problem 5: money needs the latest (strong consistency and quorums)
For the wallet, eventual isn't OK: we need the latest balance every time. Strong consistency (Vogels): "After the update completes, any subsequent access ... will return the updated value." The strongest form is linearizability: every operation looks as if it happened at a single instant, as if there were one copy. That's the definition of C that Gilbert and Lynch used to prove CAP (episode 14).
How do we get it with three copies? With quorums.
| In a college | With N copies |
|---|---|
| 3 notice boards, the exam date on all | N = 3: every key lives on 3 replicas |
| New date pinned on 2 boards (the peon hasn't reached the third) | W = 2: a write is done when 2 copies have it |
| You check any 2 boards: at least one has the new date | R = 2: read 2 copies; W + R > N → the sets overlap |
A quorum is the minimum number of copies that must take part in a write (W) or a read (R).
Demo 4: measure W + R > N
import random
random.seed(7)
N = 3 # copies of every key
def stale_read(W, R):
versions = [1] * N # every copy has version 1
for i in random.sample(range(N), W): # write v2, W copies say "ok"
versions[i] = 2
newest = max(versions[i] for i in random.sample(range(N), R))
return newest == 1 # read missed the new write?
for W, R in [(1, 1), (2, 1), (2, 2), (3, 1)]:
stale = sum(stale_read(W, R) for _ in range(10_000))
print(f"W={W} R={R} W+R>N: {W + R > N!s:5} stale: {stale / 100:.1f}%")
Output:
W=1 R=1 W+R>N: False stale: 66.4%
W=2 R=1 W+R>N: False stale: 32.6%
W=2 R=2 W+R>N: True stale: 0.0%
W=3 R=1 W+R>N: True stale: 0.0%
The math matches: with W = 1, R = 1, the read hits the one updated copy 1/3 of the time, so about 2/3 (66%) of reads are stale. Vogels: "If W+R > N, then the write set and the read set always overlap and one can guarantee strong consistency." (random.seed(7) makes the run repeatable.)
The price of strong
- A bigger W: every write waits for more machines, including the slowest.
- A bigger R: every read asks more machines.
- During a partition, if you can't reach enough copies, you can't answer: the C side of CAP.
Problem 6: choose per request
The consistency ladder
| Step (strongest first) | Promise | Good for |
|---|---|---|
| Strong (linearizable) | Everyone sees the latest, as if one copy | Wallet, last seat, usernames |
| Causal | Cause before effect, everywhere | Chats, comment threads |
| Read-your-writes | You see your own changes | Profile, your own posts |
| Monotonic reads | Never go back in time | Feeds, counters |
| Eventual | Agree after a while | Ratings, likes, view counts |
(The middle three are often combined; they're promises about one user's view rather than strict levels of one ladder.) Rule of thumb: use the lowest step that keeps users happy. Lower steps are faster, cheaper and stay available during partitions.
A real database: DynamoDB
From the Amazon DynamoDB Developer Guide ("DynamoDB read consistency"):
- "Eventually consistent is the default read consistent model for all read operations." Such a read "might not reflect the results of a recently completed write operation."
- "If you set
ConsistentReadto true, DynamoDB returns a response with the most up-to-date data." - "Eventually consistent reads are half the cost of strongly consistent reads."
- "Strongly consistent reads from a global secondary index or a DynamoDB stream are not supported."
# boto3 (AWS's Python library): the menu is fine eventually consistent,
table.get_item(Key={"id": "menu-42"})
# the wallet asks for the latest
table.get_item(Key={"id": "wallet-7"}, ConsistentRead=True)
(This snippet needs an AWS account and a real table, so it's shown, not run.)
The whole chain
- Replicas lag → eventual consistency, with an inconsistency window (900 ms in Demo 1).
- My post vanished → read-your-writes (session consistency).
- 3 comments, then 2 → monotonic reads: remember the version, or stick to one replica.
- Reply before its question → causal consistency: hold it until its cause is shown.
- Money → strong consistency; quorums with W + R > N gave 0% stale reads.
- Pick a step of the ladder per request (DynamoDB's
ConsistentRead).
Common mistakes (and the real errors)
| Mistake | Code | Result | Fix |
|---|---|---|---|
| Spreading one user's reads over lagging copies | for now, r in [(1100, R1), (1200, R2), ...]: ver, value = r.read(now) |
3 comments → 2 comments → 3 comments |
Remember the version, or stick to one replica |
| Showing messages in arrival order | for m in arrivals: print("shows", m["text"]) |
shows Ravi: Yes, till 11 pm! with no question |
Hold a message until its after is shown |
| Weak quorum for money | N=3, W=1, R=1 for the wallet |
stale: 66.4% |
W + R > N, e.g. W=2, R=2 |
| Reading before anything reached a copy | have[-1] when have is empty |
IndexError: list index out of range |
Handle "no value yet" (return None) |
| Strong everywhere | ConsistentRead=True on every read |
twice the read cost, slower | Strong only where it matters |
The IndexError one is easy to hit in Demo 1: read R3 at t=500, before even the first write has reached it (its lag is 900):
class Replica:
def __init__(self, name, lag):
self.name, self.lag, self.log = name, lag, []
def read(self, now):
have = [v for t, v in self.log if t + self.lag <= now]
return have[-1]
r3 = Replica("R3", 900)
r3.log.append((0, "rating 4.1"))
print(r3.read(500))
Traceback (most recent call last):
File "main.py", line 10, in <module>
print(r3.read(500))
~~~~~~~^^^^^
File "main.py", line 6, in read
return have[-1]
~~~~^^^^
IndexError: list index out of range
Fix: return have[-1] if have else None.
Mini project: a session with read-your-writes and monotonic reads
A Session remembers a floor: the highest version it has written or seen. A read from a replica below the floor is too old for this user, so it falls back to the primary.
# Mini project: a session that gives read-your-writes + monotonic reads on top of lagging replicas
import random
random.seed(3)
class Primary:
def __init__(self):
self.log = [] # list of (time, value)
def write(self, value, now):
self.log.append((now, value))
return len(self.log) # the version of this write
class Replica:
def __init__(self, primary, lag):
self.p, self.lag = primary, lag
def version(self, now): # how many writes have reached me
return sum(1 for t, _ in self.p.log if t + self.lag <= now)
def read(self, now):
v = self.version(now)
return v, (self.p.log[v - 1][1] if v else None)
class Session:
def __init__(self, primary, replicas):
self.p, self.replicas, self.floor = primary, replicas, 0
def write(self, value, now):
self.floor = max(self.floor, self.p.write(value, now)) # read-your-writes
def read(self, now):
r = random.choice(self.replicas) # a load balancer picks any copy
v, value = r.read(now)
if v < self.floor: # too old for me: use the primary
v, value = len(self.p.log), self.p.log[-1][1]
how = "primary"
else:
how = f"replica lag {r.lag}"
self.floor = max(self.floor, v) # monotonic reads
return f"t={now}: {value!r:12} ({how})"
db = Primary()
replicas = [Replica(db, 0), Replica(db, 500), Replica(db, 2000)]
asha = Session(db, replicas)
db.write("bio: hi", 0)
asha.write("bio: chai!", 1000)
for now in [1000, 1100, 1200, 1300, 1600, 3500]:
print(asha.read(now))
Output:
t=1000: 'bio: chai!' (replica lag 0)
t=1100: 'bio: chai!' (primary)
t=1200: 'bio: chai!' (primary)
t=1300: 'bio: chai!' (replica lag 0)
t=1600: 'bio: chai!' (replica lag 500)
t=3500: 'bio: chai!' (replica lag 2000)
Asha never sees her old bio, even though two of the three replicas are behind at first. Most reads still go to replicas; only the ones that would break her promises go to the primary. Extend it: count how many reads went to the primary, and try a 5,000 ms lag.
Practice
- Homework: in the quorum demo, try N = 5 with W = 3, R = 2 and W = 3, R = 3. Also W = 1, R = 5 and W = 5, R = 1.
- Homework: in Demo 2, stick each user to one replica instead (hint: pick the replica from the user's name). Does the page still go back in time?
- Homework: in Demo 3, add a third message, "Meera: Great, going now!", which replies to Ravi's reply, and make all three arrive in reverse order.
- Which step of the ladder would you choose for: a cricket score, a bank balance, a group chat, your own profile picture, a YouTube view count?
- N = 5. What is the smallest R that gives strong reads if W = 2? If W = 5?
Solutions and hints
1.
import random
random.seed(7)
def stale_read(N, W, R):
versions = [1] * N
for i in random.sample(range(N), W):
versions[i] = 2
newest = max(versions[i] for i in random.sample(range(N), R))
return newest == 1
for N, W, R in [(5, 3, 2), (5, 3, 3), (5, 1, 5), (5, 5, 1)]:
stale = sum(stale_read(N, W, R) for _ in range(10_000))
print(f"N={N} W={W} R={R} W+R>N: {W + R > N!s:5} stale: {stale / 100:.1f}%")
N=5 W=3 R=2 W+R>N: False stale: 10.1%
N=5 W=3 R=3 W+R>N: True stale: 0.0%
N=5 W=1 R=5 W+R>N: True stale: 0.0%
N=5 W=5 R=1 W+R>N: True stale: 0.0%
W = 3, R = 2 is stale 1 time in 10 (choosing the 2 missed copies out of 5: 1 of 10 pairs). W = 1, R = 5 makes writes fast and reads slow; W = 5, R = 1 the opposite.
2.
class Replica:
def __init__(self, name, lag):
self.name, self.lag, self.log = name, lag, []
def read(self, now):
n = sum(1 for t, _ in self.log if t + self.lag <= now)
return n, self.log[n - 1][1]
R1, R2 = Replica("R1", 0), Replica("R2", 900)
for r in (R1, R2):
r.log += [(0, "2 comments"), (1000, "3 comments")]
replicas = [R1, R2]
def sticky(user): # the same user always gets the same replica
return replicas[sum(map(ord, user)) % len(replicas)]
for user in ["ravi", "asha"]:
r = sticky(user)
print(user, "->", r.name, [r.read(now)[1] for now in (1100, 1200, 1300, 2000)])
ravi -> R1 ['3 comments', '3 comments', '3 comments', '3 comments']
asha -> R2 ['2 comments', '2 comments', '2 comments', '3 comments']
Asha's replica is behind, but she never goes backwards: monotonic reads hold. (It's still not read-your-writes if she wrote the third comment herself.)
3. Release whole chains with a recursive show:
# on this replica: the reply to the reply arrives first, then the reply, then the question
arrivals = [{"id": 3, "text": "Meera: Great, going now!", "after": 2},
{"id": 2, "text": "Ravi: Yes, till 11 pm!", "after": 1},
{"id": 1, "text": "Priya: Andheri shop open?", "after": None}]
shown, held = set(), []
def show(m):
print(" shows", m["text"])
shown.add(m["id"])
for h in [h for h in held if h["after"] == m["id"]]:
held.remove(h)
show(h) # recursion: release whole chains
for m in arrivals:
if m["after"] is None or m["after"] in shown:
show(m)
else:
held.append(m)
print(" holds", m["text"], "until message", m["after"])
holds Meera: Great, going now! until message 2
holds Ravi: Yes, till 11 pm! until message 1
shows Priya: Andheri shop open?
shows Ravi: Yes, till 11 pm!
shows Meera: Great, going now!
4. Cricket score: monotonic reads (never show a lower score after a higher one). Bank balance: strong. Group chat: causal. Your profile picture: read-your-writes. View count: eventual.
5. W + R > 5: with W = 2, R = 4. With W = 5, R = 1.
Quick quiz
# 5 copies of every key
N = 5
W = 3
R = 2
# guaranteed to read the latest?
- A. Yes, always
- B. No: 3 + 2 is not more than 5
- C. Only if R1 is the leader
- D. Yes, because W is a majority
Answer
B. W + R = 5 is not greater than N = 5. The write reached 3 copies, so 2 missed it, and a read of 2 can pick exactly those two: about 10% of reads in practice 1. Make R = 3.
Interview questions
- What is eventual consistency? What is the inconsistency window? (Copies agree if writes stop; the window is the time until every observer sees the update.)
- A user updates their profile and refreshes, and sees the old one. What's missing and how do you fix it? (Read-your-writes: read from the primary for a while after a write, or track versions.)
- What are monotonic reads? Two ways to provide them. (Never see older data after newer; remember the version or stick to one replica.)
- Explain causal consistency with an example. (A reply must never appear before its question; hold effects until their causes.)
- What does W + R > N guarantee, and why? (Read and write sets overlap, so a read always includes at least one copy with the latest write.)
- Strong vs linearizable: what's linearizability? (Every operation appears to happen at one instant, as if there were a single copy.)
- How does DynamoDB let you choose consistency, and what does it cost? (
ConsistentRead=True; eventually consistent reads are half the cost.)
Glossary
| Term | Meaning |
|---|---|
| Consistency model | A promise about what reads can return after writes |
| Primary / replica | The copy that takes writes / a copy that follows it (episode 11) |
| Lag | How far behind a replica is |
| Strong consistency | After a write completes, every read returns it |
| Linearizable | Every operation looks as if it happened at a single instant, as if there were one copy |
| Weak consistency | No guarantee that later reads see a write |
| Eventual consistency | If writes stop, eventually every read returns the last value |
| Inconsistency window | Time between an update and the moment every observer is guaranteed to see it |
| Stale read | A read that returns an older value than the latest write |
| Read-your-writes | After you write, you always see your write (or newer) |
| Session / session consistency | One user's visit / read-your-writes for as long as the session lasts |
| Monotonic reads | Once you've seen a value, you never see an older one |
| Monotonic writes | One user's writes are applied in the order they made them |
| Version number | A counter that grows with every write; tells you how new a copy is |
| Sticky routing | Always sending the same user to the same replica |
| Causal consistency | If B was caused by A, everyone sees A before B |
Dependency (after) |
The earlier write that a later one was caused by |
| Quorum | The minimum number of copies that must take part in a write (W) or read (R) |
| N, W, R | Number of copies; copies a write waits for; copies a read asks |
| W + R > N | The read and write sets always overlap, so reads see the latest write |
ConsistentRead |
DynamoDB's per-request switch for a strongly consistent read |
| Global secondary index | A DynamoDB index on other attributes; strongly consistent reads aren't supported on it |
random.seed(n) |
Makes Python's random numbers repeat the same way every run |
IndexError |
Python error for an index past the end of a list |
Summary
- Replicas give eventual consistency: copies agree after an inconsistency window (900 ms in Demo 1).
- Read-your-writes stops your own post from vanishing; session consistency is that promise for one session.
- Monotonic reads stop time travel: remember the version you saw, or stick to one replica (3, 2, 3 → 3, 3, 3).
- Causal consistency holds an effect (a reply) until its cause (the question) is shown.
- Strong (linearizable) consistency for money: W + R > N gave 0% stale reads; W = 1, R = 1 gave 66%.
- Use the lowest step that keeps users happy; DynamoDB lets you choose per read, and eventually consistent reads are half the cost.
Next episode: so far every request waited for its answer. When a ChaiNow order is placed, must the customer wait for the SMS, the invoice email and the loyalty points too? Message queues and pub/sub.