- Read/Write Amplification: Evaluate the fundamental physical storage trade-offs between update-in-place (B+ Trees) and append-only log structures (LSM-Trees).
- B+ Tree Mechanics (Postgres/InnoDB): In-place page updates with WAL durability, minimizing read amplification (O(log_B N)) at the cost of high random I/O write amplification.
- LSM-Tree Mechanics (RocksDB/Cassandra): Append sequential writes to in-memory MemTables and flush immutable SSTables to disk, optimizing write throughput at the cost of compaction overhead.
- Compaction Strategies: Leveled vs Size-Tiered compaction algorithms, Bloom filter optimization, and NVMe SSD write-endurance profiling.
1. Storage Engine Physics & The Amplification Trilemma
Every database storage engine operates under the fundamental Amplification Trilemma: balancing Read Amplification (bytes read from disk per logical byte requested), Write Amplification (bytes written to disk per logical byte modified), and Space Amplification (total disk space consumed relative to uncompressed raw data).
Traditional relational engines (such as PostgreSQL and MySQL InnoDB) prioritize low Read Amplification by organizing data into balanced B+ Tree structures with in-place page updates. High-throughput time-series, log, and distributed storage engines (such as RocksDB, CockroachDB, and Cassandra) utilize Log-Structured Merge-Trees (LSM-Trees) to maximize sequential write throughput on modern NVMe drives.
// Mathematical Definitions of Storage Engine Amplifications
// --------------------------------------------------------------------
// Write Amplification Factor (WAF) = Total Bytes Written to Disk / Logical Bytes Ingested
// Read Amplification Factor (RAF) = Total Bytes Read from Disk / Logical Bytes Retrieved
// Space Amplification Factor (SAF) = Total Physical Storage Used / Uncompressed Raw Data Size2. B+ Tree Internals: Page Buffers, Slotted Pages & WAL
A B+ Tree stores all key-value records in leaf pages linked sequentially, while internal nodes maintain high-fanout routing pointers. Pages are fixed in size (typically 8KB in PostgreSQL, 16KB in InnoDB).
When a record is inserted or updated, the database modifies the in-memory buffer pool page. To guarantee ACID Durability without writing full random 8KB pages to disk on every transaction commit, the engine appends a compact record delta to the sequential Write-Ahead Log (WAL). Background checkpointing threads periodically flush dirty buffer pool pages to disk.
// C: PostgreSQL Slotted Page Layout Header Structure
typedef struct PageHeaderData {
PageXLogRecPtr pd_lsn; // LSN: Log Sequence Number of last change
uint16 pd_checksum; // Page checksum verification
uint16 pd_flags; // Page status flags
LocationIndex pd_lower; // Offset to start of free space
LocationIndex pd_upper; // Offset to end of free space (where line pointers grow)
LocationIndex pd_special; // Offset to special space (e.g. B-Tree leaf links)
ItemIdData pd_linp[1]; // Array of item / line pointers
} PageHeaderData;3. LSM-Tree Mechanics: MemTables, SSTables & Bloom Filters
LSM-Trees eliminate random disk writes by buffering mutations in memory inside a Concurrent SkipList or Red-Black Tree called the MemTable. Once the MemTable reaches its capacity limit (e.g. 64MB), it is converted to an immutable MemTable and flushed sequentially to disk as a Level 0 (L0) Sorted String Table (SSTable).
Because SSTables on disk are immutable, deleting a key involves writing a Tombstone record. To prevent read requests from scanning dozens of SSTable files on disk to find a single key, engines place a probabilistic Bloom Filter in memory for every SSTable, returning instantly if a key is guaranteed not to exist.
// Go: Simplified Concurrent SkipList MemTable Node Structure
type MemTableNode struct {
key []byte
value []byte
tag uint64 // Sequence number + OpType (Set / Delete Tombstone)
next []*MemTableNode
}
type LSMReader struct {
memtable *MemTable
sstLevels [][]*SSTableReader
}
func (r *LSMReader) Get(key []byte) ([]byte, bool) {
if val, found := r.memtable.Lookup(key); found {
return val, true
}
// Fall back to level-by-level SSTable lookup guarded by Bloom filters
return r.searchSSTables(key)
}4. Compaction Algorithms: Leveled Compaction vs Size-Tiered
Over time, accumulated SSTables degrade point lookup and range scan performance. Compaction is the background process that reads multiple overlapping SSTables, merges sorted keys, purges obsolete deleted tombstones, and outputs new non-overlapping SSTables at higher levels.
In Leveled Compaction (default in RocksDB/LevelDB), each Level $ has a strict capacity limit (e.g. = 10 ext{MB}, L_2 = 100 ext{MB}, L_3 = 1 ext{GB}$) and non-overlapping key ranges, minimizing Read Amplification and Space Amplification at the cost of higher Write Amplification ( pprox 10 - 30$).
# RocksDB Compaction & Memory Tuning (DBOptions / ColumnFamilyOptions)
[Version]
rocksdb_version=9.1.0
[DBOptions]
max_background_jobs=8
bytes_per_sync=1048576
[CFOptions "default"]
write_buffer_size=67108864 # 64MB MemTable
max_write_buffer_number=4
target_file_size_base=67108864
level0_file_num_compaction_trigger=4
compaction_style=kCompactionStyleLevelFrequently Asked Questions (FAQ)
When should an engineering team choose an LSM-Tree engine over a B+ Tree?
LSM-Tree engines (RocksDB, Cassandra, ClickHouse) excel in write-heavy workloads (ingesting logs, time-series metrics, blockchain ledger transactions) where sustained write throughput and NVMe SSD write optimization are critical. B+ Trees (PostgreSQL, MySQL) excel in read-heavy and complex transactional relational workloads.
How do Bloom Filters eliminate LSM-Tree read amplification?
A Bloom filter is an in-memory space-efficient bit array that tests set membership with zero false negatives. If the Bloom filter reports that a key is absent from an SSTable file, the engine skips disk I/O entirely.
Why do deletions in LSM-Trees initially increase disk usage?
Because SSTables on disk are immutable, a DELETE operation appends a Tombstone marker rather than removing data in place. Storage is only reclaimed when background compaction merges and discards obsolete tombstones.
Utility Security Tools Related to this Article:
Gunakan Diff Checker dan Hash Generator untuk membantu alur kerja konfigurasi keamanan Anda secara privasi di browser.