Component Architecture · Phase 2: Core Infrastructure
Storage Engines: B-Trees vs. LSM-Trees
Unpack the low-level disk mechanics of in-place B+Trees (PostgreSQL/MySQL) versus append-only Log-Structured Merge-Trees (RocksDB/Cassandra), comparing write amplification and compaction.
Primary specification: The Log-Structured Merge-Tree (O’Neil, Cheng, Gawlick, O’Neil)
Lesson 13 of 33
1d streakThe Architectural Question
Engineering teams choose traditional B-Tree relational databases for write-heavy sensor or messaging workloads, causing disk I/O bottlenecks due to random page flushes.
Core Engineering Objectives
- B+Tree mechanics: in-place 4KB/8KB page updates, random disk I/O, write amplification, page splits
- LSM-Tree mechanics: Memtable in RAM, Write-Ahead Log (WAL), immutable SSTables on disk, Bloom filters
- Compaction algorithms: Size-Tiered vs Leveled Compaction and read amplification trade-offs
1. What is it & Why it Matters
At the heart of every database lies a storage engine that maps logical operations to physical disk blocks. The fundamental constraint is the RUM Conjecture: Read Amplification (RAF), Write Amplification (WAF), and Space Amplification (SAF) cannot all be optimized simultaneously. Selecting the wrong engine for your workload leads to write stalls, flash drive burnout, and tail latency collapse.
The Write Amplification Penalty
2. In-Place B+Trees vs. Append-Only LSM-Trees
| Dimension | B+Tree Engine (PostgreSQL, MySQL InnoDB) | LSM-Tree Engine (RocksDB, Cassandra, ScyllaDB) |
|---|---|---|
| Storage Model | In-place updates on fixed-size disk pages (4KB–16KB) | Append-only immutable sequential SSTables on disk |
| Write Path | Write to WAL + dirty buffer page; random disk flush | Append to sequential WAL + write to in-memory Memtable |
| Point Read Path | O(log_B N) index page traversal (1–3 disk seeks) | Memtable -> Bloom filter -> SSTable binary search |
| Write Amplification | High (10x – 100x+ due to full-page rewrites) | Low to Moderate (5x – 20x during background compaction) |
| Read Amplification | Low (1 page read per lookup) | High (checks Memtable + multiple SSTable tiers) |
| Space Amplification | Moderate (30–50% empty page fragmentation) | Low (densely packed, compressed immutable files) |
| Ideal Workload | Read-heavy OLTP with relational joins and foreign keys | Write-heavy event logs, metrics, telemetry, and time-series |
B+TREE ARCHITECTURE (In-Place 16KB Page Overwrites):
[Client Write] --> [Buffer Pool (16KB Page)] --(Random I/O)--> [Disk Page Overwrite]
* Vulnerability: Dirty page buffer flush stalls and random disk seeks.
LSM-TREE ARCHITECTURE (Sequential Append-Only):
[Client Write] --> 1. [Sequential WAL on Disk] (Durability)
--> 2. [In-Memory Memtable (SkipList)] (O(log N) insert)
| (Asynchronous Flush when Memtable full)
v
[Level 0 SSTables (Disk, Overlapping)]
| (Background Compaction)
v
[Level 1+ SSTables (Disk, Non-Overlapping)]
+-- In-Memory Bloom Filters (Eliminate 99% of empty seeks)3. The LSM Anatomy & Bloom Filter Nuance
- 011. Memtable (RAM): An in-memory sorted structure (typically a lock-free SkipList). It accepts client writes with sub-microsecond latency and zero disk seek waiting.
- 022. Write-Ahead Log (WAL): Every write appends sequentially to an on-disk WAL before memory acknowledgement. If the server crashes, the Memtable is deterministically reconstructed from the WAL.
- 033. Immutable SSTables (Disk): When the Memtable reaches threshold (e.g. 64MB), it freezes and flushes sequentially to disk as an immutable Sorted String Table (SSTable).
- 044. Bloom Filter Point Defense: Each SSTable has an in-memory Bloom filter. If the filter returns false, the key is guaranteed NOT to exist in that SSTable, bypassing the disk read entirely.
- 055. Range Query Reality Trap: Bloom filters use cryptographic/hash functions that destroy ordering. They are completely useless for range queries (e.g.,
WHERE id BETWEEN 100 AND 200). Range queries must merge-sort active iterators across all overlapping SSTables using sparse Block Indexes.
Use it when
Choose an LSM-Tree engine (RocksDB, Cassandra, ScyllaDB) when write-to-read ratio exceeds 1:1, or when data is append-only (logs, metrics, events, chat history).
Reconsider when
Choose a B+Tree engine (PostgreSQL, InnoDB) when workloads require heavy point-in-time random reads across foreign keys and multi-table relational joins.
4. Compaction Engines & The Compaction Debt Stall
- 01Size-Tiered Compaction (STCS): Merges SSTables of roughly equal size into a larger SSTable. Pros: High write throughput, low CPU. Cons: High space overhead (requires 50–100% free disk headroom) and high read latency.
- 02Leveled Compaction (LCS - RocksDB Default): Organizes files into exponential levels (L0, L1, L2...). Levels L1 and above are strictly non-overlapping. A point read touches at most ONE SSTable per level. Its space headroom depends on implementation, level sizing, and compaction workload; verify it operationally.
- 03Time Window Compaction (TWCS): Groups immutable time-series data into fixed time buckets (e.g. 1 day). Older windows can avoid repeated compaction once they are no longer receiving writes, which is useful for time-series workloads.
- 04The Compaction Debt Write Stall: If client write throughput outpaces background disk compaction bandwidth, SSTables accumulate in Level 0 (L0). Because L0 files overlap, read latency explodes. When L0 reaches a hard limit (e.g., 32 files), the engine intentionally throttles or halts incoming writes to let compaction catch up, causing client P99 latency to jump from 1ms to 10s.
5. Compaction Cheatsheet & Production War Stories
| Compaction Strategy | Write Amplification (WAF) | Read Amplification (RAF) | Space Headroom Needed | Best Workload |
|---|---|---|---|---|
| Size-Tiered (STCS) | Low (~5x – 10x) | High (searches multiple files) | 50% – 100% free disk | Heavy write-only ingestion; historical logs |
| Leveled (LCS) | High (~15x – 30x) | Very Low (≤ 1 seek per level) | 10% – 15% free disk | Read-heavy workloads requiring low read tail latency |
| Time Window (TWCS) | Lowest (~2x – 4x) | Low for recent time queries | < 5% free disk | Time-series metrics, IoT telemetry, chat history |
Uber & Discord Production Storage Migrations
6. Active Recall Checkpoint
Active Recall Checkpoint
Why does deleting a record in an LSM-Tree initially INCREASE disk space consumption rather than decreasing it?
Hint: Think about immutability and tombstone markers.
Show answer & explanation
In an append-only LSM-Tree, existing SSTables on disk are immutable. Deleting a record writes a new "tombstone" marker entry to the Memtable and WAL, which later flushes to disk as part of a new SSTable. Both the original data and the tombstone marker coexist on disk until background compaction merges the SSTables and physically purges the deleted record.
Active Recall Checkpoint
Why does Leveled Compaction (LCS) require significantly less free disk space than Size-Tiered Compaction (STCS)?
Hint: Compare the size of the units being merged.
Show answer & explanation
In STCS, entire tiers of equal size are merged together; merging a 200GB tier requires 200GB of contiguous free disk space (100% overhead). In LCS, data is partitioned into small fixed-size files (e.g. 64MB). Compaction picks one 64MB file from Level N and merges it only with overlapping 64MB files in Level N+1, requiring only 10–15% disk headroom during compaction.
Architectural Trade-Off Analysis
Compare latency, throughput, consistency, and operational complexity across core industry alternatives.
Architecture Decision Matrix
Multi-axis engineering evaluation and FAANG interview rules of thumb.
SQL (Postgres / MySQL)
Relational ACID Store
Structured schema, relational joins, ACID transactions, and strict foreign keys.
NoSQL (Cassandra / DynamoDB)
Distributed Non-Relational Store
Horizontal partition keys, denormalized documents/wide-columns, and tunable consistency.
| Evaluation Axis | SQL (Postgres / MySQL) | NoSQL (Cassandra / DynamoDB) | Details |
|---|---|---|---|
Latency | Moderate | Strong | |
Throughput | Moderate | Strong | |
Scalability | Moderate | Strong | |
Consistency | Strong | Moderate | |
Complexity | Strong | Moderate | |
Cost | Moderate | Strong |
When to Choose in an Architecture Interview
Choose SQL when ACID guarantees are non-negotiable (financial ledgers, payment processing, inventory checkout) or when query access patterns are unpredictable and require ad-hoc analytical joins.
Choose NoSQL when write volume exceeds single-node capacity (>20K writes/sec), data is unstructured/hierarchical (logs, telemetry, user feeds), or multi-region active-active replication is mandatory.
Never say "NoSQL is faster than SQL" without qualification. SQL with proper B-Tree indexes on indexed primary keys is lightning fast. NoSQL wins on horizontal write scaling, not inherent single-row read speed.
Production Postmortem & Verification
Production Incident Postmortem
- Trigger / Setup: An IoT telemetry system writes 150,000 metrics per second into a PostgreSQL table indexed with multiple B+Trees.
- Production Symptom: Disk IOPS hits NVMe drive limits; write latency spikes to 5 seconds due to random 8KB page write amplification.
- Root Cause & Fix: Write-dominated workloads require LSM-tree storage engines (e.g. RocksDB/Cassandra) that convert random writes into sequential disk flushes.
Acceptance Criteria & Outcomes
- Compare the read, write, and space amplification characteristics of B+Trees and LSM-Trees.
- Explain how Bloom filters prevent expensive disk lookups for non-existent keys in LSM SSTables.
- Detail the trade-offs between Leveled Compaction (low space amp) and Size-Tiered Compaction (low write amp).
Architectural & Technical Interview Review
Core FAANG Interview Questions
Q01How do you justify introducing Storage Engines: B-Trees vs. LSM-Trees into a high-scale production architecture?Click to reveal model answer →Hide answer ↑Requirements & Design Brief
Introduce Storage Engines: B-Trees vs. LSM-Trees only when measured scale, data size, or failure boundaries exceed single-node capacity. State the exact bottleneck, evaluate operational overhead, and verify that the trade-offs justify the added moving parts.
Q02What is the primary trade-off and hidden operational cost of Storage Engines: B-Trees vs. LSM-Trees?Click to reveal model answer →Hide answer ↑Architecture Trade-offs
It improves scalability and availability, but introduces network hops, serialization overhead, and eventual consistency or coordination complexity.
Q03How do you handle catastrophic failure or dependency degradation in Storage Engines: B-Trees vs. LSM-Trees?Click to reveal model answer →Hide answer ↑Failure Review & Recovery
Implement connect/read timeouts, exponential backoff with jitter, and fallback defaults so downstream degradations do not cause cascading outages.
Production Pitfalls & Anti-Patterns
Critical Failure Anti-Patterns
Premature Distributed Complexity
Scattering distributed components before identifying concrete write, read, or storage limits creates accidental points of failure and operational debt.
Production Mitigation: Start with the simplest modular design that satisfies requirements, evolving it only as measured constraints dictate.
Unbounded Retries and Cascading Storms
When a dependency degrades, immediate synchronized retries multiply downstream traffic, turning a minor slowdown into a total fleet outage.
Production Mitigation: Enforce strict retry budgets, exponential backoff, and full randomized jitter on all client calls.
Neglecting Observability and Metrics
Deploying architecture without distributed tracing or p99 tail latency alerts leaves engineers blind when partial partitions occur.
Production Mitigation: Export metrics for request rate, error rate, p95/p99 duration, and saturation at every service boundary.