LogTreeDB: Building an LSM Storage Engine from Scratch

A short architectural write-up on designing a disk-backed key-value storage engine using Log-Structured Merge Tree (LSM) principles.

Why LogTreeDB?

LogTreeDB started from a curiosity about what really happens below a database API.

Modern databases often feel like black boxes: data goes in, data comes out, and performance magically scales. LogTreeDB was built to peel back those layers and understand how durability, performance, and correctness are achieved at the storage-engine level.

Rather than relying on existing libraries, LogTreeDB focuses on first-principles design, closely inspired by the ideas in Designing Data-Intensive Applications (DDIA).

The Core Problem

Disks are slow at random writes.

Traditional data structures like B-Trees update data in place, which leads to:

• random I/O
• poor write throughput
• complex locking

Log-Structured Merge Trees (LSMs) solve this by never updating data in place. Instead, all writes are sequential, and data is reorganized later.

LogTreeDB is a minimal but correct implementation of this idea.

High-Level Architecture

At a high level, LogTreeDB follows a classic LSM layout:

Each stage has a single responsibility and clear invariants.

Write Path

1. Write-Ahead Log (WAL)

Every write is first appended to a Write-Ahead Log before being applied in memory.

Why this matters:

• guarantees durability
• enables crash recovery
• keeps disk writes sequential

On restart, the WAL is replayed to reconstruct in-memory state.

2. MemTable

After WAL append, writes are applied to an in-memory MemTable:

• sorted by key
• fast reads and writes
• holds tombstones for deletes

Deletes are logical — they are recorded as tombstones rather than removing data immediately.

3. Immutable MemTable

When the MemTable reaches a size threshold:

• it is frozen into an Immutable MemTable
• a new MemTable immediately takes over writes
• flushing to disk happens without blocking new writes

This separation is critical for sustained write throughput.

SSTables (Sorted String Tables)

An SSTable is an immutable, sorted, on-disk file created by flushing an Immutable MemTable.

Properties:

• written once, read many times
• sorted by key
• sequential disk writes
• no in-place updates

In Phase 1 of this project, SSTables used a simple linear scan for reads. More advanced indexing was introduced later (more on that below).

Read Path

Reads traverse layers in priority order:

1. Active MemTable
2. Immutable MemTable
3. SSTables (newest → oldest)

The first matching key wins.

This ensures:

• newer writes override older ones
• tombstones correctly mask deleted values

Deletes & Tombstones

Deletes do not immediately remove data.

Instead:

• a tombstone is written
• it propagates through MemTables and SSTables
• actual deletion happens during compaction

This design guarantees correctness across crashes and multiple on-disk files.

WAL Truncation

Once an Immutable MemTable has been safely flushed to an SSTable and fsynced:

• the WAL is truncated
• disk usage stays bounded
• startup recovery remains fast

Crash Recovery

On startup:

1. Existing SSTables are discovered
2. WAL is replayed
3. In-memory state is rebuilt

At no point is acknowledged data lost.

Design Trade-offs

Advantages

• high write throughput
• sequential disk I/O
• simple concurrency model

Trade-offs

• read amplification
• background compaction complexity
• multiple storage layers

These trade-offs are intentional and fundamental to LSM-based systems.

Current Project Phase

Phase 1 — Minimal & Correct LSM (Completed)

• WAL with crash recovery
• MemTable & Immutable MemTable
• SSTable flush & linear-scan reads
• Tombstones
• WAL truncation after safe flush

Phase 2 — Read Optimization (Completed)

• Sparse index per SSTable
• Binary search over sparse index
• Bounded data scans
• Per-SSTable Bloom filters
• Dynamically sized Bloom filters (bits-per-key)
• SSTable footer-based metadata discovery

Phase 3 — Compaction & Levels (Completed)

• Multi-level storage hierarchy (L0, L1, L2, …)
• Background compaction thread
• L0 → L1 leveled compaction
• K-way merge using SSTable iterators
• Newest-version wins semantics
• Tombstone cleanup during compaction
• Obsolete SSTable deletion
• Disk space reclamation

At this point, LogTreeDB is a fully functional single-node LSM storage engine, closely resembling the core architecture of LevelDB / RocksDB.

Read Optimization (Phase 2)

Phase 2 focuses on reducing read amplification, especially for negative lookups.

Sparse Index

Each SSTable contains a sparse in-memory index mapping:

key → byte offset

Instead of scanning from the beginning of the file, LogTreeDB:

1. Binary-searches the sparse index
2. Seeks directly to the nearest offset
3. Performs a bounded linear scan

This drastically reduces disk I/O while keeping SSTables simple and immutable.

Bloom Filters

Each SSTable also owns a Bloom filter:

• built at flush time
• persisted alongside the SSTable
• loaded on SSTable open

Before any disk seek:

• the Bloom filter is checked
• if negative, the SSTable is skipped entirely

This makes most missing-key lookups complete without touching disk.

Compaction & Levels (Phase 3)

Without compaction, SSTables would grow unbounded, causing:

• high read amplification
• excessive disk usage

Phase 3 introduces leveled compaction.

Levels

Level-0 (L0)

• new SSTables from MemTable flushes
• overlapping key ranges
• read newest → oldest

Level-1+ (L1, L2, …)

• non-overlapping key ranges
• sorted SSTables
• single SSTable consulted per level for reads

Each level has a maximum size. Exceeding it triggers compaction.

Compaction Process

1. Pick a compaction plan (e.g. L0 → L1)
2. Select input SSTables and overlapping target SSTables
3. Create iterators over all inputs
4. Perform a k-way merge (newest first)
5. Drop obsolete versions and tombstones
6. Write new SSTable(s) to the next level
7. Atomically swap metadata
8. Delete old SSTables

All compaction happens in the background, without blocking reads or writes.

Correctness Guarantees

• newer versions always win
• tombstones suppress older values
• no data loss during crashes
• SSTables remain immutable

Why This Matters

At the end of Phase 3, LogTreeDB demonstrates:

• how real databases achieve high write throughput
• why immutability simplifies correctness
• how background compaction controls long-term performance
• the practical trade-offs of LSM trees

Final Thoughts

LogTreeDB is built to understand systems, not to compete with production databases.

By implementing every layer manually — WAL, MemTables, SSTables, Bloom filters, compaction — it exposes the true mechanics behind modern storage engines.

If you understand LogTreeDB, you understand the heart of LevelDB, RocksDB, and Cassandra.

Running LogTreeDB

LogTreeDB is distributed as a pre-built runnable JAR, so you can try it without cloning the repository or building from source.

Prerequisites

• Java 21+
• a local directory for data storage

Download

wget https://github.com/manojayyanavara/logtreedb/releases/download/v1.0.0/logtreedb-1.0.0.jar

Run LogTreeDB

Choose a data directory (it will be created automatically):

java -jar logtreedb-1.0.0.jar

Example Commands

# Put a key
java -jar logtreedb-1.0.0.jar put key-1 value-1

# Get a key
java -jar logtreedb-1.0.0.jar get key-1

# Delete a key
java -jar logtreedb-1.0.0.jar delete key-1

Restart Safety

You can safely stop and restart the process:

• WAL replay reconstructs in-memory state
• SSTables are rediscovered from disk
• deletes and overwrites remain consistent

This mirrors how real-world LSM-based systems guarantee durability across restarts.

---

LogTreeDB is intentionally designed as an embeddable storage engine. A networked API and containerized deployment are natural future extensions, but the current form keeps the focus on core storage mechanics.

This post documents the journey of building a storage engine from first principles.