Storage Engine Internals

What's being tested

Interviewers are probing your practical understanding of storage-engine building blocks: how data is laid out on disk, how writes survive crashes, how reads stay fast under heavy write load, and the tradeoffs between competing designs. eBay cares because backend services must store and serve huge volumes reliably and with predictable latency; the interviewer wants to see that you can pick appropriate primitives and reason about performance, durability, and operational costs for production systems.

Core knowledge

B-tree vs LSM-tree: B-trees excel at random reads and in-place updates (good for OLTP); LSM-trees (log-structured merge trees) optimize for high write throughput via memtable + immutable SSTables and background compaction.
Memtable and SSTable: LSM write path: write to memtable (in-memory), append to WAL, then flush immutable SSTable files; SSTables support merges during compaction and are immutable on disk.
Write-ahead log (WAL) and fsync semantics: durability requires persisting the WAL; group-commit reduces syscalls. Know the cost: durable commit typically involves an fsync (~ms latency) unless batched.
Compaction tradeoffs: compaction reduces read amplification and reclaims space but causes CPU/disk I/O spikes, write amplification (extra bytes written), and needs throttling to avoid latency spikes.
Write amplification, read amplification, space amplification: quantify where possible — LSMs may have write amplification >1 depending on compaction strategy; tune levels/size ratios to balance. Lowering write amplification usually increases read cost.
Crash recovery patterns: replay WAL, apply checkpoints, reconcile partially flushed files; beware of torn writes — use checksums, file versioning, atomic rename, and directory-level sync ordering.
Concurrency control: MVCC enables lock-free reads with multiple versions; alternatives include page latches or fine-grained locks for in-place structures like B-trees. Consider isolation vs latency tradeoffs.
Bloom filters: probabilistic filter on SSTables reduces unnecessary disk reads; store one per file/level and size for desired false-positive rate $p$ using $m = -\frac{n \ln p}{(\ln 2)^2}$ bits.
Caching & page replacement: hot-data caching (page cache vs application cache) matters; implement LRU or CLOCK, and size to avoid eviction storm during compaction or bulk loads.
Tombstones & GC: LSMs mark deletes as tombstones and only reclaim space during compaction; heavy delete workloads can increase compaction pressure and read cost.
File formats and checksums: each SSTable/segment should include checksums and a footer index for atomic file scans and quick recovery; use versioned filenames and atomic renames to publish files.
Tip: measure p50/p95/p99 latencies separately for reads/writes and track write-amplification and compaction I/O as production SLO signals.

Worked example — "Design a storage engine for a key-value store with crash recovery and efficient reads"

First 30 seconds: clarify durability SLOs (sync-on-every-write vs periodic), expected workload (read-heavy vs write-heavy), dataset size vs memory, and expected concurrency. Skeleton answer pillars: (1) persistent write path (in-memory memtable + WAL append), (2) on-disk layout (SSTables with levelled/size-tiered compaction), (3) read path (memtable lookup, Bloom filters, level scanning), and (4) crash recovery and metadata publishing (WAL replay and atomic file moves). A key tradeoff to flag: choose levelled compaction to reduce read amplification at the cost of higher write amplification, or size-tiered for lower write cost but slower reads — justify by workload. Also discuss operational controls: compaction throttling, scheduling, and compaction backpressure to protect tail latencies. Close by saying: "if I had more time I'd add metrics (write-amplification, compaction-lag), implement prioritized compaction for hot keys, and sketch test plans including crash-injection and long-running throughput tests."

A second angle — "Compare B-tree and LSM-tree designs for a mixed OLTP workload with frequent point-read and range scan patterns"

Same primitives apply but constraints shift: with many small point-updates and frequent range scans, B-tree can be preferable due to in-place updates and cheaper range iteration; LSM-tree needs read-merge across levels causing range-scan cost and higher tail latency. Emphasize hybrid mitigations: implement a read-only memtable or level compaction hints, maintain a sparse index in memory for SSTables, or use smaller levels to bound range-scan cost. Discuss concurrency: B-tree benefits from latch coupling and range locks for scans, while LSM benefits from MVCC-style versioning to present consistent snapshots during compaction. Conclude that workload profile (point vs range ratio, write bursts, and latency SLOs) should determine the choice, and propose microbenchmarks to validate.

Common pitfalls

Pitfall: Optimizing only for throughput. Engineers often design for maximum writes/sec (e.g., huge memtable flush size) which amplifies read latency and compaction spikes; instead expose tunables and prioritize SLOs for tail latency.

Pitfall: Ignoring partial-write modes. A tempting but wrong shortcut is trusting file renames without checksums; this fails on torn writes. Always include checksums, atomic file publish (rename after fsync directory), and WAL replay guarantees.

Pitfall: Over-indexing in memory. Storing full in-memory primary indexes for massive datasets wastes RAM; use sparse indexes, sampled offsets, or a two-tier index (in-memory hash to SSTable id + on-disk block index) to bound memory while keeping lookups efficient.

Connections

Interviewers may pivot to adjacent topics like distributed replication (raft-based WAL shipping and leader/follower semantics), storage-level compaction coordination in multi-tenant clusters, or backup/restore patterns (snapshot + WAL incremental backups). Be ready to discuss how single-node storage choices affect distributed consistency and recovery.