Design a single-node embedded key-value storage engine (similar to RocksDB or LevelDB) capable of sustaining 250,000 random writes/sec of 1 KB payloads while bounding p99 point-lookup latency under 8 ms and preventing unbounded disk growth from overwrites and tombstones.
From patterns to decisions.
Design a single-node embedded key-value storage engine (similar to RocksDB or LevelDB) capable of sustaining 250,000 random writes/sec of 1 KB payloads while bounding p99 point-lookup latency under 8 ms and preventing unbounded disk growth from overwrites and tombstones.
A B+Tree performs random 16.
A B+Tree performs random 16 KB page reads and dirty-page flushes on random keys, exhausting 80,000 NVMe random IOPS. An LSM-tree batches writes in a sequential WAL and RAM SkipList, flushing 64 MB sorted runs sequentially.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | B+Tree offers O(log N) read amplification (1 tree traversal) vs LSM-tree checking MemTable + L0 + L1..Ln. | |
| Trade-off 2 | LSM-tree achieves 10x-50x higher random write throughput at the cost of background compaction CPU and I/O. |
Quantify random IOPS bottleneck
250k writes/sec exceeds 80k SSD random IOPS when buffer pool hit rate drops.
Step 2
Contrast in-place page mutation (B+Tree) with append-only sequential WAL + immutable SSTables (LSM-tree).
Identify the three amplification metrics
Write Amplification (WA), Read Amplification (RA), and Space Amplification (SA).
Alternative 1
B+Tree with large NVMe write-back cache (still hits random flush wall at 10 TB).
Alternative 2
Hash-indexed Bitcask (requires all keys to fit in RAM, violating 16 GB limit for 10B keys).
Failure Mode 1
Forgetting descending seqNum sorting causes Get() to return stale overwritten values.
// InternalKey ordering: userKey ASC, seqNum DESC (newest version first)
record InternalKey(byte[] userKey, long seqNum, byte opType) implements Comparable<InternalKey> {
@Override
public int compareTo(InternalKey other) {
int cmp = Arrays.compareUnsigned(this.userKey, other.userKey);
if (cmp != 0) return cmp;
return Long.compare(other.seqNum, this.seqNum);
}
}
Core Java implementation of the.
Core Java implementation of the LSM write path (WAL group commit + SkipList MemTable) and point lookup checking MemTable, L0 Bloom filters, and non-overlapping L1+ SSTables.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Reference-counted Version snapshots avoid reader/compactor locks at the cost of delaying file deletion until active reads finish. |
Step 1
Append to WAL with CRC32C and insert into ConcurrentSkipListMap.
Step 2
Swap active MemTable to immutable queue at 64 MB and flush asynchronously.
Step 3
On Get(key), probe MemTable -> Immutable MemTables -> L0 (all files, Bloom-filtered) -> L1..Ln (binary search file range, Bloom-filtered, binary search sparse index).
Alternative 1
Partitioned index/filter blocks cached in the 14.5 GB LRU block cache instead of pinning all Bloom filters in RAM.
Failure Mode 1
Skipping Bloom filter or checking L0 oldest-first returns stale values or wastes NVMe IOPS.
public byte[] get(byte[] userKey) {
// 1. Check active & immutable MemTables
byte[] val = findInMemTable(activeMemTable, userKey);
if (val != null) return val == TOMBSTONE ? null : val;
for (MemTable imm : immutableMemTables) {
val = findInMemTable(imm, userKey);
if (val != null) return val == TOMBSTONE ? null : val;
}
// 2. Check all overlapping L0 SSTables newest-first
Version v = currentVersion.acquire();
try {
for (SSTableMeta sst : v.level0FilesNewestFirst()) {
if (!sst.bloomFilter.mightContain(userKey)) continue;
byte[] res = sst.searchDataBlock(userKey, blockCache);
if (res != null) return res == TOMBSTONE ? null : res;
}
// 3. Check L1..Ln (at most 1 SSTable per level)
for (int lvl = 1; lvl < v.numLevels(); lvl++) {
SSTableMeta sst = v.binarySearchLevel(lvl, userKey);
if (sst == null || !sst.bloomFilter.mightContain(userKey)) continue;
byte[] res = sst.searchDataBlock(userKey, blockCache);
if (res != null) return res == TOMBSTONE ? null : res;
}
return null;
} finally {
v.release();
}
}
Implementation & Guardrails (3).
Leveled Compaction bounds space amplification to ~1.1x (critical at 10 TB) and limits L1-L6 lookup fan-out to 1 SSTable per level, whereas Size-Tiered Compaction can spike to 2x space amplification (10 TB wasted) and high read amplification.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Leveled compaction saves ~9 TB of SSD capacity vs Size-Tiered, at the cost of 3x higher compaction write volume. |
Compare Space Amplification
Leveled (~1.1x) vs Size-Tiered (~2.0x during major compaction).
Compare Read Amplification
Leveled (L0 + 1 file per level) vs Size-Tiered (multiple overlapping tiers).
Step 3
Mitigate Leveled Write Amplification (~10-12x) using LZ4 compression and parallel subcompactions.
Alternative 1
FIFO compaction for strict TTL time-series data with no updates/deletes.
Alternative 2
Tiered + Leveled hybrid (L0-L2 tiered, L3-L6 leveled).
Failure Mode 1
Disabling compression during L0->L6 compaction causes internal I/O (3.0 GB/s) to saturate the 3.5 GB/s NVMe link.
// Leveled compaction trigger: pick level with highest score (size / maxBytesForLevel)
double maxScore = 0.0;
int targetLevel = -1;
for (int lvl = 0; lvl < numLevels - 1; lvl++) {
double score = (lvl == 0)
? (double) l0Files.size() / 4.0
: (double) levelBytes[lvl] / (256L * 1024 * 1024 * Math.pow(10, lvl - 1));
if (score > maxScore) { maxScore = score; targetLevel = lvl; }
}
Unchecked bursts cause L0 pileups.
Unchecked bursts cause L0 pileups and write stalls; massive tombstone ranges degrade range scans. Both require backpressure rate-limiting and tombstone-aware compaction scoring.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Soft throttling adds 20-240 us per write during bursts to prevent multi-second hard write stalls. |
Step 1
Apply soft write throttling at 12 L0 files and hard stall at 24 L0 files.
Step 2
Track tombstone count in SSTable properties and boost compaction priority when tombstones > 20%.
Step 3
Support RangeTombstones (DeleteRange) so a single marker covers millions of keys.
Alternative 1
Dynamic level-size base adjustment to match actual bottom-level size.
Failure Mode 1
Dropping tombstones before the bottommost level (L6) resurrects deleted keys from deeper SSTables.
// Proactive write backpressure before hitting hard L0 limit (24)
int l0Count = currentVersion.l0FileCount();
if (l0Count >= 24) {
waitForCompactionSignal();
} else if (l0Count >= 12) {
long delayMicros = (l0Count - 11) * 20L;
LockSupport.parkNanos(delayMicros * 1_000L);
}
Key-value separation (WiscKey) stores only.
Key-value separation (WiscKey) stores only keys and 16-byte value pointers in the LSM-tree while keeping large values in an append-only vLog, slashing compaction write amplification by 10x+.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | WiscKey cuts compaction I/O dramatically for large values (> 1 KB) but adds an extra random NVMe read on RangeScan. |
Step 1
Store (valueLogFileId, offset, length) in the SSTable when value.length > 1 KB.
Step 2
Run asynchronous vLog garbage collection to relocate live values and reclaim tail space.
Step 3
For cloud-native storage, persist immutable SSTables and MANIFEST directly to S3 with local NVMe read caching.
Alternative 1
RocksDB BlobDB integrated directly into compaction.
Failure Mode 1
vLog garbage collection falling behind under high overwrite rates exhausts disk space despite small LSM levels.
// WiscKey-style value pointer stored inline in SSTable instead of 10 KB blob
record ValuePointer(long vLogFileId, long offset, int length) {
byte[] encode() {
return ByteBuffer.allocate(20).putLong(vLogFileId).putLong(offset).putInt(length).array();
}
}
Theory & Tips and Tricks
Practical heuristics & interview traps
- 01Interview anchor: LSM-trees trade read amplification and background compaction CPU/I/O for 10x-50x higher random write throughput than B+Trees on SSDs and HDDs.
- 02Trade-off tip: Leveled compaction saves ~9 TB of SSD capacity vs Size-Tiered, at the cost of 3x higher compaction write volume.
- 03Watch out for: Dropping tombstones before the bottommost level (L6) resurrects deleted keys from deeper SSTables.
Design Lsm Tree Storage Engine — Normal → Load / Fault → Recovery
LSM-trees trade read amplification and background compaction CPU/I/O for 10x-50x higher random write throughput than B+Trees on SSDs and HDDs.
Putting Design a Write-Optimized LSM-Tree Storage Engine Together
LSM-trees trade read amplification and background compaction CPU/I/O for 10x-50x higher random write throughput than B+Trees on SSDs and HDDs.
Putting Design a Write-Optimized LSM-Tree Storage Engine Together
- Append to WAL with CRC32C and insert into ConcurrentSkipListMap.
- Swap active MemTable to immutable queue at 64 MB and flush asynchronously.
- On Get(key), probe MemTable -> Immutable MemTables -> L0 (all files, Bloom-filtered) -> L1..Ln (binary search file range, Bloom-filtered, binary search sparse index).
Interview Readiness Check
Unchecked bursts cause L0 pileups and write stalls; massive tombstone ranges degrade range scans. Both require backpressure rate-limiting and tombstone-aware compaction scoring.
Walk through bottlenecks, back-of-the-envelope math, and failure recovery.
Make the trade-off yourself.
Practice Check
Test your understanding
What is the primary benefit of applying Hash Tables & Probabilistic Bloom Filters in production systems?
Design a Write-Optimized LSM-Tree Storage Engine
LSM-trees trade read amplification and background compaction CPU/I/O for 10x-50x higher random write throughput than B+Trees on SSDs and HDDs.
