System Design · Lesson 4 of 18
Choosing and Scaling Databases
SQL vs NoSQL, replication, sharding, CAP and when to denormalize.
- Intermediate
- 55 min read
- 7 objectives
Before this lessonLesson 3: Scaling and Caching
What you will learn
- Choose a database family from the access pattern
- Design composite and covering indexes and explain B-tree vs LSM
- Compare replication topologies and handle replication lag
- Partition data with range, hash and consistent hashing
- Tame hot keys, rebalancing and cross-shard joins
- Pick isolation levels and fix lost updates and write skew
- Choose between 2PC and sagas
Your Progress
0 of 18 lessons 0%
- Lessons0 / 18
- Completed0
- Est. time left~ 16 hours
Progress is saved in this browser. No account needed.
Tip: pressing Next marks this lesson complete automatically.
The database is usually the hardest part of a system to scale, because it is the part that holds state which must stay correct. Stateless app servers can be cloned in seconds; a database has to be copied (replication) and split (partitioning) without losing or contradicting data, and every copy or split costs you a guarantee you used to get for free.
This lesson is the toolkit every later case study leans on. It covers how to choose a store from its access pattern (not its hype), how indexes really work and why they slow writes, the three replication topologies and their failure modes, partitioning methods and criteria including consistent hashing, the problems sharding creates, transaction isolation with a concrete example of every anomaly, distributed transactions (2PC and sagas), and finally five workloads with a reasoned database choice for each. Every concept comes with a worked example; the Python runs in your browser.
If you have not yet, skim Lesson 2: Core Concepts (CAP, consistency models) and Lesson 3: Scaling and Caching first. The case studies that use this material most heavily are the key-value store, chat and the food delivery capstone.
Step 1 — Start from the access pattern, not the product
"Which database?" is the wrong first question. The right first question is "what are the five queries this system runs most, how often, and what must be true about their answers?" Write them down before naming any technology. For each one, pin down:
- Shape of the read. Point lookup by key? A range ("last 20 orders")? An ad-hoc filter on many columns? A full-text match? A multi-hop relationship?
- Read/write ratio and rate. 100 writes/s and 100k writes/s are different universes. So are 10:1 and 1:10.
- Size and growth. 50 GB fits on one machine's SSD with room to spare; 50 TB does not.
- Correctness needs. Must two concurrent writes never both succeed (seat booking, balances)? Can a read be a few seconds stale (like counts, feeds)?
- Transactions. Does one user action need to change several rows atomically? Across entities that would live on different machines?
- Latency target. A p99 of 5 ms rules out anything that needs a disk seek per request; 500 ms does not.
Worked example: a "my orders" screen. The query is "the 20 most recent orders for customer X", run 3,000 times per second, answer may be two seconds stale, never changes other rows. That is a single-key range read — every store on this page can serve it. Now add "cancel an order and refund the payment atomically": that needs a multi-row transaction, which immediately narrows the field. The requirements picked the database; the brand names are just the implementation.
Step 2 — SQL versus NoSQL: what actually differs
"SQL vs NoSQL" is a slightly misleading split. "NoSQL" is five or six unrelated families that share only one trait — they are not relational. The real differences are along these axes:
| Axis | Relational (SQL) | Typical NoSQL |
|---|---|---|
| Data model | Tables of rows with typed columns; relationships via foreign keys and joins | Key → blob, document, wide row, or graph; relationships embedded or duplicated |
| Schema | Declared up front, enforced on write (schema-on-write) | Implicit; the application interprets it on read (schema-on-read). There is always a schema — it just lives in your code |
| Queries | Declarative SQL; ask questions you did not plan for | Queries designed around the key; unplanned questions are slow or impossible |
| Transactions | Multi-row, multi-table ACID is the default | Usually single-key or single-document atomicity; multi-item transactions exist (DynamoDB, MongoDB 4+) but cost more |
| Scaling | Scale up first; replicas for reads; sharding is possible but manual (or Vitess, Citus, CockroachDB, Spanner) | Built to partition across nodes from day one |
| Consistency | Strong on a single primary | Often tunable per request (Cassandra QUORUM vs ONE), eventual by default in many |
The honest summary: relational databases trade horizontal scale for flexibility of querying and strong guarantees; most NoSQL stores trade flexible querying and multi-row guarantees for effortless partitioning and predictable latency at huge scale. "Distributed SQL" (Spanner, CockroachDB, YugabyteDB) tries to have both and pays for it in write latency, because every commit coordinates across replicas.
Worked example: the same data, five ways
The same data -- a customer, their addresses and their orders -- in five models.
The access pattern decides which shape is right, not the data.
RELATIONAL (Postgres, MySQL): normalise, join at read time
customers(id PK, name, email UNIQUE)
addresses(id PK, customer_id FK, line1, city)
orders(id PK, customer_id FK, total_minor, placed_at)
order_items(order_id FK, sku, qty, price_minor)
-> Any question is answerable later ("revenue by city last week") with a JOIN.
-> One transaction can touch all four tables atomically.
DOCUMENT (MongoDB, Firestore): embed what is read together
{ _id: "c42", name: "Ada", email: "ada@x.io",
addresses: [{ line1: "1 Main St", city: "Pune" }],
recent_orders: [{ id: "o9", total_minor: 48950, items: [...] }] } # capped at 20
-> One read renders the whole profile page. No joins.
-> "Revenue by city" now means scanning every document, or a second pipeline.
KEY-VALUE (Redis, DynamoDB used as KV): one key, one opaque blob
GET session:9f2c... -> { customer_id: 42, cart: [...], exp: ... }
-> Sub-millisecond, trivially sharded. The store cannot answer ANY
question except "what is the value for this exact key?"
WIDE-COLUMN (Cassandra, ScyllaDB, Bigtable): design one table per query
orders_by_customer PRIMARY KEY ((customer_id), placed_at DESC, order_id)
-> "Latest 20 orders for customer 42" = one partition, one sequential read.
-> Want orders by restaurant? That is a SECOND table you write to as well.
GRAPH (Neo4j, Neptune): relationships are first-class
(:Customer {id:42})-[:ORDERED]->(:Order)-[:FROM]->(:Restaurant)
(:Customer {id:42})-[:FRIEND]->(:Customer {id:77})
-> "Restaurants my friends-of-friends ordered from" is a 3-hop traversal,
not a 3-way self-join that explodes on large tables.Notice what moved. In the relational model the query is flexible and the write is simple. In the document and wide-column models the write does extra work (embedding, writing to two tables) so that one specific read is a single fetch. That is the core NoSQL trade: you model for the queries you know, and pay later for the ones you did not predict.
The families, and when each one wins
| Family | Examples | Strong at | Weak at | Real use cases |
|---|---|---|---|---|
| Relational | PostgreSQL, MySQL, SQL Server, Aurora | Transactions, constraints, ad-hoc queries and joins, mature tooling | Write scale beyond one primary; very wide/sparse data | Orders, payments, inventory, user accounts, anything with money or invariants |
| Key-value | Redis, Memcached, DynamoDB, etcd | Sub-ms point reads/writes by key, trivially partitioned, TTLs | Anything that is not "get by exact key"; Redis durability is optional | Sessions, caches, rate-limit counters, feature flags, leaderboards (sorted sets), distributed locks |
| Document | MongoDB, Firestore, Couchbase | Nested objects read as a whole, evolving schemas, per-document atomicity | Many-to-many relations, cross-document joins and reporting | Product catalogues with varied attributes, CMS content, user profiles, mobile app backends |
| Wide-column | Cassandra, ScyllaDB, HBase, Bigtable | Massive write throughput (LSM), multi-DC replication, range reads within a partition | Ad-hoc queries, secondary indexes, transactions; you design one table per query | Chat messages, activity logs, IoT events, time-ordered per-entity histories |
| Graph | Neo4j, Amazon Neptune, JanusGraph | Multi-hop traversals ("friends of friends who like X"), path finding | Bulk aggregation, horizontal scale of a single connected graph | Fraud rings, recommendations, knowledge graphs, access-control hierarchies |
| Search | Elasticsearch, OpenSearch, Solr, Typesense | Full-text relevance, typo tolerance, faceted filters, log analytics | Being a source of truth (refresh lag, no transactions, reindex pain) | Product search, log search, autocomplete; always fed from a primary store |
| Time-series | TimescaleDB, InfluxDB, Prometheus, ClickHouse | Append-heavy timestamped points, compression (10x+), downsampling, time-window aggregates | Updates, point lookups by non-time keys | Metrics, monitoring, sensor data, financial ticks |
| Object storage | S3, GCS, Azure Blob | Cheap, durable (11 nines) blobs of any size | Low-latency small reads, in-place updates, queries | Images, video, backups, data lake files; the DB stores only the key |
Wrong answers candidates give
- "NoSQL because it scales." Scale to what? A single Postgres primary on modern hardware handles tens of thousands of simple writes per second and several TB of data. If your numbers fit, you have just given away transactions for nothing.
- "MongoDB because the schema might change."
ALTER TABLE ... ADD COLUMNis instant in modern Postgres, and aJSONBcolumn gives you schemaless fields inside a relational row. Schema flexibility alone is rarely a reason. - "Elasticsearch as the database." It is a derived index. Keep the truth in a transactional store and feed search by change data capture (CDC).
- "One database for everything." Real systems are polyglot: the food delivery capstone uses Postgres, Redis, Elasticsearch and a warehouse, each for the workload it fits.
Step 3 — Indexes: how lookups get fast, and why writes pay
Without an index, WHERE email = ? means reading every row — a full table scan. An index is a second, separate data structure holding the indexed column(s) in sorted (or hashed) order plus a pointer back to the row, so the engine can jump to matches. Like the index at the back of a textbook: you trade some extra pages for not reading the whole book.
Worked example: scan versus index lookup
200,000 user rows in insertion order. We look for one email, first by scanning, then with a sorted index and binary search — which is what a B-tree does, one page at a time. Then a composite index, used correctly and incorrectly.
import bisect, random
random.seed(7)
N = 200_000
COUNTRIES = ["IN", "US", "BR", "DE", "JP"]
ids = random.sample(range(10**9), N) # unique, in no useful order
# The "heap": rows stored in insertion order, like a table with no index
rows = [{"id": i, "email": f"user{ids[i]:09d}@mail.com",
"country": random.choice(COUNTRIES), "age": random.randint(18, 80)}
for i in range(N)]
target = rows[123_456]["email"]
# 1) Full table scan: WHERE email = ? -- every row must be examined,
# because without a UNIQUE index the engine cannot stop at the first hit.
examined, hit = 0, None
for r in rows:
examined += 1
if r["email"] == target:
hit = r["id"]
print(f"full scan: examined {examined:,} rows -> row {hit}")
# 2) Secondary index on email: sorted (key, row_id) pairs + binary search.
# A real B-tree does the same thing, but in pages of ~hundreds of keys.
index = sorted((r["email"], r["id"]) for r in rows)
keys = [k for k, _ in index]
lo, hi, comparisons = 0, len(keys), 0
while lo < hi:
comparisons += 1
mid = (lo + hi) // 2
if keys[mid] < target:
lo = mid + 1
else:
hi = mid
print(f"index lookup: {comparisons} comparisons -> row {index[lo][1]}")
# 3) Composite index (country, age): a range scan touches only matching entries
comp = sorted((r["country"], r["age"], r["id"]) for r in rows)
lo = bisect.bisect_left(comp, ("IN", 30, -1))
hi = bisect.bisect_right(comp, ("IN", 32, N))
print(f"(country, age) with country='IN' AND age 30..32: read {hi - lo:,} entries")
# 4) Same index, but the query skips the leftmost column: WHERE age = 30.
# Entries are sorted by country first, so age=30 rows are scattered in
# five separate runs -- the planner must read the whole index (or the table).
matches = sum(1 for c, a, _ in comp if a == 30)
print(f"(country, age) with only age=30: read all {len(comp):,} entries "
f"to find {matches:,}")full scan: examined 200,000 rows -> row 123456 index lookup: 18 comparisons -> row 123456 (country, age) with country='IN' AND age 30..32: read 1,831 entries (country, age) with only age=30: read all 200,000 entries to find 3,168
200,000 row reads versus 18 comparisons is the whole point of an index, and the gap grows with the table: a billion rows is still about 30 comparisons. The last two lines teach the leftmost-prefix rule: a composite index on (country, age) is sorted by country first, then age within each country. It serves filters on country, or on country and age, but not on age alone — those rows are scattered across the index.
B-trees: the default in every relational database
A B-tree (strictly, a B+tree) stores keys in fixed-size pages (8 KB in Postgres, 16 KB in InnoDB). Internal pages hold keys and child pointers; leaf pages hold the keys and either the row itself (a clustered index, like InnoDB's primary key) or a pointer to it. Because each page holds hundreds of keys, the tree is extremely shallow.
import math
PAGE = 16 * 1024 # InnoDB page size; Postgres uses 8 KB
ENTRY = 8 + 6 + 4 # BIGINT key + child page pointer + per-entry overhead
fanout = PAGE // ENTRY
print(f"keys per internal page (fanout): ~{fanout}")
for rows in (1e6, 1e9, 1e11):
depth = math.ceil(math.log(rows) / math.log(fanout))
print(f"{rows:>7.0e} rows -> B-tree depth {depth}")
# Leaves hold every key; the levels above them are tiny and stay in RAM,
# so a point lookup costs about one disk read (the leaf) even at 1e9 rows.
leaf_pages = math.ceil(1e9 / fanout)
internal_pages = sum(math.ceil(1e9 / fanout ** k) for k in range(2, 5))
print(f"1e9 rows: {leaf_pages:,} leaf pages (~{leaf_pages * PAGE / 1e9:.0f} GB), "
f"{internal_pages:,} internal pages (~{internal_pages * PAGE / 1e6:.0f} MB)")
# The write side: every INSERT must also update every secondary index.
print()
DISK_RANDOM_WRITES = 20_000 # page writes/s a volume can sustain (illustrative)
for n_idx in (0, 1, 3, 6, 10):
page_writes = 1 + n_idx # table page + one leaf page per index
print(f"{n_idx:>2} secondary indexes -> {page_writes:>2} page writes per insert "
f"-> ~{DISK_RANDOM_WRITES // page_writes:,} inserts/s ceiling")keys per internal page (fanout): ~910 1e+06 rows -> B-tree depth 3 1e+09 rows -> B-tree depth 4 1e+11 rows -> B-tree depth 4 1e9 rows: 1,098,902 leaf pages (~18 GB), 1,211 internal pages (~20 MB) 0 secondary indexes -> 1 page writes per insert -> ~20,000 inserts/s ceiling 1 secondary indexes -> 2 page writes per insert -> ~10,000 inserts/s ceiling 3 secondary indexes -> 4 page writes per insert -> ~5,000 inserts/s ceiling 6 secondary indexes -> 7 page writes per insert -> ~2,857 inserts/s ceiling 10 secondary indexes -> 11 page writes per insert -> ~1,818 inserts/s ceiling
Two lessons in that output. First, depth barely grows: a billion rows is four levels, and the top three are 20 MB that live permanently in memory, so a point lookup costs about one disk read. Second, every secondary index is another structure to update on every insert, and on every update that touches an indexed column. A table with ten indexes does eleven page writes per insert. That is the precise reason indexes slow writes — and why "just add an index on every column" is a wrong answer: each unused index is pure write cost, extra storage, and more to keep in the buffer pool.
Composite, covering, partial and other index kinds
-- orders(id, customer_id, status, placed_at, total_minor, ...) -- 400M rows
-- Composite index: column ORDER matters. Equality columns first, range/sort last.
CREATE INDEX orders_cust_time ON orders (customer_id, placed_at DESC);
-- uses it: WHERE customer_id = 42 ORDER BY placed_at DESC LIMIT 20 (seek + read 20)
-- uses it: WHERE customer_id = 42 AND placed_at > now() - interval '30 days'
-- CANNOT: WHERE placed_at > now() - interval '1 day' (leftmost column missing)
-- Covering index: INCLUDE the columns the query returns, so the engine never
-- visits the table ("index-only scan"). Saves one random read per row.
CREATE INDEX orders_cust_cover ON orders (customer_id, placed_at DESC)
INCLUDE (status, total_minor);
-- "my orders" list page: SELECT id, status, total_minor, placed_at ... -> index only
-- Partial index: index only the rows you query. 400M orders, ~50k are active.
CREATE INDEX orders_active ON orders (placed_at) WHERE status IN ('PAID', 'PREPARING');
-- tiny, stays in RAM, and completed orders cost nothing to write into it
-- Unique index: an index that is also a correctness guarantee.
CREATE UNIQUE INDEX payments_idem ON payments (idempotency_key);
-- Expression index: the query must use the same expression.
CREATE INDEX users_email_lower ON users (lower(email));
-- uses it: WHERE lower(email) = 'ada@x.io' CANNOT: WHERE email = 'Ada@x.io'
-- Always check the plan rather than guessing:
EXPLAIN ANALYZE SELECT id, status FROM orders WHERE customer_id = 42
ORDER BY placed_at DESC LIMIT 20;
-- Index Only Scan using orders_cust_cover ... rows=20 ... Heap Fetches: 0- Column order in a composite index: put equality filters first, then the range or sort column.
(customer_id, placed_at)serves "customer 42, newest first";(placed_at, customer_id)would force reading every order in the time range for all customers. - Covering indexes remove the extra random read from index to table for every row. On a list page returning 50 rows that is 50 fewer disk reads.
- Selectivity matters. An index on a boolean column like
is_deleted(95% false) is nearly useless; the planner will scan anyway. A partial index on the rare value is what you want. - Hash indexes answer only equality, never ranges or sorting; B-trees do both, which is why they are the default.
LSM trees: the write-optimised alternative
A B-tree updates pages in place, which means random writes. A log-structured merge tree (Cassandra, ScyllaDB, RocksDB, LevelDB, HBase, and the storage under many NewSQL systems) never updates in place. Writes go to an in-memory sorted buffer (the memtable) plus an append-only write-ahead log; when the memtable fills it is flushed as an immutable sorted file (an SSTable). Reads check the memtable, then SSTables newest-first. Background compaction merges SSTables and discards overwritten values.
import bisect
class LSM:
"""Toy LSM tree: writes go to a memtable; full memtables are flushed as
immutable sorted runs (SSTables); reads check newest to oldest."""
def __init__(self, memtable_limit=4):
self.mem, self.runs, self.limit = {}, [], memtable_limit
self.seq_writes = 0 # bytes are appended, never rewritten in place
def put(self, key, value):
self.mem[key] = value # O(1) in RAM (plus a WAL append on disk)
if len(self.mem) >= self.limit:
run = sorted(self.mem.items())
self.runs.insert(0, run) # newest run first
self.seq_writes += len(run)
self.mem = {}
def get(self, key, use_bloom=False):
if key in self.mem:
return self.mem[key], 0
probes = 0
for run in self.runs:
if use_bloom and key not in {k for k, _ in run}: # stand-in for a bloom filter
continue # "definitely not here": skip the disk read
probes += 1
i = bisect.bisect_left(run, (key,))
if i < len(run) and run[i][0] == key:
return run[i][1], probes
return None, probes
def compact(self):
merged = {}
for run in reversed(self.runs): # oldest first, newer values overwrite
merged.update(run)
self.runs = [sorted(merged.items())]
self.seq_writes += len(merged) # compaction rewrites data: write amplification
db = LSM()
for i in range(20):
db.put(f"user:{i:02d}", f"v1-{i}")
db.put("user:03", "v2-3") # an update is just a newer entry
for i in range(20, 23):
db.put(f"user:{i:02d}", f"v1-{i}")
print("runs on disk:", len(db.runs), " memtable:", sorted(db.mem))
print("get user:03 ->", db.get("user:03")) # found in newest run holding it
print("get user:00 ->", db.get("user:00")) # oldest key: probes many runs
print("get user:99 ->", db.get("user:99"), "(miss: every run probed)")
print("with bloom ->", db.get("user:99", use_bloom=True))
db.compact()
print("after compaction: runs =", len(db.runs), " get user:00 ->", db.get("user:00"),
" total entries written:", db.seq_writes)runs on disk: 6 memtable: []
get user:03 -> ('v2-3', 1)
get user:00 -> ('v1-0', 6)
get user:99 -> (None, 6) (miss: every run probed)
with bloom -> (None, 0)
after compaction: runs = 1 get user:00 -> ('v1-0', 1) total entries written: 47
The toy shows every LSM trade-off in miniature. Writes are cheap and sequential. Reads may have to probe several files (read amplification) — the worst case is a key that does not exist at all. Bloom filters fix most of that: a few bits per key answer "definitely not in this file" so the read skips it without touching disk. Compaction restores fast reads but rewrites data again and again (write amplification — 47 entries written for 24 puts here, and 10–30x in real systems).
| B-tree | LSM tree | |
|---|---|---|
| Write pattern | Random, in-place page updates | Sequential appends; compaction in the background |
| Write throughput | Good | Excellent — the reason Cassandra absorbs 100k+ writes/s per node class |
| Point read | ~1 disk read, predictable | Memtable + bloom filters; usually 1 read, occasionally more |
| Range scan | Excellent (leaves are linked in order) | Good, but merges across several files |
| Space | Fragmentation, ~30% slack in pages | Compresses well; temporary duplicates until compaction |
| Latency spikes | Rare | Compaction can steal disk bandwidth; needs tuning |
| Used by | Postgres, MySQL/InnoDB, SQL Server, Oracle | Cassandra, ScyllaDB, RocksDB, HBase, Bigtable |
Rule of thumb: write-heavy, append-mostly, key-scoped data (events, messages, metrics) suits LSM; read-heavy data with rich queries and transactions suits B-trees.
Step 4 — Replication: copies for availability, reads and locality
Replication keeps the same data on several machines. It buys three separate things, and it helps to name which one you want: availability (lose a node, keep serving), read scale (spread reads over copies), and locality (a copy near users in each region). Redundancy removes the single point of failure; replication is the mechanism that keeps the redundant copies in step.
Topology 1: leader-follower (primary-replica)
same region)] L -->|async stream| F2[(Follower B
same region)] L -->|async stream| F3[(Follower C
other region)] APP -->|stale-tolerant reads| F2 APP -->|stale-tolerant reads| F3
All writes go to one leader, which streams its log to followers. Reads can go to followers when slight staleness is acceptable; a follower is promoted if the leader dies.
One node accepts writes and ships its change log (Postgres WAL, MySQL binlog) to followers, which replay it. It is simple, avoids write conflicts entirely, and is what most systems run. Its limits: write throughput is capped at one node, and failover is where the danger lives.
Synchronous versus asynchronous
| Mode | Leader acknowledges a commit when… | Write latency | Data lost if the leader dies |
|---|---|---|---|
| Asynchronous | It is durable locally | Lowest (~1 ms) | Whatever had not shipped yet — typically milliseconds, up to seconds under load |
| Synchronous (all) | Every follower has it | Slowest follower's round trip; one dead follower blocks all writes | None |
| Semi-synchronous | At least one follower has it | One extra round trip (~1 ms in-region, 60–150 ms cross-region) | None, as long as the promoted follower is the synced one |
| Quorum (Raft/Paxos) | A majority has it | Majority round trip | None; tolerates ⌊(n−1)/2⌋ failures |
The common production setup is one synchronous follower in the same region (no data loss on failover) plus asynchronous followers for reads and a cross-region disaster-recovery copy.
Replication lag and read-your-writes
With asynchronous followers, a follower is always a little behind. Usually that is milliseconds; during a backup, a burst of writes or a long query on the follower it can reach seconds or minutes. That lag produces user-visible anomalies:
- Read-your-writes violation — you save your profile, refresh, and see the old value.
- Non-monotonic reads — two refreshes hit two followers with different lag; a new comment appears, then disappears.
- Inconsistent prefix — you see an answer before the question it replies to, because they were read from different partitions.
The write succeeded, but the very next read went to a follower that had not replayed it yet. The user concludes their save was lost.
class Cluster:
"""One leader, one async follower that applies the leader's log `lag_ms` late."""
def __init__(self, lag_ms):
self.log, self.lag = [], lag_ms # log entries: (commit_ms, key, value)
def write(self, now, key, value):
self.log.append((now, key, value))
return len(self.log) # the log position (LSN) of this write
def _read(self, key, upto):
val = None
for _, k, v in self.log[:upto]:
if k == key:
val = v
return val
def follower_lsn(self, now):
return sum(1 for t, _, _ in self.log if t + self.lag <= now)
def read_leader(self, key):
return self._read(key, len(self.log))
def read_follower(self, now, key):
return self._read(key, self.follower_lsn(now))
c = Cluster(lag_ms=300)
c.write(0, "name:42", "Ada")
lsn = c.write(1_000, "name:42", "Ada Lovelace") # user 42 edits their profile
# The profile page reloads 50 ms later and is routed to the follower.
print("t=1050 follower sees:", c.read_follower(1_050, "name:42"), " <- user thinks the save failed")
print("t=1050 leader sees: ", c.read_leader("name:42"))
# Fix 1: route a user's reads to the leader for a window after they write.
last_write = {"42": 1_000}
def read_profile_v1(now, user):
if now - last_write.get(user, -10**9) < 1_000:
return c.read_leader("name:" + user), "leader"
return c.read_follower(now, "name:" + user), "follower"
print("fix 1:", read_profile_v1(1_050, "42"), read_profile_v1(2_500, "42"))
# Fix 2: the client keeps the LSN of its last write (a cookie / session token);
# a follower serves the read only if it has replayed at least that far.
def read_profile_v2(now, user, min_lsn):
if c.follower_lsn(now) >= min_lsn:
return c.read_follower(now, "name:" + user), "follower"
return c.read_leader("name:" + user), "leader (follower behind)"
print("fix 2:", read_profile_v2(1_050, "42", lsn), read_profile_v2(1_400, "42", lsn))t=1050 follower sees: Ada <- user thinks the save failed
t=1050 leader sees: Ada Lovelace
fix 1: ('Ada Lovelace', 'leader') ('Ada Lovelace', 'follower')
fix 2: ('Ada Lovelace', 'leader (follower behind)') ('Ada Lovelace', 'follower')
Both fixes are used in production. The time window is simple and good enough for most products. The LSN (or GTID, or a "session consistency token" as Cosmos DB calls it) is precise: it routes to a follower only when that follower has caught up to this user's last write. For monotonic reads, pin each user to one follower (hash the user id) so they never go back in time.
Failover: where leader-follower goes wrong
- Lost writes. With async replication, the promoted follower may be missing the old leader's last writes. If the old leader comes back and those writes are discarded, ids can be reused — GitHub once had a MySQL incident where reused auto-increment ids exposed data across tables that cached them in Redis.
- Split brain. A network blip makes the old leader look dead; a follower is promoted; now two nodes accept writes. Prevent it with fencing (the old leader's lease expires, or its storage access is revoked) and consensus-based election (Patroni with etcd, Orchestrator, managed RDS/Aurora failover).
- Timeout tuning. Too short and you fail over on every GC pause; too long and you are down for a minute. 10–30 seconds is common.
Topology 2: multi-leader
Several nodes accept writes — typically one leader per region — and replicate to each other asynchronously. Writes are fast locally and each region survives the others being unreachable. The price is write conflicts: two regions edit the same row at the same time. Resolution options, worst to best: last-write-wins by timestamp (silently drops one write; clocks skew), custom merge logic in the app, or conflict-free replicated data types (CRDTs) for counters, sets and collaborative text. Use it for multi-region apps where data is naturally owned by one region most of the time (a user's own calendar), or for offline-first clients (every phone is a "leader").
Topology 3: leaderless (Dynamo style)
Any replica accepts reads and writes. The client (or a coordinator node) sends each write to all N replicas of the key and waits for W acknowledgements; reads query R replicas and take the newest version. If W + R > N, every read set overlaps every write set in at least one replica, so the read sees the latest acknowledged write. Cassandra, ScyllaDB, Riak and DynamoDB's internals work this way.
import random
random.seed(1)
N = 3 # replicas per key
def trial(W, R):
replicas = [0] * N # version number each replica holds; start at v0
# Write v1: it reaches W replicas before we acknowledge (the rest lag behind)
for i in random.sample(range(N), W):
replicas[i] = 1
# Read: ask R random replicas, keep the highest version seen
return max(replicas[i] for i in random.sample(range(N), R))
print(" W R W+R>N stale reads / 10,000")
for W, R in [(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (1, 3)]:
stale = sum(trial(W, R) == 0 for _ in range(10_000))
print(f" {W} {R} {str(W + R > N):5} {stale:>6,}")W R W+R>N stale reads / 10,000 1 1 False 6,723 1 2 False 3,345 2 1 False 3,331 2 2 True 0 3 1 True 0 1 3 True 0
With N = 3, the classic choice is W = 2, R = 2: it tolerates one node down for both reads and writes. W = 1, R = 1 is fast and highly available but serves stale data constantly. Stale replicas are repaired by read repair (the coordinator writes back the newest version it saw) and anti-entropy (background Merkle-tree comparisons). Caveats worth saying aloud: quorums do not give you transactions or linearizability on their own, concurrent writes still need versioning (vector clocks or last-write-wins), and sloppy quorums with hinted handoff trade the overlap guarantee for availability. The key-value store lesson builds this in full.
| Leader-follower | Multi-leader | Leaderless | |
|---|---|---|---|
| Accepts writes | One node | One per region/site | Any replica |
| Write conflicts | None | Yes — must resolve | Yes — versioning + repair |
| Write availability | Lost during failover | High, per region | High (any W nodes) |
| Consistency | Strong on leader, lagging on followers | Eventual across regions | Tunable per request |
| Examples | Postgres, MySQL, MongoDB, Redis | MySQL group/circular, CouchDB, Active Directory | Cassandra, ScyllaDB, Riak, DynamoDB |
Step 5 — CAP and PACELC, stated correctly
CAP says: when a network partition separates replicas, a system must choose between consistency (every read sees the latest write, or gets an error) and availability (every request to a live node gets a non-error response, possibly stale). Partitions are not optional in a distributed system — cables get cut, switches reboot — so the real choice is "CP or AP during a partition".
- CP example: a bank ledger on a Raft-replicated store. The minority side of a partition refuses writes (and linearizable reads) until it can reach a majority. Users on that side see errors — correct, because two sides both approving withdrawals is worse.
- AP example: a shopping cart on Dynamo-style storage. Both sides keep accepting "add to cart"; when the partition heals, carts are merged (the union of items). A deleted item might reappear — an accepted, cheap anomaly.
PACELC completes the picture: if Partitioned, choose A or C; Else (normal operation), choose Latency or Consistency. This is the trade you face every day, not just during outages: a synchronous cross-region write costs 100 ms on every request. Cassandra with ONE is PA/EL; Spanner is PC/EC; Postgres with async replicas is effectively PC/EL for leader reads and stale for follower reads.
Wrong answer to avoid: "I will pick CA." A CA system is one that never partitions — a single node. The moment you add a replica over a network you are choosing between C and A for partitions. And the choice is per feature, not per company: balances CP, like counts AP.
Step 6 — Partitioning (sharding): splitting data across machines
Replication copies all the data everywhere; it helps reads but not writes or total size. When one leader cannot absorb the write rate, or the data no longer fits on one machine, you partition: each node owns a subset. Delay this as long as you reasonably can — sharding is a one-way door that makes every later feature harder — but put the future shard key on every row from day one.
Partitioning methods
Worked example throughout: a photo-sharing app with users, photos, follows and comments, 300M users and 20B photos.
- Horizontal partitioning (sharding) — different rows of the same table on different nodes. Photos for users 0–9,999,999 on shard 0, and so on (or by hash). The schema is identical on every shard. This is what "sharding" usually means and the only method that scales a single huge table.
- Vertical partitioning — different tables (or columns) on different nodes: profiles on one database, the follow graph on another, photo metadata on a third. It is really "split by feature", and it lines up with service boundaries. Easy and low-risk — but each piece can still outgrow one node (20B photo rows will), so it delays sharding rather than replacing it. The column variant moves rarely read, bulky columns (a 50 KB
bio_html) to a side table so the hot table stays small. - Directory-based partitioning — a lookup service stores
key → shardexplicitly. Any mapping is possible: move one user, give a celebrity their own shard, rebalance gradually. The directory becomes a critical dependency (cache it in every app server, replicate it) and one more hop.
Partitioning criteria: how a key picks its partition
| Criterion | How | Good for | Breaks when |
|---|---|---|---|
| Range | Contiguous key ranges: A–F, G–M…, or by date | Range scans ("orders in March"), time-ordered data, easy splitting of a range | Keys are skewed or monotonic: with a timestamp key every write hits the newest range |
| Hash (mod N) | hash(key) % N | Even spread of random point lookups | N changes: almost every key moves (see below). Range scans become scatter-gather |
| List | Explicit value lists: EU countries → shard 3 | Data residency (GDPR), region-local workloads | One list value is enormous |
| Round-robin | Row i → partition i mod N | Bulk loads and parallel analytics scans | You need to find a row by key — every partition must be asked |
| Consistent hashing | Keys and nodes on a hash ring; key goes to next node clockwise | Clusters that grow and shrink (caches, Dynamo-style stores) | Needs virtual nodes for balance; range scans still scatter |
| Composite | e.g. list by region, then hash within region | Residency plus even spread; tenant then entity | Complexity; more for the router to know |
Worked example: why mod N hurts, and what fixes it
import bisect, hashlib
from collections import Counter
def h(s): # stable across runs (Python's hash() is salted)
return int(hashlib.md5(s.encode()).hexdigest()[:12], 16)
KEYS = [f"user:{i}" for i in range(100_000)]
# --- Strategy 1: hash mod N ---
def mod_n(key, n):
return h(key) % n
moved = sum(mod_n(k, 4) != mod_n(k, 5) for k in KEYS)
print(f"mod-N, 4 -> 5 nodes: {moved / len(KEYS):6.1%} of keys move")
# --- Strategy 2: consistent hashing ring with virtual nodes ---
class Ring:
def __init__(self, nodes, vnodes):
self.vnodes, self.points = vnodes, [] # sorted list of (position, node)
for n in nodes:
self.add(n)
def add(self, node):
for v in range(self.vnodes):
bisect.insort(self.points, (h(f"{node}#{v}"), node))
def owner(self, key):
i = bisect.bisect(self.points, (h(key), "")) % len(self.points)
return self.points[i][1] # first point clockwise from the key
for vnodes in (1, 100):
ring = Ring(["A", "B", "C", "D"], vnodes)
before = {k: ring.owner(k) for k in KEYS}
load = Counter(before.values())
ring.add("E")
moved = sum(before[k] != ring.owner(k) for k in KEYS)
spread = max(load.values()) / min(load.values())
print(f"ring, {vnodes:>3} vnode(s), 4 -> 5 nodes: {moved / len(KEYS):6.1%} of keys move; "
f"busiest/idlest node before = {spread:.2f}x")
# --- Strategy 3: fixed logical partitions, reassigned whole ---
P = 1024 # chosen once, never changes
assign = {p: "ABCD"[p % 4] for p in range(P)}
def owner_fixed(key):
return assign[h(key) % P]
before = {k: owner_fixed(k) for k in KEYS}
for p in range(0, P, 5): # new node E takes every 5th partition
assign[p] = "E"
moved = sum(before[k] != owner_fixed(k) for k in KEYS)
print(f"1024 fixed partitions, add E: {moved / len(KEYS):6.1%} of keys move "
f"({sum(v == 'E' for v in assign.values())} partitions copied to E)")mod-N, 4 -> 5 nodes: 79.8% of keys move ring, 1 vnode(s), 4 -> 5 nodes: 17.3% of keys move; busiest/idlest node before = 41.60x ring, 100 vnode(s), 4 -> 5 nodes: 19.6% of keys move; busiest/idlest node before = 1.06x 1024 fixed partitions, add E: 20.3% of keys move (205 partitions copied to E)
Going from 4 to 5 nodes with hash % N moves 80% of keys — for a cache that is a near-total miss storm, for a database it is copying 80% of your data. The minimum possible is 20% (the new node's fair share). A consistent-hash ring achieves close to that, but with one point per node the load is wildly uneven (the busiest node owns 40x the idlest's share); virtual nodes (100–256 points per physical node) even it out to within a few percent and let a bigger machine take more points. The third approach — a fixed number of logical partitions (1024 here) mapped to nodes by a table — is what Elasticsearch, Couchbase, Riak and most sharded SQL setups (Vitess keyspaces, Citus shards) actually use: whole partitions move, the key-to-partition function never changes, and it doubles as a simple directory.
Choosing a shard key
- Align with the dominant query. If 95% of queries say
WHERE tenant_id = ?, shard by tenant; those queries touch exactly one shard, keep their joins and transactions local, and scale linearly. - High cardinality.
countryhas ~200 values and one of them is huge;user_idhas hundreds of millions. - Even frequency. A key with a few very hot values (a celebrity, a default tenant) concentrates load.
- Not monotonic if you range-partition — auto-increment ids and timestamps put every insert on the last shard. Hash them, or prefix them.
- Immutable. Changing a row's shard key means moving it between machines.
Secondary indexes on sharded data come in two flavours. A local index lives on each shard and covers only that shard's rows: writes are cheap, but a query by the indexed column must ask every shard (scatter-gather). A global index is itself partitioned by the indexed value: reads hit one index shard, but each write now updates two places, usually asynchronously (DynamoDB global secondary indexes are eventually consistent for exactly this reason).
Step 7 — The problems sharding creates
Cross-shard joins and denormalisation
"Show a photo with its owner's name and avatar" joins photos (sharded by owner) with users. If the viewer's feed contains photos from 300 users on 64 shards, a join means 64 queries plus merging in the app. The standard fixes: denormalise (copy owner_name and owner_avatar onto the photo row, updated asynchronously when a user edits their profile), co-locate related tables on the same shard key (photos and comments both sharded by photo_owner_id), keep small reference tables replicated to every shard (countries, currencies), and push reporting to a warehouse. Denormalisation means accepting that a renamed user's old name lingers on some photos for a few seconds.
Referential integrity
Foreign keys cannot span databases. A comment on shard 7 referencing a photo on shard 12 cannot be protected by REFERENCES. The application must check on write, deletes must cascade via events ("photo deleted" → comment service removes its rows), and a periodic job finds and cleans dangling references. Design so that most invariants are within one shard key and you will need very little of this.
Rebalancing
Shards grow unevenly and traffic shifts, so data must move while the system is live. Moving a partition safely: start copying a snapshot to the new node, stream changes made during the copy (the change log), briefly block or dual-write the partition, verify, flip the routing entry, then delete the old copy. That is why the fixed-partitions approach (move whole partitions, never re-hash) and directory-based mappings dominate: they make each move small and independent. Never let rebalancing run automatically on a fast trigger — a node that is merely slow can cause a cascade of moves that makes everything slower.
Hot partitions and the celebrity problem
Even a perfect hash spreads keys evenly, not traffic. One key can be hot: a celebrity's post receiving 90k likes per second, a flash-sale product, the single "global" counter. Hashing does not help — one key always lands on one shard.
import hashlib
from collections import Counter
def shard(key, n=8):
return int(hashlib.md5(key.encode()).hexdigest(), 16) % n
# A celebrity post gets 90,000 like-writes/s; 10,000 other posts share 10,000/s.
writes = ["post:celebrity:likes"] * 90_000 + [f"post:{i}:likes" for i in range(10_000)]
load = Counter(shard(k) for k in writes)
print("unsalted per-shard writes/s:", [load[s] for s in range(8)])
# Salting: spread ONE logical counter over 64 physical sub-keys.
# (With only 8-16 sub-keys, hashing them onto 8 shards is itself lumpy.)
SALT = 64
def salted(key, i):
return f"{key}#{i % SALT}" if key == "post:celebrity:likes" else key
load = Counter(shard(salted(k, i)) for i, k in enumerate(writes))
print("salted per-shard writes/s:", [load[s] for s in range(8)])
# The price: a read of the celebrity counter must now gather 16 sub-keys.
counters = Counter(salted(k, i) for i, k in enumerate(writes))
total = sum(counters[f"post:celebrity:likes#{i}"] for i in range(SALT))
print(f"read = sum of {SALT} sub-keys = {total:,} likes")unsalted per-shard writes/s: [1233, 1207, 1294, 1284, 1270, 1260, 1224, 91228] salted per-shard writes/s: [12484, 8238, 12543, 13941, 12520, 9698, 18100, 12476] read = sum of 64 sub-keys = 90,000 likes
Salting (splitting one logical key into many physical sub-keys) turns one 91k-writes/s shard into eight shards at 8–18k each; reads pay by summing 64 sub-keys, which is fine for a count that is read far less often than it is written, or cached. Other tools: detect and isolate hot tenants onto dedicated shards (directory mapping), absorb writes in memory and flush aggregates every second (Redis INCR, then batch to the DB), and for fan-out problems, treat celebrities differently — the news feed lesson pulls celebrity posts at read time instead of pushing them to 100M timelines.
Cross-shard transactions and queries
A transfer between two users on different shards is no longer one local transaction — see Step 9. Queries that do not include the shard key ("all orders over $1,000 today") hit every shard, so their latency is the slowest shard's latency. Keep them off the request path.
Step 8 — Transactions and isolation levels
ACID in one line each: Atomicity — all of the transaction's writes happen or none do (abort is always safe). Consistency — the application's invariants hold before and after (mostly your job; constraints help). Isolation — concurrent transactions do not see each other's partial work; how strictly is the isolation level. Durability — once committed, it survives a crash (the write-ahead log is fsynced, and replicated if you configured it).
Isolation is where real bugs live, because the default level in most databases is weaker than people assume. Each anomaly below is a real bug class with a concrete interleaving:
-- Each anomaly as two sessions (T1, T2) interleaved in time, top to bottom.
-- 1. DIRTY READ (allowed only by READ UNCOMMITTED)
T1: BEGIN; UPDATE accounts SET balance = balance - 500 WHERE id = 1;
T2: SELECT balance FROM accounts WHERE id = 1; -- sees the -500
T1: ROLLBACK; -- T2 acted on money that never moved
-- 2. NON-REPEATABLE READ (allowed by READ COMMITTED, the Postgres default)
T1: BEGIN; SELECT price FROM items WHERE id = 7; -- 100
T2: UPDATE items SET price = 120 WHERE id = 7; COMMIT;
T1: SELECT price FROM items WHERE id = 7; -- 120: same query, new answer
T1: -- an invoice built from both reads is internally inconsistent
-- 3. PHANTOM READ (a new ROW appears that matches an earlier predicate)
T1: BEGIN; SELECT count(*) FROM bookings WHERE room = 5 AND day = '2026-10-01'; -- 0
T2: INSERT INTO bookings(room, day) VALUES (5, '2026-10-01'); COMMIT;
T1: INSERT INTO bookings(room, day) VALUES (5, '2026-10-01'); COMMIT;
-- double-booked: row locks cannot lock a row that did not exist yet
-- fix: a UNIQUE (room, day) constraint, or SERIALIZABLE
-- 4. LOST UPDATE (read-modify-write in app code; see the Python below)
T1: SELECT stock FROM items WHERE id = 7; -- 2
T2: SELECT stock FROM items WHERE id = 7; -- 2
T1: UPDATE items SET stock = 1 WHERE id = 7; COMMIT;
T2: UPDATE items SET stock = 1 WHERE id = 7; COMMIT; -- should be 0
-- fixes: SET stock = stock - 1 | SELECT ... FOR UPDATE | version column CAS
-- 5. WRITE SKEW (two txns read overlapping data, write DIFFERENT rows)
T1: SELECT count(*) FROM doctors WHERE on_call; -- 2, so "I can leave"
T2: SELECT count(*) FROM doctors WHERE on_call; -- 2, so "I can leave"
T1: UPDATE doctors SET on_call = false WHERE name = 'alice'; COMMIT;
T2: UPDATE doctors SET on_call = false WHERE name = 'bob'; COMMIT;
-- nobody on call. Snapshot isolation does NOT prevent this.
-- fixes: SERIALIZABLE, or SELECT ... FOR UPDATE on the rows you counted| Level | Dirty read | Non-repeatable read | Phantom | Lost update | Write skew | Default in |
|---|---|---|---|---|---|---|
| Read uncommitted | Possible | Possible | Possible | Possible | Possible | Rarely used |
| Read committed | Prevented | Possible | Possible | Possible | Possible | Postgres, Oracle, SQL Server |
| Repeatable read / snapshot isolation | Prevented | Prevented | Prevented in Postgres; possible in MySQL for locking reads | Postgres aborts one; MySQL allows it for plain SELECT-then-UPDATE | Possible | MySQL InnoDB |
| Serializable | Prevented | Prevented | Prevented | Prevented | Prevented | CockroachDB, Spanner (strict), FoundationDB |
Worked example: the lost update and its three fixes
# Two checkout requests for the last 2 units of stock, interleaved step by step.
db = {"stock": 2, "version": 0}
# --- Anti-pattern: read-modify-write in application code ---
db["stock"] = 2
a = db["stock"] # T1 reads 2
b = db["stock"] # T2 reads 2 (before T1 writes)
db["stock"] = a - 1 # T1 writes 1
db["stock"] = b - 1 # T2 writes 1 -- T1's decrement is lost
print("read-modify-write: stock =", db["stock"], "(2 units sold, 1 deducted)")
# --- Fix 1: atomic update in the database ---
# UPDATE items SET stock = stock - 1 WHERE id = ? AND stock > 0
def atomic_decrement():
if db["stock"] > 0: # the row lock makes check + write one indivisible step
db["stock"] -= 1
return True
return False
db["stock"] = 2
print("atomic UPDATE: ", [atomic_decrement() for _ in range(3)], "stock =", db["stock"])
# --- Fix 2: optimistic concurrency (compare-and-set on a version column) ---
# UPDATE items SET stock = ?, version = version + 1 WHERE id = ? AND version = ?
def cas(expected_version, new_stock):
if db["version"] != expected_version:
return False # 0 rows updated: someone else got there first
db["stock"], db["version"] = new_stock, db["version"] + 1
return True
db.update(stock=2, version=0)
s1, v1 = db["stock"], db["version"] # T1 reads (2, v0)
s2, v2 = db["stock"], db["version"] # T2 reads (2, v0)
print("T1 CAS:", cas(v1, s1 - 1)) # succeeds -> (1, v1)
print("T2 CAS:", cas(v2, s2 - 1), "-> T2 re-reads and retries")
s2, v2 = db["stock"], db["version"]
print("T2 CAS retry:", cas(v2, s2 - 1), " final stock =", db["stock"])read-modify-write: stock = 1 (2 units sold, 1 deducted) atomic UPDATE: [True, True, False] stock = 0 T1 CAS: True T2 CAS: False -> T2 re-reads and retries T2 CAS retry: True final stock = 0
Prefer the atomic UPDATE ... SET stock = stock - 1 WHERE stock > 0 whenever the logic fits in one statement — it is correct at every isolation level. Use optimistic version checks when the change is computed in application code and conflicts are rare (edits to a document). Use SELECT ... FOR UPDATE when conflicts are frequent and retries would be wasteful, keeping the transaction short.
Worked example: write skew, which snapshot isolation does not stop
# Rule: at least one doctor must stay on call. Alice and Bob both feel unwell
# and click "go off call" at the same moment.
committed = {"alice": True, "bob": True}
def request_off_call(me, snapshot):
on_call = sum(snapshot.values())
if on_call >= 2: # "someone else is still covering"
return {me: False} # the write this transaction wants to make
return {}
# SNAPSHOT ISOLATION (Postgres REPEATABLE READ, Oracle "serializable"):
# both transactions read the same snapshot and write DIFFERENT rows,
# so there is no write-write conflict and both commit.
snap = dict(committed)
w_alice = request_off_call("alice", snap)
w_bob = request_off_call("bob", snap)
si = dict(committed); si.update(w_alice); si.update(w_bob)
print("snapshot isolation:", si, "-> doctors on call:", sum(si.values()))
# SERIALIZABLE: the result must equal SOME serial order. Run them one after
# the other (what 2PL or SSI effectively forces; SSI aborts one and you retry).
ser = dict(committed)
for me in ("alice", "bob"):
ser.update(request_off_call(me, dict(ser)))
print("serializable: ", ser, "-> doctors on call:", sum(ser.values()))snapshot isolation: {'alice': False, 'bob': False} -> doctors on call: 0
serializable: {'alice': False, 'bob': True} -> doctors on call: 1
Write skew is the anomaly that bites teams who think "we use repeatable read, we are safe". Each transaction reads a set of rows, makes a decision, and writes a different row, so no write-write conflict is ever detected. Other real instances: two people booking the last meeting room slot via a "count overlapping bookings" check, two users claiming the same username checked via SELECT, a balance spread over two accounts where the rule is "total must stay positive". Fixes: SERIALIZABLE (Postgres implements it with SSI, which detects the dangerous pattern and aborts one transaction — your code must retry), explicitly locking the rows you read with FOR UPDATE, or materialising the conflict as a row both transactions must update or a UNIQUE constraint.
Step 9 — Distributed transactions: 2PC versus sagas
Once the rows of one business action live in different databases (different shards or different services), there is no single COMMIT. Two approaches exist.
Two-phase commit (2PC)
Phase 1 asks every participant to promise it can commit, holding locks. Phase 2 tells them the outcome. If the coordinator dies between the phases, prepared participants are stuck holding locks.
2PC gives real atomicity across nodes. Its costs: at least two extra round trips per transaction, locks held across the network for the duration, and a blocking failure mode — a participant that voted YES cannot decide on its own if the coordinator disappears, so it holds its locks until the coordinator recovers. Databases that do this internally (Spanner, CockroachDB, Vitess, XA in Postgres/MySQL) replicate the coordinator's state with consensus to remove that single point of failure. Across services owned by different teams, or with external APIs (a payment provider cannot "prepare"), 2PC is not available at all.
Sagas
A saga splits the action into a sequence of local transactions, each committed on its own, with a compensating action for each step that semantically undoes it if a later step fails. There is no isolation: other requests can see the intermediate state (stock reserved but payment not yet taken), so you design for it with states like PENDING.
log = []
def step(name, fail=False):
def run(order):
if fail:
raise RuntimeError(f"{name} failed")
log.append(f" do {name}")
return run
def undo(name):
return lambda order: log.append(f" comp {name}")
def run_saga(order, steps):
done = []
for action, compensate in steps:
try:
action(order)
done.append(compensate)
except RuntimeError as e:
log.append(f" !! {e}; compensating in reverse")
for c in reversed(done):
c(order) # each compensation must itself be idempotent + retried
return "CANCELLED"
return "CONFIRMED"
def order_saga(courier_ok):
return [
(step("reserve stock"), undo("release stock")),
(step("authorise payment"), undo("void authorisation")),
(step("assign courier", fail=not courier_ok), undo("unassign courier")),
(step("confirm order"), undo("n/a")),
]
for ok in (True, False):
log.clear()
result = run_saga({"id": 88231}, order_saga(courier_ok=ok))
print(f"courier available={ok}: {result}")
print("\n".join(log))courier available=True: CONFIRMED do reserve stock do authorise payment do assign courier do confirm order courier available=False: CANCELLED do reserve stock do authorise payment !! assign courier failed; compensating in reverse comp void authorisation comp release stock
- Orchestration — a central saga coordinator (a workflow engine such as Temporal, AWS Step Functions, or your own state machine table) calls each step and its compensation. Easy to follow and monitor; the orchestrator's state must be durable.
- Choreography — each service reacts to events ("stock reserved" → payment service charges → "payment captured" → dispatch …). Loosely coupled, but the flow exists only as the sum of subscriptions and becomes hard to reason about beyond three or four steps.
- Compensations are not rollbacks. You cannot un-send an email; you send an apology. A refund is a new transaction, not the deletion of a charge. Each step and compensation must be idempotent because it will be retried. Publishing the events reliably needs the transactional outbox, covered in Lesson 5.
| 2PC | Saga | |
|---|---|---|
| Atomicity | Real, all-or-nothing | Eventual, via compensation |
| Isolation | Yes (locks) | None — intermediate states are visible |
| Latency | Extra round trips, locks held | Each step commits immediately |
| Failure behaviour | Can block on coordinator loss | Always progresses; may compensate |
| Works across services / external APIs | No | Yes |
| Use when | Inside one distributed database (shards of one system) | Business workflows spanning services: orders, bookings, onboarding |
The best option is often neither: choose the shard key so the transaction is local. If a wallet's balance and its ledger entries share wallet_id, a payment between two wallets is the only cross-shard case left, and it can be modelled as a saga of two ledger entries with a pending state.
Step 10 — Picking a database for five workloads
Size each workload first; the numbers make most of the decision.
DAY = 86_400
# 1. Payments ledger: 5M orders/day, 2 double-entry rows each, 10x peak
ledger_peak = 5e6 * 2 / DAY * 10
ledger_tb_year = 5e6 * 2 * 300 * 365 / 1e12
print(f"1 ledger: {ledger_peak:,.0f} writes/s peak, {ledger_tb_year:.1f} TB/year")
# 2. Product catalogue + search: 50M products, 4 KB each, 30k searches/s
print(f"2 catalogue: {50e6 * 4e3 / 1e9:,.0f} GB of documents, 30,000 searches/s")
# 3. Sessions + leaderboard: 10M concurrent sessions, 1 KB each, 15 ops/s per 1k users
print(f"3 sessions: {10e6 * 1e3 / 1e9:,.0f} GB in RAM, {10e6 / 1000 * 15:,.0f} ops/s")
# 4. Device metrics: 2M devices x 20 metrics every 10 s
pts = 2e6 * 20 / 10
raw_tb = pts * DAY * 16 / 1e12 # 8-byte timestamp + 8-byte float
compressed_gb = pts * DAY * 1.4 / 1e9 # delta-of-delta + XOR float compression
print(f"4 metrics: {pts:,.0f} points/s, {raw_tb:.1f} TB/day raw, "
f"~{compressed_gb:,.0f} GB/day compressed")
# 5. Social graph: 500M users, 200 friends on average
edges = 500e6 * 200
print(f"5 graph: {edges:,.0f} directed edges (~{edges * 16 / 1e12:.1f} TB), "
f"friends-of-friends for one user = {200 * 200:,} candidates")1 ledger: 1,157 writes/s peak, 1.1 TB/year 2 catalogue: 200 GB of documents, 30,000 searches/s 3 sessions: 10 GB in RAM, 150,000 ops/s 4 metrics: 4,000,000 points/s, 5.5 TB/day raw, ~484 GB/day compressed 5 graph: 100,000,000,000 directed edges (~1.6 TB), friends-of-friends for one user = 40,000 candidates
1. Payments ledger for an e-commerce platform
Pick: PostgreSQL (or MySQL), one primary + a synchronous replica + async read replicas. 1,200 writes/s and about 1 TB/year fit comfortably on one primary for years. Model it as an append-only double-entry ledger (entries(id, account_id, amount_minor, txn_id), balances derived or maintained atomically in the same transaction), with UNIQUE(idempotency_key) and CHECK constraints. Balance-affecting reads go to the primary. Why not Cassandra or MongoDB: you would give up multi-row transactions and constraints — the entire point of a ledger — to solve a scale problem you do not have. Revisit with Citus/Vitess or Spanner/CockroachDB when writes approach tens of thousands per second, sharding by account_id.
2. Product catalogue with faceted search
Pick: a document store or Postgres JSONB as the source of truth, plus Elasticsearch/OpenSearch for search, fed by CDC. 50M products with wildly different attributes (a TV has "screen size", a shirt has "fit") suit documents. Search needs relevance ranking, typo tolerance, synonyms and facet counts ("Brand: Sony (214)") at 30k queries/s — an inverted index's job, not a B-tree's. Changes flow from the primary store via Debezium/Kafka into the index within a second or two; product pages read by id from the primary store behind a cache. Wrong answer: LIKE '%tv%' on Postgres (a full scan, no relevance), or Elasticsearch as the only copy (reindexing, mapping changes and split-brain history make it a poor source of truth).
3. Sessions, rate limits and a live leaderboard
Pick: Redis (clustered, with a replica per shard). 10 GB fits in RAM; 150k ops/s is a few Redis shards. Sessions are SETEX session:<id> 1800 ... (TTL does expiry for free), rate limits are INCR + EXPIRE or a Lua token bucket (see the rate limiter lesson), the leaderboard is a sorted set (ZINCRBY, ZREVRANGE 0 99 in O(log n)). Accept: losing a node may lose the last second of writes — fine for sessions (users log in again) and counters, not fine for money. If you need durability at this latency, DynamoDB is the managed alternative.
4. Metrics from 2 million devices
Pick: a time-series or columnar store — TimescaleDB, InfluxDB, ClickHouse, or Prometheus + Thanos/Mimir for monitoring. 4M points/s and 5.5 TB/day raw is far beyond an OLTP database, but time-series engines compress timestamps (delta-of-delta) and floats (XOR) to around 1.4 bytes per point, turning it into under 500 GB/day. Partition by time (daily chunks), keep raw data 7 days, 1-minute rollups for 90 days and hourly rollups forever, and drop old chunks by deleting whole files instead of millions of rows. Ingest through Kafka so a slow database does not drop device data. Wrong answer: Postgres with one row per point and a B-tree on (device_id, ts) — the index alone would not keep up with 4M inserts/s.
5. "People you may know" on a 500M-user social graph
Pick: store the graph as sharded adjacency lists (by user id) in a wide-column or sharded SQL store, and compute recommendations offline; use a graph database for interactive, bounded traversals. 100B edges (1.6 TB) is too big for one graph-database machine, and a two-hop query from one user already touches 40,000 nodes — at 20k requests/s that is 800M edge reads per second. So candidates are computed in batch (Spark: friends-of-friends counts, ranked), stored per user, and served as a key lookup. A graph database (Neo4j, Neptune) is the right tool for exploratory, deeper traversals on a bounded subgraph — fraud-ring detection over a few million accounts, or an access-control hierarchy. Wrong answer: a recursive SQL self-join on a 100B-row follows table at request time.
The trade-off summary — how to talk about databases in an interview
- Default to a relational database and say why you are leaving it for each workload that does: a write rate, a data size, a query shape, or a latency the numbers prove.
- Index for the queries you run, composite in the right column order, and remember every index is paid for on every write.
- Replicate before you shard. Replicas give availability and read scale; sharding is the expensive step for write scale and size. Name your replication mode and what you lose on failover.
- Handle replication lag explicitly: read-your-writes via leader reads or LSN tokens, monotonic reads via sticky followers.
- Choose a shard key from the dominant query, high cardinality, non-monotonic; plan for hot keys; move whole logical partitions rather than re-hashing.
- Know your isolation level and the anomaly it allows; use atomic updates, version checks or locks deliberately.
- Avoid distributed transactions by design; when you cannot, use 2PC inside one database and sagas across services.
- CP or AP is a per-feature decision, and PACELC reminds you that latency is the everyday cost of consistency.
// Write your solution here
// Write your solution here
// Write your solution here
// Write your solution here
Finished reading? Mark this lesson complete to track your progress.
