Database Internals and Storage Engines Questions

B+ trees on disk are organized as fixed-size pages (blocks). Pages are typed: root/internal pages hold keys + child page pointers; leaf pages hold keys + record pointers (or record RID) and are doubly/singly linked for fast range scans. Internal pages only store routing info; all actual records live in leaves. Pages may include header/metadata and space for variable-length keys; overflow chaining is used for very large keys/values.

Lookup and range-scan costing (I/O per page)

• Fanout f ≈ floor((page_size − overhead) / (key_size + pointer_size)). Tree height h ≈ ⌈log_f(N_leaf_entries)⌉.
• Point lookup I/O ≈ h page reads (one per level). If root/internal pages are cached, effective random I/O ≈ number of uncached levels (often 1 random to fetch leaf).
• Range scan of R consecutive records: cost ≈ h (to reach first leaf, often 1 random if cached internals) + ceil(R / entries_per_leaf) sequential leaf page reads. So model: 1 random + S sequential where S ≈ pages covering the range.

Trade-offs: random vs sequential I/O

• On spinning disks, random I/O has very high latency (seek+rotational) vs sequential which amortizes seeks; so minimizing random reads (by caching internal nodes, clustering, prefetching, larger pages) is crucial. On SSDs random I/O penalty shrinks but per-page transfer and queueing still matter.
• Larger pages increase sequential throughput (more records per I/O) and raise fanout (lower h ⇒ fewer random seeks), but each random read transfers more bytes (read amplification) and increases buffer-pool footprint per cached page.
• Smaller pages reduce read amplification and cache pressure for mixed workloads with lots of small random reads, but increase tree height and the number of random I/Os per lookup.

Effects of page size, fanout, and clustering (qualitative quantification)

• Page size: doubling page size roughly doubles fanout, which reduces height logarithmically. Example: if f increases from 100→200, h for 1M leaf entries goes from ≈3 to ≈2 levels. But each page read moves 2× data and consumes 2× buffer space.
• Fanout: higher fanout → much lower h → fewer random I/Os; also fewer internal pages to cache. But large keys (wider entries) reduce fanout.
• Clustering (clustered index / physical ordering): massively reduces random I/O for range scans; a fully clustered index can turn O(h + S) into effectively one random + S sequential pages. For point lookups that target localized ranges, clustering reduces page misses; for uniform random accesses it matters less.
• Memory usage: buffer pool cost ≈ (#cached pages) × page_size. Higher page_size reduces number of distinct pages for same data (fewer pages overall) but each cached page is larger. Higher fanout → fewer internal pages to keep cached (good). Caching internals is high leverage: storing root+top levels (small) avoids most random I/O.

Best practices

• Cache top internal levels to turn lookups into “1 random (leaf) + sequential” on reads.
• Choose page size balancing sequential throughput vs random latency and buffer pool size (common choices 4KB–16KB).
• Use clustering for workloads with range scans; use smaller pages or LSM/append structures for write-heavy random workloads.
• Consider SSD characteristics: you can afford smaller pages and more random I/Os compared to HDD, but still benefit from clustering and higher fanout.

Situation: We need to support efficient binary search over a large, immutable, sorted array stored on disk but compressed for space. The core tension: maximize compression ratio while keeping random-access latency low enough for binary search (many point reads).

Approaches (high level)

• Compress by blocks (chunk-level) so you can read/seek a single block to inspect multiple elements, instead of decompressing whole file per probe.
• Use element-level compression only when element-level random access is cheap (rare) or when you maintain an index of per-element offsets (costly).

Compression techniques

• Delta encoding: store first value of block explicitly, subsequent values as differences (varint/zigzag). Works best for monotonic numeric sequences; gives excellent compression and cheap in-block sequential decode.
• Front-coding (prefix compression): for sorted strings, store a “shared-prefix length” with each entry or use group front-coding where a block stores full first string and subsequent strings as suffixes. Great when keys share prefixes (e.g., URLs).
• Combine techniques: within a block, use front-coding for strings and delta+varint for numeric IDs.

Block vs element-level compression (trade-offs)

• Block compression: read 1 disk range to access many entries; amortizes decompression cost across multiple probes (useful for cache, sequential scans). But binary search inspects log2(N) positions → block reads per probe ~log2(N) if blocks align to single elements; better if index maps to block boundaries.
• Element-level: best compression (no padding), but random-access requires reading and decoding per element or maintaining per-element offsets → heavy index memory or many small I/Os.

Designing block indices to minimize latency

• Build a top-level sparse index mapping logical array positions (or value ranges) to block offsets plus the first key/value in block. For binary search:
  • Search index first (in-memory) to find block that could contain target — reduces disk seeks to one block per probe.
  • Keep index small by sampling every k-th element (tune k). Use two-level index for huge datasets: in-memory root index covering large ranges and on-disk second-level index.
• Store for each block:
  • file offset, compressed size, first key (and maybe last key) and optionally metadata (min/max, cardinality).
  • CRC/version to validate.
• Optimize block size: choose size to balance compression (larger blocks compress better) vs random-access latency (smaller blocks are cheaper to fetch). Typical sweet spot: 4–64 KB depending on storage and expected access pattern.
• Support fast in-block search: store occasional restart points inside block (every r entries) so you can binary-search within compressed block without scanning from block start; for front-coded strings, store restart boundaries with full keys.

Latency and CPU trade-offs

• Larger blocks => fewer index entries, higher compression, higher per-read decode cost and more CPU; smaller blocks => more seeks but lower decode cost.
• Use asynchronous prefetching and read-ahead when binary search will touch predictable neighboring blocks.
• Keep the sparse index fully in-memory (compact: store only first key + offset; use succinct structures or tries for strings) to avoid extra disk I/Os.

Summary (practical recipe)

• Partition into blocks (tuned size), compress inside block using delta for numerics and front-coding for strings, store per-block metadata (first/last key, offset, compressed length).
• Keep an in-memory sparse index (two-level if needed) to map key ranges to block offsets so each binary search probe does one in-memory index search + one disk read and in-block decode using restart points.
• Tune block size, sampling rate, and restart interval to balance disk I/O vs CPU decompression for your workload and storage characteristics.

High-level summary: InnoDB, RocksDB, and WiredTiger target different trade-offs. All can be used for OLTP, but they excel under different write patterns, concurrency models, and recovery expectations.

Storage model & compaction

• InnoDB: B+tree clustered primary key (page/extent-based). Writes are page-oriented; background purge/merge, online index maintenance. No LSM compaction; less write amplification for random small updates on hot pages because updates are in-place within pages and flushed via redo log.
• RocksDB: LSM-tree. Writes append to WAL then memtable; background compaction merges SSTables across levels. Compaction causes higher write amplification but optimizable (leveling vs tiering, compaction filters).
• WiredTiger: B-Tree with a log-structured storage layer and checkpointing (MVCC). It uses block manager and eviction; optional lookaside table for long-running transactions. Less compaction-heavy than LSM, but internal file reorganization and checkpoints resemble middle ground.

Write amplification

• InnoDB: Low-to-moderate — redo log + dirty page flushes; amplification mostly due to full-page writes when pages churn.
• RocksDB: Highest by default — compaction re-writes data multiple times; can be tuned (compression, compaction strategy, write-buffer sizes) to reduce amplification.
• WiredTiger: Moderate — writes go to journal + modified pages; eviction/checkpointing causes extra IO but typically less than heavy LSM compaction.

Concurrency & locking

• InnoDB: Mature row-level locking + gap locks + MVCC snapshot reads; excellent for high-concurrency OLTP with ACID semantics.
• RocksDB: Single-process library; fine-grained memtable/SST concurrency but concurrency control is at DB client/application layer (transactions via RocksDB transactions API or higher-level engines). Good parallelism for background compaction but requires careful tuning for simultaneous readers/writers.
• WiredTiger: MVCC with snapshot isolation and configurable cache; good concurrent reads/writes and lock-free reads in many cases. MongoDB adoption shows robust concurrency for document workloads.

Crash recovery & durability

• InnoDB: Durable with redo logs (crash-safe) and fast recovery via redo + undo. Proven robustness for RDBMS.
• RocksDB: WAL ensures durability; recovery rebuilds memtables from WAL and relies on SSTables (compaction state can be replayed). Recovery time depends on WAL size and number of files.
• WiredTiger: Write-ahead journal + checkpoints; crash recovery replays journal up to last checkpoint. Recovery is generally fast but depends on checkpoint cadence.

Workloads they excel at

• InnoDB: Classic OLTP with relational schema, many small transactions, strong consistency, complex queries and secondary indexes.
• RocksDB: High-ingest workloads, write-heavy time-series or key-value workloads, embed as storage engine in distributed databases (e.g., Cassandra alternatives, MyRocks) where tuning compaction/SSD characteristics pays off.
• WiredTiger: Document-store OLTP with mixed read/write and large working sets (MongoDB uses it). Good when MVCC snapshot isolation and efficient caching matter.

Practical guidance

• For strict RDBMS OLTP with joins and transactions: InnoDB first choice.
• For extreme write throughput on SSDs with careful compaction tuning and where you can accept higher write amplification: RocksDB.
• For document/JSON workloads needing strong concurrency and lower write amplification than LSM: WiredTiger.

Trade-offs: RocksDB yields best raw write throughput at cost of write amplification and compaction tuning; InnoDB offers predictable ACID behavior with lower amplification for random updates; WiredTiger balances both with good concurrency and checkpointing. Choose by workload pattern, storage medium (HDD vs NVMe), recovery RTO requirements, and operational willingness to tune compaction.

Write-Ahead Logging (WAL) — core idea

• Before changing database pages on disk, record a log record describing the change (redo info, and often undo info) to a sequential WAL. The WAL is flushed to stable storage first; only then are in-place data page writes allowed. This guarantees that committed updates can be replayed after a crash.

Crash recovery using WAL

• On startup, the system scans WAL from the last checkpoint:
  • REDO: Reapply committed changes whose page images on disk may be stale (ensure durability).
  • UNDO: Roll back effects of transactions that had not committed at crash time (using undo or compensating records).
• Because WAL contains the authoritative sequence of changes, recovery replays the log to rebuild a consistent state.

Checkpoints

• A checkpoint records a point in the log where all pages dirtied before that LSN (log sequence number) have been flushed to disk (or the checkpoint notes which pages remain dirty). Checkpoints bound recovery time: recovery only needs to scan from the last checkpoint forward.
• Frequency of checkpoints trades recovery time and write amplification: more frequent checkpoints reduce recovery time but increase immediate I/O.

fsync frequency and group commit

• fsync after every transaction commit: strongest durability (no acknowledged commit is lost), but highest latency and poor throughput due to synchronous disk flush per commit.
• Group commit: batch multiple commit log records into a single fsync. Improves throughput and amortizes fsync latency, at cost of slightly higher commit latency variance and small window where recent commits not yet durable.
• Delayed or no fsync (rely on OS): higher throughput/low latency but risk of losing recent commits on crash.

Trade-offs & tuning for high-throughput systems

• Aim: maximize sequential WAL throughput while bounding latency and acceptable data-loss window.
• Strategies:
  • Use group commit with small flush intervals (e.g., 5–20 ms) to balance latency vs throughput.
  • Increase WAL buffer size and use asynchronous I/O or direct I/O to avoid OS buffering unpredictability.
  • Configure checkpoint cadence: less frequent checkpoints reduce sync stalls but increase recovery time and potentially more WAL replay.
  • Use fast durable media (NVMe, battery-backed NVM) to reduce fsync cost.
  • Consider multi-threaded WAL writers, partitioned logs, or sharded WALs to reduce contention.
  • Employ different durability levels (sync-on-commit for critical ops, async for best-effort) exposed to clients.
• Risks: aggressive grouping or delaying fsync raises the RPO (possible committed-but-not-durable window); too-frequent fsyncs kill throughput.

Summary

• WAL provides durable, redo-able history; checkpoints bound recovery cost; fsync policy and group commit are levers balancing durability, latency, and throughput. Tune based on required durability guarantees, acceptable recovery windows, and hardware characteristics.