Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Write-Optimized
LSM-Tree Storage Engine.

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.
Start the journey5 stages
Loading diagram…
Design a Write-Optimized LSM-Tree Storage Engine architecture sketch diagram
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

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.

01
SYSTEM-DESIGN · STAGE 01L4 · FUNDAMENTALS

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.

ChoiceWhat it buysWhat it costs
Trade-off 1B+Tree offers O(log N) read amplification (1 tree traversal) vs LSM-tree checking MemTable + L0 + L1..Ln.
Trade-off 2LSM-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);
    }
}
02
SYSTEM-DESIGN · STAGE 02L5 · APPLIED DESIGN

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.

ChoiceWhat it buysWhat it costs
Trade-off 1Reference-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();
    }
}
03
SYSTEM-DESIGN · STAGE 03L6 · SCALE & TRADE-OFFS

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.

ChoiceWhat it buysWhat it costs
Trade-off 1Leveled 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; }
}
04
SYSTEM-DESIGN · STAGE 04L6 · SCALE & TRADE-OFFS

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.

ChoiceWhat it buysWhat it costs
Trade-off 1Soft 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);
}
05
SYSTEM-DESIGN · STAGE 05L7 · STAFF / PRINCIPAL

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+.

ChoiceWhat it buysWhat it costs
Trade-off 1WiscKey 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.
Behavioral Progression · Design Lsm Tree Storage Engine

Design Lsm Tree Storage Engine — Normal → Load / Fault → Recovery

Send Request
1. Normal Request Ingress
Traffic: 1x baseline · Latency (p99): 4 ms
Process State
2. Core Execution & State Lookup
Traffic: 1x baseline · Latency (p99): 9 ms
Inject 10x Spike
3. Scale Spike / Failure Injection
Traffic: 10x burst · Latency (p99): 185 ms

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.

Synthesis / One connected design

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.

A candidate architecture, not a universal answer

Putting Design a Write-Optimized LSM-Tree Storage Engine Together

Step 1
Step 2
Step 3
  1. Append to WAL with CRC32C and insert into ConcurrentSkipListMap.
  2. Swap active MemTable to immutable queue at 64 MB and flush asynchronously.
  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).
Unchecked bursts cause L0 pileups and write stalls; massive tombstone ranges degrade range scans. Both require backpressure rate-limiting and tombstone-aware compaction scoring.
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.

Practice / Explain the consequences

Make the trade-off yourself.

Practice Check

Test your understanding

Question 1 of 3

What is the primary benefit of applying Hash Tables & Probabilistic Bloom Filters in production systems?

Key takeaway

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.