Chapter 9: Storage Engines

1. What is a Storage Engine?

A storage engine is the component of a database that manages how data is stored, retrieved, and updated on disk. It sits below the query layer and is responsible for physical data organization, indexing, concurrency control, and crash recovery.

Storage Engine Responsibilities

2. B-Tree Deep Dive

B-Trees (Balanced Trees) are the workhorse of traditional databases. They provide O(log n) reads and writes, efficient range scans, and in-place updates.

Structure & Properties

• Balanced: All leaf nodes are at the same depth
• Branching Factor: Each node has up to m children (typically 100-200 for disk-based trees)
• Sorted: Keys are kept in sorted order within nodes
• Self-Balancing: Automatically rebalances on insert/delete via splits and merges

B-Tree vs B+ Tree

Operations

Search - O(log n)

Insertion - Page Splits

When a node overflows (exceeds max keys), it splits into two nodes. This can cascade up the tree.

Page Size Tradeoffs

Write Amplification in B-Trees

A 100-byte write can trigger:

1. Read: Load 16KB page from disk
2. Modify: Update 100 bytes in memory
3. Write: Write entire 16KB page back (160x amplification)
4. Cascading Splits: If page splits, write 2 pages + update parent (up to 48KB for single insert)
5. WAL: Write log entry (~200 bytes)

Total: 10-30x write amplification is typical.

3. LSM-Tree Deep Dive

Log-Structured Merge Trees optimize for write throughput by batching writes in memory and sequentially flushing to disk. Reads are slower but mitigated with caching and bloom filters.

Architecture

Write Path - Sequential Writes Win

1. Write to WAL: Append-only log for crash recovery (~200 bytes, <1ms)
2. Insert into Memtable: In-memory skip list or AVL tree (O(log n), microseconds)
3. Flush to SSTable: When memtable reaches size threshold (e.g., 64MB), write sorted run to L0 (sequential disk write, ~100 MB/s on SSD)
4. Background Compaction: Merge overlapping SSTables across levels to maintain sorted order

Read Path - Multi-Level Lookup

1. Check Memtable: Most recent writes (O(log n))
2. Check Immutable Memtable: Being flushed to disk (if exists)
3. Check L0 SSTables: May overlap, need to check all (use bloom filters)
4. Check L1...Ln SSTables: Non-overlapping per level, binary search by key range
5. Merge: If key exists in multiple levels (e.g., updates), return most recent version

SSTable Structure

Levels & Compaction

Bloom Filters - Avoiding Disk Reads

A bloom filter is a probabilistic data structure that can answer "definitely NOT in set" or "maybe in set".

Impact: With 10 bits/key and 20 SSTables in L0, bloom filters eliminate ~19.8 unnecessary disk reads per lookup (only 0.9% false positives).

4. B-Tree vs LSM-Tree Comparison

Performance Numbers - Real Hardware

When to Choose B-Tree

• Read-Heavy: OLTP workloads with 80%+ reads (e.g., web app backends)
• Point Lookups: SELECT * WHERE id = ? dominates
• Updates: Frequent in-place updates (UPDATE users SET last_login = NOW())
• Consistent Latency: No compaction stalls (trading higher p99 for predictable p50)
• Low Space Overhead: Storage constrained

When to Choose LSM-Tree

• Write-Heavy: Time-series, logging, analytics ingestion (90%+ writes)
• High Throughput: Need to sustain 100K+ writes/sec
• Append-Only: Inserts dominate (no updates/deletes)
• SSD Optimization: Leverage sequential write performance
• Compression: Better compression ratios (entire SSTables compressed)

5. Write Amplification

Write Amplification (WA) = Total bytes written to disk / Bytes written by application

A 1 KB application write might cause 30 KB of disk writes due to:

• Updating data structures (pages, SSTables)
• Write-ahead logging
• Compaction (LSM) or page splits (B-Tree)

B-Tree Write Amplification

Factors:

• Page Size: 16 KB pages → 160x amplification for 100-byte writes
• Page Splits: Can trigger 2-3 page writes (48 KB)
• WAL: Additional 100-500 bytes per write
• Double-Write Buffer: InnoDB writes pages twice (once to double-write buffer, then to data file) → 2x amplification

Typical WA: 10-30x for OLTP workloads

LSM-Tree Write Amplification

Compaction Overhead:

• Leveled Compaction (RocksDB): Each level is 10x the previous. A write at L0 gets rewritten ~5 times → WA ≈ 10-30x
• Size-Tiered Compaction (Cassandra): Merge SSTables of similar size. WA ≈ 5-10x but more space amplification

Calculation: For leveled compaction with 10x growth and 6 levels:

SSD Wear & Endurance

Minimizing Write Amplification

6. Compaction Strategies

Compaction merges SSTables to remove duplicate keys, apply tombstones, and maintain sorted order. The strategy trades off write amplification, space amplification, and read amplification.

Size-Tiered Compaction (STCS)

Used by: Cassandra (default), HBase

Algorithm:

1. Group SSTables of similar size (e.g., 10 MB)
2. When 4 SSTables accumulate, merge them into one (40 MB)
3. Repeat at next tier (4 × 40 MB → 160 MB)

Pros:

• Low write amplification (each SSTable compacted ~log₄(N) times → WA ≈ 5-10x)
• Simple to implement

Cons:

• High space amplification (multiple overlapping SSTables → 2-3x overhead)
• Slow reads (must check many SSTables)
• Temporary space spike during compaction (need 2x space)

Leveled Compaction (LCS)

Used by: RocksDB (default), LevelDB, Cassandra (optional)

Algorithm:

1. L0 allows overlapping SSTables (direct memtable flushes)
2. L1...Ln have non-overlapping SSTables within each level
3. L_i+1 is 10x the size of L_i
4. When L_i exceeds threshold, pick overlapping SSTables from L_i and L_i+1, merge, write to L_i+1

Pros:

• Fast point lookups (bloom filters + at most 1 SSTable per level → check ~7 SSTables)
• Low space amplification (~10% overhead, no overlapping SSTables except L0)
• Predictable performance (no temporary space spikes)

Cons:

• High write amplification (each byte rewritten ~10x per level → WA ≈ 30x)
• Compaction can bottleneck writes (L0 stalls)

Universal Compaction

Used by: RocksDB (option for write-heavy workloads)

Algorithm: Hybrid between size-tiered and leveled. Pick SSTables to compact based on size ratio and age.

Pros:

• Lower write amplification than leveled (WA ≈ 10-15x)
• Good for write-heavy workloads

Cons:

• Higher space amplification than leveled
• More complex tuning

FIFO Compaction

Used by: RocksDB (time-series data)

Algorithm: Drop oldest SSTables when total size exceeds threshold. No merging.

Pros:

• Minimal write amplification (WA ≈ 1x, just WAL + flush)
• Perfect for TTL-based data (logs, metrics)

Cons:

• No duplicate removal (wastes space if keys updated)
• Requires time-ordered keys

Compaction Strategy Comparison

Compaction Triggers & Throttling

Compaction runs in background threads but can stall writes if it falls behind.

7. Write-Ahead Log (WAL)

The Write-Ahead Log ensures durability by logging all changes before applying them to the database. If the database crashes, it replays the WAL to recover uncommitted changes.

Why WAL is Needed

Problem: Databases use in-memory buffer pools to cache pages. If a transaction commits but the dirty page hasn't been flushed to disk, a crash loses the change.

Solution: Write to WAL first (cheap sequential append), then modify buffer pool. On crash, replay WAL.

WAL Structure

Total: ~100-500 bytes per log entry (depending on data size)

WAL Write Process

Key Insight: WAL writes are sequential (fast), data page writes are random (slow). WAL makes commits fast by deferring expensive random I/O.

Group Commit Optimization

fsync() is expensive (~5-10ms on SSD). Batching multiple transactions into one fsync improves throughput.

Transactions 1, 2, 3 all commit with a single fsync → 3x throughput improvement.

Checkpoint & WAL Truncation

WAL grows unbounded. Periodically, the database performs a checkpoint:

1. Flush all dirty pages to disk
2. Record checkpoint LSN in a special file
3. Truncate WAL entries before checkpoint LSN (they're now redundant)

Recovery: Start from last checkpoint, replay WAL from checkpoint LSN to end.

WAL & Replication

WAL is also used for replication:

• PostgreSQL: Replicas stream WAL entries from primary
• MySQL: Binary log (similar to WAL) is shipped to replicas
• RocksDB: WAL can be tailed for change data capture (CDC)

WAL Performance Tuning

8. Page Cache & Buffer Pool

Disk I/O is 1000x slower than memory. Databases cache frequently accessed pages in memory to avoid disk reads.

InnoDB Buffer Pool

InnoDB's buffer pool is a large memory area (typically 50-80% of RAM) that caches data and index pages.

Buffer Pool Structure

LRU Eviction - Midpoint Insertion

Standard LRU has a problem: a full table scan evicts the entire cache. InnoDB uses midpoint insertion:

Algorithm:

1. New pages inserted at midpoint (head of "old" sublist)
2. If page accessed again within 1 second, promote to "young" sublist
3. Evict from tail of "old" sublist

Benefit: Full table scan pages stay in "old" sublist and are quickly evicted, preserving hot pages in "young" sublist.

Dirty Page Flushing

Modified pages (dirty pages) must eventually be written to disk. InnoDB has multiple flushing mechanisms:

RocksDB Block Cache

RocksDB uses a simpler block cache (similar to OS page cache):

• Uncompressed Block Cache: Stores decompressed data blocks (fast reads)
• Compressed Block Cache: Stores compressed blocks (save memory)
• Index & Filter Cache: Separate cache for index blocks and bloom filters

Eviction: Standard LRU with sharding (16-64 shards to reduce lock contention).

Cache Hit Rate & Performance

Rule of Thumb: Every 1% increase in cache hit rate reduces latency by ~10%.

Buffer Pool Tuning

9. Compression

Compression reduces storage costs and can improve I/O throughput (fewer bytes to read/write). The tradeoff is CPU overhead.

Compression Levels

Compression Algorithms

InnoDB Transparent Page Compression

InnoDB compresses individual 16 KB pages:

1. Compress page (e.g., 16 KB → 8 KB with zlib)
2. Write compressed page to disk (saves 8 KB)
3. On read, decompress page into buffer pool (16 KB in memory)

Tradeoff: 30-50% space savings, but 20-30% CPU overhead. Enable for cold tables only.

LSM-Tree Compression

RocksDB compresses entire data blocks (not individual keys):

Compression per Level: RocksDB allows different compression per level:

Dictionary Compression (LSM)

For repeated strings (e.g., URLs, user agents), RocksDB can build a dictionary per SSTable:

• Training: Analyze sample keys/values, extract common substrings
• Encoding: Replace substrings with 2-byte codes
• Compression Boost: 5-10x for text-heavy data (vs 2-3x with LZ4 alone)

Prefix Compression (B-Tree)

B-Tree nodes store sorted keys. Consecutive keys often share prefixes:

Savings: Store "user_1234" once, then only store suffixes ("5", "6", "7"). For long keys (e.g., URLs), this saves 80-90% space.

Compression Impact on Performance

10. Real Storage Engines

InnoDB (MySQL)

• Type: B+ Tree with clustered primary key
• Concurrency: MVCC (multi-version concurrency control), row-level locking
• Durability: WAL (redo log) + double-write buffer
• Strengths: ACID transactions, fast point lookups, efficient range scans
• Weaknesses: Write amplification (10-30x), page splits under heavy writes
• Use Case: General-purpose OLTP (e-commerce, SaaS apps)

RocksDB (Meta/Facebook)

• Type: LSM-Tree with leveled compaction
• Concurrency: Lock-free writes, reader-writer locks for compaction
• Durability: WAL + memtable snapshots
• Strengths: Extreme write throughput (500K ops/sec), tunable compaction, embeddable (C++ library)
• Weaknesses: Slower reads than B-Tree, compaction stalls
• Use Case: Write-heavy workloads (time-series, logging, stream processing)
• Used By: MySQL (MyRocks storage engine), CockroachDB, TiDB, Kafka Streams

WiredTiger (MongoDB)

• Type: B-Tree (default) or LSM-Tree (configurable)
• Concurrency: MVCC, document-level locking
• Durability: WAL (journal) + checkpoints
• Strengths: Hybrid approach, excellent compression (Zstd), fast snapshots
• Weaknesses: Complex tuning, checkpoints can cause latency spikes
• Use Case: MongoDB workloads (document store, mixed read/write)

LevelDB (Google)

• Type: LSM-Tree with leveled compaction
• Concurrency: Single-writer, multiple readers
• Durability: WAL
• Strengths: Simple API, fast writes, embeddable
• Weaknesses: Single-threaded writes, no replication, abandoned by Google (RocksDB is successor)
• Use Case: Embedded key-value store (Chrome IndexedDB, Bitcoin Core)

BadgerDB (Go)

• Type: LSM-Tree with value separation
• Concurrency: Multi-threaded writes via MVCC
• Durability: WAL (value log) + separate key log
• Strengths: Stores large values separately (reduces compaction overhead), written in Go (no CGO)
• Weaknesses: Immature compared to RocksDB, garbage collection overhead
• Use Case: Go applications needing embedded KV store (IPFS, Dgraph)

Comparison Table

Pluggable Engines in Practice

MySQL Storage Engine Options:

• InnoDB: Default, ACID, row-level locking
• MyISAM: Table-level locking, fast reads, no transactions (deprecated)
• Memory: In-memory tables, fast but volatile
• MyRocks: RocksDB backend, 2-3x better compression, 5-10x write throughput
• TokuDB: Fractal tree, high compression (acquired by Percona, end-of-life)

Example: Facebook migrated MySQL from InnoDB to MyRocks (RocksDB), reducing storage by 50% and increasing write throughput by 3x.

11. Emerging Approaches

Learned Indexes (ML-Based)

Replace B-Tree nodes with machine learning models that predict the position of a key.

Idea: B-Tree is essentially a learned function: given key K, predict its position. Train a neural network to approximate this function.

Pros:

• Smaller index size (MB vs GB for B-Tree)
• Fewer cache misses (no pointer chasing)
• Theoretically faster lookups (O(1) vs O(log n))

Cons:

• Only works for read-only or append-only data (retraining cost)
• Requires predictable key distribution
• Complex implementation, unproven at scale

Status: Research stage (Google's 2018 paper), not production-ready.

Bw-Tree (Lock-Free B-Tree)

Microsoft's lock-free B-Tree for SQL Server Hekaton (in-memory OLTP).

Key Ideas:

• Delta Updates: Instead of modifying nodes in-place, append delta records
• Atomic CAS: Use compare-and-swap for lock-free updates
• Log-Structured: Periodically consolidate deltas into new base pages

Pros:

• High concurrency (no locks, no latches)
• Scales to 100+ cores

Cons:

• Complex implementation (1000s of lines vs B-Tree)
• Delta chains can cause read amplification

Status: Production in SQL Server Hekaton, not widely adopted elsewhere.

Fractal Trees (Toku Storage Engine)

A variant of B-Tree that buffers writes at internal nodes to reduce random I/O.

Key Ideas:

• Each internal node has a buffer (4-64 MB)
• Writes accumulate in buffers, flushed to children when full
• Converts random writes into sequential flushes

Pros:

• Better write throughput than B-Tree (10x for bulk inserts)
• Better compression than LSM (no duplicate keys across levels)

Cons:

• Complex implementation
• Slower point queries (must check buffers up the tree)

Status: TokuDB (Percona) reached end-of-life in 2021. Not widely adopted.

Append-Only B-Trees (CouchDB, Riak)

Instead of in-place updates, write new versions of pages (copy-on-write).

Pros:

• MVCC without row versioning
• Fast snapshots (root pointer = snapshot)
• Crash recovery via root pointer

Cons:

• High write amplification (entire root-to-leaf path rewritten)
• Requires compaction to reclaim space

Status: Used in CouchDB and Riak, niche use case.

Key-Value Separation (WiscKey, BadgerDB)

Store keys in LSM-Tree, but store large values in a separate log.

Pros:

• Reduces compaction overhead (don't rewrite large values)
• Lower write amplification for value-heavy workloads

Cons:

• Extra disk read for values (not in cache)
• Garbage collection complexity (value log grows unbounded)

Status: BadgerDB (production), WiscKey (research).

Chapter Summary

Key Takeaways

• B-Trees: Balanced tree, O(log n) reads/writes, in-place updates. Best for read-heavy OLTP.
• LSM-Trees: Append-only, sequential writes, background compaction. Best for write-heavy workloads.
• Write Amplification: 10-30x typical. Critical for SSD endurance.
• Compaction: Size-tiered (low WA, high space), leveled (low space, high WA), FIFO (minimal WA).
• WAL: Durability via sequential logging. Group commit for throughput.
• Caching: Buffer pool with midpoint insertion LRU. 99% cache hit rate is ideal.
• Compression: LZ4 for hot data (fast), Zstd for cold data (high ratio).
• Real Engines: InnoDB (B-Tree, OLTP), RocksDB (LSM, write-heavy), WiredTiger (hybrid).

Decision Matrix

Interview Cheat Sheet

Worked Examples: Storage Engine Math

B-Tree Page Split Cascade: Write Amplification Calculation

A 100-byte insert into a full 16KB page triggers a page split. Calculate the actual I/O cost:

Average Case Analysis:

• Fill Factor: B-Trees maintain 50-70% page occupancy on average
• Split Frequency: With 70% fill factor and 16KB pages storing ~115 rows (140 bytes each), a split occurs every ~115 inserts
• Amortized Cost: 16KB split cost / 115 inserts = 140 bytes per insert = 1.4x average write amplification
• WAL Overhead: Add ~200 bytes per insert for write-ahead log → total ~1.6x average write amp

LSM Write Amplification: Multi-Level Compaction

Calculate write amplification for leveled compaction (RocksDB default):

Leveled Compaction Write Path

Size-Tiered Compaction (Cassandra):

• Merge Strategy: Combine 4 SSTables of similar size → 1 larger SSTable
• Tiers: 10MB → 40MB → 160MB → 640MB (log₄ growth)
• Write Amplification: Each SSTable compacted log₄(N) times = ~5-10x (lower than leveled)
• Space Amplification: Up to 2x (multiple overlapping SSTables before compaction)

RocksDB Tuning Example: High Write Throughput

Production configuration for write-heavy workload (logging, time-series):

# RocksDB Configuration (C++ API or options file)
# Goal: Maximize write throughput, tolerate higher space/read amplification

# Memtable Configuration
write_buffer_size = 256MB          # Larger memtable → fewer flushes
                                   # Default: 64MB. Tradeoff: more memory, slower recovery
max_write_buffer_number = 4        # 4 memtables before write stall
                                   # Total memory: 256MB × 4 = 1GB per column family

# L0 Compaction Tuning
level0_file_num_compaction_trigger = 8
                                   # Start L0→L1 compaction when 8 SSTables in L0
                                   # Higher value = more write throughput, worse reads
level0_slowdown_writes_trigger = 20
                                   # Slow writes when L0 reaches 20 files
level0_stop_writes_trigger = 36
                                   # Stop writes when L0 reaches 36 files (avoid this!)

# Compaction Threads
max_background_compactions = 4     # 4 parallel compaction threads
                                   # Matches typical 4-core CPU, adjust based on hardware
max_background_flushes = 2         # 2 parallel memtable flush threads

# SSTable Configuration
target_file_size_base = 256MB      # Larger SSTables → fewer files, less compaction overhead
                                   # Default: 64MB. Tradeoff: slower individual compactions
max_bytes_for_level_base = 2GB     # L1 size = 2GB (10x larger than default)
max_bytes_for_level_multiplier = 10
                                   # Each level is 10x the previous (L2=20GB, L3=200GB, ...)

# Compression (reduces write amp via smaller files)
compression = "lz4"                # Fast compression (10 GB/s encode)
                                   # Alternatives: snappy (faster), zstd (better ratio)
bottommost_compression = "zstd"    # Higher compression for oldest level (rarely read)

# Write Ahead Log (WAL)
wal_bytes_per_sync = 1MB           # fsync WAL every 1MB (balance durability vs throughput)
                                   # Default: 0 (fsync every write = slow)

# Bloom Filters (mitigate read amplification from high L0 files)
bloom_bits_per_key = 10            # 10 bits = 0.9% false positive rate
                                   # Memory cost: 10 bits × 1M keys = 1.25MB per SSTable

Impact of Configuration

Interview Callout: Demonstrating First-Principles Understanding

Interviewer asks: "Why are B-Trees read-optimized and LSM-Trees write-optimized?"

Strong answer (shows calculation from first principles):

"B-Trees do in-place updates: a 100-byte write modifies 1 page (16KB). Write amplification is page_size / write_size = 160x per page write, but most inserts don't cause splits, so amortized write amp is ~1.4x for inserts + 10-20x for WAL/page flushes = 15-30x total. Reads are O(log n) with single tree traversal = 3-4 disk seeks. LSM-Trees append to memtable (O(log n) in-memory), then batch-flush to L0. Every write is eventually rewritten through compaction: L0→L1 (10x), L1→L2 (10x), ... for 6 levels = 10-30x write amp. Reads must check multiple levels: memtable + L0 (10 files) + L1-L6 (1 file each with bloom filter) = up to 17 disk seeks worst case. Trade-off: LSM trades write amp for sequential I/O (500 MB/s) vs random I/O (50 MB/s) = 10x throughput gain. B-Tree trades higher write amp for single-lookup reads."

This demonstrates: (1) Quantitative reasoning, (2) Understanding of I/O characteristics, (3) Knowledge of real-world performance numbers, (4) Ability to articulate trade-offs.