Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover (Deep Dive)

Every database decision in a system-design interview reduces to the same question: what does the engine actually do on disk, and what does that cost you — a page write, a compaction pass, a network round trip to a quorum. This page derives the numbers instead of asserting them: how many disk pages a B-tree lookup touches, how write amplification scales with index count, why snapshot isolation still lets an invariant break, and exactly what happens, second by second, when a leader dies mid-write.

1. Isolation levels & anomalies, derived

An isolation level is defined by which anomalies it refuses to let a concurrent schedule produce. Five anomalies matter:

• Dirty read — transaction A reads a row transaction B wrote but has not committed; if B rolls back, A read a value that never existed.
• Non-repeatable read — A reads the same row twice in one transaction and gets two different values because B committed an update to it in between.
• Phantom — A re-runs the same WHERE query twice and gets a different set of rows because B inserted or deleted a matching row in between.
• Lost update — A and B both read-modify-write the same row from the same starting value; the second write silently overwrites the first's effect instead of building on it.
• Write skew — A and B each read an overlapping snapshot, each writes a different row based on what they read, and the combination violates an invariant that spanned both rows. No single row was overwritten, so it is invisible to any check that only looks for write-write conflicts.

Isolation level	Mechanism	Dirty read	Non-repeatable read	Phantom	Lost update	Write skew
Read Committed	fresh snapshot per statement; never reads uncommitted rows	prevented	allowed	allowed	allowed	allowed
Repeatable Read / Snapshot Isolation	one snapshot per transaction, fixed at first read; readers never block writers	prevented	prevented	usually prevented	prevented (first-committer-wins abort on the same row)	allowed
Serializable (true, e.g. PostgreSQL SSI)	tracks read/write dependencies across transactions; aborts one side of a dangerous cycle	prevented	prevented	prevented	prevented	prevented

Why Snapshot Isolation still allows write skew: SI's whole mechanism is "give every transaction a consistent point-in-time view and let it write without blocking readers." That mechanism only detects a conflict when two transactions touch the same row — a lost update. Write skew's two transactions touch different rows, each individually consistent with the snapshot each transaction read, so SI has nothing to flag. Only true serializability, which reasons about the transactions' read/write dependency graph rather than row-level overlap, catches it. This exact anomaly — two on-call doctors each independently signing off because the snapshot showed "2 on call," leaving zero — is traced in full in the companion deep-dive "Write Skew, Lost Update & Snapshot Isolation"; the isolation-level table above is the piece that page assumes.

2. B-tree read cost — derived from disk pages, not asserted

Mechanism: a B-tree node is one disk page holding a sorted array of keys; every level you descend is exactly one page read, because a page's children are laid out so you can binary-search a page in memory and jump straight to the one child that must contain your key. Cost is therefore levels = ⌈log_fanout(rows)⌉ page reads for a cold lookup.

Traced example. A page is ~8 KB; a key+pointer pair is ~16 bytes, so one page holds 8192 / 16 ≈ 500 children — the fanout. For 1 billion rows:

Level	Rows reachable (fanout^level)	>= 1,000,000,000 ?
1 (root)	500	no
2	250,000	no
3	125,000,000	no
4 (leaf)	62,500,000,000	yes

So log_500(1e9) = 3.33, rounded up to 4 levels ⟹ 4 page reads worst case for any row in a billion-row table. In practice the root (1 page) and level 2 (≤500 pages, a few MB) sit permanently in the buffer pool cache, so a warm lookup costs only the last 1–2 levels as real disk I/O — the "~4 I/O, top levels cached" rule of thumb falls straight out of this arithmetic.

3. LSM-tree write path, compaction, and write amplification

Mechanism: instead of finding and rewriting a page in place, an LSM-tree makes every write cheap and sequential, then pays the cost back later in the background. The diagram traces both engines' write path side by side:

Two details the diagram compresses:

• WAL before memtable. The write is durable the instant it's fsynced to the write-ahead log / commit log — before it ever touches the memtable or an SSTable. If the process crashes with data only in the (volatile) memtable, recovery replays the WAL, not the memtable; this is what makes an LSM engine safe to ack a write the moment the log fsync returns.
• Compaction is not optional housekeeping — it's back-pressure. Flushes create new SSTables faster than compaction can merge them under sustained write load; when the compaction queue backs up, the engine deliberately stalls or throttles incoming writes rather than let read amplification (too many small SSTables to check per read) grow unbounded. During a compaction pass the old SSTables being merged and the new merged SSTable(s) they're becoming both exist on disk at once — a transient ~2x space amplification that must be budgeted, not just the steady-state size.
• Tombstones and resurrection. A delete doesn't remove bytes, it writes a tombstone marker; compaction only purges the tombstone (and the data it shadows) after gc_grace_seconds. If a replica was down longer than gc_grace_seconds and missed the delete, and the tombstone is purged on the healthy replicas before that replica resyncs, anti-entropy can propagate the replica's stale, pre-delete value back in — the deleted row resurrects. The fix is mechanical: gc_grace_seconds must exceed the longest realistic node-down time, or repair must run first.
• Write amplification scales with index count. A single LSM structure under leveled compaction typically rewrites each byte ~10–30x over its lifetime as it's merged down through levels (call it WA_base). Every secondary index is its own compacted structure, so one logical write fans out into 1 + S compacted writes for S secondary indexes: total write amplification ≈ WA_base × (1 + S). With WA_base = 10 and 3 secondary indexes: 10 × 4 = 40x — a 100-byte logical write costs ~4 KB of actual disk writes over time. This is the concrete reason write-optimized engines discourage piling on secondary indexes.

	B-tree	LSM-tree
Optimized for	reads / point lookups / range scans	writes / ingest
Write cost	random page write + possible split	sequential append; cost deferred to compaction
Read cost	one tree walk (~log_fanout(rows))	check newest→oldest SSTable, Bloom-filtered
Used by	PostgreSQL, MySQL/InnoDB	Cassandra, RocksDB, ScyllaDB

4. Query join planning & index judgment

Mechanism: a cost-based planner estimates the row counts and available indexes on both sides of a join and picks whichever algorithm minimizes estimated page reads — it is not free to pick its favorite.

• Nested loop — for each outer row, probe the inner side. Cost ≈ outer_rows × cost_of_one_inner_probe. Wins when the outer side is small (a selective filter already applied) and the inner side has a usable index, so each probe is a cheap B-tree lookup (§2's ~log_fanout(rows) reads) rather than a scan. Example: filtering Customers down to 1 row, then index-probing a 10-million-row Orders table on customer_id costs ≈ log_500(1e7) ≈ 2.6 → 3 page reads — trivially cheap.
• Hash join — build an in-memory hash table on the smaller side (cost ≈ its row count), then stream-probe the larger side (cost ≈ its row count). Total ≈ O(N + M), no index and no sort needed. Wins for large, non-selective equi-joins with no helpful index — e.g. joining all 10M orders to all 100K customers with no filter: nested loop would be ~10M probes; hash join is one linear pass over each side.
• Merge join — if both inputs are already sorted on the join key (from an index scan or a preceding ORDER BY), merge them in one linear pass, O(N + M), with almost no memory. Wins when that sortedness is already there "for free" — forcing a sort just to enable a merge join usually loses to a hash join.

Index judgment — when NOT to add an index:

• Write cost. Every index is another structure every INSERT/UPDATE/DELETE must maintain — more WAL, more page splits (B-tree) or more compacted structures (§3's write-amplification formula). An index that serves a rare query can cost more in write overhead than it ever saves in read latency.
• MVCC index bloat defeats HOT. Under MVCC (PostgreSQL), an UPDATE writes a new row version. If the new version fits on the same page and no indexed column changed, PostgreSQL can do a Heap-Only Tuple (HOT) update — patch the page in place, skip touching any index. The moment a column is indexed, any update to it (or a page-full eviction) forces a full index-entry write for every index on the table, not just the one on that column, defeating HOT and multiplying update cost. Indexing a column that is updated often but rarely queried is a classic self-inflicted regression.
• Partial & covering indexes. A partial index only indexes rows matching a predicate (e.g. WHERE status = 'active') — smaller, cheaper to maintain, and still useful because most queries only ever ask about active rows. A covering index includes extra non-key columns so the query can be answered from the index alone (an index-only scan), skipping the heap fetch entirely — the trade is index size for one fewer random I/O per row.
• Deliberate scan on low selectivity. A column with few distinct values (a boolean, a status enum with 3 states) touches a large fraction of the table for any single value; a sequential scan reading pages in order beats an index scan doing that many scattered random-access page reads. The planner's choice to ignore an index here is usually correct — forcing it is usually a regression.

5. Distributed database mechanics

Quorum (cross-reference). With N replicas, a write acked by W and a read from R: R + W > N forces the read and write sets to overlap on at least one replica, guaranteeing a read sees the latest acknowledged write; W > N/2 stops two concurrent writes from both reaching quorum. Full tuning table and the pigeonhole argument live in "Quorum Arithmetic — Why R + W > N" and "Quorum in Practice"; this page builds on that inequality rather than re-deriving it.

Replication lag (cross-reference). Async replication means a follower is always slightly behind the leader; reading from a lagging replica right after your own write makes your own change appear to vanish (read-your-writes violation). The fixes (route-to-leader briefly, pin a user to one replica, causal ordering) are covered in "Replication Lag & Failover — Read-Your-Writes, Split-Brain & Fencing." The rest of this section extends that page's failover mechanics with the concrete timeline below.

LWW-by-cell-timestamp hazard (Cassandra-style). Systems that resolve conflicts with per-cell Last-Write-Wins compare timestamps, not real time. If node A's clock runs 100ms fast, a write it accepts at true time 08:59:59.900 can carry a later timestamp than a write node B (correct clock) accepts at true time 09:00:00.000 — LWW picks A's write, silently discarding the one that actually happened last. There is no conflict error; the earlier-in-truth write simply wins and the other vanishes. This is a distinct failure mode from lost update (§1): there, the DB detects a same-row conflict and aborts one side; here, the DB never knows a conflict happened at all — the fix is NTP-disciplined clocks plus, where it matters, an application-level logical clock (e.g. a monotonic counter) instead of wall time.

Multi-leader / multi-region write-write conflicts (DynamoDB global tables). Each region accepts writes locally for low latency, then replicates to other regions asynchronously. Two regions can both accept a write to the same item concurrently; when replication reconciles, the default resolution is again LWW by timestamp — one region's update is silently discarded. Avoiding data loss here means either accepting LWW's trade-off (simple, occasionally lossy) or moving to application-level conflict resolution (vector clocks, CRDTs, or "last writer wins per field" with a real business rule) — the same conflict-resolution judgment call as quorum-based sibling resolution.

Traced example: async failover, second by second

t	Event
t0	Leader L accepts write W100, acks the client, begins async replication to F1/F2
t0 + 5ms	L crashes before W100 reaches any follower — the RPO window opens; F1's last replicated write is W99
t0 + 10s	Heartbeat timeout trips; a quorum election promotes F1 (majority of surviving replicas agree); F1's term/epoch bumps 41 → 42
t0 + 10.1s	Fencing: the storage layer / proxy now rejects any request carrying an epoch below 42 — if L reboots and tries to write as the "old" leader (epoch 41), it is rejected, preventing split-brain
t0 + 10.2s	Clients are redirected to F1. RPO = W100 (everything acked but not yet replicated at crash time) — bounded by the async replication lag, here ~5ms of writes

The fencing step is not optional decoration: without a monotonically increasing epoch that every read/write must present, a recovered "zombie" leader that still believes it's in charge can accept writes that conflict with the new leader's — actual split-brain, not just a theoretical risk.

Redis durability — two independent axes

Redis's "is my data safe" question has two separate answers that are easy to conflate:

• Persistence axis — AOF (append-only file logging every write command, fsync policy always/everysec/no trading durability for throughput) vs RDB (periodic point-in-time snapshot — fast to restart from, but loses everything since the last snapshot). This determines what survives a process restart.
• Availability axis — replica count (replication factor) plus Sentinel (or Redis Cluster) doing automated failover if the primary dies. This determines whether the service stays up, independent of whether writes are durable to disk.

These are orthogonal: you can have replicas with no persistence (survives a primary crash, but a full-cluster restart loses everything) or persistence with no replicas (survives a restart, but the primary is a single point of failure for availability). Production durability needs both axes covered — typically AOF everysec plus at least one replica under Sentinel/Cluster quorum.

Federation vs ETL-to-warehouse vs CDC vs service-API

Approach	Freshness	Best when	Cost
Database federation	live	cross-domain queries need current data and you control the sources' schemas	query availability now depends on every source being up; fan-out tail latency (below)
ETL to warehouse	batch (hours)	analytics/BI at scale, decoupled from OLTP load	stale by the batch window; not for operational reads
CDC (change data capture)	near-real-time (seconds)	you want low source load and low latency without a live federated query	connector/schema-evolution infra; eventual, not synchronous, consistency
Service API	live	domain ownership/encapsulation matters more than query flexibility	network hop per call; N+1 fan-out if the API doesn't expose the shape you need

Fan-out tail-latency amplification. A federated query hitting k sources in parallel is only as fast as the slowest one, and the odds that at least one is slow grow with k. If a single source has a 1% chance of a slow (>200ms) response, fanning out to k = 10 sources gives 1 − 0.99^10 ≈ 9.6% chance that at least one is slow — nearly 10x the single-source tail risk. This is why federated fan-out needs a per-source timeout with partial-result tolerance (return what answered by the deadline, flag what didn't) and a mediator that back-pressures — caps concurrent fan-out and sheds load — rather than opening unbounded parallel calls per incoming request.

6. A worked BCNF counterexample, and a one-line capacity estimate

The classic 3NF-but-not-BCNF case. Relation Teach(Student, Course, Instructor) with two functional dependencies:

1. {Student, Course} → Instructor — a student's instructor for a course is determined by the pair.
2. Instructor → Course — each instructor teaches only one course.

Because of FD 2, {Student, Instructor} is also a candidate key (knowing the student and the instructor pins down the course too). Course is therefore a prime attribute (part of a candidate key) — which is exactly why 3NF, which only forbids non-prime attributes depending on a non-superkey, lets this schema through. But BCNF forbids any determinant that isn't a superkey, and Instructor (the left side of FD 2) is not a superkey on its own — so the relation violates BCNF while satisfying 3NF.

Student	Course	Instructor
Alice	Databases	Prof. Kay
Bob	Databases	Prof. Kay
Alice	Networks	Prof. Lin

The transfer anomaly this produces: if Prof. Kay switches from teaching Databases to teaching Systems, every row mentioning Prof. Kay must be updated in lockstep (Alice's and Bob's). Miss one and the table now claims Prof. Kay teaches two different courses at once, contradicting FD 2 with no constraint mechanism to catch it. Decomposing to BCNF — StudentInstructor(Student, Instructor) and InstructorCourse(Instructor, Course), the latter with Instructor as its actual key — fixes the anomaly (the course lives in exactly one row per instructor) at the cost of no longer being able to enforce {Student, Course} → Instructor directly via a single relation's key (the classic BCNF-vs-3NF dependency-preservation trade-off).

Capacity estimate, one line at a time: 500M rows × ~1 KB average row ≈ 512 GB logical; with typical index/overhead of ~30%, budget ≈ 666 GB of storage. Separately, for IOPS: a peak of 10,000 QPS against a buffer pool with a 95% cache-hit rate means only the 5% miss rate ever reaches disk — ~500 physical IOPS to size storage against, not the raw 10,000 QPS figure people default to.

Pitfalls

• Assuming "REPEATABLE READ" is serializable — in PostgreSQL/MySQL it is snapshot isolation, and write skew slips straight through it.
• Sizing storage IOPS off raw QPS instead of the cache-miss rate — massively overprovisions or, worse, underprovisions if the working set doesn't fit the buffer pool assumed.
• Adding an index reflexively for every query pattern without weighing the write-side cost — especially the MVCC/HOT interaction, which is easy to miss because the regression shows up as slower UPDATEs, not slower reads.
• Setting gc_grace_seconds shorter than realistic node-downtime, silently resurrecting deleted data on the next anti-entropy repair.
• Trusting LWW-by-timestamp across machines without clock discipline — a fast clock can make an objectively older write "win."
• Unbounded fan-out to federated sources with no per-source timeout — one slow source stalls the entire aggregate response.

Judgment layer

B-tree vs LSM-tree. Choose B-tree when reads/scans dominate and you need in-place transactional updates with predictable latency (OLTP on Postgres/MySQL) — you pay write amplification and random I/O for that. Choose LSM when ingest rate is the bottleneck (metrics, logs, event streams, wide-column stores) and you can tolerate read amplification mitigated by Bloom filters and periodic, tunable compaction — and you must actively manage compaction back-pressure and secondary-index count as first-class costs, not afterthoughts.

Join algorithm choice. Nested loop wins with a small, filtered outer side and an indexed inner side; hash join wins for large, unfiltered equi-joins with no useful index (memory permitting — else it spills to a grace hash join); merge join wins when both sides are already sorted for free. Forcing a sort purely to enable a merge join is rarely a win over letting the planner hash instead.

When not to index. An index is a standing tax on every write to that column — justify it against actual query frequency, not hypothetical ones. Prefer a partial index when only a subset of rows is ever queried, a covering index when the win is skipping the heap fetch, and no index at all when selectivity is low enough that a sequential scan is genuinely cheaper — trust the planner's cost estimate over an instinct to "just add an index."

Takeaways

• Snapshot Isolation is not serializability — it silently allows write skew because it only ever checks same-row conflicts, never cross-row invariants.
• B-tree lookup cost and LSM write amplification are both derivable arithmetic (fanout/levels; base amplification × (1 + secondary indexes)) — never just asserted.
• A cost-based join plan and the decision to skip an index are the same kind of judgment: estimate the actual page-read cost of each option and let that pick the winner.
• Async failover always has an RPO window bounded by replication lag, and is only safe from split-brain once a fencing token is enforced — quorum election alone is not enough.

---

Synthesized from Kleppmann, Designing Data-Intensive Applications (ch. 3 storage engines, ch. 7 transactions, ch. 9 consistency & consensus); the RocksDB/Cassandra compaction & write-amplification literature; PostgreSQL documentation on MVCC, HOT updates, and SSI; the DynamoDB Global Tables and Redis persistence/Sentinel documentation; Ramakrishnan & Gehrke on query optimization and BCNF decomposition. Cross-references: "Write Skew, Lost Update & Snapshot Isolation," "Quorum Arithmetic — Why R + W > N," "Quorum in Practice," "Replication Lag & Failover," "Storage Engines — How B-tree & LSM-tree Work." Re-authored/Deepened for this guide.

I just read a lesson on **Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover (Deep Dive)** (System Design) and want to truly understand it. Explain Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.