LSMStorageEngine

An educational Log-Structured Merge-Tree (LSM Tree) Storage Engine in Modern C++20

This repository teaches how an LSM Tree storage engine works internally through a complete, working implementation with extensive documentation.

---

What is an LSM Tree?

An LSM (Log-Structured Merge) Tree is a data structure that converts random writes into sequential writes to achieve high write throughput. It is the storage engine behind many modern databases:

• RocksDB (Facebook/Meta)
• LevelDB (Google)
• Apache Cassandra
• TiKV (PingCAP)
• ScyllaDB
• Bigtable (Google)

flowchart LR
    W[Write] --> WAL[Write-Ahead Log<br/>Sequential Disk Write]
    WAL --> MT[MemTable<br/>In-Memory Buffer]
    MT -->|Flush| SST[SSTable<br/>Immutable On-Disk File]
    SST & SST2[SSTable] -->|Compaction| MERGED[Merged SSTable]

Loading

Architecture

graph TB
    subgraph "LSMStorageEngine"
        API[put / get / del] --> WAL[Write Ahead Log]
        API --> MT[Active MemTable]

        MT -->|Full| IMT[Immutable MemTable]
        IMT -->|Flush| SST[SSTable]

        SST -->|Background| COMP[Compaction]
        COMP --> NEW_SST[Merged SSTable]

        REC[Crash Recovery] --> WAL
        REC --> SST
    end

    style WAL fill:#f96
    style MT fill:#6f9
    style IMT fill:#f9f
    style SST fill:#99f
    style COMP fill:#ff9

Loading

Features

• put(key, value) - Write a key-value pair
• get(key) - Read a value by key
• del(key) - Delete a key by writing a tombstone
• Write-Ahead Log (WAL) - Durable writes with crash recovery
• MemTable - In-memory sorted buffer (std::map)
• SSTables - Immutable, sorted, on-disk files
• Flush - Move data from MemTable to SSTable
• Compaction - Background merge and deduplication
• Crash Recovery - WAL replay on startup
• Thread-safe - Mutex-protected concurrent access
• Background Compaction - Non-blocking merge operations

Learning Path

Step	Document	What You'll Learn
1	Introduction	Project overview and how to use it
2	Why LSM?	The problem LSM Trees solve
3	DB vs Storage Engine	Where LSM fits in a database
4	Write Path	How data is written
5	Read Path	How data is retrieved
6	WAL	Duravia and the Write-Ahead Log
7	MemTable	In-memory write buffer
8	SSTables	On-disk sorted files
9	Flush	Memory to disk transfer
10	Compaction	Background merge and cleanup
11	Crash Recovery	Recovery from unexpected shutdown
12	Threading Model	Concurrency design
13	Design Decisions	Every architectural choice explained
14	Project Structure	Code organization
15	Future Work	Possible improvements

Repository Structure

LSMStorageEngine/
├── CMakeLists.txt           # Build system
├── LICENSE                  # MIT License
├── README.md                # This file
├── include/lsm/             # Public headers
│   ├── config.h             # Configuration
│   ├── types.h              # Core types
│   ├── status.h             # Error handling
│   ├── wal.h                # Write-Ahead Log
│   ├── memtable.h           # MemTable
│   ├── sstable.h            # SSTable
│   ├── flush.h              # Flush
│   ├── compaction.h         # Compaction
│   ├── recovery.h           # Crash recovery
│   └── engine.h             # Main engine
├── src/                     # Implementation
├── tests/                   # Tests
├── examples/                # Examples
├── benchmarks/              # Benchmarks
└── docs/                    # Documentation (15 files)

Build Instructions

Prerequisites

• C++20 compiler (GCC 11+, Clang 14+, Apple Clang 15+, MSVC 2022+)
• CMake 3.20+
• Make, Ninja, or Xcode

Build

git clone https://github.com/yourusername/LSMStorageEngine.git
cd LSMStorageEngine
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build . --parallel

Run Tests

cd build
ctest --output-on-failure

Run Example

./build/examples/basic_usage

Run Benchmarks

cmake .. -DLSM_BUILD_BENCHMARKS=ON
cmake --build . --parallel
./build/benchmarks/run_benchmark

CMake Options

Option	Default	Description
LSM_BUILD_TESTS	ON	Build unit tests
LSM_BUILD_EXAMPLES	ON	Build examples
LSM_BUILD_BENCHMARKS	OFF	Build benchmarks
LSM_ENABLE_ASAN	OFF	Address sanitizer
LSM_ENABLE_UBSAN	OFF	Undefined behavior sanitizer
LSM_ENABLE_TSAN	OFF	Thread sanitizer

Usage Example

#include "lsm/engine.h"
#include <iostream>

int main() {
    lsm::Config config;
    config.db_path = "my_database";

    lsm::LSMEngine engine(config);

    // Write data
    engine.put("greeting", "Hello, LSM Tree!");
    engine.put("language", "C++20");

    // Read data
    auto [status, value] = engine.get("greeting");
    if (value) {
        std::cout << *value << std::endl;  // Hello, LSM Tree!
    }

    // Delete data
    engine.del("language");

    // Update data
    engine.put("greeting", "Updated greeting");

    return 0;
}

Write Path

sequenceDiagram
    participant App as Application
    participant Engine as LSMEngine
    participant WAL as WriteAheadLog
    participant MT as MemTable

    App->>Engine: put("key", "value")
    Engine->>WAL: append("key", "value")
    WAL-->>Engine: synced
    Engine->>MT: insert("key", "value")
    Engine-->>App: OK

Loading

Read Path

sequenceDiagram
    participant App as Application
    participant Engine as LSMEngine
    participant AMT as Active MemTable
    participant IMT as Immutable MemTable
    participant SST as SSTables

    App->>Engine: get("key")
    Engine->>AMT: search
    alt Not in Active MemTable
        Engine->>IMT: search
        alt Not in Immutable MemTable
            Engine->>SST: search (newest first)
        end
    end
    Engine-->>App: value or not_found

Loading

Design Decisions

Every architectural decision is documented with a clear why:

Decision	Choice	Rationale
MemTable data structure	std::map	STL, simple, sorted, no external deps
SSTable immutability	Immutable	Thread-safe reads, crash safety
Compaction strategy	Full compaction	Simplest correct implementation
Threading model	Single mutex	Correct and easy to understand
Bloom filters	Not implemented	Educational focus on core concepts
Compression	Not implemented	STL-only, clarity over performance

See Design Decisions for the complete discussion.

Testing

test_wal         - WAL append, recovery, sequence numbers
test_memtable     - Put, get, delete, update, overflow
test_sstable      - Create, read, tombstone, range check
test_flush        - MemTable to SSTable flush
test_compaction   - Merge, deduplication
test_recovery     - WAL and SSTable recovery
test_engine       - End-to-end put/get/delete
test_concurrent   - Multi-threaded read/write

Benchmarks

Approximate results on a modern SSD (2024 MacBook Pro):

Benchmark	10k ops	100k ops
PUT throughput	~500K ops/sec	~500K ops/sec
GET throughput	~800K ops/sec	~800K ops/sec
Recovery time	< 5ms	< 50ms

Run benchmarks yourself:

cd build && ./benchmarks/run_benchmark 100000

What This Is NOT

• ❌ Not a production database
• ❌ Not a replacement for RocksDB/LevelDB
• ❌ No SQL, networking, or transactions
• ❌ No compression, caching, or bloom filters

What This IS

• ✅ A complete, working LSM storage engine
• ✅ 15 detailed documentation files
• ✅ Clean, modern C++20 code
• ✅ Thread-safe concurrent access
• ✅ Crash recovery
• ✅ 8 test suites
• ✅ Benchmark framework

References

• The Log-Structured Merge-Tree (O'Neil et al., 1996)
• Bigtable: A Distributed Storage System for Structured Data
• LevelDB Implementation
• RocksDB Wiki
• Database Internals (Alex Petrov)

License

MIT License. See LICENSE for details.